Tire树是一种字典树,也是一种多叉树结构。
![](http://www.algmain.com/wp-content/uploads/2023/02/v2-1a14af8debfc6aca2d893a5205c5a8a0_1440w.jpg)
实际上按照本文所叙述的理论,Tire树可以归结为商数类哈希函数。其采用26位计数进制方式(以英文字母为基础)。
下面是有关于英文单词的统计情况:
![](http://www.algmain.com/wp-content/uploads/2023/02/v2-d6358ea90183694c92d59447399486ca_1440w.jpg)
![](http://www.algmain.com/wp-content/uploads/2023/02/v2-fb6c4898739addd32277978d40852536_1440w.jpg)
![](http://www.algmain.com/wp-content/uploads/2023/02/v2-d52e6a2f6b33d57e1779356bd13fc089_1440w.jpg)
由以上数据统计可以分析得出Tire树的基本情况:
- 最大查找长度至少要设置至20。
- 平均最大查找长度应当接近于8。
- 各个分支路径上的数据记录分布不均匀,某些路径上过多,某些路径上过少。
如果使用哈希树进行处理,则可以做到如下几点:
- 无需对英文单词的长度做出限制。
只是单词较长时,取余运算需要消耗较多CPU时间。也可以对英文单词预先使用余数类哈希函数进行处理,将结果数值作为字符串的关键字。这样处理整数要远优于处理长字符串。 - 目前英文单词数量超过100万,常用单词5万。以本文推荐的除数数列\(M^*\)为例,那么最大查找长度预估为3(256×255×253 = 16515840,远大于1000000),其平均查找长度应该不超过3。
- 数据记录都会靠近根节点,各分支路径数据是均衡的。可以通过优先插入出现频次高的单词,再插入出现频次低的单词,提高查询击中概率,减少平均查找长度。
以上就是哈希树在处理英文单词时相对于Tire树的优势。