質問: **「kitten」「sitting」、2単語間のレーベンシュタイン距離は、設定によって「3」だったり「5」だったりするのでしょうか?** ・「レーベンシュタイン距離」はあくまでも考え方であって、正式な公式は存在しない? ・あるいは、公式はあるけれども、そこへ割り振るコストは自由に設定可能ということでしょうか? ・一般的には置換コストは「1」「2」、何れなのでしょうか? > > 上の変形では挿入・削除・置換のそれぞれのコストを1に設定したが、これらのコストには別々の値を割り振る事も可能である > > >
回答: まず置換のコストについて レーベンシュタイン距離の定義は、 > > 具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される > > > ですので、置換操作が許されるならばコストは1、置換操作が許されない場合はそれを削除・挿入で置き換えてコストは2となります。 また手順の「最小」回数を求めるので、置換操作が許されるならば、それを削除・挿入で置き換えてコストを2とすることはできません。 従って、置換操作を許すか否かでレーベンシュタイン距離が変わることになります。 参考: 名前の元となった論文はこちら。