レーベンシュタイン距離 (編集距離) とは、一方の文字列を他方の文字列に変換するために必要な、文字の挿入・削除・置換の最小操作回数を表す指標です。1965 年にロシアの数学者ウラジーミル・レーベンシュタインが提唱しました。2 つの文字列がどれだけ「似ているか」を定量的に測定する手法として、情報科学の幅広い分野で活用されています。

具体例として、「kitten」と「sitting」のレーベンシュタイン距離は 3 です。k を s に置換、e を i に置換、末尾に g を挿入という 3 回の操作で変換できます。距離が 0 であれば 2 つの文字列は完全に一致し、距離が大きいほど文字列間の差異が大きいことを意味します。文字列アルゴリズムの書籍で計算方法を詳しく学べます。

計算には動的計画法 (DP) を使用します。2 つの文字列の長さを m と n とすると、(m+1) x (n+1) の行列を構築し、各セルに部分文字列間の最小編集距離を記録していきます。時間計算量は O(mn)、空間計算量も O(mn) ですが、直前の行だけを保持する最適化により空間計算量を O(min(m,n)) に削減できます。

レーベンシュタイン距離の代表的な応用例はスペルチェッカーです。ユーザーが入力した単語が辞書に存在しない場合、辞書内の全単語との編集距離を計算し、距離が小さい単語を修正候補として提示します。Google 検索の「もしかして」機能もこの原理に基づいています。あいまい検索 (ファジーマッチング) でも、完全一致ではなく一定の編集距離以内の結果を返すことで、タイプミスに対応した検索を実現しています。

バイオインフォマティクスの分野では、DNA やタンパク質の配列比較にレーベンシュタイン距離の変種が使われています。生物学的な配列比較では挿入・削除・置換のコストが均一ではないため、操作ごとに異なる重みを設定できる重み付き編集距離や、ギャップペナルティを導入した Needleman-Wunsch アルゴリズムなどが発展しました。自然言語処理基礎の書籍も参考になります。

類似の指標として、ハミング距離 (同じ長さの文字列間で異なる位置の数)、ダメラウ-レーベンシュタイン距離 (隣接文字の転置も 1 操作として扱う)、ジャロ-ウィンクラー距離 (先頭部分の一致を重視する) などがあります。用途に応じて適切な距離指標を選択することが重要です。

文字数カウントの観点では、レーベンシュタイン距離は 2 つのテキストの類似度を文字単位で定量化する基本的な手法です。テキストの差分検出、バージョン管理、盗用検出、機械翻訳の品質評価 (TER: Translation Edit Rate) など、文字列の比較が必要なあらゆる場面で活用されています。大規模なデータセットでは計算コストが課題となるため、BK 木やトライ木を使った効率的な近似検索手法も開発されています。