在设计存储单词的字典之类的东西时,TRIE是最推荐的数据结构吗?有没有其他可以提高时间或内存性能的替代方案?
我相信,如果没有冲突,哈希可能是好的,但是对于重叠的单词,内存需求开始变得不好: over,overlap,overlaps,overlapped,overlapped都占用独占存储,而我们可以在trie中共享空间。
编辑:感谢@Moron和你们所有人非常有用的答案。我同意--生成散列键是O(n),TRIE搜索也是如此。然而,对于hash来说,随着链式增加时间,事情可能会变得更糟,而对于TRIE,这不会发生。我的担心仍然是,对于TRIE中的每个节点,我需要保留一个指针,如果字典大小很小,它可能会使事情变得混乱。
发布于 2010-07-08 02:29:29
你可以考虑Directed Acyclic Word graph,它基本上是一个trie,但有更好的内存使用,根据维基的说法,对于英语,内存消耗比trie低得多。
在时间上,它就像一个trie,可能比hash更好。不知道哈希的O(logn)时间是从哪里来的。对于合理的散列,它应该是O(n),其中n是要搜索的单词的长度。
发布于 2010-07-08 02:19:45
与哈希表相比,trie具有以下优点:
在最坏的情况下,与不完美的哈希表相比,
O(m)时间)。不完美的哈希表可能会有键冲突。键冲突是不同键到哈希表中相同位置的哈希函数映射。在不完美的哈希表中最坏情况下的查找速度是O(N)时间,但更典型的是O(1),计算散列所花费的时间。尝试有以下缺点:
在某些情况下,在查找数据时,
如果缺点是你可以接受的,我建议你使用trie。
来源:Wikipedia: Trie#As a replacement of other data structures
发布于 2010-07-08 02:21:33
我想这是个大问题,对吧?也许可以尝试一下Bloom filter?
https://stackoverflow.com/questions/3197614
复制相似问题