56175


[レーベンシュタイン距離(編集距離)](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)を計算して、２単語間の最小編集コストを求めようとしています。  
以下のように、[python-Levenshtein](https://pypi.org/project/python-
Levenshtein/)というライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。

「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、[レーベンシュタイン距離(編集距離)](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)のアルゴリズムに入れると確かに、最小値は3です。

しかし、グラフで左下をスタート、右上をゴールとして斜線はコスト0、横・縦はコスト1とすると最短距離(赤線のコスト合計)は「5」となり、グラフ上で「3」はどのように求まるのか、プログラムとのちがいは何なのかわからない状態です。

グラフ  
[![画像の説明をここに入力](https://i.stack.imgur.com/OoC2K.png)](https://i.stack.imgur.com/OoC2K.png)

プログラム結果

[code]

    $ python edit_graph.py
    3
    
[/code]

実行したコード

[code]

    #!/usr/bin/env python
    # coding: utf8
    
    import Levenshtein
    
    text1 = 'kitten'
    text2 = 'sitting'
    
    print (Levenshtein.distance(text1, text2))
    
[/code]


CC BY-SA 4.0
2019-06-28T06:23:59.100
56174
2019-06-29T11:55:53.360
2019-06-29T11:55:53.360
question
python python3 アルゴリズム データ構造 グラフ理論
レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して


レーベンシュタイン距離は各編集操作それぞれに別々のコストを割り当てることが可能です。ライブラリが出力したものは、挿入・削除・置換にコスト1を割り当てた場合のレーベンシュタイン距離だと思われます。グラフで求めているものは、挿入・削除にコスト1、置換にコスト2が割り振った場合(あるいは置換操作がなく、削除と挿入にした場合)のレーベンシュタイン距離となります。


CC BY-SA 4.0
2019-06-28T06:48:38.163
56175
2019-06-28T06:48:38.163
27410
56174
answer