首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在设计字典之类的东西时推荐的数据结构?

问在设计字典之类的东西时推荐的数据结构?
EN

Stack Overflow用户
提问于 2010-07-08 02:13:57
回答 3查看 632关注 0票数 3

在设计存储单词的字典之类的东西时,TRIE是最推荐的数据结构吗?有没有其他可以提高时间或内存性能的替代方案?

我相信,如果没有冲突,哈希可能是好的,但是对于重叠的单词,内存需求开始变得不好: over,overlap,overlaps,overlapped,overlapped都占用独占存储,而我们可以在trie中共享空间。

编辑:感谢@Moron和你们所有人非常有用的答案。我同意--生成散列键是O(n),TRIE搜索也是如此。然而,对于hash来说,随着链式增加时间,事情可能会变得更糟,而对于TRIE,这不会发生。我的担心仍然是,对于TRIE中的每个节点,我需要保留一个指针,如果字典大小很小,它可能会使事情变得混乱。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2010-07-08 02:29:29

你可以考虑Directed Acyclic Word graph,它基本上是一个trie,但有更好的内存使用,根据维基的说法,对于英语,内存消耗比trie低得多。

在时间上,它就像一个trie,可能比hash更好。不知道哈希的O(logn)时间是从哪里来的。对于合理的散列,它应该是O(n),其中n是要搜索的单词的长度。

票数 2
EN

Stack Overflow用户

发布于 2010-07-08 02:19:45

与哈希表相比,trie具有以下优点:

在最坏的情况下,与不完美的哈希表相比,

  1. 在trie中查找数据的速度更快( O(m)时间)。不完美的哈希表可能会有键冲突。键冲突是不同键到哈希表中相同位置的哈希函数映射。在不完美的哈希表中最坏情况下的查找速度是O(N)时间,但更典型的是O(1),计算散列所花费的时间。
  2. 在trie中不存在不同键的冲突。仅当单个键与多个值关联时,才需要trie中类似于存储键冲突的散列表桶的
  3. 桶。
  4. 在向trie中添加更多键时,无需提供哈希函数或更改哈希函数。
  5. trie可以按键提供条目的字母顺序。

尝试有以下缺点:

在某些情况下,在查找数据时,

  1. 尝试的速度可能比哈希表慢,特别是在硬盘驱动器或其他辅助存储设备上直接访问数据时,这些设备的随机访问时间比主内存要长。
  2. 要将所有键表示为字符串(如浮点数)并不容易-使用其编码的位串进行直接编码会产生没有特别意义的长链和前缀。

如果缺点是你可以接受的,我建议你使用trie。

来源:Wikipedia: Trie#As a replacement of other data structures

票数 5
EN

Stack Overflow用户

发布于 2010-07-08 02:21:33

我想这是个大问题,对吧?也许可以尝试一下Bloom filter?

http://en.wikipedia.org/wiki/Bloom_filter

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/3197614

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档