1 定義
編集距離は、二つの文字列を互いに変換する際に必要な最小操作回数を表す尺度である。ここでいう操作は通常、文字の挿入、削除、置換の三つを基本とし、各操作に同じ重みを与えるか、あるいは別々のコストを設定して扱う。文字列同士の近さを数値で示せるため、比較や検索の基礎概念として用いられる。
1.1 基本的な考え方
この距離は、単に見た目が似ているかどうかではなく、実際にどれだけ手順を踏めば一方を他方へ移せるかに着目する。たとえば、短い語の綴りが少し違う場合でも、少数の操作で一致させられるなら距離は小さいと評価される。逆に、共通部分が少ない文字列では、必要な操作数が増える。
1.2 文字列変換の操作
編集距離の定義は、許される操作の選び方に依存する。もっとも基本的な枠組みでは、既存の文字を消したり、新しい文字を加えたり、別の文字へ置き換えたりすることで変換を進める。これらの操作を組み合わせた最短経路が距離となる。
1.2.1 挿入
挿入は、文字列の任意の位置に一文字を追加する操作である。長さを一つ増やすため、欠けている要素を補う役割を担う。比較対象の片方にしか存在しない文字を取り込むときに使われる。
1.2.2 削除
削除は、文字列中の一文字を取り除く操作である。余分な文字を消して、もう一方の文字列に近づける際に用いられる。挿入と対をなす基本操作とみなされることが多い。
1.2.3 置換
置換は、ある文字を別の文字へ入れ替える操作である。長さは変えずに内容だけを修正できるため、誤入力や表記ゆれの修正に適している。挿入と削除を組み合わせるより少ない回数で済む場合もある。
1.3 距離としての性質
編集距離は、適切な条件のもとで距離関数として扱える。つまり、値が負にならず、同じ文字列同士ではゼロとなり、順序を入れ替えても値は変わらず、三つの文字列の関係にも整合的である。こうした性質により、抽象的な距離空間の例としても重要である。
2 種類
編集距離には複数の定義があり、許される操作やコストの設定によって名称が変わる。基本形を拡張して、実際の用途に合わせた柔軟な尺度を作ることができる。
2.1 レーベンシュタイン距離
レーベンシュタイン距離は、最も広く知られた編集距離の一つである。挿入、削除、置換を用いて一方の文字列を他方へ変える最小回数を測る。一般に「編集距離」と言う場合、この形式を指すことが多い。
2.1.1 標準的な編集距離
標準形では、各操作のコストを一律に 1 とする。これにより、どの変換も同じ重みで数えられ、計算や解釈が単純になる。文字列比較の入門的なモデルとして扱いやすい。
2.1.2 重み付き編集距離
重み付き編集距離では、操作ごとに異なるコストを割り当てる。たとえば、置換を高く評価したり、特定の文字の入れ替えを安く扱ったりできる。実際の誤り傾向や分野特有の事情を反映しやすい。
2.2 ダメラウ距離
ダメラウ距離は、通常の編集操作に加えて、隣り合う二文字の交換を認める変種である。入力ミスの中でも、文字の順序が入れ替わる現象を自然に表現できるため、綴り修正などで有用である。
2.2.1 隣接文字の交換
この操作では、隣接する二つの文字を入れ替えて一度の変換とみなす。たとえば、打ち間違いで順序が逆になった場合に対応しやすい。レーベンシュタイン距離よりも現実の誤りに近い場面がある。
2.3 その他の拡張
編集距離は、単純な文字単位の比較にとどまらず、より長い単位や特定の制約を導入して拡張される。対象の構造や用途に応じて、部分列や制限条件を組み込んだ変種が考案されている。
2.3.1 部分列に関する変種
この種の変種では、全文一致ではなく、部分列や共通の連続区間に注目することがある。長い文章や系列の中から対応する箇所を探す場面で役立つ。比較対象の全体構造を緩やかに扱えるのが特徴である。
2.3.2 制約付き編集距離
制約付き編集距離は、利用できる操作の順序や回数、対象範囲に条件を設けたものを指す。現実の処理では、無制限に操作できない場合があるため、こうした条件が意味を持つ。計算問題としては難度が上がることもある。
3 計算法
編集距離の計算には、効率よく最小値を求めるための標準的な方法がある。代表的なのは動的計画法で、部分問題の結果を順に利用しながら全体の解を構成する。
3.1 動的計画法
動的計画法では、文字列の先頭から順に部分的な対応を考え、小さな比較結果を積み上げる。各位置までの最小コストを表に記録し、その値を使って次の状態を更新する。編集距離の代表的な解法として広く知られている。
3.1.1 表の構成
通常は、二つの文字列の長さに対応する二次元表を用意する。表の各セルには、先頭部分どうしを一致させるための最小コストを格納する。行と列を順に埋めていくことで、最終的な距離が得られる。
3.1.2 再帰関係
更新式は、直前の状態から挿入、削除、置換の三方向を比較して決める。対応する文字が同じなら追加コストを抑え、異なるなら置換を考慮する。これにより、局所的な選択から全体最適を導ける。
3.2 計算量
編集距離の計算量は、文字列の長さに強く依存する。基本的な動的計画法は分かりやすい一方で、大規模データでは負荷が問題になることがある。
3.2.1 時間計算量
標準的な方法では、二つの長さをそれぞれ n、m とすると、計算時間は概ね n×m に比例する。すべての部分問題を調べるためである。短い文字列では扱いやすいが、長くなると処理量が増える。
3.2.2 空間計算量
表全体を保持する方式では、必要な記憶領域も n×m となる。ただし、前後の行だけあれば更新できる場合には、使用メモリを減らせる。用途によっては、時間と空間のどちらを優先するかが選択の要点となる。
3.3 高速化手法
実用面では、標準手法をそのまま使うだけでなく、計算範囲を狭めたり、機械語レベルの並列性を活かしたりして高速化する。特に大量の文字列を扱う場合に重要である。
3.3.1 帯域制限
帯域制限では、距離が小さいと見込まれる対角周辺だけを計算対象にする。差が大きすぎる領域を省くことで、不要な処理を減らせる。近い文字列同士の比較では有効性が高い。
3.3.2 ビット演算を用いる方法
ビット演算を利用する手法では、文字集合や状態遷移をビット列で扱い、複数の比較を同時に進める。ハードウェアの並列性を生かしやすく、特定の条件下で大幅な高速化が期待できる。ただし、実装はやや複雑になる。
4 性質と応用
編集距離は理論的性質と実務的用途の両面で価値がある。距離空間の例として数学的に扱えるだけでなく、文字列や系列の近似照合にも応用される。
4.1 距離空間としての性質
適切に定義された編集距離は、距離の公理を満たすため、幾何学的な考え方で分析できる。これにより、索引付けや近傍探索など、距離に基づく手法と結びつく。
4.1.1 非負性
編集距離は、最小操作回数として定義されるため、値が負になることはない。操作の数を数える仕組み自体が、この性質を保証する。最小値がゼロになるのは同一文字列の場合である。
4.1.2 対称性
二つの文字列の役割を入れ替えても、必要な操作数が同じになるよう設計されている。挿入と削除を対応づければ、変換方向が逆でも同じ距離として解釈できる。これが比較の公平性を支える。
4.1.3 三角不等式
三角不等式は、ある文字列から別の文字列へ直接変えるよりも、中間の文字列を経由した方が長くならないことを示す。距離の連結可能性を保証する重要な条件である。複数の比較結果を組み合わせる際の基盤にもなる。
4.2 応用分野
編集距離は、入力修正から生体分子の比較まで、さまざまな場面で利用される。対象は文字列に限られず、符号列や記号系列の照合にも広がっている。
4.2.1 綴り訂正
綴り訂正では、誤記された語と辞書中の候補を比較し、距離の小さいものを提案する。打ち間違いや脱字、余分な文字の混入を検出しやすい。検索エンジンや入力支援でよく使われる。
4.2.2 文書比較
文書比較では、二つのテキストの差分を概観する指標として活用される。完全一致では見落とす微小な変更を捉えやすい。校正、版管理、簡易な差分判定などに向いている。
4.2.3 系列解析
系列解析では、時系列や記号列の近さを測るために編集距離が用いられる。単なる文字の一致ではなく、順序や局所的な変化を考慮できる。異なる長さのデータを比較する場面でも扱いやすい。
4.2.4 生物配列の比較
生物配列の比較では、DNAやタンパク質の配列間で変化の度合いを評価する。変異や挿入、欠失を模したモデルとして機能するため、配列アラインメントの考え方と親和性が高い。近縁関係の推定や解析の補助に使われる。