Skip to main content
タグを編集; タイトルを編集
リンク
user32568
user32568

レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して

タグを編集
リンク
user32568
user32568
ソース リンク
user32568
user32568

レーベンシュタイン距離(編集距離)の出力とグラフにおける最短経路に関して

レーベンシュタイン距離(編集距離)を計算して、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))