[を] Dynamic Programming による類似文字列マッチの実装例
でPerlのコードがあったのでPHPで書いてみた。途中まで。keyとtextを配列ではなくて文字列にしている点がちょっと違う。Perlのコードを読むことは滅多にないので新鮮。

<?php
$key  = ' ' . $argv[1];
$text = ' ' . $argv[2];

$C = array();
$t_len = strlen($text);
$k_len = strlen($key);
for ($j = 0; $j < $t_len; $j++) {
    $C[0][$j] = 0;
}
for ($i = 0; $i < $k_len; $i++) {
    $C[$i][0] = $i;
}
for ($i = 1; $i < $k_len; $i++) {
    for ($j = 1; $j < $t_len; $j++) {
        $u = $C[$i-1][$j];
        $l = $C[$i][$j-1];
        $d = $C[$i-1][$j-1];
        if ($key[$i] == $text[$j]) {
            $C[$i][$j] = $d;
        } else {
            $C[$i][$j] = 1 + min($u, $l, $d);
        }
    }
}
echo "score: ".$C[$k_len-1][$t_len-1]."\\n";

GoogleやYahoo!の「もしかして～」はどんなアルゴリズムで出しているんだ？と友人と何度か議論したことがありますが、こういうアルゴリズムも使ってるんでしょーか。