@blog.justoneplanet.info

日々勉強

PHPで文字列の類似度を求める

レーベンシュタイン距離を使う。

function mb_str_split($str, $split_len = 1) {
    mb_internal_encoding('UTF-8');
    mb_regex_encoding('UTF-8');
    if ($split_len <= 0) {
        $split_len = 1;
    }

    $strlen = mb_strlen($str, 'UTF-8');
    $ret    = array();

    for ($i = 0; $i < $strlen; $i += $split_len) {
        $ret[] = mb_substr($str, $i, $split_len);
    }
    return $ret;
}

function getLevenshteinFactor($string1, $string2, $insert = 1, $delete = 1, $replace = 1) {
    $string1 = mb_str_split($string1);
    $length1 = count($string1);
    $string2 = mb_str_split($string2);
    $length2 = count($string2);

    if ($length1 < $length2) {
        $c = $string1;
        $string1 = $string2;
        $string2 = $c;
        $o = $length1;
        $length1 = $length2;
        $length2 = $o;
    }

    $d = array();
    $d[0] = array();
    for ($i = 0; $i < $length2 + 1; $i++) {
        $d[0][$i] = $i;
    }

    for ($i = 1; $i < $length1 + 1; $i ++) {
        $d[$i] = array();
        $d[$i][0] = $i;
        for ($j = 1; $j < $length2 + 1; $j ++) {
            $cost = ($string1[$i - 1] === $string2[$j - 1]) ? 0 : 1;
            $d[$i][$j] = min(
                $d[$i - 1][$j] + $insert,
                $d[$i][$j - 1] + $delete,
                $d[$i - 1][$j - 1] + ($replace * $cost)
            );print($d[$i][$j]);
        }
    }
    $distance = $d[$length1][$length2];
    $rate = $distance / $length1;
    return $rate;
}

他のサイトから持ってきたけど期待した値と少し違ったので調整した。

コメントはまだありません»

No comments yet.

RSS feed for comments on this post.TrackBack URL

Leave a comment