algorithm - 如何模糊搜索字典单词？

Question

我在这里阅读了很多讨论基于编辑距离的模糊搜索的主题，Elasticsearch/Lucene 等工具提供了开箱即用的功能，但我的问题有点不同。假设我有一个单词字典，{'cat', 'cot', 'catalyst'}，和一个字符相似度关系 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”，算法应该报告以下匹配项:

('cot', 0)
('cat', 0)
('catalyst', 0)

其中数字是找到的匹配项的从 0 开始的索引。我试过 Aho-Corasick algorithm ，虽然它非常适合精确匹配，但在一个字符的“相似”字符数量相对较少的情况下，它的性能会随着我们增加一个字符的相似字符数量而呈指数下降。谁能指出我这样做的更好方法？模糊性是绝对必要的，它必须考虑字符的相似性(即，不要盲目地依赖于编辑距离)。

需要注意的是，在野外，字典会非常大。

Answer 1

我可能会尝试使用余弦相似度，使用每个字符的位置作为特征，并根据您的字符关系使用匹配函数映射特征之间的乘积。

不是很具体的建议，我知道，但我希望它能帮到你。

已编辑:扩展答案。

利用余弦相似度，您将计算两个向量的相似程度。在您的情况下，规范化可能没有意义。所以，我要做的是一些非常简单的事情(我可能把问题简单化了):首先，将 CxC 的矩阵视为一个依赖矩阵，其中两个字符相关的概率(例如，P('t' | 'l' ) = 1).这也将允许你有部分依赖来区分完全匹配和部分匹配。在此之后，我将为每个位置计算每个单词的字母不相同的概率(使用 P(t_i, t_j) 的补码)，然后您可以使用总和来汇总结果。

它将计算特定单词对不同的术语数，并允许您定义部分依赖关系。此外，实现非常简单，应该可以很好地扩展。这就是为什么我不确定我是否误解了你的问题。