双数组前缀树(Double array Trie)

引言

前缀树通常用在字符串查询和模糊匹配中,今天讨论前缀树的相关实现,着重了解双数组前缀树的优势。

什么是前缀树
三数组前缀树
双数组前缀树

什么是前缀树 Trie (Retrieval)

Trie 是一种字符搜索树,是一种有效的索引方法,也是一种有穷自动机 DFA( deterministic finite automaton),DFA 就是一种有终止状态的状态转移。

如下图:

查询一个字符串,按字符从根节点搜索,像状态转移一样。

Trie 的算法复杂度依赖于搜索Key的大小,而不依赖于数据的大小,即算法复杂度是O(m),所以它一般比B Tree这种基于比较的索引方法快很多。

如何实现一个前缀树

二维数组存储

比如存储单词,每一层用数组a[第i层][26个字符+1(终止符号)]来存储。

因为数组长度不可变,每一层字符比较稀疏的话,就会造成空间的浪费。

链表存储

使用链表来存储每一层,空间可控制,但是状态转移的时候,必须遍历链表,算法复杂度就变成了O(m*n)（n是每层节点中的数量）,降低了查询效率。

如下图:

Hash 存储

Hash 表每层搜索的算法复杂度在O(1)，算是一种比较好的实现。但是算hash值，解决hash冲突，实际搜索效率还是比不上二维数组。

三数组前缀树(tripple-array)

使用 base next check 三个数组来存储.

参照上面的图我们理解一下: s->t,输入c字符。

base:base数组中每一个元素代表一个节点,base[s]的值是next和check数组的起始索引.
next:存储base[s]节点,在输入某个状态c,得到的下一个状态。即 next[base[c]+c]=t
check:存储转换过程中的的上一状态。check[base[s] + c] = s

通过三个数组,next维护转换的结果,check维护转换的上一状态，构造一个前缀树。这个做法做到空间节省，但是还不够,我们看下面的双数组前缀树。

双数组前缀树(Double-Array Trie）

双数组前缀树是对三数组前缀树的压缩优化,将next数组和base数组合并,check数组保留。

如下图:

check[base[s] + c] = s
base[s] + c = t

用check保存状态转移过程中的上一个状态,base[s]保存上一状态的偏移量。

双数组前缀树构造例子

假定输入两个前缀为’ab’, ‘ad’，将字母a-z映射为数字1，2，3,…, 26.
这里用-1代表数组元素为空，-2代表叶子节点, -3代表根节点
- 初始状态
  
  对于索引0，check[0]=-3代表根节点, base[0]表示偏移基地址为1，其他元素为-1表示为空
输入前缀ab
- 输入a
  
  base[0]+a，由状态0跳转到状态2. check[2]为-1，说明为空，更新为父状态0；base[2]更新为跳转过来的base, 即base[0]的值1
- 输入b
  
  base[2]+b，由状态2跳转到状态3，check[3]为-1，说明为空，更新为父状态2；由于字符串结束，将base[3]更新为-2，代表叶节点。
输入前缀ad
- 输入a
图中base和check的状态不会变化。根据base[0]+a，从状态0跳转到2。 check[2]不为空，但check[2]的值0与其父状态S=0相等，则无需更新，进入状态2，等待输入下一个字符。这个过程相当于一个查询过程
- 输入d
base[2]+d，由状态2跳转到状态5，check[5]为-1，说明为空，更新为父状态2；由于字符串结束，将base[5]更新为-2，代表叶节点。
输入字符串ca,解决冲突问题
- 输入c
状态由0跳转到状态4，check[4]空闲，将check[4]赋值为0，base[4]赋值为1.
- 输入a, 发生冲突
根据base[4]+4 状态从4跳转到2，但是check[2]非空，并且check[2]=0不等于父状态4，此时发生冲突
- 解决冲突
  - 重新查找base 和 check数组新的空闲位置,我们找到base[6]和check[6]。我们将base[4]改为6-a=5。check[6]=4。如下图: