[PHP][マルチバイト対応]レーベンシュタイン距離を求める(解説つき)

概要

2つの文字列の類似度を定量的に表すことのできる、レーベンシュタイン距離。

• 名寄せの際には非常に重宝する。
• スペルチェック時の「もしかして」にも利用できる。
• DNA配列同士の類似性を判断するためにも応用されている。異なる生物種が持つ同様の遺伝子を同定したり、またそれらの距離を測ることで種が分岐してから経過した時間を推定することができる。

最後は完全に筆者の趣味だが、とにかく応用のきくわくわくするアルゴリズムなのである。

さて、このレーベンシュタイン距離、PHPではlevenshtein()という標準関数で簡単に求めることができる。ただしこれはマルチバイトに対応していない。

マルチバイトに対応したレーベンシュタイン距離算出の処理は、下記のような記事で既出で、ここに書いてある内容をコピペすれば、問題なくレーベンシュタイン距離を求めることができる。

• [マルチバイト対応] レーベンシュタイン距離を求める
• mb_levenshtein 二つの文字列のレーベンシュタイン距離を計算する（マルチバイト対応版）

ただ一方で、ここに書かれている内容を理解するのはなかなか難易度が高い。
アルゴリズムが何をしているのか、よくわからないのである。
本記事では、自分の書いているコードが何をしているのかきちんと把握しておきたい、そんな方のために、PHPでのマルチバイト版レーベンシュタイン距離算出のロジックを説明してみたいと思う。

実装例

マルチバイト版levenshtein()

/**
 * 2つの文字列の乖離度を返す（何文字いじったらstr1がstr2になるか）
 */
public static function mbLevenshtein($str1, $str2)
{
    $str1 = preg_split('//u', $str1, -1, PREG_SPLIT_NO_EMPTY);
    $str2 = preg_split('//u', $str2, -1, PREG_SPLIT_NO_EMPTY);
    $rowCnt = count($str1);
    $lineCnt = count($str2);
    if (!$rowCnt) {
        return $lineCnt;
    }
    if (!$lineCnt) {
        return $rowCnt;
    }
    $progression1 = array_fill(0, $lineCnt + 1, 0);
    $progression2 = array_fill(0, $lineCnt + 1, 0);
    for ($line = 0; $line <= $lineCnt; ++$line) {
        $progression1[$line] = $line;
    }
    for ($row = 0; $row < $rowCnt; ++$row) {
        $progression2[0] = $progression1[0] + 1;
        for ($line = 0; $line < $lineCnt; ++$line) {
            $cost0 = $progression1[$line] + ($str1[$row] === $str2[$line] ? 0 );
            $cost1 = $progression1[$line + 1] + 1;
            if ($cost1 < $cost0) {
                $cost0 = $cost1;
            }
            $cost2 = $progression2[$line] + 1;
            if ($cost2 < $cost0) {
                $cost0 = $cost2;
            }
            $progression2[$line + 1] = $cost0;
        }
        $tmp = $progression1;
        $progression1 = $progression2;
        $progression2 = $tmp;
    }
    return $progression1[$lineCnt];
}

解説

そもそもレーベンシュタイン距離とは、文字列Aと文字列Bがあった際に、文字列Aから最小何文字操作（文字の追加・置換・削除）したら、文字列Bになるか、という値である。

というわけで、今回は「アイスホッケー」と「アイラブホットケーキ」のレーベンシュタイン距離を算出してみる。

レーベンシュタイン距離を求める際には、まず次のような表を用意する。
ポイントは、それぞれの文字列の冒頭に空欄を入れておくことである。

	□	ア	イ	ラ	ブ	ホ	ッ	ト	ケ	ー	キ
□
ア
イ
ス
ホ
ッ
ケ
ー

この表の左上から、左側の文字列→上側の文字列への変換に必要な操作数を入れていく。
空からあらゆる文字列への変換には、文字列の文字数分の操作（追加）が必要である。
逆に、あらゆる文字列から空への変換にも、文字列の文字数分の操作（削除）が必要である。
だから表は、まずこうなる。

	□	ア	イ	ラ	ブ	ホ	ッ	ト	ケ	ー	キ
□	０	１	２	３	４	５	６	７	８	９	１０
ア	１
イ	２
ス	３
ホ	４
ッ	５
ケ	６
ー	７

実装例でいうと、$rowCntが一番左下の数字、$lineCntが一番右上の数字、$progression1が、最上段の数字の配列にあたる。

実装例の前半部分

    $str1 = preg_split('//u', $str1, -1, PREG_SPLIT_NO_EMPTY);
    $str2 = preg_split('//u', $str2, -1, PREG_SPLIT_NO_EMPTY);
    $rowCnt = count($str1);
    $lineCnt = count($str2);
    if (!$rowCnt) {
        return $lineCnt;
    }
    if (!$lineCnt) {
        return $rowCnt;
    }
    $progression1 = array_fill(0, $lineCnt + 1, 0);
    $progression2 = array_fill(0, $lineCnt + 1, 0);
    for ($line = 0; $line <= $lineCnt; ++$line) {
        $progression1[$line] = $line;
    }

さて、表を使ってレーベンシュタイン距離を求める際は、表の各値を1行ずつ左から順に埋めていく。埋めていく際のルールは、次の3つの値で、最小の値を入れていく、というものである。

• 左上のマスの数字＋α（ただし上と左の文字が一致する場合、α＝0、異なる場合、α＝1）
• 1つ上のマスの数字＋1
• 1つ左のマスの数字＋1

なぜこれでうまくいくのかというと、たとえば表のAの値（「アイス」を「アイラブ」に変換する最小操作数）というのは、

	□	ア	イ	ラ	ブ	ホ	ッ	ト	ケ	ー	キ
□	０	１	２	３	４	５	６	７	８	９	１０
ア	１
イ	２			B	C
ス	３			D	A
ホ	４
ッ	５
ケ	６
ー	７

• Bの値（「アイ」を「アイラ」に変換する最小操作数）に1操作（「ス」と「ブ」の置換）を加えたもの（ただしお互い増える文字が一緒なら、置換の必要がないため、1操作加える必要もない）
• Cの値（「アイ」を「アイラブ」に変換する最小操作数）に1操作（「ス」の削除）を加えたもの
• Dの値（「アイス」を「アイラ」に変換する最小操作数）に1操作（「ブ」の追加）を加えたもの

のどれかになるからである。
さて、そのルールに基づいて表を埋めると以下のようになり、晴れて「アイスホッケー」を「アイラブホットケーキ」に変換する際の最小操作数（＝レーベンシュタイン距離）「4」が求まる。

	□	ア	イ	ラ	ブ	ホ	ッ	ト	ケ	ー	キ
□	０	１	２	３	４	５	６	７	８	９	１０
ア	１	０	１	２	３	４	５	６	７	８	９
イ	２	１	０	１	２	３	４	５	６	７	８
ス	３	２	１	１	２	３	４	５	６	７	８
ホ	４	３	２	２	２	２	３	４	５	６	７
ッ	５	４	３	３	３	３	２	３	４	５	６
ケ	６	５	４	４	４	４	３	３	３	４	５
ー	７	６	５	５	５	５	４	４	４	３	４

実装例でいうと、for一巡目の$progression2は2行目の数字の配列にあたる。だから、左端の列の値は必ず1行上の左端の列の値に＋1をしたものとなる。
そこから右に順に数字を埋めていく。左上のマスとの比較（$cost0）、1つ上のマスとの比較（$cost1）、1つ左のマスとの比較（$cost2）で最小の値を入れているのがわかる。
そして、2行目が右端の列まで埋まったら、3行目、4行目、と同様の処理を進めていく。
最終的に返却する値は、最終行の右端の値、すなわちレーベンシュタイン距離となっている。

実装例の後半部分

    for ($row = 0; $row < $rowCnt; ++$row) {
        $progression2[0] = $progression1[0] + 1;
        for ($line = 0; $line < $lineCnt; ++$line) {
            $cost0 = $progression1[$line] + ($str1[$row] === $str2[$line] ? 0 );
            $cost1 = $progression1[$line + 1] + 1;
            if ($cost1 < $cost0) {
                $cost0 = $cost1;
            }
            $cost2 = $progression2[$line] + 1;
            if ($cost2 < $cost0) {
                $cost0 = $cost2;
            }
            $progression2[$line + 1] = $cost0;
        }
        $tmp = $progression1;
        $progression1 = $progression2;
        $progression2 = $tmp;
    }
    return $progression1[$lineCnt];

狐につまされたような印象を受けるかもしれないが、こうして2つの文字列の類似度（正確にはレーベンシュタイン距離は乖離度だが）を簡単に求めることができるのである。
アルゴリズムの面白さを感じてもらえると嬉しい。