我已經閱讀了很多討論基於編輯距離的模糊搜索的主題,像Elasticsearch/Lucene這樣的工具提供了開箱即用的功能,但是我的問題有點不同。假設我有字的字典,{「貓」,「擔架牀」,「催化劑」},以及字符相似關係F(X,Y)如何模糊搜索字典單詞?
f(x, y) = 1, if characters 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',該algorit hm應報告以下匹配:
3210其中number是找到的匹配的從0開始的索引。我已經嘗試過Aho-Corasick algorithm,雖然它對於精確匹配非常有用,並且在一個角色的「相似」字符數量相對較少的情況下,它的性能會隨着我們增加角色類似字符的數量而呈指數級下降。任何人都可以指出我更好的方式嗎?模糊性是絕對必要的,它必須考慮到字符相似性(即不要盲目依賴編輯距離)。
有一點需要注意的是,在野外,字典將會非常大。
我玩過它,但我不確定這是如何有助於如果字典是巨大的 - 我仍然必須匹配字典單詞與查詢逐一。 BITAP似乎工作得很好,當你有一些大文本和一個模式從該文本grep。 – 2013-05-03 10:44:24
我用JSON測試了7個屬性和約420行的表。更大的文本grep肯定會提高性能,但即使使用簡單的2字符,性能也令人滿意..這是我的測試完成。希望這些信息有幫助。 – 2013-05-04 06:16:07