すべての部分文字列に対する編集距離を求めるアルゴリズム

Question

2つの文字列sとtが指定されています。私はsの各部分文字列をtに編集距離（Levenshtein距離）で見つける必要があります。実際には、それぞれiの位置をsに知っておく必要があります。位置で開始されたすべての部分文字列の最小編集距離はどれくらいですか？例えば

：

t = "ab"  
s = "sdabcb" 

そして、私のようなものを取得する必要があります：

{2,1,0,2,2}

説明：

1st position: 
distance("ab", "sd") = 4 (2*subst) 
distance("ab", "sda") = 3(2*delete + insert) 
distance("ab", "sdab") = 2 (2 * delete) 
distance("ab", "sdabc") = 3 (3 * delete) 
distance("ab", "sdabcb") = 4 (4 * delete) 
So, minimum is 2 

2nd position: 
distance("ab", "da") = 2 (delete + insert) 
distance("ab", "dab") = 1 (delete) 
distance("ab", "dabc") = 2 (2*delete) 
.... 
So, minimum is 1 

3th position: 
distance("ab", "ab") = 0 
... 
minimum is 0 

などを。

私はもちろん、ブルートフォースアルゴリズムを使用してこのタスクを解決することができます。しかし、より高速なアルゴリズムはありますか？

ありがとうございました。

Answer 1

ワグナー・フィッシャーアルゴリズムは、すべての接頭辞に対して「無料」と答えます。

http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

ワグナーフィッシャー行列の最後の行はtからsの各プレフィックスからの編集距離を含んでいます。

問題の最初の亀裂として、それぞれiを実行して、ワーグナーフィッシャーを実行し、最後の行の最小要素を選択します。

他の誰かがもっと良いアプローチを知っている（または見つけることができる）かどうかを知りたいと思うでしょう。

Answer 2

指定された文字列の部分文字列を見つけることは非常に簡単です。 通常のLevenshteinアルゴリズムを使用し、わずかに変更します。

FIRST： の代わりに0,1,2,3,4,5と行列の最初の行を埋め、... あなたがゼロでそれを完全に埋めます。 （緑の長方形）

秒： 次にアルゴリズムを実行します。

THIRD： の代わりにあなたが最後の行の中で最も小さい値を検索し、それを返し、最後の行の最後のセルを返します。 （赤い長方形）

例： 針： "ABA"、干し草の山： "CのアバのC" - >結果= 1（変換アバ - > ABA）

Iが見つかりました。ここに：http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/

私はそれをテストして動作します。

これは、あなたの質問と同じように、文字を文字ごとにステップするという提案よりもはるかに高速です。行列は一度しか作成しません。