【PHP関数】レーベンシュタイン距離を求める関数の日本語対応

■レーベンシュタイン距離とは
■2バイト文字に対応させる

■レーベンシュタイン距離とは

このコピペチェックツールで利用しているアルゴリズムです。編集距離とも呼ばれています。2つの文字列を何回変更すると同じ文字列になるかを求めるアルゴリズムです。

レーベンシュタイン距離は数値が小さいほど同じような文字列であると判断できます。レーベンシュタイン距離が0のものが全く同じ文字列となります。

このレーベンシュタイン距離ですが、phpではlevenshteinメソッドとして提供されています。しかし、このlevenshteinメソッドは2バイト文字列である日本語には対応していません。正しいレーベンシュタイン距離が出ません。

今回は、この関数を２バイト文字列に対応させます。

■2バイト文字に対応させる

Qiitaで２バイト対応させるコードが公開されていました。ありがとうございます。この関数を利用することで、日本語でも正確にレーベンシュタイン距離を取得することができています。

[マルチバイト対応] レーベンシュタイン距離を求めるから引用させていただきました。

<?php
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 $s1 / $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];
}

という感じです。

CopyContentDetectorでは、このアルゴリズムを使ってコピペ文章かコピペ文章じゃないかを判定する基準データとしています。

ぜひ、参考にしてみてください。では。