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

      2016/07/14

レーベンシュタイン距離日本語対応

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

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

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

 

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

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

 

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

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

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

<?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では、このアルゴリズムを使ってコピペ文章かコピペ文章じゃないかを判定する基準データとしています。

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

 

megane

megane

最近、個人事業主から法人へと進化しました。 エンジニア歴13年位です。PHPとかMysqlを使ってWebシステムを構築します。 Javaも書きます。 CakePHPも使います。 サーバのチューニングもごりごりやります。 あと、お肉と自動車が好きです。Twitterとか申請どうぞ。

 - PHP ,