如何模糊搜索字典单词？

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）的补数），然后您可以使用总和来汇总结果。

它会计算特定字对的不同项的数量，它允许您定义部分依赖项。此外，实施非常简单，并且应该很好地扩展。这就是为什么我不确定我是否误解了你的问题。