数算实习后缀树数组

高级数据结构之四

——后缀树、后缀数组张铭、郝丹2013年11月Trie结构和Patricia树引子：BST（二叉搜索树）不是平衡的树树结构与输入数据的顺序有很大的关系输入顺序:4、5、6、7、8输入顺序:7、5、4、6、8

Trie结构和Patricia树引子：BST（二叉搜索树）不是平衡的树树结构与输入数据的顺序有很大的关系输入顺序:4、5、6、7、8输入顺序:7、5、4、6、8

BST：关键码范围分解，由树中关键码值决定为了解决BST的平衡性问题，考虑使用树堆等

从根本上消除不平衡，改变关键码的划分方式——关键码空间分解（对关键码范围进行均分）Trie结构

关键码对象空间分解“trie”这个词来源于“retrieval”主要应用信息检索（informationretrieval）

自然语言大规模的英文词典Trie树的两个原则：关键码集合固定能够对结点进行分层标记Trie结构

关键码对象空间分解“trie”这个词来源于“retrieval”主要应用信息检索（informationretrieval）

自然语言大规模的英文词典Trie树的两个原则：关键码集合固定能够对结点进行分层标记若元素可以用0~9的数字组合标记，那么根结点分出10个子结点，分别标记为0~9；然后每个子结点又可以分出10个结点…二叉Trie结构元素为2、5、9、17、41、45、630(<32)1(>32)0(<16)1(>16)0(<8)0(<4)1(>48)1(>8)1(>4)2591741631(>40)450(<44)1(>44)0(<48)本质上，二叉树二叉Trie结构元素为2、5、9、17、41、45、630(<32)1(>32)0(<16)1(>16)0(<8)0(<4)1(>48)1(>8)1(>4)2591741631(>40)450(<44)1(>44)0(<48)本质上，二叉树同一棵子树下面的结点，共享了他们父结点的前缀，如2(0000)和5(0001)哈夫曼树，也是一种二叉Trie树英文字符树——26叉Trie

Trie结构由于常被用于存储字典中的单词，因此常被称为“字符树”一棵子树代表具有相同前缀的关键码的集合前缀树：“an”子树代表具有相同前缀an-的关键码集合{and，ant}内部结点不存储单词信息不等长的字符树，加“*”标记

存储单词an、and、ant、bad、bee

a

n

d

t

b

a

e

and

ant

an

*

*

*d

e只有叶结点存储单词信息bad

bee*

*可压缩Briandais字符树（森林）elamxlumn*omy*u*****Trie树的前身，Rene

De

La

Briandais,

1959年提出的Briandais字符树和Trie树Briandais字符树(树林)为了区分相同前缀关键码，在字符树中每个关键码的结尾处加上一个特殊字符“*”所有叶结点都是“*”Trie树假设字符树的基数为d，则Trie结构每个结点存储d个指针Trie树的检索效率很高。Trie，Fredkin命名，1960年Trie字符树的特点Trie结构也不是平衡的t子树下的分支比z子树下的多26个分支因子——庞大的26叉树PATRICIA结构为了获得更加平衡的结构，D.Morrision发明的Trie结构变体PATRICIA（PracticalAlgorithmToRetrieveInformationCodedInAlphanumeric）根据关键码的每个二进制位的编码来划分本质，二叉树

PATRICIA结构图压缩PATRICIA结构PATRICIA的二进制路径往往比字符树长，要压缩PATRICIA的特点改进后的压缩PATRICIA树是满二叉树每个内部结点都代表一个位的比较必然产生两个子结点一次检索不超过关键码的位个数Triev.s.PATRICIA根据实际应用，选择合适的结构如中文字典建议采用PATRICIA，因为常用汉字有几千个Trie的应用信息检索——查询文章中的词语给主串T、模式串S，查询S是否在T中出现过传统的暴力匹配方法|T|*|S|次比较其他改进的匹配技术：如Boyer-Moore算法，O(|T|+|S|)后缀Trie：O(|T|)T的子串必定是某个T的某个后缀的前缀，将T的所有后缀插入Trie中，然后查询S即可。后缀Trie

aababcabdbcabdbcabdT=abcabd，S=cababcabdbcabdcabdabdbdddadddabdbcabdcabdd

bdbbc

.从根结点往下匹配，可以搜索到单词的任意子串后缀Trie的特点Trie：n叉树，每个结点表示从根结点到此结点所经过的所有字符组成的字符串后缀Trie：本质上，Trie表示所给字符串的所有后缀从后缀Trie到后缀树SuffixTrie特点：每条边上只记录一个字符就是一棵Trie树，具有Trie树的所有性质但是因为SuffixTrie的构造时间复杂度比较高，所以有局限性SuffixTree把Trie树中出现的单链收缩成一条边，边上记录多个字符[路径压缩]后缀Trie到后缀树（单路径压缩）T=abcabdaabcabdbcabdbcabddadddabdbcabdcabdd

bdbc.ababcabdcabddbcabdddabdbcabdcabdd

bdcabd.后缀树(SuffixTree)后缀树是表示一个字符串S所有后缀串的树结点：开始的字符或压缩字符串边标注为子串——该字符串在原串中的起止位置边表示不同字符分支所有根到树叶结点的路径，可以表示串S的所有后缀串S=MALAYALAM$0123456789(4,9)YALAM$(4,9)YALAM$(4,9)YALAM$(4,9)YALAM$5173620849(9,9)$(0,0)M(9,9)$(2,3)LA(8,9)M$(1,1)A(8,9)M$(2,3)LA(1,9)ALAYALAM$(8,9)M$(8,8)M(3,3)A(6,7)LA(5,5)A(7,7)A(6,7)LA后缀树(SuffixTree)后缀树，表示一个字符串的所有后缀这些后缀组成Trie压缩Trie，得到字符串的后缀树S=MALAYALAM$0123456789(4,9)YALAM$(4,9)YALAM$(4,9)YALAM$(4,9)YALAM$5173620849(9,9)$(0,0)M(9,9)$(2,3)LA(8,9)M$(1,1)A(8,9)M$(2,3)LA(1,9)ALAYALAM$(8,9)M$(8,8)M(3,3)A(6,7)LA(5,5)A(7,7)A(6,7)LAS=MALAYALAM$0123456789(4,9)YALAM$(4,9)YALAM$(4,9)YALAM$(4,9)YALAM$5173620849(9,9)$(0,0)M(9,9)$(2,3)LA(8,9)M$(1,1)A(8,9)M$(2,3)LA(1,9)ALAYALAM$(8,9)M$(8,8)M(3,3)A(6,7)LA(5,5)A(7,7)A(6,7)LA0MALAYALAM$1ALAYALAM$2LAYALAM$3AYALAM$4YALAM$5ALAM$6LAM$7AM$8M$9$后缀Trie和后缀树的构造过程早期的SuffixTrie和SuffixTree的构造算法字符串的处理顺序是从右到左，因此，算法是离线算法(off-line)——一次性输入要处理的字符串（文本…）实际应用期待在线算法(on-line)——输入不是一次性给出E.Ukkonen,On-LineConstructionofSuffixTrees,Algorithm(1995)14:249-260SuffixTrie的在线构造EskoUkkonen和DerickWood，Approximate

string

matching

with

suffix

automata,

Algorithmica,

1993(10),

5:353-364.已知字符串T=t1t2…tn，Ti表示T的前缀t1…ti(1<=i<=n),如何利用Ti-1后缀Trie构造Ti的后缀Trie?把ti连接到Ti-1的每个后缀之后空后缀εSTrie(T)字符串T的Suffix

Trie（STrie(T)）定义为一个增强型的DFA（Q∨{Γ}，root,F,g,f)T：一个字符串t1t2t3t4….tnQ：将STrie(T)映射到T的子串构成的集合F：DFA的终态集合辅助状态Γ：用于区分空后缀和非空后缀root：后缀树STrie的根结点。迁移函数g：存在Q中的状态x’和y’(x’和y’分别表示字符串x和y的状态），若g(x’,a)=y’，那么y=xa后缀函数f：对于字母表中任意字符a，若x=ay，则f(x)=y后缀Trie

aababcabdbcabdbcabdT=abcabd，S=cababcabdbcabdcabdabdbdddadddabdbcabdcabdd

bdbbc

.g:SuffixTrie中的边，链接字符构成子串f:

Suffix

Trie中的辅助链接，链接后缀SuffixTrie的构造算法源自：E.Ukkonen,On-LineConstructionofSuffixTrees,Algorithm(1995)14:249-260如何根据STrie(Ti-1)构造STrie(Ti)?top表示状态t1…ti-1在Trie中增加新边：哪些地方加新边—STrie(Ti-1)中所有后缀(f(r))之后状态r的后缀链接（suffix

link）f(r)，有助于构造suffix

trieSuffixTries

aababcabdbcabdbcabdT=abcabddadddabdbcabdcabdd

bdbbc

STrie(T)=(Q

{

},root,F,g,f).suffixlink，通过f函数定义迁移函数，通过g函数定义SuffixTries

aababcabdbcabdbcabdT=abcabddadddabdbcabdcabdd

bdbbc

STrie(T)=(Q

{

},root,F,g,f).suffixlink，通过f函数定义迁移函数，通过g函数定义对于Ti-1的所有后缀，都在STrie(Ti-1)从最深状态t1…ti-1到

的suffixlinks形成的路径上，这条路径称为STrie(Ti-1)的boundarypath注意：图中只给出了最后一层（T）的suffixlinksSuffxTries的构造效率SuffixTrie的构造时间与其大小（STrie(T)）成比例，因此，其最坏时间复杂度是O(|T|2).STrie(T)中结点数目是T的子串数。由于长度为n的字符串T至多有O(n2)个子串，因此，STrie(T)的大小是O(n2)。最坏情况O(n2)：T=ambm后缀树历史-O(n)Weiner1973(positiontree)特点：处理顺序是从右到左；从最小的后缀开始处理，增加后缀的长度McCreight1976(发明B树的人之一)特点：按照后缀长度递减的顺序，构造后缀树Ukkonen1995(主要介绍此算法)E.Ukkonen.On-lineconstructionofsuffix-trees.Algorithmica,14:249-60,1995.后续算法JuhaKarkkainen和PeterSanders2003…Suffix

Trie到Suffix

Tree的构造

——BANANAS的后缀树构造BANANAS的后缀树：先由B开始,接着是BA,然后BAN,….不断更新直到构造出BANANAS的后缀树.加入一个新的前缀需要访问树中已有的后缀,并在之后加入一个字符从最长的一个后缀开始,一直访问到最短的后缀(空后缀).每个后缀会在以下三种结点的其中一种结束.叶结点显式结点(explicit

state)隐式结点(implicitstate)显式结点和隐式结点T=abcabdaabcabdbcabdbcabddadddabdbcabdcabdd

bdbc.ababcabdcabddbcabdddabdbcabdcabdd

bdcabd.explicit

stateimplicit

state加入一个新的前缀需要访问树中已有的后缀,并在之后加入一个字符从最长的一个后缀开始(图中的BAN),一直访问到最短的后缀(空后缀).每个后缀会在以下三种结点的其中一种结束.叶结点显式结点(explicit

state)隐式结点(implicitstate)叶结点的处理加入的字符在叶结点时，直接延长边即可，新后缀还在叶结点BOOK的后缀树隐式结点的处理(1/2)加入的字符在隐式结点什么都不做，或割开一条边，并在后加入一条新边BOOK的后缀树KKBOOKK的后缀树隐式结点的处理(2/2)加入的字符在隐式结点什么都不做，或割开一条边，并在后加入一条新边BOOKK->BOOKKE隐式结点的处理(2/2)加入的字符在隐式结点什么都不做，或割开一条边，并在后加入一条新边BOOKK->BOOKKE隐式结点.后缀Trie中存在的、由于路径压缩而隐藏的结点.后缀树的构造过程中,有时要把一些隐式结点转化为显式结点.显式结点的处理加入字符在显式结点什么都不做加入一条新边，成为一个在叶结点UKK算法对于构造SuffixTree的两个基本步骤：类似于STrie(Ti-1）到Strie(Ti)的构造过程1、延长一条边2、插入一条边性质：一朝为叶，终身为叶实现中的优化技巧：后缀指针fUKK算法特殊性质一朝为叶，终身为叶：当一个后缀成为叶结点之后，那么它就一直会是叶结点根据此性质我们可以得到：如果已经知道某条边指向的结点是叶结点，则可以直接把这条边定义成指向字符串末尾的边UKK算法构建图例STree(cac):cac//叶结点ac//叶结点c//非叶结点Root//非叶结点STree(caca)：caca//叶结点aca//叶结点ca//非叶结点a//非叶结点root//非叶结点激活结点和结束结点active

point(激活结点)和endpoint(结束结点)往STree(Ti-1)中增加ti?对于STree(Ti-1)中boundarypath上的每个状态sh，一定存在激活结点sj和结束结点sj’j是沿着STree(Ti-1)的boundary

path中下标最小的非叶结点状态j’是沿着STree(Ti-1)的boundary

path中下标最小的具有ti-transition(输入字符是ti的转移迁移函数已定义）的状态激活结点和终结点的示例s4s5s1s2

aabbcabcaTi-1=abcati=bs3a

bc

Boundary

path:

abca->bca->ca->a->ε->

sjsj’激活结点示例(1/2)BOOK->BOOKK显式结点激活结点示例(2/2)BOOKK->BOOKKE隐式结点激活结点的性质每次更新后缀树中，第一个非叶结点为激活结点，具有以下性质：1、所有在激活结点之前加入的后缀都在叶结点，且它们都比激活结点长2、所有在激活结点之后加入的后缀都不在叶结点上结束结束结点遍历时遇到的第一个不需要建立新的叶结点的后缀。即，第一个什么都不需要做得后缀结束结点之后的结点也不需要更新重要性质：当前的结束结点是下阶段的激活结点UKK算法流程对于叶结点，第一次建立时就将它所对应的边指向字符串末尾每次更新从激活结点（含）开始一直到结束结点（不含）下一次的激活结点就是这一次的结束结点1.

Update(新前缀)2.

{3.

当前后缀=激活结点4.

待加字符=新前缀最后一个字符5.

done=false;6.

while(!done){7.

if(当前后缀在显式结点结束){8.

if(当前结点后没有以待加字符开始的边)9.

在当前结点后创建一个新的叶结点10.

else11.

done=true;12.

}else{13.

if(当前隐式节点的下一个字符不是待加字符){14.

从隐式节点后分割此边15.

在分割处创建一个新的叶节点16.

}else17.

done=true;18.

if(当前后缀是空后缀)19.

done=true;20.

else21.

当前后缀=下一个更短的后缀22.

}23.

激活结点=当前后缀24.

}13.

if(当前隐式结点的下一个字符不是待加字符){14.

从隐式结点后分割此边15.

在分割处创建一个新的叶结点16.

}else17.

done=true;

18.

if(当前后缀是空后缀)19.

done=true;20.

elseif(!done)21.

当前后缀=下一个更短的后缀22.

}23.

激活结点=当前后缀沿着boundarypath更新(1/2)

aabbcabbcaba

bbc

activepointTi-1=abcabSTrie(Ti-1)ti=dendpointlastlayerofsuffixlinks(boundarypath)firstgroupsecondgroupFirstgroup:s1…sj(activepoint)直接在最后增加一个分支结点Secondgroup:sj+1…sj’-1

增加一个新的分支沿着boundarypath更新(2/2)

aabbcabbcaba

bbc

activepointTi-1=abcabSTrie(Ti-1)ti=dendpointfirstgroupsecondgroupddddddSTrie(T)的激活结点和结束结点

aabbcabbcaba

bbc

activepointTi-1=abcabSTrie(Ti-1)ti=dendpointlastlayerofsuffixlinks(boundarypath)firstgroupsecondgroupFirstgroup的处理方法

abb

firstgroupsecondgroupSTree(Ti-1)ti=dactivepointendpointTi-1=abcab(3,

)abcab(3,

)bcab(3,

)cabcabcabab(1,2)b(2,2)cabopentransition:STree(T)中指向叶结点的迁移g’(s,(k,i-1))=r，增加ti后，g’(s,(k,i))=rOpenTransitions

abbd

firstgroupsecondgroupSTree(Ti)ti=dWecolorthenewtransitionandnewnodegreenactivepointendpointTi-1=abcab(3,

)abcabd(3,

)bcabd(3,

)cabdcabdcabdcabdddab(1,2)b(2,2)Secondgroup的处理方法

abbd

firstgroupsecondgroupSTree(Ti)ti=dactivepointendpointTi-1=abcab(3,

)abcabd(3,

)bcabd(3,

)cabdcabdcabdcabdddab(1,2)b(2,2)对于boundarypath上的状态sh(j<=h<j’)沿着suffixlinks，增加新的分支注：既要关注explicitstate，也要关注implicitstate优化：后缀指针后缀指针：后缀指针存在于每个显示结点上，都指向一个更短的后缀。如果一个后缀表示txtx+1….ty。那么这个指针指向表示tx+1….ty的结点。后缀指针可以在更新后缀树的时候进行同步更新。时间复杂度分析UKK算法是一个在线的算法，依次构建STree(T0),STree(T1)…STree(Tn)=STree(T)树中最多有|T|个叶结点，最多有|T|-1个显式分支结点，因此，树中至多2|T|-2个transitions（边）总时间复杂度为：O(N)单词粒度的后缀树“Iknowyouknow$”63通用后缀树Suffix

Tree：单一字符串，线性构造时间字符串构成的集合{S1,S2,…,Sn}，其对应的后缀表示成树形，记为通用后缀树（generalized

suffix

tree，简称GST）构造过程：建议使用不同的特殊符号（如$,#...）表示不同的字符串SiGST示例S1=ababS2=aab后缀树的应用查找字符串中的子串统计S中出现T的次数找出S中最长的重复子串出现了两次以上的子串两个字符串的公共子串最长共同前缀(LCP)回文串66后缀树的应用中文切词关联分析发现经常共同出现的短语频繁模式挖掘生命科学：基因/蛋白序列对比/分类……67Trie的应用信息检索——查询文章中的词语给主串T、模式串S，查询S是否在T中出现过传统的暴力匹配方法|T|*|S|次比较其他改进的匹配技术：如Boyer-Moore算法，O(|T|+|S|)后缀Trie：O(|T|)T的子串必定是某个T的某个后缀的前缀，将T的所有后缀插入Trie中，然后查询S即可69统计T中出现S的次数查“ALA”$YALAM$M$ALAYALAM$M$YALAM$M$YALAM$M$YALAM$AALLA51736208495和1匹配T=MALAYALAM$0123456789最长共同前缀(LCP)70lcp(suffixi,suffixj)=strlen(lca(i,j))

$YALAM$M$ALAYALAM$M$YALAM$M$YALAM$M$YALAM$AALLA5173620849ALAStringLength=3lcaT=MALAYALAM$0123456789lcp:longestcommonprefixlca:lowestcommonancestors最长共同子串GiventwostringsS1andS2,wearenowinterestedinfinding,foreach

i,findindexjsuchthatlce(i,j)ismaximal.GRAINY$0123456RAILWAY$01234567lce(0,0)=0lce(1,0)=3RAIRAIlceandlca构造S1和S2的通用前缀树T计算T中每个结点的字符串深度为lca查询预处理Tlce(i,j)=stringdepthoflcaofsuffixiofS1andsuffixjofS2计算字符串S1

和S2的最长公共子串lce回文回文：ApalindromeisastringthatreadsthesameinbothdirectionsE.g.,CATGTAC回文问题：寻找字符串S中最大的回文思考：如何使用后缀树和后缀数组来求解回文问题后缀数组后缀数组：后缀数组SA是一个一维数组,它保存1..n的某个排列SA[1],SA[2],,SA[n],并且保证Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。5ALAM$1ALAYALAM$7AM$3AYALAM$6LAM$2LAYALAM$0MALAYALAM$8M$4YALAM$9$MALAYALAM$

01234567895173620849后缀数组的构造后缀数组：后缀数组SA是一个一维数组,它保存1..n的某个排列SA[1],SA[2],,SA[n],并且保证Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。简单来说，后缀数组就是“排第几的是谁”名次数组：名次数组Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。可以视为大小简单来说，名次数组就是问“你排第几”显然，两者只要知道一个，就可以推出另外一个sa[i]=j

rank[j]=i

后缀数组的构造——倍增算法字符串T中任意后缀Ti=ti…tn,n为T的长度计算Ti的长度为1的前缀(ti…ti+k-1)的rank值，记为rank(i)

计算Ti的长度为2的前缀(ti…ti+k-1)的rank值，记为rank(i)->…计算Ti的长度为2k+1(2k<=n<2k+1)的前缀(ti…ti+k-1)的rank值，记为rank(i)基数排序基数排序后缀数组字符串S的后缀数组SA对S的所有后缀的指针排序即后缀树叶结点的字典序后缀树ST=后缀数组SA+LCP数组79后缀数组(SuffixArray)31