0

1) なぜこれらの行に 1 を追加するのですか?

    d[i-1, j] + 1, // deletion 
    d[i, j-1] + 1, // insertion

この線

if s[i] = t[j] then cost := 0

        else cost := 1

削除された/より短い単語の長さを考慮に入れる必要がありますか、それとも何か不足していますか?

2) また、コメントには削除と挿入が記載されています。低い値は削除された文字を表すため、両方の単語 (単語の長さを表す整数 j/i) で削除された文字をチェックしていると考えるのは正しいですか。

使用されているコードは次のとおりです (疑似コードであり、言語固有の問題がないため、このスレッドはどの言語カテゴリにもありません)。

http://www.iterasi.net/openviewer.aspx?sqrlitid=z0cloj7xhk-ce0f72v4cjq

4

2 に答える 2

2

http://www.merriampark.com/ld.htmを読んだことがありますか？

ある文字列を別の文字列にするために必要な変換のコスト（挿入と削除の数）を計算しています。

変換するためのこの「コスト」は、2つのストリング間の距離を示します。

交換はどうですか？これがダメラウ・レーベンシュタインアルゴリズムですが、これは異なります。交換を含めても、物事はそれほど改善されません。

本質は、2つの単語の間に行列を作成し、各単語の各文字から他の単語の各文字までの「距離」を列ごとに計算することです。そのマトリックスの右下隅は、すべての文字を考慮した合計距離です。

質問1）

「上の」セルは変更の履歴を反映しており、その行の文字は（通常）これとは異なるため、このセルはそれに関連する削除です。

「左」のセルは変更の履歴を反映しており、その列の文字は（通常）これとは異なるため、このセルはそれに関連する挿入です。

これが通常はかなり間違っているのは、3文字のシーケンスを持つ単語だけです。英語では珍しい。

行と列の比較のコストは0または1です。

「履歴プラス1つの変更」の最小値と変更の実際のコストが適用可能なコストです。

質問2）

変数iとjは何の長さでもありません。それらは比較マトリックス内の位置です。「挿入」と「削除」は、ある単語を別の単語に変換するために必要なアクションです。挿入/削除アクションの数は、単語間の距離です。

于 2009-05-13T10:03:43.563 に答える
1

1）これらの線は、削除の場合は挿入の場合の距離を計算し、置換の場合は「コスト」を使用した距離を計算します。

削除と挿入は、距離の計算では事実上「1」としてカウントされるため、+1になります。

文字が異なる場合にのみ置換があったと信じることができるため、両方の文字が等しい場合は「cost=0」...

新しい距離は、これら3つの仮説間の最小距離であるため、常に1を追加するとは限りません...

2）「FooBar」と「FoBaWhatever」の間の距離を計算すると、2番目の文字列が最初の文字列より長くても文字が削除されます...

もちろん、2番目の文字列が2番目の文字列よりも短い場合（FooBar-> FoBa）、いくつかの削除が見つかりますが、それらがどこにあるかを事前に知ることはできません...

于 2009-05-13T09:58:36.377 に答える