2つの文字列の違いを示す。
文字列を、他方の文字列に
置換、挿入、削除の手順で変換した際の最小手順数。
PHP:
levenshtein関数があるが、対応しているのはascii文字だけであろうかと思われる。
noteにPHPで実装されたサンプルがあるので、それのstrposとｓｔrlenをそれぞれ
mb_strpos mb_strlenに置き換え、及び文字列からのインデックス指定の文字切り出しを
角括弧を使ったものから mb_substr（$i,1)に変更。
使う際には、 mb_internal_encoding必要。
function LevenshteinDistance($s1, $s2)
{
$sLeft = (mb_strlen($s1) > mb_strlen($s2)) ? $s1 : $s2;
$sRight = (mb_strlen($s1) > mb_strlen($s2)) ? $s2 : $s1;
$nLeftLength = mb_strlen($sLeft);
$nRightLength = mb_strlen($sRight);
if ($nLeftLength == 0)
return $nRightLength;
else if ($nRightLength == 0)
return $nLeftLength;
else if ($sLeft === $sRight)
return 0;
else if (($nLeftLength < $nRightLength) && (mb_strpos($sRight, $sLeft) !== FALSE))
return $nRightLength - $nLeftLength;
else if (($nRightLength < $nLeftLength) && (mb_strpos($sLeft, $sRight) !== FALSE))
return $nLeftLength - $nRightLength;
else {
$nsDistance = range(1, $nRightLength + 1);
for ($nLeftPos = 1; $nLeftPos <= $nLeftLength; ++$nLeftPos)
{
$cLeft = mb_substr($sLeft,$nLeftPos - 1,1);
$nDiagonal = $nLeftPos - 1;
$nsDistance[0] = $nLeftPos;
for ($nRightPos = 1; $nRightPos <= $nRightLength; ++$nRightPos)
{
$cRight = mb_substr($sRight,$nRightPos - 1,1);
$nCost = ($cRight == $cLeft) ? 0 : 1;
$nNewDiagonal = $nsDistance[$nRightPos];
$nsDistance[$nRightPos] =
min($nsDistance[$nRightPos] + 1,
$nsDistance[$nRightPos - 1] + 1,
$nDiagonal + $nCost);
$nDiagonal = $nNewDiagonal;
}
}
return $nsDistance[$nRightLength];
}
}
