文字列間のレーベンシュタイン距離を求める

レーベンシュタイン距離というのを知った。

Wikipedia のレーベンシュタイン距離の項によると：

レーベンシュタイン距離（レーベンシュタインきょり）は、二つの文字列がどの程度異なっているかを示す距離（距離空間を参照）である編集距離（へんしゅうきょり）の一種類である。具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。名称は、1965年にこれを考案したロシアの学者ウラジミール・レーベンシュタインにちなむ。

だそう。上記ページに擬似コードによる実装例が載ってるのと、次のページの Python での実装例が参考になった。なので JavaScript でやってみた。

　cf. 編集距離 (Levenshtein Distance) – naoyaのはてなダイアリー

#!/usr/bin/env node

function levenshtein_distance(a, b) {
  var m = [];
  var i, j, x;

  for (i = 0; i <= a.length; i++) {
    m[i] = [];
  }
  for (i = 0; i <= a.length; i++) {
    m[i][0] = i;
  }
  for (j = 0; j <= b.length; j++) {
    m[0][j] = j;
  }
  for (i = 1; i <= a.length; i++) {
    for (j = 1; j <= b.length; j++) {
      if (a[i-1] == b[j-1]) {
        x = 0;
      } else {
        x = 1;
      }
      m[i][j] = Math.min(m[i-1][j] + 1, m[i][j-1] + 1, m[i-1][j-1] + x);
    }
  }
  for (i = 0; i <= a.length; i++) {
    console.log(m[i]);
  }

  return m[a.length][b.length];
}

var s1 = process.argv[2];
var s2 = process.argv[3];
console.log(levenshtein_distance(s1, s2));

実行例：

takatoh@nightschool $ ./ld.js apple play
4
takatoh@nightschool $ ./ld.js perl pearl
1