PHP
アルゴリズム
文字列
類似度
真夏の夜の淫夢

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


導入

PHPにはsimilar_textlevenshteinといった、2つの文字列の類似度を計算するための関数があります。しかしこれらはマルチバイトを考慮しておらず、とりわけUTF-8バイト列に対しては計算精度が悪化するという特徴があります。そこで今回はUTF-8マルチバイト対応版のlevenshtein_utf8という関数を作ってみることにしました。なおsimilar_textの方は計算量が大きすぎて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 $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
)

)