如何模糊搜索字典單詞？

Question

我已經閱讀了很多討論基於編輯距離的模糊搜索的主題，像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，雖然它對於精確匹配非常有用，並且在一個角色的「相似」字符數量相對較少的情況下，它的性能會隨着我們增加角色類似字符的數量而呈指數級下降。任何人都可以指出我更好的方式嗎？模糊性是絕對必要的，它必須考慮到字符相似性（即不要盲目依賴編輯距離）。

有一點需要注意的是，在野外，字典將會非常大。

Answer 1

我正在使用Fuse JavaScript Library作爲我的一個項目。這是一個適用於JSON數據集的JavaScript文件。這是相當快的。看看它。
它已經實現了一個完整的Bitap算法，利用了谷歌（來自他的網站）的Diff，Match &補丁工具的修改版本。

該代碼很容易理解算法的實現。

Answer 2

我可能會嘗試使用餘弦相似度，使用每個字符的位置作爲要素，並根據您的字符關係使用匹配函數在要素之間映射產品。

不是一個非常具體的建議，我知道，但我希望它可以幫助你。

編輯：擴展答案。

使用餘弦相似度，您將計算兩個向量的相似程度。在你的情況下，標準化可能沒有意義。所以，我要做的事情很簡單（我可能會過分簡化問題）：首先，將CxC的矩陣看作一個與兩個字符相關的概率的依賴矩陣（例如，P（'t'|'l' ）= 1）。這也可以讓你有部分依賴關係來區分完美匹配和部分匹配。在此之後，我將計算每個位置每個單詞的字母不相同的概率（使用P（t_i，t_j）的補數），然後您可以使用總和來彙總結果。

它會計算特定字對的不同項的數量，它允許您定義部分依賴項。此外，實施非常簡單，並且應該很好地擴展。這就是爲什麼我不確定我是否誤解了你的問題。