質問: 文字列間の距離を測るレーベンシュタイン距離の拡張の重み付きレーベンシュタイン距離というものの定義がよく分からなくなったので質問します。 通常のレーベンシュタイン距離は、文字列1を文字列2に編集する場合の挿入・削除・置換の最少回数を距離としています。挿入・削除・置換についてそれぞれ重みを設定して合算するのが重み付きレーベンシュタイン距離だそうです。 この場合、重み付きレーベンシュタイン距離のアルゴリズムとしては次のどちらの解釈が多数派なのでしょうか? 1. 通常のレーベンシュタイン距離で求めた最少の編集回数に対して挿入・削除・置換ごとの回数に重みを掛けて合計したもの 2. 通常のレーベンシュタイン距離のコスト計算で加算される挿入・削除・置換コストの1を重みに取り替えて計算したもの 2.の場合は途中で加算される編集コストが変わることにより最少の編集回数・手順も変わります。 私は直感的に1.のほうかと思って実装したのですが、調べてみると2.も多いです。 1. go-lsd-parametrized/lsd.go at master · deltam/go-lsd-parametrized 2. weighted-levenshtein/clev.pyx at master · infoscout/weighted-levenshtein
回答: 2が正しいです。1は距離の公理を満たさない場合があります。 距離は,遠回りをすると大きな値になります。 d(X, Y) ≦ d(X, Z) + d(Z, Y) 追加コスト=1,削除コスト=1,置換コスト=3 として,1の方法で次の編集距離を計算してみます。 d("ABCDEFG", "ABCXEFG") = 3 d("ABCDEFG", "ABCEFG") = 1 d("ABCEFG", "ABCXEFG") = 1 d("ABCDEFG", "ABCEFG") + d("ABCEFG", "ABCXEFG") = 2 遠回りをしているのにスコアが小さくなってしまいました。 2の方法で計算した場合は,このようなことは起こりません。