クジラ机ブログ

レーベンシュタイン距離をJavaScriptで計算する

JavaScriptでレーベンシュタイン距離を求めるプログラムを書いてみたので、ここにメモしておきます。レーベンシュタイン距離とは、文字列同士の編集距離を表します。スペルチェックなどにも用いられるものです。

参考) レーベンシュタイン距離(Wikipedia)(英語版)

#!/usr/bin/env rhino
// レーベンシュタイン距離を求める関数
function calcDist(a, b) {
  if (a == b) return 0;
  if (a.length == 0) return b.length;
  if (b.length == 0) return a.length;
  var matrix = new Array(a.length + 1);
  for (var i = 0; i <= a.length; i++)
    matrix[i] = new Array(b.length + 1);
  for (var i = 0; i <= a.length; i++)
    matrix[i][0] = i;
  for (var j = 0; j <= b.length; j++)
    matrix[0][j] = j;
  for (var i = 1; i <= a.length; i++) {
    for (var j = 1; j <= b.length; j++) {
      var x = a[i - 1] == b[j -1] ? 0 : 1;
      matrix[i][j] = Math.min(
        matrix[i - 1][j] + 1,
        matrix[i][j - 1] + 1,
        matrix[i - 1][j- 1] + x
      );
    }
  }
  return matrix[a.length][b.length];
}
// ---
// テスト
var base = "今日は猫がよくなく。";
var list = [
  base,
  "こたつで猫が丸くなる。",
  "今猫がなく。",
  "昨日は猫がよくないた。",
  "今日は孫がよくなく。",
  "昨日孫の調子がよくなく。",
  "イタリアにも猫がよくいる。"
];
list.sort(function (a, b) {
  return calcDist(base, a) - calcDist(base, b);
});
for (var i in list) {
  var dist = calcDist(base, list[i]);
  print(dist + "\t" + list[i]);
}

実行結果:

0	今日は猫がよくなく。
1	今日は孫がよくなく。
3	昨日は猫がよくないた。
4	今猫がなく。
5	昨日孫の調子がよくなく。
6	こたつで猫が丸くなる。
8	イタリアにも猫がよくいる。