Levenstein-distance-like metric中的最近鄰居搜索

Question

我有一組單詞（'詞典'），並且我必須從字典中找到最接近的單詞，給定一個新單詞。 （我使用'word'作爲關鍵字，因爲它實際上是一個抽象'字母'的可變長度序列）。

我使用Levenstein距離作爲度量的概括 - 我需要概括的原因是我需要交換兩個給定字母的特定「成本」 - 例如，我需要與'a'交換' b'與'c'交換'a'的成本更低。我想我仍然必須說服自己，我的泛化仍然是一個指標。

目前我正在使用樸素的線性搜索，即迭代字典中的所有單詞並跟蹤最小距離，我正在尋找更高效的方法。

我開始閱讀關於最近鄰搜索的方法，但是對於我來說，主要的概念難點是我的'點'（單詞）沒有嵌入到我可以想象的空間中，並且它們不是具有維度的向量等。

考慮到這一點，我想聽聽一些關於尋找哪些算法的建議。

Answer 1

讓我重新表達你的問題，並給你一個可能的答案。沒有看到你的數據集，我不知道哪個對你更好。

您已經有了一個算法，給定兩個單詞，給出它們之間的距離。它是基於Levenstein距離爲這些詞彙之間的路徑，對成本進行一些修改。而且你希望找到與給定單詞最接近的單詞，而不必搜索整個字典。

我會嘗試的最簡單的方法就是從您的單詞開始，搜索所有可能的修改集，直到找到字典中最接近的單詞爲止。你想要一個修改的廣度優先搜索。商店(0, your_word)在某種0​​的唯一入口（堆是很容易實現的），搶在距離一個隨機字典中的詞作爲目前最好的解決方案，那麼只要優先級隊列不爲空：

Take the lowest cost element out. 
If it is more expensive than your best solution: 
    stop, return your best. 
For each possible one step modification of that word: 
    if the new word is in the dictionary and is lower cost than your best: 
     improve best estimate 
    else: 
     store (new_cost, new_word) in the priority queue 

這將導致以原始單詞開始的指數增長搜索集。但是如果字典中有附近的單詞，它應該很快找到。如果你走這條路線，你可能希望在搜索空間上限後放棄。

這可能遠非最佳解決方案，但編程和嘗試不應太難。