我需要将一系列用户输入的单词与大型单词词典进行匹配（以确保输入的值存在）。
因此，如果用户输入：
"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.
如果单词列表的大小很小，我可以使用包含所有单词的字符串并使用正则表达式。
但是考虑到单词列表可能包含成千上万个肠，我认为这是行不通的。
那么某种“树”是实现此目标的方法吗？
任何想法或建议，将不胜感激！
预先感谢，马特
按照Appel和Jacobsen在“世界上最快的拼字游戏计划”中的论文中所述，将单词列表放入DAWG（有向无环单词图）中（哥伦比亚免费提供）。为了进行搜索，您将遍历该图并维护一组指针：在一个字母上，您将确定性地转换为带有该字母的子代；在通配符上，将所有子代添加到集合中。
效率将与Thompson对grep的NFA解释大致相同（它们是相同的算法）。DAWG结构具有 极高的 空间效率-远远不只是存储单词本身。而且很容易实现。
最坏的情况是将字母的大小（26？）提高到通配符数量的乘方。但是，除非您的查询以N个通配符 开头 ，否则简单的从左到右搜索将在实践中很好地工作。我建议禁止查询以太多的通配符开头，或者创建多个dawg，例如，dawg用于镜像，dawg用于向左旋转三个字符，依此类推。
例如，匹配通配符的任意序列______总是很昂贵的，因为组合上有很多解决方案。dawg将很快列举所有解决方案。
______
