検索オートコンプリートの数学（編集距離）

Q: 検索オートコンプリートの数学（編集距離）とは何ですか？

長さ m の文字列 A = a_1 a_2 \cdots a_m と長さ n の文字列 B = b_1 b_2 \cdots b_n に対して、A の先頭 i 文字と B の先頭 j 文字の間の編集距離を D[i][j] とする。編集距離は次の漸化式（動的計画法）で定義される。 D[0][j] = j, \quad D[i][0] = i D[i][j] = \begin{cases} D[i-1][j-1] & (a_i = b_j) \\ 1 + \min\big(D[i-1][j],\ D[i][j-1],\ D[i-1][j-1]\big) & (a_i \neq b_j) \end{cases} 最終的に D[m][n] が文字列 A, B 間の編集距離（レーベンシュタイン距離）である。

Q: 検索オートコンプリートの数学（編集距離）は社会やプログラミングでどのように使われていますか？

検索オートコンプリートにおける編集距離ベースの候補ランキング: ユーザーの入力文字列と辞書内の各単語との編集距離をDPで計算し、距離が小さい（似ている）順に「もしかして」候補を並べ替えて提示する。実際の検索エンジンは、これに加えて単語の出現頻度や前方一致なども組み合わせてスコアリングしている。

文字列同士の「近さ」を動的計画法で測り、タイプミスを補正する仕組み

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 編集距離（レーベンシュタイン距離）は、ある文字列を別の文字列に変換するために必要な「挿入・削除・置換」の最小回数を表す指標
2: 動的計画法（DP）を使うと、2つの文字列の全長さの組み合わせを総当たりせずに、DPテーブルを1マスずつ埋めるだけで最小回数を効率的に計算できる
3: 検索エンジンやスマホの入力補完は、入力された文字列と辞書内の単語との編集距離が小さいものを「もしかして」候補として提示している

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

編集距離（レーベンシュタイン距離）は、ある文字列を別の文字列に変換するために必要な「挿入・削除・置換」の最小回数を表す指標

身につく武器・思考力

動的計画法（DP）を使うと、2つの文字列の全長さの組み合わせを総当たりせずに、DPテーブルを1マスずつ埋めるだけで最小回数を効率的に計算できる

実社会・ITでの活躍現場

•検索オートコンプリートにおける編集距離ベースの候補ランキング
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

2つの短い単語（例: タイプミスした単語と正しい単語）を入力し、「1マスずつ計算」ボタンでDPテーブルが左上から右下へ埋まっていく様子をステップ実行してみよう。各セルでは「左（削除）・上（挿入）・左上（置換または一致）」の3方向からの最小値+1を計算しており、右下隅の値が最終的な編集距離になる。

入力した文字列（例: タイプミス）辞書内の候補単語

		s	i	t	t	i	n	g
	0
k
i
t
t
e
n

🔍 現在のマス D[0][0] の計算:

境界セルは「空文字列との距離」なので、そのまま行番号または列番号がセットされます。

↑ 各マスは「左（挿入）・上（削除）・左上（置換または一致）」の3方向のうち最小のコストを採用して埋められます。右下隅の最終セルが2つの文字列間の編集距離です。

直感チェック！ミニクイズ

"kitten" を "sitting" に変換するために必要な最小の編集回数（編集距離）はいくつか？

Layer 2 — 定義・受験・証明

定義

長さ $m$ の文字列 $A = a_1 a_2 \cdots a_m$ と長さ $n$ の文字列 $B = b_1 b_2 \cdots b_n$ に対して、 $A$ の先頭 $i$ 文字と $B$ の先頭 $j$ 文字の間の編集距離を $D[i][j]$ とする。編集距離は次の漸化式（動的計画法）で定義される。

D[0][j] = j, \quad D[i][0] = i

D[i][j] = \begin{cases} D[i-1][j-1] & (a_i = b_j) \\ 1 + \min\big(D[i-1][j],\ D[i][j-1],\ D[i-1][j-1]\big) & (a_i \neq b_j) \end{cases}

最終的に $D[m][n]$ が文字列 $A, B$ 間の編集距離（レーベンシュタイン距離）である。

公式・数理モデル

D[i][j] = \min\big(D[i-1][j]+1,\ D[i][j-1]+1,\ D[i-1][j-1]+\mathbb{1}[a_i \neq b_j]\big)

証明・導出

動的計画法が正しく最小編集回数を求められる理由（最適部分構造）：

文字列 $A$ の先頭 $i$ 文字を文字列 $B$ の先頭 $j$ 文字に変換する「最短の操作列」を考える。最後の1手に着目すると、必ず次の3パターンのいずれかである。

1. 削除: $a_i$ を削除する → 残りは「 $A$ の先頭 $i-1$ 文字を $B$ の先頭 $j$ 文字に変換する」問題に帰着し、コストは $D[i-1][j] + 1$ 。 2. 挿入: $b_j$ を挿入する → 「 $A$ の先頭 $i$ 文字を $B$ の先頭 $j-1$ 文字に変換する」問題に帰着し、コストは $D[i][j-1] + 1$ 。 3. 置換または一致: $a_i$ を $b_j$ に置き換える（すでに一致していれば操作不要）→「 $A$ の先頭 $i-1$ 文字を $B$ の先頭 $j-1$ 文字に変換する」問題に帰着し、コストは $D[i-1][j-1] + \mathbb{1}[a_i \neq b_j]$ 。

この3つの部分問題はいずれも、元の問題より真に小さい部分文字列同士の編集距離であり、それぞれがすでに最小値として確定していれば（帰納法の仮定）、3つのコストの最小値を取ることで $D[i][j]$ も必ず最小値になる。

境界条件 $D[0][j] = j$ （空文字列を $j$ 文字の文字列にするには $j$ 回の挿入が必要）、 $D[i][0] = i$ （ $i$ 文字を空文字列にするには $i$ 回の削除が必要）から出発し、 $i, j$ を1つずつ増やしながら全マスを埋めていけば、各マスの計算は既に確定した左・上・左上のマスの値のみに依存するため、 $O(mn)$ 回の計算で全体の最小値 $D[m][n]$ に到達できる。

押さえておきたいポイント

全探索（すべての操作列を試す）は文字列長に対して指数時間かかるが、動的計画法なら $O(mn)$ の多項式時間で計算できる
各セル $D[i][j]$ は「その位置までの部分問題の最適解」を表しており、一度計算した値は再利用されるため計算量が大幅に削減される（メモ化の考え方）
検索エンジンの「もしかして: ○○」、スマホIMEの予測変換、DNA配列のアラインメント（生物情報学）、スペルチェッカーなど、文字列の近さを扱うあらゆる応用の基盤になっている
操作ごとのコストに重み（例えば置換のコストを高くする）を導入すれば、キーボード配置を考慮した「タイプミスしやすさ」重視の補完なども設計できる

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

検索オートコンプリートにおける編集距離ベースの候補ランキング

ユーザーの入力文字列と辞書内の各単語との編集距離をDPで計算し、距離が小さい（似ている）順に「もしかして」候補を並べ替えて提示する。実際の検索エンジンは、これに加えて単語の出現頻度や前方一致なども組み合わせてスコアリングしている。

1// 動的計画法による編集距離（レーベンシュタイン距離）の計算
2function editDistance(a: string, b: string): number {
3  const m = a.length;
4  const n = b.length;
5
6  // DPテーブルの初期化（境界条件: 空文字列との距離）
7  const dp: number[][] = Array.from({ length: m + 1 }, (_, i) =>
8    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
9  );
10
11  for (let i = 1; i <= m; i++) {
12    for (let j = 1; j <= n; j++) {
13      if (a[i - 1] === b[j - 1]) {
14        dp[i][j] = dp[i - 1][j - 1]; // 一致: コスト0で継承
15      } else {
16        dp[i][j] =
17          1 +
18          Math.min(
19            dp[i - 1][j], // 削除
20            dp[i][j - 1], // 挿入
21            dp[i - 1][j - 1] // 置換
22          );
23      }
24    }
25  }
26
27  return dp[m][n];
28}
29
30// 辞書内の候補と入力文字列との編集距離で「もしかして」候補をランキング
31function suggestCorrections(input: string, dictionary: string[], topK: number = 3) {
32  return dictionary
33    .map((word) => ({ word, distance: editDistance(input, word) }))
34    .sort((x, y) => x.distance - y.distance)
35    .slice(0, topK);
36}
37
38const dictionary = ["mathematics", "math", "myth", "method", "path"];
39console.log(suggestCorrections("mathe", dictionary));
40// => [{ word: "math", distance: 1 }, { word: "myth", distance: 2 }, ...]