レーベンシュタイン距離っていうのは一つの文字列と文字列の距離の求め方です。
ざっくり言うと、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の文字列を削除したりしてはイカンのです。
d[ i1, i2 ]は文字列Aのi1番目までの文字列と文字列Bのi2番目までの文字列の距離です。
A：a(1)a(2)…a(i1)
B：b(1)b(2)…b(i2)
DP法により、この距離をd[ i1 – 1, i2]、d[ i1, i2 – 1]、d[ i1 – 1, i2 – 1]を使って求めるわけですが、次のように考えるべきです。
・Aからの削除によりＢに近づく場合：
Aから末尾の文字a(i1)を削除すれば「a(1)～a(i1 – 1)の文字列」と「b(1)～b(i2 – 1)の文字列」との距離に帰着されるので、d[ i1, i2 ]はd[ i – 1, i2]の距離に末尾文字a(i1)を削除するコストを足したものと等しい。
・Aへの挿入によりＢに近づく場合：
a(1)～a(i1)の末尾にb(i2)を挿入すれば、
“「a(1)～a(i1)b(i2)の文字列（Ａ側の末尾にb(i2)を加えた）」と「b(1)～b(i2 – 1)の文字列」の距離”
“「a(1)～a(i1)b(i2)の文字列」と「b(1)～b(i2)の文字列」の距離”
は等しくなるのでd[ i1, i2 ]はd[ i1, i2 – 1 ]の距離にb(i2)を挿入するコストを足したものに等しい。
・Ａの文字を置換することでＢに近づく場合：
a(i1)をb(i2)に置換すればよいので、d[ i1, i2 ]はd[ i1 – 1, i2 – 1]にa(i1)を置換するコストを足したものに等しい。
というわけで、PHPで書くと以下のようになります。
/**
* レーベンシュタイン距離を求める。
* @param $a A文字列
* @param $b B文字列
* @param $i_c 挿入コスト
* @param $r_c 置換コスト
* @param $d_c 削除コスト
* @return 距離
*/
function leven($a, $b, $i_c=1, $r_c=1, $d_c=1)
{
$len_a = strlen($a);
$len_b = strlen($b);
$matrix = array();
for ($jj = 0; $jj <= $len_b; $jj++) {
$matrix[0][$jj] = $jj*$i_c; // 全挿入
}
for ($ii = 0; $ii <= $len_a; $ii++) {
$matrix[$ii][0] = $ii*$d_c; // 全削除
}
for ($i = 1; $i <= $len_a; $i++) for ($j = 1; $j <= $len_b; $j++) {
$del = $matrix[$i-1][$j] + $d_c; // 削除
$ins = $matrix[$i][$j-1] + $i_c; // 挿入
$rep = $a[$i-1] == $b[$j-1] ? $matrix[$i-1][$j-1] : $matrix[$i-1][$j-1] + $r_c; // 置換
$matrix[$i][$j] = min($ins, $del, $rep);
}
return $matrix[$len_a][$len_b];
}
PHPにはそもそもlevenshtein()という関数があり、上記のような関数を自分で作る必要はないです。挿入コスト・置換コスト・削除コストをいろいろ変えたとき、上記関数はPHPの組込関数と結果が一致します。しかし、Wikipediaのものは一致しません。Wikipedia方式は次のような解釈と思います。
・Bからの削除によりAに近づく場合：
Bからb(i2)を削除すれば良いので、d[ i1, i2 ]はd[ i1, i2 – 1 ]にb(i2)を削除するコストを足したものに等しい。
・Aへの挿入によりＢに近づく場合：
a(1)～a(i1 – 1)の文字列にb(i2)を挿入すればよいので、d[ i1, i2 ]はd[ i1 – 1, i2 ]にb(i2)を挿入するコストを足したものに等しい。
・Ａの文字を置換することでＢに近づく場合：
a(i1)をb(i2)に置換すればよいので、d[ i1, i2 ]はd[ i1 – 1, i2 – 1]にa(i1)を置換するコストを足したものに等しい。
この方が理解しやすいですが、両方の文字列を編集しているのでもともとの定義からは外れていると思います。ただし、たいていの場合に上記の2つの解釈は結果が一致します。というか、挿入コストと削除コストが等しい場合には同じになります。逆に言うと、コストが挿入と削除で対称でない場合は違う結果になります。
ただし、レーベンシュタイン距離が距離の公理を満たすためには挿入と削除に対して対称でなければならないため、結局どっちでもイイっていう。
あるいは基本的に私が勘違いしている可能性も高いです。
以上
