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

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

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));

実行例:

[email protected] $ ./ld.js apple play
4
[email protected] $ ./ld.js perl pearl
1
カテゴリー: algorithm, JavaScript パーマリンク

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

  1. ピンバック: 文字列間のレーベンシュタイン距離を求める(2)Haskell版 | blog.PanicBlanket.com

  2. ピンバック: 文字列間のレーベンシュタイン距離を求める(3)Haskell版ふたたび | blog.PanicBlanket.com

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください