如何模糊搜索詞典單詞？

假設我有字的字典，{「貓」，「擔架牀」，「催化劑」}，以及字符相似關係F（X，Y）如何模糊搜索詞典單詞？

f(x, y) = 1, if x and y are similar 
     = 0, otherwise

這些「相似性」可以通過指定程序員。這樣，比方說，

f('t', 'l') = 1 
f('a', 'o') = 1 
f('f', 't') = 1

但是，

f('a', 'z') = 0 
etc.

現在，如果我們有一個查詢 'cofatyst'，算法應報告下列匹配：

3210

其中數字是找到的匹配的基於0的起始索引。我已經嘗試過Aho-Corasick algorithm，雖然它對於精確匹配非常有用，並且在字符的「相似」字符數量相對較少的情況下，它的性能會呈指數增長，因爲我們會增加字符的相似字符數。任何人都可以指出我更好的方式嗎？模糊性是絕對必要的，它必須考慮到字符相似性（即不要盲目依賴編輯距離）。

來源

2013-05-02 yati sagade

所以基本上，你想要某種最小編輯距離，考慮到某些字符（如字符併攏鍵盤上）更有可能被交換？我的直覺告訴我你將在StackOverflow上得到更好的迴應。 – acattle 2013-05-02 09:37:11

正確！類似人物的概念可能不同（例如，當你對某些東西進行OCR時，更可能被誤解爲't'或'i'而不是被誤讀爲'a'）好吧，以及 – 2013-05-02 09:42:20

可能的重複[如何模糊搜索詞典詞？]（http://stackoverflow.com/questions/16333766/how-to-fuzzily-search-for-a-dictionary-word）你顯然張貼在兩個SO和語言學。堆棧交換。關於後者的問題隨後在此遷移。 – jogojapan 2013-05-08 09:10:08

levenshtein距離與您正在尋找的相似，但可能不如細粒度。不過，我相信你可以重新實現該算法的更多控制版本。

http://en.wikipedia.org/wiki/Levenshtein_distance

來源

2013-05-02 13:19:58 beiller

這是一個開始，但問題是，對於一個巨大的字典，如何在查詢中搜索字典*子字符串*？ Levenshtein距離計算算法可以修改以適應：http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/但是，它只給出匹配子字符串的最小Levenshtein距離 - 沒有給出匹配的位置。我認爲我很接近，如果在這裏有足夠的頭腦風暴，我們可以想出一些簡潔的東西。 – 2013-05-02 17:43:36

如何模糊搜索詞典單詞？

回答

相關問題