与Tire树的区别

Tire树是一种字典树,也是一种多叉树结构。

图11 Tire树基本结构

实际上按照本文所叙述的理论,Tire树可以归结为商数类哈希函数。其采用26位计数进制方式(以英文字母为基础)。

下面是有关于英文单词的统计情况:

图12 英文单词长度的分布情况
图12 英文单词长度绝大多数为8
图13 英文字母在英文单词种出现的频率

由以上数据统计可以分析得出Tire树的基本情况:

  1. 最大查找长度至少要设置至20。
  2. 平均最大查找长度应当接近于8。
  3. 各个分支路径上的数据记录分布不均匀,某些路径上过多,某些路径上过少。

如果使用哈希树进行处理,则可以做到如下几点:

  1. 无需对英文单词的长度做出限制。
    只是单词较长时,取余运算需要消耗较多CPU时间。也可以对英文单词预先使用余数类哈希函数进行处理,将结果数值作为字符串的关键字。这样处理整数要远优于处理长字符串。
  2. 目前英文单词数量超过100万,常用单词5万。以本文推荐的除数数列\(M^*\)为例,那么最大查找长度预估为3(256×255×253 = 16515840,远大于1000000),其平均查找长度应该不超过3。
  3. 数据记录都会靠近根节点,各分支路径数据是均衡的。可以通过优先插入出现频次高的单词,再插入出现频次低的单词,提高查询击中概率,减少平均查找长度。
    以上就是哈希树在处理英文单词时相对于Tire树的优势。