如何模糊搜索词典单词？

假设我有字的字典，{“猫”，“担架床”，“催化剂”}，以及字符相似关系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'，算法应报告下列匹配：

3210

其中数字是找到的匹配的基于0的起始索引。我已经尝试过Aho-Corasick algorithm，虽然它对于精确匹配非常有用，并且在字符的“相似”字符数量相对较少的情况下，它的性能会呈指数增长，因为我们会增加字符的相似字符数。任何人都可以指出我更好的方式吗？模糊性是绝对必要的，它必须考虑到字符相似性（即不要盲目依赖编辑距离）。

来源

2013-05-02 yati sagade

所以基本上，你想要某种最小编辑距离，考虑到某些字符（如字符并拢键盘上）更有可能被交换？我的直觉告诉我你将在StackOverflow上得到更好的回应。 – acattle 2013-05-02 09:37:11

正确！类似人物的概念可能不同（例如，当你对某些东西进行OCR时，更可能被误解为't'或'i'而不是被误读为'a'）好吧，以及 – 2013-05-02 09:42:20

可能的重复[如何模糊搜索词典词？]（http://stackoverflow.com/questions/16333766/how-to-fuzzily-search-for-a-dictionary-word）你显然张贴在两个SO和语言学。堆栈交换。关于后者的问题随后在此迁移。 – jogojapan 2013-05-08 09:10:08

levenshtein距离与您正在寻找的相似，但可能不如细粒度。不过，我相信你可以重新实现该算法的更多控制版本。

http://en.wikipedia.org/wiki/Levenshtein_distance

来源

2013-05-02 13:19:58 beiller

这是一个开始，但问题是，对于一个巨大的字典，如何在查询中搜索字典*子字符串*？ Levenshtein距离计算算法可以修改以适应：http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/但是，它只给出匹配子字符串的最小Levenshtein距离 - 没有给出匹配的位置。我认为我很接近，如果在这里有足够的头脑风暴，我们可以想出一些简洁的东西。 – 2013-05-02 17:43:36

如何模糊搜索词典单词？

回答

相关问题