0

典型的な動的レーベンシュタイン距離アルゴリズムでは、 cell の値を計算するために、d[i][j]とiはjそれぞれ行番号と列番号でありd[i-1][j-1]+0/1、d[i-1][j]+1との最小値を取りd[i][j-1]+1ます。ただし、 と の最小値d[i-1][j-1]+0/1はd[i-1][j]+1常に になるように思われます。この場合、計算にd[i-1][j-1]+0/1含めるのは冗長に思えます。レーベンシュタイン距離アルゴリズムで>d[i-1][j]+1の場合はありますか?そうでない場合は、この比較を省略した方が効率的ではないでしょうか?d[i-1][j-1]+0/1d[i-1][j]+1

編集:調査不足の質問で申し訳ありません。アルゴリズムの標準的な実行では、d[i-1][j-1]+0/1>のインスタンスが表示されd[i-1][j]+1ます。

    A
 +-+-+
 |0|1|
 +-+-+
A|1|0|
 +-+-+

（2行目を考えてください）。

4

1 に答える 1

1

ウィキペディアの記事を参照すると、最後のケースの最小値は「削除」のケースで取られる必要があります。

と の間のレーベンシュタイン距離を計算したいとしますabc(ab以降は固定で表記を省略します)。

反復評価により、次の中間結果が得られます。

lev(0,0) = 0 (1st case applies)
lev(0,1) = 1 (1st case applies)
lev(0,2) = 2 (1st case applies)

lev(1,0) = 1 (1st case applies)
lev(1,1) = min(2,2,0) (2nd case, minimum taken in last term) = 0
lev(1,2) = min(1,2,1) (2nd case, minumum taken in last term) = 1

lev(2,0) = 2 (1st case applies)
lev(2,1) = min(3,1,2) (2nd case, minimum taken in second term) = 1 (*)
lev(2,2) = min(2,2,0) (2nd case, minimum taken in the last term) = 0

lev(3,0) = 3 (1st case applies)
lev(3,1) = min(4,2,2) (2nd case, minimum taken in the second and third term) = 2
lev(3,2) = min(3,1,2) (2nd case, minimum taken in the second term) = 1 (*)

(*) でマークされた行は、2 番目のケースが発生するケースですが、最後の項で最小値が取られていません。動的計画表も表示するオンライン計算機は、ここにあります。

于 2014-07-14T19:09:17.197 に答える