深入浅出双数组Trie树

对于字符串来说，还有一种查询效率较高的数据结构，叫做Trie树。

比如我们有一系列的字符串：{bachelor#, bcs#, badge#, baby#, back#, badger#, badness#}，我们之所以每个字符串都加上#，是希望不要一个字符串成为另外一个字符串的前缀。把它们放在Trie树中，如图所示。

在这棵Trie树中，每个节点都包含27个字符。上面的是根节点，如果字符串的个字符是“b”，则“b”的位置就有一个指针指向第二个层次的节点，从这一层的节点开始，下面挂的整棵树，都是以“b”开头的字符串。第二层的节点也是包含27个字符，如果字符串的第二个字符是“c”则“c”的位置也有一个指针指向第三个层次的节点，第三个层次下面挂的整棵树都是以“bc”为前缀的，以此类推，直到碰到“#”，则字符串结束。通过这种数据结构，我们对于字符串的查找速度就和字符串的数量没有关系了，而是字符串有多长，我们就顶多查找多少个节点，而字符串的长度都是有限的，所以查询速度是相当的快。

当然细心的同学也发现了，高速度的代价就是空间占用太大，而且是指数增加的，还是以27为底数的。好在还是英文啊，说破天不过就是26个字母，要是中文可怎么办啊。所以咱们可不能有没有的都列在哪里，出现的字符咱就占用空间，不出现的咱可不浪费。基于这种理念，上面的那棵Trie树就变成了图的样子。

图中仅仅保留了已有的字符，并将每个节点变成了一种状态(State)，在没有任何输入的情况下，我们处于根节点的状态，当输入字符“b”后，便到了下一层的状态S_b ，当再输入字符“a”后，就到了再下一层的状态S_ba ，所有在S_ba 下面挂着的整棵树都是以“ba”作为前缀的。

熟悉编译原理或者形式语言的同学已经发现了，这是一个有限状态机。不熟悉的同学也不要紧，很容易理解，假设有一个门，有两个按钮“开”和“关”，代表用户的输入，门有两种状态，“开着”和“关着”。门的状态根据用户的输入而变化，比如门处于“关着”的状态，用户输入“开”，就转换到“开着”的状态，然后再点“关”，就回到“关着”的状态。当然也可以识别不合法的输入，比如门本来就“开着”，你还猛点“开”这个按钮，门或者报错，或者没有反应。在上面的有限状态机中也是这样的，一开始处于根节点的状态，用户输入“b”，就进入状态S_b，输入“c”，就进入状态S_bc ，再输入“s”，进入状态S_bcs ，后用户输入“#”，字符串结束，进入状态S_bcs# ，说明字符串“bcs#”在我们的状态机里面是合法的，存在的。如果用户输入“b”之后输入“z”，在状态机中没有对应的状态，所以以“bz”开头的字符串是不存在的。通过我们的这个有限状态机，同样能够起到查询字符串的作用。

其实这个状态机还可以进一步简化。我们发现有的状态是有多个后续状态的，比如S_bac ，根据输入的不同进入不同的后续状态，而有的状态的后续状态是的，比如当用户到达状态S_bach ，此后的合法输入就是“elor#”，所以根本不需要一个个的进入状态S_bache ，S_bachel ，S_bachelo ，S_bachelor ，直到状态S_bachelor# 才发现用户输入是否存在，而是在到达状态S_bach 之后，直接比较剩余的字符串是否是“elor#”就可以了，所以上面的有限状态机可以变成图的样子，所谓的剩余的这些字符串，我们称之为后缀。

接下来的任务，就是如何将这个简化了的树形结构更加紧凑的保存起来了。我们在这里要介绍一种不需要占用太多空间的Trie树的数据结构，双数组Trie树。

顾名思义，双数组Trie树就是将上述的树形结构保存在两个数组中，那怎么保存呢？

我们来看上面的这个树形结构，多么像咱们的组织架构图啊，上面的根节点是总经理，各个中间节点是各部门的经理，后那些后缀就是咱们的员工了。现在公司要开会了，需要强行把这个树形结构压扁成数组结构，一个挨一个的坐，那应该要维护的就是上下级的关系。对于总经理，要知道自己的直接下级，以及公司有多少领导干部。对于中层领导，一方面要知道自己的上级在哪里坐，下级在哪里坐；对于基层领导，除了知道上级在哪里坐，还需要知道员工在那里坐。

双数组Trie树就是一个维护上下级关系的一个数据结构。它主要包含两个数组BASE和CHECK，用来保存和维护领导干部之间的关系的，另外还有一个顺序结构TAIL，可以在内存中，也可以在硬盘上，用来安排咱们员工坐的。更形象的说法，两个数组就相当于主席台，而员工只有密密麻麻坐在观众席上了。

BASE和CHECK数组就代表主席台上的座位，如果第i位，BASE[i]和CHECK[i]都为0，说明这个位置是空的，还没有人坐。如果不是空的，说明坐着一位领导干部，BASE[i]数组里面是一个偏移量offset，通过它，可以计算出下属都坐在什么位置，比如领导S_b 有两个下属S_ba 和S_bc ，如果领导S_b 坐在第r个位置，则BASE[r]中保存了一个偏移量q(q>=1)，对于下属S_ba ，是由S_b 输入“a”到达的，我们将字符“a”编号成一个数字a，则S_ba 就应该坐在q+a的位置，同理S_bc 就应该坐在q+c的位置。CHECK[i]数组里面是一个下标，通过它，可以知道自己的领导坐在什么位置，比如刚才讲到的下属S_ba ，他坐在q+a的位置，他的领导S_b坐在第r个位置，那么CHECK[q+a]里面等于r，同理CHECK[q+c]里面也应该是r，那BASE[q+a]和BASE[q+c]中保存的什么呢？当然就是S_ba 和S_bc 他们的下属的位子了。所以职场中，每个人都同时扮演两种角色，一方面是上司的下属，一方面是下属的上司，所以每个位子i都有两个数字BASE[i]和CHECK[i]，坐在每个位子上的人都应该知道，自己的上司是谁，下属是谁。

对于基层领导稍有不同，因为基层领导的下属就是普通员工了，不坐在双数组主席台上了，而是坐在TAIL观众席上了，所以对于基层领导，如果他坐在第i个位置，则BASE[i]就不是正的了，而是一个负的值p，表示他是基层领导，在双数组主席台上 没有下属了，而|p|则表示基层领导所下属的哪些普通员工在TAIL观众席上的位置。

至于TAIL观众席的结构，就非常简单了，普通员工嘛，别那么多讲究，一个挨一个的做，用$符合进行分割。

根据上述的原理，上面的那颗树保存在双数组里面应该如图，至于这里面的数据如何形成，下面会一步一步详细说明:

图中的下方是对每个字符的编号。从图中我们可以看出，总经理S_ᵋ 总是坐在头一把交椅，CHECK[1]=20，主席台总共有20个位子，总经理当然应该对干部的总体情况有所把握。总经理的下属S_b 坐在BASE[1]+b = 1+2=3的位子上，S_b 的上司是总经理，所以CHECK[3]=1，S_b 的下属有两个S_ba 和S_bc ，他们的座位BASE[3]+a=6+1=7以及BASE[3]+c=6+3=9，自然CHECK[7]和CHECK[9]都等于3，以此类推。有人可能会困惑为什么BASE[1]是1而BASE[3]是6，不是1也不是5呢？这是在安排座位的过程中逐渐形成的，从下面双数组Trie树的形成过程大家会更详细的了解，在这里就简单说明一下，对于每一个坐在第i个位置的领导，BASE[i]里面都保存下属相对于他的offset，当然每个领导都希望offset越小越好，这样自己的下属也能坐在前面，对于总经理来说，当然他牛，所以BASE[1]可以取小值1，因为总经理刚坐下的时候，主席台是空的，他的下属随便坐都可以，对于其他的领导干部就不一定了，如果BASE[i]取1，结果计算后给自己的下属安排位置的时候，发现位置以及被先来的人坐了，所以没办法，只有增加BASE[i]，让自己的下属往后坐坐。对于状态S_bab ，S_bc ，S_bach ，S_back ，S_badn ，S_badger ，S_badge# ，他们的BASE[i]都是负的，所以他们是基层领导，通过BASE[i]里面的值的值，可以找到TAIL观众席中自己的下属，比如S_bab 的BASE值为-17，在TAIL中第17个字符开始是“y#$”，所以连接起来就是“baby#”。当然TAIL中也有一些很奇怪的，比如第20和第22个都只保存了“#$”，这说明了，除了结束符“#”之外，在后一个字符才与其他的字符串做了区分，第20个就是这样的，“back#”到了字符“k”才和“bachelor#”有所区分(“back#”和“bachelor#”都是以bac为开头的，都归S_bac 领导，必须提拔字符“k”和“h”到主席台，形成状态S_back 和S_bach 来区分两个团队)，既然分开了，就是一个单独的团队，虽然后面只跟了一个“#”，S_back 作为一个小小领导，也需要等上主席台，别拿村长不当干部。其实还有更惨的，对于第13个，就只剩下分隔符“$”，这是因为“badge”完全是另外一个字符串“badger”的前缀，多亏加了个结束符“#”才将两者区分开来，对于“badge#”来讲，到了“#”字符才区分，那么只好也做上主席台，做个光杆司令了。还有一点奇怪的就是，TAIL中为什么有空位置啊，比如位置7,8,9？这是历史原因造成的，因为一开始字符串“bachelor#”刚来的时候，其他的字符串还没来，公司规模较小，就一个团队，不需要那么多层领导，所以就S_b 作为的一个团队的头坐主席台，其他的“achelor#”都坐观众席，所以“achelor#$”总共占了9个位置，后来“bcs#”来了，光是领导S_b 不足以区分这两个字符串团队“bachelor#”和“bcs#”(他们都是以b开头的啊)，所以“achelor#”中的字符“a”和“bcs#”的字符“c”都被提拔为领导岗位，对两个字符串团队以作区分，就形成了状态S_ba 和S_bc (从此“bachelor#”可以说我们是以ba开头的，而“bcs#”可以说我们是以bc开头的)，后来“back#” 来了，仅仅字符“ba”以及“bac”都不足以区分“bachelor#”和“back#”，所以，不但“bachelor#”中的字符“c”被提拔成领导岗位，形成状态S_bac ，字符“h”也被提拔，形成状态S_bach ，从而员工就剩下了“elor#”，被提拔了三位，所以位置7,8,9就空下来了，那为什么不让后面的字符跟上呢？一方面，在双数组主席台中，其他团队的下属的位置都已经标好了，这一跟上都要改，比较麻烦，另外一方面，TAIL很可能保存在硬盘文件中的，将文件中的内容移动，也是很低效的事情。

有了上述结构，对字符串进程查询就方便了，一般按照以下的流程进行：

 

//输入: String inputString=”a₁ a₂ …… a_n #”转换成为int[] inputCode

boolean doubleArrayTrieSearch(int[] inputCode) {

int r=1;

int h=0;

do {

int t = BASE[r] + inputCode[h];

if(CHECK[t] != r){

//在双数组中找不到相同前缀，说明不存在与这个集合

// a₁ a₂ …… a_h-1 都相同，a_h 不同

//座位t上坐的不是你的领导，在这棵树上这个字符串找不到组织

return false;

} else {

//前缀暂且相同，继续找下一层状态

// a₁ a₂ …… a_h 都相同，下个循环比较a_h+1

//说明你属于这个大团队，接着看是否属于某一个小团队

r = t;

}

h = h + 1;

} while(BASE[r]>0)

//到这一步双数组中的结构查询完毕，BASE[r]<0，应该从TAIL中查找了

If（h == inputCode.length - 1）{

//如果已经到了结束符#，说明这个字符串所有的字符都在双数组中，是个光杆司令

Return true;

}

Int[] tailCode = getTailCode(-BASE[r]);//从TAIL中拿出后缀

If(compare(tailCode, inputCode, h+1, inputCode.length -1) == 0){

//比较TAIL中的字符串和inputCode中剩下的”a_h+1 …… a_n #”是否相同，相同则存在

Return true;

} else {

Return false;

}

}

 

接下来，我们就来看看这种微妙的数据结构是如何构造的。其实构造过程说起来很简单，就是一开始整个双数组中只有根节点，然后随着字符串的不断插入而形成。要插入一个新的字符串，首先还是要调用上面的代码进行搜索一下的，如果能够搜索出来，则这个字符串原来就存在，则什么都不做，如果没有搜索出来，就需要进行插入操作。根据上面的搜索程序，搜索不出来分为两种情况，也就是上面的程序中返回False的地方

1) 种情况是在双数组中找不到相同的前缀。也即对于输入字符串a₁ a₂ … a_h-1 a_h a_h+1 … a_n #，在双数组中，a₁ a₂ … a_h-1 能找到对应的状态S a₁ a₂… a_h-1 ，然而从a_h开始，找不到对应的状态S a₁ a₂ … a_h-1 a_h，所以需要将S a₁ a₂ … a_h-1 a_h作为S a₁ a₂ … a_h-1的下属加入到双数组中，然后将a_h+1 … a_n #作为S a₁ a₂ … a_h-1 a_h的员工放到TAIL中。然而加入的时候存在一个问题，就是原来S a₁ a₂ … a_h-1已经有了一些下属，并经过原来排位置，找到了合适的BASE值，通过它能够找到这些下属的座位。这个时候状态S a₁ a₂ … a_h-1 a_h来了，当它想要按照BASE[r] + a_h=t找到位置的时候，发现CHECK[t]不为0，也即位置让其他先来的人占去了。这个时候有两种选择，一种选择是改变自己的领导S a₁ a₂ … a_h-1的BASE值，使得连同S a₁ a₂ … a_h-1 a_h和其他的下属都能够找到空位子坐下，这就需要对自己的领导S a₁ a₂ … a_h-1的原有下属全部迁移。另一种选择就是既然CHECK[t]不为零，说明被别人占了，把这个占了作为的人迁走，我S a₁ a₂ … a_h-1 a_h还是坐在这里，要迁走位置t的人可不容易，要先看他的领导的面子，也即根据CHECK[t]=p找到他的领导的位置，迁移位置t的人，需要改变他的领导的BASE[p]，而BASE[p]的改变，必将导致他的领导的原有所有下属都要迁移，另找 位置。那么选择哪一种方式呢？要看哪种方式迁移的人数少，就采取哪种方式。

2) 第二种情况是在双数组中找出的前缀相同，但是从TAIL中取出的后缀和输入不同。也即对于输入字符串a₁ a₂ … a_h-1 a_h a_h+1 … a_n #，在双数组中，a₁ a₂… a_h 能找到对应的状态S a₁ a₂ … a_h ，而a_h是基层领导，从TAIL中找出基层员工a_h+1 a_h+2… a_h+k b₁b₂……b_m和剩余的字符串a_h+1 a_h+2… a_h+k a_h+k+1… a_n #进行比较，结果虽不相同，但是他们却有共同的前缀a_h+1 a_h+2… a_h+k，为了区分这是两个不同的字符串团队，他们的共同领导a_h+1 a_h+2… a_h+k是要放到双数组中作为中层领导的，而个能够区分两个字符串的字符a_h+k+2和b₁则作为基层领导放到双数组中，两者在TAIL中的基层员工分别是a_h+k+2 … a_n#和b₂……b_m

下面咱就详细来一步一步看上面那个双数组Trie是如何构造的。

步骤1 初始状态

如图，初始状态，创业伊始，仅有根节点总经理，BASE[1]=1，CHECK[1]=1，TAIL为空。

步骤2 加入bachelor#

加入个字符串团队bachelor#，个字符“b”作为基层领导进入双数组，成为总经理的下属，所以状态S_b的位置为BASE[1]+b = 1 + 2 = 3，CHECK[3]为0，可直接插入，设CHECK[3]=1，后缀achelor#进入TAIL，BASE[3] = -1，表面S_b为基层领导，员工在TAIL中的偏移量为1。如图。

步骤3 加入bcs#

加入bcs#，找到状态S_b，是基层领导，从TAIL中读出后缀进行比较，achelor#和cs#，两者没有共同前缀，所以将a和c放入双数组中作为基层领导区分两个字符串团队即可。新加入的两个状态S_ba和S_bc都是状态S_b的下属，所以先求BASE[3]=q，先假设q=1，1+a = 1+1=2，1+c=1+3=4，CHECK[2]和CHECK[4]都为0，可以用来放S_ba和S_bc，所以BASE[3]=1，CHECK[2]=3，CHECK[4]=3。两个后缀chelor#和s#放入TAIL，基层领导S_ba的BASE[2]=-1，指向TAIL中的后缀chelor#，BASE[4]=-10，指向TAIL中的后缀s#。如图所示。

步骤4 加入badge#

加入badge#，找到状态S_ba，是基层领导，从TAIL中读取后缀chelor#和dge#进行比较，两者没有共同前缀，于是将字符c和d放入双数组作为基层领导来区分两个字符串团队，形成状态S_bac和S_bad，都作为S_ba的下属，于是要计算S_ba的BASE[2]=q，假设q=1，1+c = 1+3 = 4，1+d = 1+4 = 5，由于CHECK[4]不为零，所以产生冲突，再次假设q=2，2+c = 5，2+d=6，检查CHECK[5]和CHECK[6]都为零，可以放S_bac和S_bad，所以BASE[2]=2，CHECK[5]=2，CHECK[6]=2。两个后缀helor#和ge#放入TAIL，基层领导S_bac的BASE[5]=-1，指向TAIL中的helor#后缀，基层领导S_bad的BASE[6]=-13，指向TAIL中ge#后缀。如图。

步骤5 加入baby#

加入baby#，找到状态S_ba，有两个下属是S_bac和S_bad，却没有S_bab，要将S_bab加入到双数组中。当前S_ba的BASE[2]=2，根据它来安排S_bab的位置，2+b=4，然而CHECK[4]不为零，有冲突，位置以及被占了。有两种选择，一种是改变S_ba的BASE[2]的值，造成S_bac，S_bad，S_bab都要移动，另一种是移动第4位的状态S_bc，先要找他的领导S_b，要移动S_bc，需要修改S_b的BASE[3]的值，如果被修改，则状态S_ba和S_bc需要移动。权衡两种选择，选择后者。原来BASE[3]=q=1，假设q=2，2+a=3，2+c=5，CHECK[3]不为零，有冲突，再假设q=3，也有冲突，直到假设q=6，6+a=7，6+c=9，CHECK[7]和CHECK[9]都不为零，可以用来放S_ba和S_bc，所以BASE[3]=6，S_ba从第2个位置移动到第7个位置，S_bc从第4个位置移动到第9个位置，CHECK[7]和CHECK[9]设为3。把别人赶走了，S_bab就放在了第4个位置，CHECK[4]=7。后缀y#进入TAIL，基层领导S_bab的BASE[4]=-17指向TAIL中的后缀y#。如图。

步骤6 加入back#

加入back#，找到状态S_bac，是一个基层领导，从TAIL中读取后缀helor#和k#进行比较，两者没有共同前缀，需要将h和k放到双数组中作为基层领导来区分两个字符串团队，成为状态S_bach和S_back，都是S_bac的下属，计算S_bac的BASE[5]=q，假设q=1,1+k=12,1+h=9，由于CHECK[9]不为零，冲突，再假设q=2，2+k=13，2+h=10，CHECK[10]和CHECK[13]都为零，可以用来存放状态S_bach和S_back，所以BASE[5]=2，CHECK[10]=5，CHECK[13]=5。后缀elor#和#进入TAIL，状态S_bach的BASE[10]=-1指向TAIL中的后缀elor#，状态S_back所谓BASE[13]=-20指向TAIL中的后缀#。如图。

步骤7 加入badger#

加入badger#，找到状态S_bad，是基层领导，从TAIL中读取后缀ge#和ger#进行比较，两者有相同的前缀ge，所以g和e需要放入双数组作为中层领导，形成状态S_badg和S_badge，另外#和r需要放入双数组作为基层领导，来区分两个不同的字符串团队，形成状态S_badge#和S_badger。

先放入状态S_badg，他的领导是S_bad，计算BASE[6]=q，假设q=1，1+g=8，由于CHECK[8]为零不冲突，所以第8个位置可以用来放状态S_badg，BASE[6]=1，CHECK[8]=6。

然后放状态S_badge，他的领导是S_badg，计算BASE[8]=q，假设q=1，1+e=6，由于CHECK[6]不为零，冲突，再假设q=2还是冲突，直到假设q=6，6+e=11，由于CHECK[11]为零，所以不冲突，所以第11个位置可以用来放状态S_badge，于是BASE[8]=6，CHECK[11]=8。

后放状态S_badge#和S_badger，他们的领导是S_badge，计算BASE[11]=q，假设q=1，1+r=19，1+#=20，由于CHECK[19]和CHECK[20]都为零，不冲突，所以第19个位置和第20个位置可以用来放状态S_badger和S_badge#，于是BASE[11]=1，CHECK[19]=11，CHECK[20]=11。

后缀#和空后缀进入TAIL，基层领导S_badger的BASE[19]=-22，指向TAIL中的后缀#，基层领导S_badge#的BASE[20]=-13，指向TAIL中的空后缀。

步骤8 加入badness#

加入badness#，找到状态S_bad，不是基层领导，有下属S_badg，所以要将状态S_badn加入双数组以加入一个新的字符串团队，后缀ess#入TAIL中。

要放置S_badn，需要看他的领导Sbad的BASE[6]=1，1+n=15，CHECK[15]为零，不冲突，正好第15个位置空着，可以放置状态S_badn。如图。