レーベンシュタイン距離(編集距離)を計算して、2単語間の最小編集コストを求めようとしています。
以下のように、python-Levenshteinというライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。
「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、レーベンシュタイン距離(編集距離)のアルゴリズムに入れると確かに、最小値は3です。
しかし、グラフで左下をスタート、右上をゴールとして斜線はコスト0、横・縦はコスト1とすると最短距離(赤線のコスト合計)は「5」となり、グラフ上で「3」はどのように求まるのか、プログラムとのちがいは何なのかわからない状態です。
プログラム結果
$ python edit_graph.py
3
実行したコード
#!/usr/bin/env python
# coding: utf8
import Levenshtein
text1 = 'kitten'
text2 = 'sitting'
print (Levenshtein.distance(text1, text2))