Damerau-Levenshtein 距離計算ツール｜転置を 1 編集で数えるタイプミス距離

2 つの文字列を入力すると、Damerau-Levenshtein 距離・類似度（%）・正規化値を返す計算ツール。挿入・削除・置換に加えて「隣接 2 文字の入れ替え（転置）」も 1 編集として数え、4 操作の内訳まで分解して表示する。

💡 このツールについて

「recieve」と「receive」、「teh」と「the」のような i と e、h と e の打ち間違いは、隣り合う 2 文字を入れ替えただけの典型的なタイプミスだ。ところが通常の Levenshtein 距離では、この入れ替えを「削除 1 回 + 挿入 1 回」または「置換 2 回」として距離 2 と数えてしまい、実際の打ち間違いの「近さ」を過大評価する。

Damerau-Levenshtein 距離は、この隣接スワップを 1 回の操作として扱う。だからキーボード入力のタイプミスや OCR 誤読のような「人が起こしやすい誤り」に対して、より直感に合う距離を返す。このツールは距離だけでなく、その距離が挿入・削除・置換・転置の何回ずつで構成されているかをカードで個別表示するため、2 つの文字列がどこでどうずれたのかを目で追える。fuzzy search のしきい値設計やスペルチェッカの候補絞り込みを、手元のデータで実測しながら決められる。

🧐 よくある質問

Levenshtein 距離と何が違いますか？ 扱う操作の種類が違います。Levenshtein は挿入・削除・置換の 3 種類だけを数えます。Damerau-Levenshtein はこれに「隣接する 2 文字の入れ替え（転置）」を 1 操作として加えます。「ab」を「ba」にする場合、Levenshtein では距離 2、Damerau-Levenshtein では距離 1 になります。

OSA 版とは何ですか？ このツールは Optimal String Alignment（OSA）版を使っています。同じ部分文字列を複数回編集しない、という制約付きの Damerau-Levenshtein です。実装が軽く実用上ほぼ同じ結果になるため広く使われますが、まれに本来の Damerau-Levenshtein より距離が大きく出るケースがあります。

類似度と正規化値はどう計算されますか？ 正規化値は「距離 ÷ 2 文字列の長い方の文字数」で、0（完全一致）から 1（全く別物）の範囲を取ります。類似度はその裏返しで (1 − 正規化値) × 100 を % 表示したものです。長さの違う文字列どうしを公平に比べるための値です。

日本語や絵文字も比較できますか？ できます。比較は文字単位（コードポイント単位）で行うため、ひらがな・漢字も 1 文字として数えます。ただしサロゲートペアで表現される一部の絵文字は 2 単位として扱われる点に注意してください。

入力に上限はありますか？ 各入力欄は最大 2000 文字までです。距離計算は文字数の積に比例する処理のため、長文どうしの比較は短い単語の比較より時間がかかります。

📚 編集距離まわりの豆知識

Damerau-Levenshtein 距離は、1964 年に Frederick Damerau が「人間のタイプミスの大半は 1 文字の挿入・削除・置換か、隣接 2 文字の入れ替えのいずれかである」と報告したことに由来する。この知見はスペルチェッカや fuzzy search の基礎となり、現在も検索エンジンの「もしかして」候補や入力補正で使われている。実務では距離をそのまま使うより、文字列の長さで割った正規化値やしきい値と組み合わせるのが定石で、短い人名なら距離 1〜2 まで、長い文章なら正規化値 0.1 以下を「ほぼ同一」とみなすなど、対象データごとにこのツールで実測して基準を決めると誤判定が減る。