編集距離 (レーベンシュタイン距離)｜コードで実践

編集距離 (レーベンシュタイン距離)

このレッスンで分かること

素朴に再帰で書くと、各文字について「挿入 / 削除 / 置換 / そのまま」の 4 通りを分岐するため、計算量は指数的に爆発します

編集距離 とは、ある文字列 s1 をもう 1 つの文字列 s2 に変えるために必要な、最小の編集操作回数のことです

この問題は スペルチェック、DNA 配列比較、diff ツール、機械翻訳の評価指標 など、現実世界で非常に多く応用されます

編集距離とは

2 つの文字列を一致させるために必要な最小編集回数を、二次元 DP で求める古典問題に挑戦します。本レッスンでは、編集距離の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

編集距離 とは、ある文字列 s1 をもう 1 つの文字列 s2 に変えるために必要な、最小の編集操作回数のことです。許される編集操作は挿入、削除、置換の 3 種類で、それぞれ 1 回として数えます。例えば kitten を sitting に変えるなら、k を s に置換、e を i に置換、最後に g を挿入する、という 3 手順で完了します。よって編集距離は 3 です。

この問題は スペルチェック、DNA 配列比較、diff ツール、機械翻訳の評価指標 など、現実世界で非常に多く応用されます。Git の git diff も、内部的にはこの考え方の親戚を使っています。

編集距離は「文字列の似ている度合い」を数値化する基本指標。動的計画法 (DP) の代表問題でもある。

なぜ DP なのか

素朴に再帰で書くと、各文字について「挿入 / 削除 / 置換 / そのまま」の 4 通りを分岐するため、計算量は指数的に爆発します。しかし、同じ部分問題が何度も現れるため、結果を メモ化 することで O(m * n) に落とせます。m、n はそれぞれ文字列の長さです。

状態の定義

dp[i][j] を「s1 の最初の i 文字を、s2 の最初の j 文字に変えるのに必要な最小編集回数」と定義します。すると次の漸化式が成り立ちます。

s1[i-1] == s2[j-1] なら dp[i][j] = dp[i-1][j-1] (何もしない)
そうでなければ dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

それぞれは削除、挿入、置換に対応します。

DP の鍵は「状態 (どこまで処理したか) と遷移 (次にどう進むか)」を言語化することにある。

初期条件

空文字列に対しては、もう片方の文字数ぶんだけ挿入または削除する必要があります。よって dp[i][0] = i、dp[0][j] = j です。

図解

diagram (will load when visible)

図のポイント (テキスト併記)

セル dp[i][j] は、左上 / 左 / 上の 3 方向の値から min を取って遷移します

セル dp[i][j] は、左上 / 左 / 上の 3 方向の値から min を取って遷移します。表を左上から右下に向かって埋めていけば、最終的に dp[m][n] が答えです。

Python 実装

Python

def editDistance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

二次元配列 dp を 0 初期化したあと、1 行目と 1 列目に初期値を埋め、二重ループでセルを順番に確定させます。min を取るのが DP の心臓部です。

JavaScript 実装

JavaScript

function editDistance(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  return dp[m][n];
}

ロジックは Python と完全に同じです。Array.from で二次元配列を作る点が JS 特有の書き方です。

よくある間違い

1 つ目は 初期化忘れ。dp[i][0] = i を埋めないと、最初の列がすべて 0 になり、結果が小さすぎる値になります。2 つ目は インデックスのずれ。s1[i-1] と s2[j-1] を比べることに注意してください。dp[i][j] は「最初の i 文字」を意味するので、対応する文字は i-1 番目です。3 つ目は 置換と挿入を混同 すること。3 通りの遷移のうち、左上が置換、左が挿入、上が削除です。

やってみよう

editDistance("horse", "ros") を計算する。答えは 3 (h を r に置換、o はそのまま、r を削除、s はそのまま、e を削除)。
表を紙に書き出して、左上から右下に向かって埋めてみる。dp の遷移の理解が一気に深まる。
空間計算量を O(min(m, n)) に削減する rolling array 版にも挑戦してみる。

編集距離は DP の入門と総決算 を兼ねる名問題。状態の定義と遷移を自分の言葉で説明できれば、他の DP も怖くなくなる。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は 最長増加部分列 (LIS) で、数列の中で増加し続ける部分列の最長の長さを DP で求める問題に挑戦します。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

編集距離の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 編集距離とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

編集距離 (レーベンシュタイン距離)