Tag Archives: レーベンシュタイン距離

[PHP]マルチバイト文字列を比較して類似の度合いを計算する

Facebook にシェア
Delicious にシェア
LINEで送る
Pocket

PHP には2つの文字がどれだけ似ているかを表す関数が2つ用意されています。
ひとつは similar_text() で、もうひとつは levenshtein() です。

similar_text() は類似度をパーセントで返し、
levenshtein() は、両者を一致させるのにかかる作業量を返します。

後者のレーベンシュタイン距離を調べるアルゴリズムは Wikipedia に掲載されているので、
それを参考にマルチバイト対応版 mb_levenshtein を作ってみました。

<?php
function mb_levenshtein($str1, $str2, $encoding){
  $length1 = mb_strlen($str1, $encoding);
  $length2 = mb_strlen($str2, $encoding);
  
  $str1 = mb_str_split($str1, $encoding);
  $str2 = mb_str_split($str2, $encoding);
  
  $distance = array();
  for($i=0;$i<=$length1;$i++){
    $distance[$i] = array();
    $distance[$i][0] = $i;
  }
  for($i=0;$i<=$length2;$i++){
    $distance[0][$i] = $i;
  }
  $cost = 0;
  for($i=1;$i<=$length1;$i++){
    for($j=1;$j<=$length2;$j++){
      $cost = ($str1[$i - 1] === $str2[$j-1]) ? 0 : 1;
      $distance[$i][$j] = min(
        $distance[$i - 1][$j] + 1,
        $distance[$i][$j - 1] + 1,
        $distance[$i - 1][$j - 1] + $cost
      );
    }
  }
  return $distance[$length1][$length2];
}

function mb_str_split($str, $encoding){
  $arr = array();
  $length = mb_strlen($str, $encoding);
  for($i=0;$i<$length;$i++){
    $arr[] = mb_substr($str, $i, 1, $encoding);
  }
  return $arr;
}

$str1 = "sample";
$str2 = "example";

header("Content-type:text/html; charset=utf-8");

echo mb_levenshtein($str1, $str2, 'utf-8');

Posted in PHP | Tagged , | Leave a comment