用於檢索靠近Levenshtein距離的字符串的數據結構

例如，從英語單詞集開始，是否有一種結構/算法允許使用快速檢索字符串（如「light」和「tight」）的字符串單詞「正確」作爲查詢？也就是說，我想檢索與查詢字符串具有較小Levenshtein距離的字符串。用於檢索靠近Levenshtein距離的字符串的數據結構

2013-02-13 MaiaVictor

我在想最快的方法是預先構建一個可以在O（1）時間索引和訪問的相似性緩存。訣竅是找到添加到緩存的常見拼寫錯誤，這可能會相當大。

我想象谷歌會用各種各樣的統計查詢搜索數據做類似的事情。

2013-02-13 02:17:53 kufudo

好的方法，如果這實際上是拼寫錯誤，不是非常有用，如果它是更多的理論應用Levenshtein距離。 – us2012 2013-02-13 02:19:04

你的意思是什麼？如果這是我想象的內存使用會使它不切實際。 – MaiaVictor 2013-02-13 02:22:26

@ us2012這是目的。 – MaiaVictor 2013-02-13 02:27:21

由於對長度爲n和m的琴絃計算Levenshtein距離爲O(nm)，計算所有Levenshtein距離L(querystring, otherstring)的幼稚方法非常昂貴。

但是，如果您將Levenshtein算法可視化，則它基本上會填充具有編輯距離的n * m表格。但對於以相同的幾個字母（前綴）開頭的單詞，Levenshtein表的前幾行將是相同的。（固定查詢字符串，當然。）

這建議使用trie (also called prefix tree)：讀取查詢字符串，然後建立一個Levenshtein行的樹。之後，您可以輕鬆遍歷它來查找接近查詢字符串的字符串。

（這不意味着你必須建立一個新的查詢字符串的新線索。我不認爲這是對全對距離的同樣耐人尋味的結構。）

我想我最近看到一篇關於這個的文章，它有一個很好的python實現。如果我能找到它，會添加一個鏈接。 編輯：Here it is, on Steve Hanov's blog.

2013-02-13 02:34:22 us2012

這裏的BK-tree數據結構可能是適當的。它旨在有效地支持「查詢單詞中編輯距離小於等於k的所有單詞都是什麼」格式的查詢？它的性能保證相當不錯，而且實現起來並不困難。

希望這會有所幫助！

2013-02-13 09:11:25 templatetypedef

回答