類似文字列マッチの実装例 今度はPHPのlevenshtein関数

zuzara : Dynamic Programming による類似文字列マッチの実装例 in PHP
昨日の記事でコメントをいただいた情報を参考にすると、

<?php
echo levenshtein($argv[1], $argv[2]) . "\\n";

これで同じ結果が得られるか、と思いきやちょっとアルゴリズムが違うようです。

% php dynamicprogramming.php abcd dabc # 昨日の
score: 1
php levenshtein.php abcd dabc # 上記コード
2

と違う結果が返ってきた。

levenshtein関数はext/standard/levenshtein.cで定義されていて、PHPに直すと

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

$p1 = array();
$p2 = array();
$l1 = strlen($text);
$l2 = strlen($key);
for ($i2 = 0; $i2 <= $l2; $i2++) {
    $p1[$i2] = $i2;
}
for ($i1 = 0; $i1 < $l1; $i1++) {
    $p2[0] = $p1[0] + 1;
    for ($i2 = 0; $i2 < $l2; $i2++) {
        $c0 = $p1[$i2] + (($key[$i1] == $text[$i2]) ? 0 : 1);
        $c1 = $p1[$i2+1] + 1;
        $c2 = $p2[$i2] + 1;
        $p2[$i2+1] = min($c0, $c1, $c2);
    }
    $tmp = $p1;
    $p1 = $p2;
    $p2 = $tmp;
}
$c0 = $p1[$l2];

echo "score: $c0\\n";

こんな感じ。PHP5.2.0から拝借。ソースのコメントにはonly optimized for memory usage, not speedと書いてある。$tmpで$p1と$p2を入れ替えるとうまくいく、というのは不思議。

あとコメントでいただいたunno氏の話はここでもちょっと出ました。
zuzara : 「日本語スペルチェック」、「表記のゆれ」：API化して欲しい！