【へんしゅうきょり】
編集距離 とは？
💡 何回直せば同じになる？文字列の「似てる度」を数値化
📌 このページのポイント
ひよこ 編集距離って何を測るものなの？
ペンギン先生 2つの文字列がどれくらい違うかを数値で表すものだよ。「kitten」を「sitting」に変えるには最低3回の操作が必要だから、編集距離は3になるんだ。
ひよこ 操作って具体的には何をするの？
ペンギン先生 文字の挿入、削除、置換の3種類だよ。kittenをsittingにするには、kをsに置換、eをiに置換、末尾にgを挿入の3操作だね。
ひよこ どうやって最小回数を計算するのかな？
ペンギン先生 動的計画法を使うんだ。2つの文字列の長さm×nの表を作って、左上から順番に最小操作数を埋めていく。右下のマスに最終的な編集距離が入るよ。
ひよこ どんなところで使われてるの？
まとめ：ざっくりこれだけ覚えればOK！
「編集距離」って出てきたら「文字列を直す最小手数で測る似てる度」と思えればだいたいOK！
📖 おまけ：英語の意味
「Edit Distance / Levenshtein Distance」 ＝ 編集距離 / レーベンシュタイン距離
💬 ロシアの数学者ウラジーミル・レーベンシュタインが1965年に提案したからこの名前なんだよ