Levenshtein Distance, Edit DistanceAlgorithm (アルゴリズム) Dynamic Programming (動的計画法) Levenshtein distance (レーベンシュタイン距離) / Edit Distance (編集距離) [Up] 「ある文字列 s と別の文字列 t がどれだけ似ているか」 を判断したい場合があります。 それを表すのが編集距離 (Edit Distance) という概念です (レーベンシュタイン距離, Levenshtein distance とも言います)。 編集距離が小さいほど「近い」、すなわち「似ている」ということになります。 文字列 s に次の3種類の操作を加えて、文字列 t に変更するにかかる手間が編集距離です。 3種類の操作それぞれにコスト(cost, 手間)が設定されるのが普通です。 置き換え(substitute) ... sの中の1文字を別の1文字で置き換える。 例
