Dynamic Programming による類似文字列マッチの実装例 in PHP

[を] 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!の「もしかして~」はどんなアルゴリズムで出しているんだ?と友人と何度か議論したことがありますが、こういうアルゴリズムも使ってるんでしょーか。

This entry was posted in いじる. Bookmark the permalink. Both comments and trackbacks are currently closed.

4 Comments

  1. Posted 2007/01/26 at 11:43 pm | Permalink

    Google の「もしかして」、は恐らくlevenshteinというアルゴリズムです。

  2. Posted 2007/01/26 at 11:52 pm | Permalink

    情報ありがとうございますー。
    PHPには同名の関数がありますね。知りませんでした。

  3. Posted 2007/01/27 at 12:30 am | Permalink

    私が「Dynamic Programming による類似文字列マッチの実装例」で書いた類似度は Edit Distance と呼ばれるもので、Levenshtein Distance と同じものですね。

    参考:文字列の類似度 – Levenshtein距離 at Project Phonethica
    http://www.phonethica.net/nao-tokui/%E6%96%87%E5%AD%97%E5%88%97%E3%81%AE%E9%A1%9E%E4%BC%BC%E5%BA%A6-levenshtein%E8%B7%9D%E9%9B%A2/

  4. unno
    Posted 2007/01/27 at 1:13 am | Permalink

    edit distance は部分的には使っている気がしますが、極端な話2文字の単語に edit distance 1 の単語集合をとってくるとひどいもので・・・。というか、アルファベット数の多い単語だとアレですね。キーボード上で近い位置などの条件をつけるのも手でしょうか。
    直感的には、やはり「検索し直し履歴」を使うのが簡単かつ高性能な気がします。

Page optimized by WP Minify WordPress Plugin