Swa*_*way 21 algorithm performance memory-management data-structures
我需要将一系列用户输入的单词与一个大的单词词典相匹配(以确保输入的值存在).
因此,如果用户输入:
"orange" it should match an entry "orange' in the dictionary.
现在的问题是用户还可以输入通配符或一系列通配符,比如说
"or__ge" which would also match "orange"
关键要求是:
* this should be as fast as possible.
* use the smallest amount of memory to achieve it.
如果单词列表的大小很小,我可以使用包含所有单词的字符串并使用正则表达式.
但是,鉴于单词列表可能包含数十万个企业,我认为这不会起作用.
那么某种"树"是这样的方式......？
对此有任何想法或建议将完全赞赏!
先谢谢,马特
Nor*_*sey 17
将您的单词列表放在DAWG(有向无环字图)中,如Appel和Jacobsen关于世界上最快拼字游戏程序(哥伦比亚的免费副本)的论文所述.对于你的搜索,你将遍历这个图表,保持一组指针:在一封信上,你向那个字母的孩子做出确定性的过渡; 在通配符上,将所有子项添加到集合中.
效率将与Thompson对grep的NFA解释大致相同(它们是相同的算法).DAWG结构非常节省空间 - 远远超过仅存储单词本身.它很容易实现.
最坏情况下的成本将是字母表的大小(26？)提升到通配符数量的幂.但除非您的查询以N个通配符开头,否则简单的从左到右搜索在实践中将很有效.我建议禁止查询以太多通配符开头,否则创建多个dawgs,例如,dawg用于镜像,dawg用于旋转左三个字符,依此类推.
例如,匹配任意序列的通配符______总是很昂贵,因为存在组合的许多解决方案.dawg将非常快速地列举所有解决方案.