3

文字列間の距離を測るレーベンシュタイン距離の拡張の重み付きレーベンシュタイン距離というものの定義がよく分からなくなったので質問します。

通常のレーベンシュタイン距離は、文字列1を文字列2に編集する場合の挿入・削除・置換の最少回数を距離としています。挿入・削除・置換についてそれぞれ重みを設定して合算するのが重み付きレーベンシュタイン距離だそうです。

http://id.fnshr.info/2011/11/29/damerau/

この場合、重み付きレーベンシュタイン距離のアルゴリズムとしては次のどちらの解釈が多数派なのでしょうか?

  1. 通常のレーベンシュタイン距離で求めた最少の編集回数に対して挿入・削除・置換ごとの回数に重みを掛けて合計したもの
  2. 通常のレーベンシュタイン距離のコスト計算で加算される挿入・削除・置換コストの1を重みに取り替えて計算したもの

2.の場合は途中で加算される編集コストが変わることにより最少の編集回数・手順も変わります。
私は直感的に1.のほうかと思って実装したのですが、調べてみると2.も多いです。

  1. go-lsd-parametrized/lsd.go at master · deltam/go-lsd-parametrized
    https://github.com/deltam/go-lsd-parametrized/blob/master/lsd.go#L96

  2. weighted-levenshtein/clev.pyx at master · infoscout/weighted-levenshtein
    https://github.com/infoscout/weighted-levenshtein/blob/master/weighted_levenshtein/clev.pyx#L457

0

2 件の回答 2

4

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の方法で計算した場合は,このようなことは起こりません。

2

コスト自体の定義は行いたいことに合わせて変えればよいのでどちらの定義でも良いとは思いますが、通常 weighted edit distance と言うと 2 の方の定義が使われます。簡単に検索してみたところ、たとえば Stanford の "Introduction to Information Retrieval" では 2 の定義が使われています。また WikiBooks の "Algorithm Implementation/Strings/Levenshtein distance" にある実装も 2 の定義に従ったものになっています。

たとえば 2 つの DNA の "類似度" のようなものを比べたくて編集距離を使うことになったとしましょう。時間発展に従って DNA が変化していく中で、挿入・削除・置換が起こる確率は互いに等しくなさそうです。元の DNA から変化した時間が短そうな DNA を見つけるためには二者間の距離が小さくなって欲しいので、そのように距離を定義したいです。するとたとえば 1 回の変化にかかるコストを 1 で揃えるのではなく、挿入・削除・置換が起こる確率に合わせて変える、という方法を思いつきます。この考え方に従うとすると、2 の定義を採用することになります。1 の定義だと DNA の変化の道筋を先に決めてから道筋の起こりやすさをコストとして足すことになりますが、それだと本当にその二者間についてその道筋が一番起こりやすかったのかまでは加味していないからです。

ただしどういう意味で「重み付き」なのかによって、多数派かどうかに関わらず定義は変わりうるので、最終的には今使っている・読んでいるものの中での定義をご確認ください。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。