レーベンシュタイン距離の挿入コストと削除コストコスミー報告書[社外秘]時代の引力に惹かれた魂を宇宙に解き放つ報告書。聞いて欲しい独り言レーベンシュタイン距離っていうのは一つの文字列と文字列の距離の求め方です。言うと、Aという文字列とBという文字列の距離を求める場合、Aの各文字を削除したり置換したり、あるいはBにある文字をAに挿入したりしてBと同じ文字列を作り、そのときの手数を距離とします。A:”abbc”とB:”acbbd”の距離を求めると以下のようになります。aとbの間にcを挿入→acbbc最後のcをdに置換→acbbdということで距離は2です。編集の方法はいくつもありますが、最小の手数のものを距離と定義します。aとbの間にcを挿入→acbbc後ろのbとcの間にdを挿入→acbbdc最後のcを削除→acbbdだと手数が3なのでNGです。プログラムでこの最小手数を求めるにはDP法(動的計画法)を用います。Wikipediaの解説でも上記の擬似コードはコメントが間違っていると思います。レーベンシュタイン距離はあくまで「Aを編集してBにするときの最小コスト」なので、編集はすべてAに対して行わなければなりません(たぶん)。Bの文字列を削除したりしてはイカンのです。]は文字列Aのi1番目までの文字列と文字列Bのi2番目までの文字列の距離です。1]を使って求めるわけですが、次のように考えるべきです。i2]の距離に末尾文字a(i1)を削除するコストを足したものと等しい。]の距離にb(i2)を挿入するコストを足したものに等しい。1]にa(i1)を置換するコストを足したものに等しい。いうわけで、PHPで書くと以下のようになります。レーベンシュタイン距離を求める。$matrix[$len_a][$len_b];}PHPにはそもそもlevenshtein()という関数があり、上記のような関数を自分で作る必要はないです。挿入コスト・置換コスト・削除コストをいろいろ変えたとき、上記関数はPHPの組込関数と結果が一致します。Wikipediaのものは一致しません。Wikipedia方式は次のような解釈と思います。]にb(i2)を削除するコストを足したものに等しい。]にb(i2)を挿入するコストを足したものに等しい。1]にa(i1)を置換するコストを足したものに等しい。この方が理解しやすいですが、両方の文字列を編集しているのでもともとの定義からは外れていると思います。場合に上記の2つの解釈は結果が一致します。いうか、挿入コストと削除コストが等しい場合には同じになります。逆に言うと、コストが挿入と削除で対称でない場合は違う結果になります。レーベンシュタイン距離が距離の公理を満たすためには挿入と削除に対して対称でなければならないため、結局どっちでもイイっていう。基本的に私が勘違いしている可能性も高いです。InductorRFRみんなが小説家になるようです。