Edit distance

2025年10月20日

Edit distance

英語表記: Edit Distance

概要

編集距離とは、ある文字列を別の文字列に変換するために必要な、最小限の編集操作（挿入、削除、置換）の回数を指す指標です。これは、二つの文字列の「似ている度合い」を数値化する非常に強力な手法であり、「アルゴリズムと計算量」の分野において、特に「動的計画法（DP）」の典型的な応用問題として知られています。この問題は、大きな問題を小さな部分問題に分割し、その結果を再利用するというDPの基本原則を理解する上で、最も重要な概念の一つとなっています。

詳細解説

編集距離を計算する目的は、与えられた二つの文字列 $S_1$ と $S_2$ の間の「隔たり」を定量的に評価することです。この距離が小さければ小さいほど、文字列は類似していると判断できます。最も一般的に用いられる編集距離の定義は「レーベンシュタイン距離 (Levenshtein distance)」と呼ばれ、以下の三種類の操作のみを許容します。

挿入 (Insertion)：文字を一つ加える。
削除 (Deletion)：文字を一つ取り除く。
置換 (Substitution)：ある文字を別の文字に置き換える。

これらの操作には通常、それぞれコスト1が割り当てられます（コストが異なるバリエーションも存在しますが、基本は1です）。編集距離は、これらの操作の合計コストが最小となる経路を探すことに他なりません。

動的計画法による解決

編集距離の計算が「動的計画法（DP）」の典型問題とされる理由は、計算構造が持つ「最適性の原理」にあります。ある文字列 $A$ の $i$ 番目までのプレフィックスと、文字列 $B$ の $j$ 番目までのプレフィックスの間の編集距離を $D(i, j)$ と定義すると、この $D(i, j)$ を求めるためには、それ以前の小さな部分問題の解（$D(i-1, j)$、$D(i, j-1)$、$D(i-1, j-1)$）を利用できるのです。

具体的には、$m \times n$ の二次元配列（DPテーブル）を作成し、以下のような漸化式を用いてテーブルを埋めていきます。

$$
D(i, j) = \min \begin{cases}
D(i-1, j) + 1 & \text{(削除)} \
D(i, j-1) + 1 & \text{(挿入)} \
D(i-1, j-1) + \text{cost}(A[i], B[j]) & \text{(置換または一致)}
\end{cases}
$$

ここで、$\text{cost}(A[i], B[j])$ は、文字 $A[i]$ と $B[j]$ が一致すれば 0、一致しなければ 1 となります。

このDPテーブルの計算は、左上から右下へと順に進められます。一度計算された部分問題の解 $D(i, j)$ はテーブルに格納され、後の計算で何度も再利用されます。もしDPを使わずに総当たりで編集経路を探そうとすると、計算量が爆発的に増大してしまいますが、DPを用いることで、計算量は文字列の長さ $m$ と $n$ に対して $O(mn)$ の多項式時間で収まります。

この $O(mn)$ という計算量は、「アルゴリズムと計算量」の観点から見ても非常に効率的であり、実用的な時間で解が得られることを示しています。このように、複雑に見える問題が、シンプルな漸化式とテーブル構造によって効率的に解けるという点が、編集距離が動的計画法の「典型問題」として頻繁に取り上げられるゆえんなのです。DPの美しさと強力さを実感できる、本当に素晴らしいアルゴリズムだと思います。

具体例・活用シーン

編集距離の概念は、私たちが日常的に利用する多くのITシステムや、高度な科学技術の分野で幅広く活用されています。

活用シーン

スペルチェック・誤字訂正システム:
ユーザーが「アルゴリズム」と入力すべきところを「アルゴリズ」と誤入力した場合、システムは辞書内の単語と入力された文字列との編集距離を計算します。距離が最小（この例では挿入操作1回）となる単語を候補として提示することで、迅速な訂正を可能にしています。
遺伝子解析（バイオインフォマティクス）:
DNAやタンパク質の配列を比較し、その類似性や進化的な隔たりを評価する際に編集距離が応用されます。遺伝子の挿入、欠失、変異（置換）といった生物学的な現象が、そのまま編集操作に対応するため、配列アライメントの基礎技術として非常に重要です。
あいまい検索（Fuzzy Search）:
データベース検索において、完全一致しなくても「似た」結果を返したい場合に利用されます。例えば、顧客名簿で「佐藤」を探す際に「佐籐」（異体字）や「サトウ」といった表記のゆれを許容するために編集距離が使われます。

例え話：最短経路を探す旅行者

編集距離の計算を理解するための比喩として、「迷路の最短経路を探す旅行者」を考えてみましょう。

旅行者（DPアルゴリズム）は、ある都市 $S_1$ から別の都市 $S_2$ へ移動しようとしています。この二つの都市は、それぞれ文字列 $S_1$ と $S_2$ に対応しており、各文字は道の途中のチェックポイントです。

旅行者は、チェックポイントを一つずつ進む際に、以下の三つの行動を選べます。

挿入（回り道）: $S_1$ にはないチェックポイントを通過する（コスト1）。
削除（スキップ）: $S_1$ のチェックポイントを一つ無視して進む（コスト1）。
置換（乗り換え）: $S_1$ のチェックポイントから $S_2$ のチェックポイントへ強制的に移動する（文字が異なればコスト1、同じならコスト0）。

旅行者の目的は、最終的な目的地 $S_2$ にたどり着くまでの総コスト（編集操作の回数）を最小にすることです。

DPテーブルは、この旅行者が「ここまで進んだ時の最小コスト」を記録する地図のようなものです。旅行者は、現在の位置 $(i, j)$ に到達するために、直前の三つの地点 $(i-1, j)$、$(i, j-1)$、$(i-1, j-1)$ のうち、どこから来たのが一番安上がりだったかを毎回比較し、その最小値を記録します。この最小値を順次記録していくプロセスこそが、動的計画法による編集距離の計算そのものなのです。

資格試験向けチェックポイント

編集距離は、応用情報技術者試験や高度試験で頻出する、動的計画法の代表例です。ITパスポート試験では直接的な計算は出ませんが、概念理解が求められます。

| 資格レベル | 出題傾向と対策 |
| :— | :— |
| ITパスポート/基本情報技術者試験 | 概念理解と分類が中心です。「編集距離とは何か？」「どのような目的に使われるか（類似度判定）」「動的計画法（DP）の適用例である」という基本的な知識を確認しましょう。具体的な計算手順よりも、DPの応用問題として認識しているかが重要です。 |
| 応用情報技術者試験 | 計算手順と漸化式の理解が求められます。簡単な文字列ペア（例：「CAT」と「COT」）を与えられ、レーベンシュタイン距離を実際に計算させる問題が出題されることがあります。DPテーブルの初期化（$D(i, 0)=i$、$D(0, j)=j$）と、最小値を選ぶ漸化式の構造を正確に覚えておく必要があります。 |
| 高度試験（アルゴリズム分野） | 計算量と応用が問われます。編集距離のアルゴリズムが $O(mn)$ の計算量を持つこと、および、コスト構造を変える（例えば、挿入と削除のコストを高くする）といった応用的なバリエーションに対応できる柔軟性が必要です。また、DPの考え方を用いて、なぜ再帰的なアプローチでは効率が悪いのか（重複計算が発生するため）を説明できることが求められます。 |