文字列間の距離を測るレーベンシュタイン距離の拡張の重み付きレーベンシュタイン距離というものの定義がよく分からなくなったので質問します。
通常のレーベンシュタイン距離は、文字列1を文字列2に編集する場合の挿入・削除・置換の最少回数を距離としています。挿入・削除・置換についてそれぞれ重みを設定して合算するのが重み付きレーベンシュタイン距離だそうです。
http://id.fnshr.info/2011/11/29/damerau/
この場合、重み付きレーベンシュタイン距離のアルゴリズムとしては次のどちらの解釈が多数派なのでしょうか?
- 通常のレーベンシュタイン距離で求めた最少の編集回数に対して挿入・削除・置換ごとの回数に重みを掛けて合計したもの
- 通常のレーベンシュタイン距離のコスト計算で加算される挿入・削除・置換コストの1を重みに取り替えて計算したもの
2.の場合は途中で加算される編集コストが変わることにより最少の編集回数・手順も変わります。
私は直感的に1.のほうかと思って実装したのですが、調べてみると2.も多いです。
go-lsd-parametrized/lsd.go at master · deltam/go-lsd-parametrized
https://github.com/deltam/go-lsd-parametrized/blob/master/lsd.go#L96weighted-levenshtein/clev.pyx at master · infoscout/weighted-levenshtein
https://github.com/infoscout/weighted-levenshtein/blob/master/weighted_levenshtein/clev.pyx#L457