假设我有一个单词词典，{'cat', 'cot', 'catalyst'} 和一个字符相似度关系 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”，算法应该报告以下匹配：
('cot', 0)
('cat', 0)
('catalyst', 0)
其中数字是找到的匹配的从 0 开始的起始索引。我已经尝试过Aho-Corasick 算法，虽然它非常适合精确匹配，并且在一个字符的“相似”字符数量相对较少的情况下，它的性能会随着我们增加一个字符的相似字符数量而呈指数下降。谁能指出我这样做的更好方法？模糊性是绝对必要的，它必须考虑到字符的相似性（即，不要盲目地仅依赖于编辑距离）。