レーベンシュタイン距離 (編集距離) とは、一方の文字列を他方の文字列に変換するために必要な、文字の挿入・削除・置換の最小操作回数を表す指標です。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)) に削減できます。時間側は事情が違い、文字の比較しかできない計算モデルでは Ω(mn) の下界が示されているほか、強指数時間仮説を前提とすると準二乗時間 (O(n^2-ε)) では計算できないことが知られています。つまり「もっと速いアルゴリズムを探す」方向には期待できないため、長い文字列や大量の候補を扱うときは計算そのものを速くするのではなく、比較する組み合わせを事前に絞る設計に切り替えるのが定石です。

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

実装で最初に決めるのは、どこまでの距離を「似ている」とみなすかの閾値です。距離は 2 つの文字数の差の絶対値を下回らないため、長さの差が閾値を超える候補は距離を計算する前に振り落とせます。これが前段の絞り込みとして最も安く効きます。閾値そのものは語の長さと合わせて決めるのが安全です。3 文字の英単語では距離 1 を許すだけで「cat」に対して「cut」「cap」「car」がすべて同じ距離 1 で並び、意味の違う語まで候補に入ります。逆に「サーバ」と「サーバー」、「リポジトリ」と「レポジトリ」のように、距離 1 で拾いたい表記揺れもあります。短い語では 1 に絞り、長い文字列では絶対値ではなく比率 (距離 ÷ 長い側の文字数) で判定し、最終的な並び順は距離だけで決めずに候補語の出現頻度も併せて重み付けする、という組み立てにすると誤った修正候補を抑えられます。

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

類似の指標として、ハミング距離 (同じ長さの文字列間で異なる位置の数)、ダメラウ-レーベンシュタイン距離 (隣接文字の転置も 1 操作として扱う)、ジャロ-ウィンクラー距離 (先頭部分の一致を重視する) などがあります。違いは具体例で見ると分かりやすく、「form」と「from」は隣接する 2 文字が入れ替わっただけのタイプミスですが、レーベンシュタイン距離では置換 2 回として距離 2 と数えられます。ダメラウ-レーベンシュタイン距離なら転置 1 回で距離 1 です。キーボード入力の打ち間違いを拾いたいのか、綴りの近さを測りたいのかで、どちらを使うかが変わります。

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

実装で見落とされやすいのは「1 文字」をどの単位で数えるかです。JavaScript の文字列は UTF-16 のコード単位で添字が付くため、str.length と str[i] で素朴に行列を回すと、サロゲートペアで表される絵文字 1 字の増減が距離 2 として数えられます。実際に「猫🙂」と「猫」を比べると、コード単位では 2、[...str] でコードポイントの配列にしてから比べると 1 になります。正規化の有無も同じくらい効きます。U+30AC で表した「ガ」と、U+30AB (カ) に U+3099 (結合文字の濁点) を続けて表した見た目の同じ文字列は、そのまま比べると距離 2 と出ますが、両方を NFC へそろえてから比べれば 0 です。人が「1 文字だけ違う」と感じる単位で距離を出したいなら、正規化形をそろえ、分割単位をコードポイント (絵文字を 1 字として扱いたいなら書記素クラスタ) に決めるところまでが実装の範囲になります。