レーベンシュタイン距離（編集距離）をPHPで

気分転換にレーベンシュタイン距離をPHPで書いてみた（研究と全く関係ないんだけど・・・）

レーベンシュタイン距離の説明は「レーベンシュタイン距離 - Wikipedia」が詳しい。

要は「文字列Aを文字列Bに変換するためにどれだけの操作が必要か」ということ。

1. kitten
2. sitten （“k”を“s”に置換）
3. sittin （“e”を“i”に置換）
4. sitting （“g”を挿入して終了）

でレーベンシュタイン距離=３だそうです。

実装してからLevens・・・と書いてEclipseのコードインテリジェンスで関数候補を見たら「levenshtein」という関数を発見・・・

標準関数でした（PHP: levenshtein）

せっかくなんでテストもしてみた。

function LevenshteinDistance($str1, $str2) {
  $d = array ();
  $len1 = strlen($str1);
  $len2 = strlen($str2);
  for ($i1 = 0; $i1 <= $len1; $i1++) {
    $d[$i1] = array ();
    $d[$i1][0] = $i1;
  }
  
  for ($i2 = 0; $i2 <= $len2; $i2++) {
    $d[0][$i2] = $i2;
  }
 
  for ($i1 = 1; $i1 <= $len1; $i1++) {
    for ($i2 = 1; $i2 <= $len2; $i2++) {
      $cost = ($str1[$i1 - 1] == $str2[$i2 - 1]) ? 0 : 1;
      $d[$i1][$i2] = min(
                $d[$i1 - 1][$i2    ] + 1, //挿入
                $d[$i1    ][$i2 - 1] + 1, //削除
                $d[$i1 - 1][$i2 - 1] + $cost //置換
      );
    }
  }
  return $d[$len1][$len2];
}
$test = array(
  array('abc', 'abc'), //0
  array('kitten', 'sitting'), //3
  array('aaaaa', 'bbbbb'),//5
  array('abc', 'bca'),//
  array('12345', '234'),
);
foreach($test as $row) {
  echo levenshtein($row[0], $row[1]);
  echo ' = ';
  echo LevenshteinDistance($row[0], $row[1]);
  echo '<br/>';
}

PHPはこーゆーときの配列処理とかなんか気持ち悪いなと思う。

レーベンシュタイン距離（編集距離）をPHPで 2008-11-11