反向Levenshtein距離

Question

在levenshtein距離你問這個問題，考慮到這兩個字符串，他們的levenshtein距離是多少。你將如何去採取一個字符串和levenshtein距離，併產生在levenshtein距離內的所有字符串。 （這也將採取一個字符集）。所以如果我傳入一個字符串x和距離d。那麼它會給我所有的編輯距離內的字符串，包括d-1和d-2 .... d-n; （n < d）。

預期的功能：

>>> getWithinDistance('apple',2,{'a','b',' '}) 
['applea','appleb','appel','app le'...] 

請注意，該程序能夠產生app le作爲空間包括在字符集。

Answer 1

有一個這樣的數據結構，稱爲Levenshtein automaton。您可以從一組字符串（可能只有一個成員）和一個固定距離構建它，然後您可以查詢它存儲的任何字符串的最遠距離爲k的所有字符串。 Python實現將在here中討論。

或者，您可以使用此類字符串的回溯進行深度限制搜索。