

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

通常のレーベンシュタイン距離は、文字列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>


CC BY-SA 4.0
2018-06-07T05:27:38.070
44583
2018-06-08T16:10:05.973
2018-06-08T16:10:05.973
19110
28816
question
アルゴリズム 自然言語処理
重み付きレーベンシュタイン距離の定義について


コスト自体の定義は行いたいことに合わせて変えればよいのでどちらの定義でも良いとは思いますが、通常 weighted edit distance と言うと 2
の方の定義が使われます。簡単に検索してみたところ、たとえば Stanford の ["Introduction to Information
Retrieval"](https://nlp.stanford.edu/IR-book/html/htmledition/edit-
distance-1.html) では 2 の定義が使われています。また WikiBooks の ["Algorithm
Implementation/Strings/Levenshtein
distance"](https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance)
にある実装も 2 の定義に従ったものになっています。

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

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


CC BY-SA 4.0
2018-06-07T06:04:15.403
44585
2018-06-07T07:03:03.133
2018-06-07T07:03:03.133
19110
19110
44583
answer


２が正しいです。１は距離の公理を満たさない場合があります。

距離は，遠回りをすると大きな値になります。  
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の方法で計算した場合は，このようなことは起こりません。


CC BY-SA 4.0
2018-06-07T06:36:51.387
44587
2018-06-07T06:36:51.387
28818
44583
answer