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

レーベンシュタイン距離とは

レーベンシュタイン距離（編集距離）とは、2つの文字列がどれだけ異なっているかを数値で表す文字列メトリックの一つです。具体的には、一方の文字列をもう一方の文字列へ変換するために必要となる、1文字単位の編集操作（挿入・削除・置換）の最小回数として定義されます。

たとえば――

次の2つの文字列を考えてみましょう。

const str1 = 'hitting';
const str2 = 'kitten';

この2つの文字列間のレーベンシュタイン距離は 3 になります。これは、以下の3回の編集操作で変換できるためです。

• kitten → hitten（「k」を「h」に置換）
• hitten → hittin（「e」を「i」に置換）
• hittin → hitting（末尾に「g」を挿入）

本記事では、2つの文字列を受け取ってレーベンシュタイン距離を計算するJavaScript関数を実装していきます。

アルゴリズムの考え方

レーベンシュタイン距離の計算には、動的計画法（Dynamic Programming）がよく使われます。2つの文字列の長さを辺とする二次元の表（行列）を作成し、各セルには「片方の先頭部分からもう片方の先頭部分まで変換するのに必要な編集回数」を格納していきます。

各セルの値は、次の3つの操作のうち最小のコストを選ぶことで求められます。

• 削除： 左隣のセルの値 + 1
• 挿入： 上のセルの値 + 1
• 置換： 左上のセルの値 +（文字が異なる場合は1、同じ場合は0）

表全体を埋め終えたとき、右下のセルに入っている値がレーベンシュタイン距離となります。

コード例

実際の実装コードは以下のとおりです。

const str1 = 'hitting';
const str2 = 'kitten';
const levenshteinDistance = (str1 = '', str2 = '') => {
  // 編集コストを記録する二次元配列（表）を作成
  const track = Array(str2.length + 1).fill(null).map(() =>
    Array(str1.length + 1).fill(null));
  // 1行目：空文字列からstr1への変換コスト（= 削除回数）
  for (let i = 0; i <= str1.length; i += 1) {
    track[0][i] = i;
  }
  // 1列目：str2から空文字列への変換コスト（= 挿入回数）
  for (let j = 0; j <= str2.length; j += 1) {
    track[j][0] = j;
  }
  // 表を順に埋めていく
  for (let j = 1; j <= str2.length; j += 1) {
    for (let i = 1; i <= str1.length; i += 1) {
      const indicator = str1[i - 1] === str2[j - 1] ? 0 : 1;
      track[j][i] = Math.min(
        track[j][i - 1] + 1,           // deletion（削除）
        track[j - 1][i] + 1,           // insertion（挿入）
        track[j - 1][i - 1] + indicator, // substitution（置換）
      );
    }
  }
  return track[str2.length][str1.length];
};
console.log(levenshteinDistance(str1, str2));

実行結果

このコードをコンソールで実行すると、次の出力が得られます。

3

期待どおり、「hitting」と「kitten」のレーベンシュタイン距離である 3 が出力されました。

まとめ

レーベンシュタイン距離は、スペルチェッカー、検索候補のあいまい一致、類似文書の検出など、さまざまな場面で活用される基本的なアルゴリズムです。動的計画法を使えば、時間計算量 O(m×n)（m, n はそれぞれの文字列長）で効率よく計算できます。ぜひ自分のプロジェクトでも活用してみてください。