レーベンシュタイン距離

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];
  }
}