xyz*_*xyz 7 algorithm tree dictionary data-structures
我有一个简单的要求(也许是假设的):
我想存储英文单词字典(n个单词)并给出一个单词(字符长度为m),字典能够判断字词是否存在于字典中.什么是适合的数据结构？
一个平衡的二叉搜索树？在C++ STL关联数据结构中完成,如set,map
要么
字符串上的特里
一些复杂性分析: 在平衡的bst中,时间将是(log n)*m(比较2个字符串需要O(m)个时间字符)
在trie中,如果在每个节点,我们可以在O(1)时间内分支,我们可以找到使用O(m),但假设在每个节点,我们可以在O(1)时间内分支是无效的.在每个节点,最大可能分支将是26.如果我们在节点处想要O(1),我们将在每个节点上的字符上保持一个短数组索引.这将炸毁空间.在trie中的几个级别之后,分支将减少,因此最好保留下一个节点字符和指针的链接列表.
什么看起来更实用？任何其他权衡？
谢谢,
luk*_*uke 12
我会说使用Trie,或者更好的是使用它更节省空间的堂兄定向非循环字图(DAWG).
它具有与Trie相同的运行时特性(插入,查找,删除),但重叠了常见的后缀以及可以节省大量空间的公共前缀.