編集距離（レーベンシュタイン距離）の求め方 - 具体例で学ぶ数学

編集距離とは 「すうがく」という単語を最低何回「編集」すれば「すがた」という単語になるでしょうか？ ただし「編集」とは、 一文字挿入、一文字削除、一文字置換 のいずれかの操作のこととしましょう。 例えば、 「すうがく」の「う」を削除 →「すがく」の「く」を「た」に置換 →「すがた」 となり、「すうがく」から「すがた」へは編集２回で行けることになります。（編集１回では行けません） このように、必要な「編集」の最低回数のことを編集距離と言います。 つまり「すうがく」と「すがた」の編集距離は $2$ です。 「編集」で許す操作は、挿入または削除または置換としましたが、置換を許さないなど、他にもバリエーションがあります。 このように「編集」の定義はいろいろありますが、挿入または削除または置換という「編集」による編集距離を、特にレーベンシュタイン距離と言います。 参考：Levenshtein dis