PHPのlevenshteinとsimilar_textは日本語をバイトで数える、mb対応の距離を自前で書く

Bynori

levenshtein()とsimilar_text()は、2つの文字列の「似ている度合い」を測る組み込み関数ですが、どちらも文字ではなくバイト単位で計算します。UTF-8の日本語(1文字3バイト)に使うと、距離が約3倍に膨らむなど、期待とずれた数字が返ります。

「表記ゆれの候補を出したい」「入力ミスの近い商品名をサジェストしたい」といった用途で、英単語では素直に動いたのに、日本語にした途端しきい値が効かなくなった、という場面があります。私も一度、距離の閾値を英語の感覚で決めて、日本語だけまったく候補が出ない状態になったことがあります。手元のPHP 8.3.6で実際に動かした結果をまとめます。

levenshteinは日本語でなぜ距離が大きくなるのか

levenshtein()は「挿入・置換・削除を何回すれば同じ文字列になるか」を数える関数です。ただし数える単位はバイトです。UTF-8のひらがなやカタカナ、漢字は1文字3バイトなので、1文字違うだけでも複数バイトぶんの差が出ることがあります。

<?php
var_dump(strlen('あ'));                    // int(3)
var_dump(levenshtein('kitten', 'sitting')); // int(3)  英語は期待どおり
var_dump(levenshtein('りんご', 'みかん'));  // int(6)  3文字すべて違うので文字単位なら3のはず
var_dump(levenshtein('カレー', 'カレ'));    // int(3)  文字単位なら1(「ー」を消すだけ)

「カレー」から「ー」を1文字消すだけなのに、距離は3になります。「ー」が3バイトだからです。距離に閾値(たとえば2以下なら候補にする)を置いていると、この差で候補から漏れます。

ひどいのは逆の面で、バイトの一部が偶然一致すると、1文字違いなのに距離が1や2に見えることです。UTF-8のひらがなは「あ」と「い」のように先頭の2バイトが共通のものが多く、違いが末尾の1バイトだけになることがあります。

<?php
var_dump(levenshtein('あ', 'い'));         // int(1)
var_dump(levenshtein('ありがとう', 'ありがとー')); // int(2)  文字単位なら1

つまり、日本語では「バイトの重なり方しだいで、距離が文字数の1倍から3倍の間でぶれる」ことになります。この数字をそのまま閾値判定に使うのは、避けたほうがよさそうです。

similar_textのパーセントも日本語ではずれるのか

similar_text()は、2つの文字列の共通部分を探して、一致したバイト数を返す関数です。第3引数に変数を渡すと、類似度のパーセントが入ります。こちらもバイト単位です。

<?php
$n = similar_text('りんご', 'りんこ', $p);
echo "$n / $p\n";   // 8 / 88.888888888889  (一致8バイト。文字単位なら2文字/3文字で66.7%)

$n = similar_text('東京都', '京都府', $p);
echo "$n / $p\n";   // 6 / 66.666666666667  (「京都」の6バイトが一致)

「りんご」と「りんこ」は、同じ「り」「ん」の2文字(6バイト)に加えて、「ご」と「こ」の先頭2バイトも一致として数えられます。文字単位の感覚だと約67%のところ、約89%と出てしまいます。見た目より似ていると判定される方向にぶれるわけです。

similar_textは引数の順序で結果が変わる

もう一つ、地味なハマりどころがあります。similar_text()は、引数を入れ替えると結果が変わることがあります。

<?php
$n = similar_text('bafoobar', 'barfoo', $p);
echo "$n / $p\n";   // 5 / 71.428571428571

$n = similar_text('barfoo', 'bafoobar', $p);
echo "$n / $p\n";   // 3 / 42.857142857143

どちらも同じ2つの文字列の比較なのに、一致数が5と3で、パーセントも71%と43%に割れます。内部で最長の共通部分を見つけて、その左右を再帰的に比べる作りで、最長の共通部分が複数あるときは最初に見つかったものが使われるためです。「AとBの類似度」のつもりで保存した値が、順序しだいで変わるのは気持ち悪いので、両方向で計算して平均や大きい側を取る、と決めておくと安定します。

文字単位で距離を出すにはどう書けばいいのか

解決策はシンプルで、mb_str_split()で1文字ずつの配列に分けてから、レーベンシュタイン距離を自分で計算します。mb_str_split()はPHP 7.4で追加された関数です。

配列ごと全体の行列を持つ必要はなく、直前の1行だけ覚えておけば足ります。メモリも省けて、実務ではこの形で十分でした。

<?php
function mb_levenshtein(string $a, string $b): int
{
    $x = mb_str_split($a);
    $y = mb_str_split($b);

    $prev = range(0, count($y));
    foreach ($x as $i => $cx) {
        $cur = [$i + 1];
        foreach ($y as $j => $cy) {
            $cur[$j + 1] = min(
                $prev[$j + 1] + 1,                      // 削除
                $cur[$j] + 1,                           // 挿入
                $prev[$j] + ($cx === $cy ? 0 : 1)       // 置換(同じ文字なら0)
            );
        }
        $prev = $cur;
    }
    return $prev[count($y)];
}

var_dump(mb_levenshtein('りんご', 'みかん'));            // int(3)
var_dump(mb_levenshtein('カレー', 'カレ'));              // int(1)
var_dump(mb_levenshtein('ありがとう', 'ありがとー'));    // int(1)
var_dump(mb_levenshtein('kitten', 'sitting'));           // int(3)
var_dump(mb_levenshtein('東京都', '京都府'));            // int(2)

これで「1文字違えば距離1」という、人間の感覚どおりの数字になります。英語の結果も組み込みのlevenshtein()と一致するので、置き換えても挙動が変わりません。「東京都」から「京都府」は、先頭の「東」を消して末尾に「府」を足す2回で、組み込み関数だとバイト単位で6と出ていたところです。

濁点と全角半角はどう扱うのか

文字単位にしても、もう一段ずれる場面があります。濁点つきの文字が、「か」+結合用の濁点(U+3099)の2コードポイントで入ってくる場合です。これは見た目は「が」1文字ですが、mb_str_split()では2要素に分かれます。macOSのファイル名などで見かけます。

比較の前に、Normalizer::normalize($s, Normalizer::FORM_C)で合成形にそろえると安定します(intl拡張が必要です)。全角の英数字と半角を同一視したいなら、mb_convert_kana()で「KV」などにそろえてから比べます。距離を測る前の正規化が、じつは精度にいちばん効く気がしています。

コストを変えたいときはどう書くのか

組み込みのlevenshtein()には、挿入・置換・削除のコストを渡す引数があります。順序は「挿入、置換、削除」です。

<?php
// levenshtein(string $s1, string $s2, int $ins = 1, int $rep = 1, int $del = 1)
var_dump(levenshtein('abc', 'abd', 1, 2, 3)); // int(2)  置換1回(コスト2)
var_dump(levenshtein('abc', 'ab',  1, 2, 3)); // int(3)  削除1回(コスト3)
var_dump(levenshtein('ab',  'abc', 1, 2, 3)); // int(1)  挿入1回(コスト1)

引数の順序が「挿入、置換、削除」なのは覚えにくいので、コストを変えるときはこの例のようにコメントを添えておくのが無難です。なお、長い文字列に使う場合、昔は255文字までという制限がありましたが、手元のPHP 8.3では300文字ずつの比較でも動きました。それでも計算量は文字数の積に比例するので、長文の比較にはあまり向きません。

まとめ

levenshtein()とsimilar_text()は、どちらもバイト単位で動くので、日本語に使うと距離や類似度がずれます。しきい値で判定する用途なら、mb_str_split()ベースの距離を自前で1つ持っておくのが近道だと思います。similar_text()は引数の順序でも結果が変わるので、使うなら両方向で計算しておくのが安心です。

よくある質問

Q. levenshteinは日本語の文字列でも使えますか?
A. エラーにはなりませんが、距離はバイト単位で計算されます。UTF-8の日本語は1文字3バイトなので、「カレー」と「カレ」の距離が1ではなく3になります。文字単位で測るなら、mb_str_split()で分割して自前で計算します。

Q. similar_textの結果は引数を入れ替えると変わりますか?
A. 変わることがあります。手元のPHP 8.3では、similar_text(‘bafoobar’, ‘barfoo’) は5、順序を逆にすると3でした。両方向で計算して大きい側(または平均)を取ると安定します。

Q. mb_str_splitはいつから使えますか?
A. PHP 7.4からです。それ以前の環境では、preg_split(‘//u’, $s, -1, PREG_SPLIT_NO_EMPTY) で1文字ずつに分けられます。

類似投稿

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です