問題 No.3247
2つの文字列の間で、一方を他方に変換するために必要な「文字の挿入」「文字の削除」「文字の置換」という基本操作の最小回数を表す指標はどれか。
【正解の解説】
エディット距離
例えば、タイポした「apple」を「apply」にするには、最後の「e」を「y」に1回置換するだけなので距離は1です。これは、文章の校正やスペルチェックで「どれだけ手直しが必要か」を測るコスト感覚に似ており、プログラミングの世界でも文字の似ている度合いを測るために広く使われています。
スポンサーリンク
【その他の選択肢の解説】
ハミング距離
ハミング距離は文字の長さが変わらない同じ桁数の比較（「1011」と「1111」など）でしか使えません。エディット距離のように「途中に文字を挿入して文字数を合わせる」ことができない点が決定的な違いであり、文字数がズレる一般的な文字列比較ではエラーになってしまいます。
ユークリッド距離
ユークリッド距離は、グラフ上の座標「(1, 2)と(4, 6)」のような数値データを計算するためのものであり、文字列の変換回数を数えるエディット距離とはまったく異なる分野の概念です。初学者が「距離という言葉のイメージ」から混同しやすい典型的な出題者の罠です。
レーベンシュタイン距離
実はレーベンシュタイン距離はエディット距離の最も有名な別名であり、文字列の変換に「挿入・削除・置換」の3つを認める定義そのものです。本問では「指標という総称（概念）」を聞いているため、より上位の用語であるエディット距離が正解となります。