tire树分析

详细的图文介绍在附件中

Trie树技术简介文档
引言
文档目的描述trie树，比较trie树与hash+lucene用于前缀搜索的效率。
Trie树
Trie,又称字典树、单词查找树,是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。相对来说,Trie树是一种比较简单的数据结构.理解起来比较简单,正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗非常大.
看了定义不一定理解，以下我们将用一张图对trie树结构进行说明
从上图可以看出：
 根节点是整个树的起点，根节点一般置为空。同样你也可以根据项目的需要对根节点进行相应的设置如：我想将上面的树拆分为两个trie树就可以将拆分后的两个树的根节点设置为 i与a。 关于根节点是否设置，如何设置根据具体架构定。
 每条分支对应一个或多个单词如 i-in-int 这里就对应了两个单词in和int。但是trie树的叶节点始终为最大的前缀或单词。
 关于trie树的查询是很容易理解的，我们输入一个a，trie首先对1级子节点i和a进行匹对，找到a对应的子树。再通过遍历整个a的子树找到a子树中所有的单词。
 trie树的添加同样很容易理解。如果我们需要添加一个单词able，分为如下几步：
1、 根据单词第一个字母，查找1级子节点，匹配到a。
2、 根据第二个之母b，发现a的子树不存在b。那么新建ab子节点，然后在一次创建 abl子节点，与able叶子节点。  如果第二个字母是d就顺d子树查找匹配并插入。
从以上我们可以看出trie树做前缀提示的优点是很突出的。但为什么最后我们未选择trie树呢？以下我将进行说明。
Trie树与hash+lucene前缀比较
背景
在选择的过程中根据项目的具体状况，我对trie与hash+lucene前缀收索进行了对比，实现语言java。
项目数据是歌曲的基本信息包含：歌曲名，歌手名，专辑，等数据。
最终实现目标：如用户输入 “刘” 系统需要提示所有的以刘开头的次如“刘德华”、 “刘欢”等 但是不能提示 “刘德”或者“刘德华冰”，也就是说提示的必须是项目需要的格式如：歌手，歌曲，专辑，歌手+专辑，同时还需要包含词频。

trie树实现
如我们有如下词： 刘欢，刘德华，刘欢欢，刘德华 冰雨 ， 刘若英， 刘若英 后来。根据上面trie树的结构图我们很清楚的知道这些词组成的树的结构。刘-刘德/刘欢/刘若-刘德华/刘欢欢/刘若英…。
根据项目需要，我们要实现的是指定的词的提示，而不是字或者单词的提示。那么这里我们如何知道当前的节点为一个我们需要的词呢？同时在代码实现过程中我们如何实现这样的trie结构呢？实现方式分为两种：
1、基于单trie树：我使用数组实现trie树的节点，使用数组的Array[0]表示其是否为词和叶子节点，Array[1]为词或字本身，Array[3]指向其子节点集。如下图：
从上图可以看出 当Array[0] 为0表示词，1非词，-1表示叶节点。
如寻找以“刘“为前缀的相关信息时。我们需要经过n（树的深度）次匹配查询然后得到我们需要的结果，并且这些匹配都是在查询阶段实现的。同时这里未实现词频，如实现词频结构更加复杂
2、基于双trie树。根据相关论文，我也实现了双trie树（Double Array Trie）一下简称DAT。这里先摘抄一段论文内容，以助于大家理解。
“ DAT是采用两个线性数组(base[]和check[])，base和check数组拥有一致的下标，（下标）即DAT中的每一个状态，也即 TRIE树中所说的节点，base数组用于确定状态的转移，check数组用于检验转移的正确性。因此，从状态s输入c到状态t的一个转移必须满足如下条 件：
base[s] + c == t
check[base[s] + c] == s”
这里就不对公式进行说明了，大家可以再web中搜索相关论文。以下主要说明一下我的实现原理：首先我创建一个hash表用于存放词（key=编号，value=词），同时创建一个base数组用于确定状态的转移与check数组用于检验转移的正确性。
那我们的双trie树是如何查询的呢？现在我们套用上面的公式。假设当前状态为s，对于输入的字符c有：
  t = base[s] + c;
  if check[t] = s then
       next state = t;
  else
       fail;
  endif
当然不止上面的一次查询，这里我们需要一个递归来查询出所有的相关词
这里同样遇到相同的问题，如寻找以“刘“为前缀的相关信息时。我们需要经过大量的计算，并且这些计算都在查询过程中完成。这样就大量耗费了查询的时间。同时这里未实现词频，如实现词频结构更加复杂
注：两种tire树的实现比较，双trie树性能优于单trie树。
双trie参考文档：
Hash+lucene实现
首先需要注意的是hash+lucene（一下简称HL）思路是杨俊拯同志提出。实现过程如下：
首先我们同过计算将song信息构建成我们需要的结构如：歌手+词频，歌曲+词频，歌手+歌曲+词频，专辑+词频。然后以计算结果创建索引。
用户查询使用lucene的prefix搜索，这里经过lucene的一次性搜索得到需要的相关信息。返回用户同时存入hash表中。如果用户在次输入相同字符串，系统根据key提取存放在hash表中的结果，这里进行一次匹配。
注意HL方案，计算主要集中在创建索引阶段。查询只需要少量的匹配。如果hash表中存在结果只需要一次匹配。这样就减少了查询时的匹配时间。提高了查询效率。

比较结果
经过以上比较，我们能够很清楚的发现。在我的理论实现中HL的查询效率明显高于trie树。并且通过代码测试验证。如查询以“刘“开头的相关信息。HL需要0-70毫秒左右。而trie树需要100+毫秒。测试硬数据量为100万。
但是我不能断定trie树的效率低于HL，由于时间问题我的trie树算法不是好的算法，同时本项目的数据结构也会影响trie树性能的发挥。但是可以肯定的是java在实现trie树的过程中，如果使用hash表肯定会增加系统的消耗和影响trie树查询的效率。