[マルチバイト対応] レーベンシュタイン距離を求める

導入

PHPにはsimilar_textやlevenshteinといった、2つの文字列の類似度を計算するための関数があります。しかしこれらはマルチバイトを考慮しておらず、とりわけUTF-8バイト列に対しては計算精度が悪化するという特徴があります。そこで今回はUTF-8マルチバイト対応版のlevenshtein_utf8という関数を作ってみることにしました。なおsimilar_textの方は計算量が大きすぎてPHPレベルで実装するに堪えないので、今回はパスということで…

• 既に@suinさんの「mb_levenshtein 二つの文字列のレーベンシュタイン距離を計算する（マルチバイト対応版）」は拝見しましたが、文字種による制約がかかると実用的ではないので、@itcomさんがコメントされているように素直な実装を行いました。といってもほとんどphp-srcからのパクりですが。
• 距離の正規化に関しては@giiko_さんが「文字列の類似度を計算するgem」で述べられている意見を取り入れました。これはlevenshtein_normalized_utf8として実装しています。

実装

コード

function levenshtein_normalized_utf8($s1, $s2, $cost_ins = 1, $cost_rep = 1, $cost_del = 1) {
    $l1 = mb_strlen($s1, 'UTF-8');
    $l2 = mb_strlen($s2, 'UTF-8');
    $size = max($l1, $l2);
    if (!$size) {
        return 0;
    }
    if (!$s1) {
        return $l2 / $size;
    }
    if (!$s2) {
        return $l1 / $size;
    }
    return 1.0 - levenshtein_utf8($s1, $s2, $cost_ins, $cost_rep, $cost_del) / $size;
}

function levenshtein_utf8($s1, $s2, $cost_ins = 1, $cost_rep = 1, $cost_del = 1) {
    $s1 = preg_split('//u', $s1, -1, PREG_SPLIT_NO_EMPTY);
    $s2 = preg_split('//u', $s2, -1, PREG_SPLIT_NO_EMPTY);
    $l1 = count($s1);
    $l2 = count($s2);
    if (!$l1) {
        return $l2 * $cost_ins;
    }
    if (!$l2) {
        return $l1 * $cost_del;
    }
    $p1 = array_fill(0, $l2 + 1, 0);
    $p2 = array_fill(0, $l2 + 1, 0);
    for ($i2 = 0; $i2 <= $l2; ++$i2) {
        $p1[$i2] = $i2 * $cost_ins;
    }
    for ($i1 = 0; $i1 < $l1; ++$i1) {
        $p2[0] = $p1[0] + $cost_ins;
        for ($i2 = 0; $i2 < $l2; ++$i2) {
            $c0 = $p1[$i2] + ($s1[$i1] === $s2[$i2] ? 0 : $cost_rep);
            $c1 = $p1[$i2 + 1] + $cost_del;
            if ($c1 < $c0) {
                $c0 = $c1;
            }
            $c2 = $p2[$i2] + $cost_ins;
            if ($c2 < $c0) {
                $c0 = $c2;
            }
            $p2[$i2 + 1] = $c0;
        }
        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp;
    }
    return $p1[$l2];
}

使用例

その1

コード

$query = 'ほあようごぁいまーしゅ';
$comps = [
    'こんにちはー',
    'おはようございまーす',
    'こんばんはー',
    'おやすみなさーい',
    'いただきまーす',
    'おつかれさまー',
    'ぬぁあああんつかれたもぉぉぉぉぉぉん',
];
foreach ($comps as $comp) {
    $sim = levenshtein_normalized_utf8($query, $comp);
    if ($sim > 0.5 and !isset($result) || $sim > $result['sim']) {
        $result['sim'] = $sim;
        $result['word'] = $comp;
        if ($result['sim'] === 1.0) {
            break;
        }
    }
}
echo '検索語: ' . $query . PHP_EOL;
if (!isset($result)) {
    echo '見つかりませんでした' . PHP_EOL;
} else if ($result['sim'] === 1.0) {
    echo '見つかりました' . PHP_EOL;
} else {
    echo 'もしかして: ' . $result['word'] . PHP_EOL;
}

実行結果

検索語: ほあようごぁいまーしゅ
もしかして: おはようございまーす

その2

コード

$base = 'やんほぬ';
$comps = [
    'かんのみほ',
    'かんのみほう',
    'かんぺみろ',
    'ああいいふろ',
    'ちゃんとみろ',
    'ターミナルさん',
];
print_r(array_map(
    function ($comp) use ($base) { return [
        'levenshtein_utf8' => levenshtein_utf8($base, $comp),
        'levenshtein_normalized_utf8' => levenshtein_normalized_utf8($base, $comp),
    ]; },
    array_combine($comps, $comps)
));

実行結果

Array
(
    [かんのみほ] => Array
        (
            [levenshtein_utf8] => 4
            [levenshtein_normalized_utf8] => 0.2
        )

    [かんのみほう] => Array
        (
            [levenshtein_utf8] => 4
            [levenshtein_normalized_utf8] => 0.33333333333333
        )

    [かんぺみろ] => Array
        (
            [levenshtein_utf8] => 4
            [levenshtein_normalized_utf8] => 0.2
        )

    [ああいいふろ] => Array
        (
            [levenshtein_utf8] => 6
            [levenshtein_normalized_utf8] => 0
        )

    [ちゃんとみろ] => Array
        (
            [levenshtein_utf8] => 5
            [levenshtein_normalized_utf8] => 0.16666666666667
        )

    [ターミナルさん] => Array
        (
            [levenshtein_utf8] => 7
            [levenshtein_normalized_utf8] => 0
        )

)