20201


**「kitten」「sitting」、2単語間のレーベンシュタイン距離は、設定によって「3」だったり「5」だったりするのでしょうか？**  
・「レーベンシュタイン距離」はあくまでも考え方であって、正式な公式は存在しない？  
・あるいは、公式はあるけれども、そこへ割り振るコストは自由に設定可能ということでしょうか？  
・一般的には置換コストは「1」「2」、何れなのでしょうか？

> 上の変形では挿入・削除・置換のそれぞれのコストを1に設定したが、これらのコストには別々の値を割り振る事も可能である

<https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2>


CC BY-SA 3.0
2015-12-20T02:15:31.177
20196
2018-06-07T07:13:32.960
7886
question
アルゴリズム
レーベンシュタイン距離は、「置換に割り振るコストの値」によって結果が異なる？


まず置換のコストについて

レーベンシュタイン距離の定義は、

> 具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される

ですので、置換操作が許されるならばコストは1、置換操作が許されない場合はそれを削除・挿入で置き換えてコストは2となります。  
また手順の「最小」回数を求めるので、置換操作が許されるならば、それを削除・挿入で置き換えてコストを2とすることはできません。

従って、置換操作を許すか否かでレーベンシュタイン距離が変わることになります。

参考:  
名前の元となった論文は[こちら](https://gitlab.doc.ic.ac.uk/wm613/inidividual-
project/raw/4fbe43f863b229b50ca13bf5f59eb029ad71f6b6/reading/litreview/levenshtein66.pdf
"levenshtein66.pdf")。


CC BY-SA 3.0
2015-12-20T04:15:50.010
20201
2015-12-20T10:51:25.417
2015-12-20T10:51:25.417
13199
13199
20196
answer


通常、自然言語処理や生物情報科学の範囲で単に[「レーベンシュタイン距離」](https://en.wikipedia.org/wiki/Levenshtein_distance)と言った場合、1
回の編集として 1 文字の挿入・削除・置換が許されていて、それぞれにかかるコストが 1
であるような[編集距離](https://en.wikipedia.org/wiki/Edit_distance)のことを言います。この定義のもとでは
"kitten" と "sitting" のレーベンシュタイン距離は 3 になります。

ただし上で述べた「コスト」を挿入・削除・置換のそれぞれについて個別に設定できるように一般化することもでき、重み付きレーベンシュタイン距離と呼ばれています。また編集操作を制限したり追加したりするなどして、広義の[「編集距離」](https://en.wikipedia.org/wiki/Edit_distance)として一般化することもできます。日本語版
Wikipedia の当該の記述はこのことに対応しようとしたのかもしれません。


CC BY-SA 4.0
2018-06-07T07:13:32.960
44588
2018-06-07T07:13:32.960
19110
20196
answer