【へんしゅうきょり】
編集距離 とは？
最終更新:
💡 何回編集すれば、同じ文字列になる？
文字列を別の文字列に変えるための、最小の編集コスト。代表的なレーベンシュタイン距離では、1文字の挿入・削除・置換を各1回として数えます。操作の種類や文字の単位によって値が変わり、意味の近さを直接測る指標ではありません。
📌 このページのポイント
ひよこ 編集距離は何を測るの？
ペンギン先生 ひよこ kittenとsittingだと？
ペンギン先生 kをsに置換してsitten、eをiに置換してsittin、末尾にgを挿入してsitting。3回で変えられ、このルールでの最小回数も3だよ。適当に見つけた編集手順の長さが、いつも最小とは限らない点には注意しよう。
ひよこ 最小回数はどう計算する？
ペンギン先生 動的計画法で、先頭からi文字とj文字の間の最小コストを表にする。最後を置換する・片方から削除する・片方へ挿入する場合を比べ、小さい値を選ぶ。空文字も扱うので、長さmとnなら表の境界を含めて(m+1)×(n+1)マスになるんだ。
ひよこ 計算にどれくらいかかる？
ペンギン先生 基本的な表の計算時間はO(mn)、表全体の保存もO(mn)だよ。距離の値だけなら、直前の行を使って表の一部だけを保存できる。具体的な編集手順も取り出したい場合は、経路の保存や復元方法も考える必要がある。
ひよこ 小さいほど意味も似ている？
ペンギン先生 文字の並びがこのルールで近い、という意味だよ。単語の意味が近いとは限らない。スペル修正の候補探しに使えるけれど、候補の頻度や文脈、文字列の長さも重要。1文字違いでも、短い名前と長い文章では受け取り方が変わるね。
ひよこ 文字を入れ替える場合も1回？
ペンギン先生 隣り合う文字の入れ替えを1操作にする方式もあるが、ここでの3操作とは別の定義だよ。操作の重みを変える方式もある。同じ編集距離という名前でも、許す操作とコストを確認しよう。
もっと詳しく知りたい人へ
日本語や絵文字でも、見た目の1文字を数えればよい？
実装が数える単位を確認します。Unicodeのコードポイントと、結合文字や絵文字を含む見た目の1文字は一致しないことがあります。用途に合わせて文字の分割や表記の正規化をそろえないと、意図した距離にならない場合があります。
まとめ：ざっくりこれだけ覚えればOK！
「編集距離」って出てきたら「決めた操作とコストで文字列を変えるための最小値」と思えばだいたいOK！
📖 おまけ：英語の意味
「Edit Distance / Levenshtein Distance」 ＝ 編集距離 / レーベンシュタイン距離
💬 レーベンシュタインは研究者の名前です。NISTの資料は、関連する原論文を1965年、英訳を1966年として挙げています。