为什么搜索引擎用这个Trie树存储词组而不是Hash容器?

isscc

搜索引擎在什么地方会用trie树存储词组？搜索框推荐？词表里面存储的显然应该是词的id啊

hgrany

Hash只有理论上是O(1). 字符串做key, 至少要把它遍历一遍吧, 还有计算key的时间, 冲突检测的时间, 怎么也不可能是常数.
不关心存储空间或者key的字符集有限的时候, trie肯定是最好的. 如果构造tree之前就知道key的集合, 用双索引的trie, 存储空间也省下了.

fenghw8088

O(1)是指平均查找长度为常数，和数据的规模无关。
有序表或树的折半查找算法平均查找长度为log2N，即查找算法的时间复杂度为O(N*log2N)。

任何查找算法都是要比较的！否则不能确定是否找到了。
Tire不懂，但Hash表是不错的查找表，而且构造和查找的思路一致，好实现！

sacry

回复 13# fenghw8088


   

而Tire树相对于Hash表虽然查找效率低，但：

?
trie的复杂度是O(m)，就只是单词长度而已。

titer1

学习了，学习了理论就是要用

titer1

每个的优点弱点都列出来了。

edgar51774

1 、省内存，特别是建立大量索引的时候很有用
2、利于内存和硬盘存储索引结合。
3、至于查找，搜索，在建立索引后一般还会有一遍处理。

ps 不过我用hash。。。。。哈

edshea

Trie树的查找时间复杂度是O(1)

hijzhang

edshea 发表于 2012-09-13 14:22
Trie树的查找时间复杂度是O(1)

不对，是O(m)，m是查找串的长度。

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

说的很详细了。跟hash也对比了

windoze

用trie可以支持“chinaun*”这样的查询