performance - 使用通配符进行单词查找的高效数据结构

Question

我需要将一系列用户输入的单词与大型单词词典进行匹配(以确保输入的值存在)。

所以如果用户输入:

"orange" it should match an entry "orange' in the dictionary.

现在要注意的是，用户还可以输入通配符或一系列通配符，例如 say

"or__ge" which would also match "orange"

关键要求是:

* this should be as fast as possible.

* use the smallest amount of memory to achieve it.  

如果单词列表很小，我可以使用包含所有单词的字符串并使用正则表达式。

但是鉴于单词列表可能包含数十万个条目，我认为这行不通。

那么某种“树”是解决这个问题的方法吗...？

对此有任何想法或建议，我们将不胜感激!

提前致谢，马特

Answer 1

按照 Appel and Jacobsen's paper on the World's Fastest Scrabble Program 中的描述，将您的单词列表放入 DAWG(有向无环词图)中(free copy 在哥伦比亚)。对于您的搜索，您将遍历此图并维护一组指针:在一个字母上，您确定性地过渡到具有该字母的 child ；在通配符上，您将所有 child 添加到集合中。

效率将与 Thompson 对 grep 的 NFA 解释大致相同(它们是相同的算法)。 DAWG 结构非常节省空间——远远超过仅存储单词本身。而且易于实现。

最坏情况下的代价是字母表的大小(26？)乘以通配符的数量。但是除非您的查询以 N 个通配符开始，否则简单的从左到右搜索在实践中会很有效。我建议禁止查询以过多的通配符开头，或者创建多个 dawgs，例如 dawg 表示镜像，dawg 表示向左旋转三个字符，等等。

匹配任意序列的通配符，例如，______ 总是很昂贵，因为有很多组合解决方案。 dawg 将很快枚举所有解决方案。