目前我試圖想出一個有效的解決問題的方法如下配方：查找最近的字符串，一對詞庫
給定的輸入字符串s和固定詞彙找到一個字符串W1 || w2（||表示級聯，w1和w2是詞典中的單詞），與s的距離最遠。
明顯天真的解決方案是：
for word1 in lexicon:
for word2 in lexicon:
if lev_dist(word1 + word2) < lev_dist(lowest):
lowest = word1 + word2
我敢肯定，必須有這個問題更好的解決方案。誰能提供任何見解？
通過在單個字符串的成本中加入下限，您可能會做得更好一些。
看着http://en.wikipedia.org/wiki/Levenshtein_distance中的算法，在你計算d [i，j]的時候，你知道你正在添加的貢獻依賴於s [i]和t [j]，其中s和t是要比較的字符串，因此可以使更改/刪除/插入的成本取決於兩個字符串內的操作位置。
這意味着您可以使用成本函數計算abcXXX和abcdef之間的距離，其中標記爲XXX的字符的操作是空閒的。這允許您計算將abcXXX轉換爲abcdef的成本，如果字符串XXX實際上是可能的最有利的字符串。
因此，對於詞典中的每個單詞w1，計算w1XXX與目標字符串以及XXXw1與目標字符串之間的距離。製作詞典的兩個副本，按w1XXX距離和XXXw1距離排序。現在按照左手和右手成本之和的順序嘗試所有對，這對成本的下限是成對的。跟蹤到目前爲止的最佳答案。當最佳答案至少與你遇到的下一個下限成本一樣好時，你知道任何你可以嘗試的東西都可以改善這個最佳答案，所以你可以停下來。
我假設你想爲同一個詞典做很多次。例如，你有一個拼寫錯誤的單詞，並且懷疑它是由於它們之間缺少空格造成的。
您肯定需要的第一件事就是估計字符串「親密度」的方法。我喜歡規範化技術。例如，用等價類中的代表替換每個字母。 （也許M和N都是M，因爲它們聽起來很相似，也許PH - > F出於類似的原因。）
現在，你會希望你的規範化詞典既可以前後輸入一個特里或類似的結構體。
現在，搜索您的針向前和向後，但跟蹤兩個方向的中間結果。換句話說，在搜索字符串中的每個位置，跟蹤在該位置已經選擇的候選trie節點的列表。
現在，比較中間結果的向前看和向後看的數組，尋找看起來像是單詞之間良好連接點的位置。您也可以逐個檢查連接點。 （換句話說，你已經找到了第一個單詞的結尾和第二個單詞的開頭。）
如果你這樣做，那麼你已經找到了你的單詞對。
如果您在同一個詞典上運行大量查詢，並希望改善查詢時間，但可以花費一些時間進行預處理，則可以創建包含w1 ||形式的所有可能詞的trie。 W2。然後你可以使用這裏描述的算法：Fast and Easy Levenshtein distance using a Trie找到你需要的任何單詞的答案。
該算法所做的工作基本上是步行樹的節點並跟蹤當前最小值。然後，如果最終出現在某個節點中，Levenshtein距離（從根節點到當前節點以及輸入字符串s）的距離已經大於迄今爲止取得的最小值，則可以修剪以此節點爲根的整個子樹，因爲它不能產生答案。
在測試中使用英語單詞和隨機查詢詞的字典時，根據您在其上運行的查詢類型的不同，它的測試速度比測試字典中每個單詞的常規方法快30到300倍。