后缀自动机_电脑基础知识_IT计算机_专业资料

《后缀自动机_电脑基础知识_IT计算机_专业资料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、译者的话：原文地址链接地址俄文用google机翻成英文再翻成中文，错误在所难免，大家多包涵……如果有什么奇怪的话直接略过吧，因为这说明我也没看懂……后缀自动机后缀自动机（单词的有向无环图）——是一种强有力的数据结构，让你能够解决许多字符串问题。例如，使用后缀自动机可以在某一字符串中搜索另一字符串的所冇出现位置，或者计算不同子串的个数——这都能在线性时间内解决。直觉上，后缀自动机可以被理解为所有子串的简明信息。一个重要的事实是，后缀自动机以压缩后的形式包含了一个长度为n的字符串的所有信息，仅需要0（n）的空间。并且，它能在0（n）时间内被构造（

2、如果我们将字母表的大小k视作常数,否则就是0（n*logk））o历史上，Blumer等人于1983年首次提出了后缀自动机的线性规模，然后在1985-1986年，人们提出了首个线性时间内构建后缀口动机的算法（Crochemore,Blumer等）。在文末链接处杏看更多细节。后缀自动机在英文中被称作“suffixaulomston”（复数形式：suffixautomata）,单词的有向无环图"direcgedacyclicwordgraph，z（简写为“DAWG”）。后缀自动机的定义定义•对给定字符串S的后缀口动机是一个最小化确定有限状态口动机，

3、它能够接收字符串S的所有后缀。下面解释这一定义：后缀自动机是一张冇向无环图，其中顶点是状态，而边代表了状态Z间的转移。某一状态t.o被称作初始状态，由它能够到达其余所有状态。自动机中的所有转移——即有向边——都被某种符号标记。从某一状态出发的诸转移必须拥有不同的标记。（另一方而，状态转移不能在任何字符上）。一个或多个状态被标记为终止状态。如果我们从初始状态t_0经由任意路径走到某一终止状态，并顺序写出所有经过边的标记，你得到的字符串必然是s的某一后缀。在符合上述诸条件的所有自动机中，后缀自动机有这最少的顶点数。（后缀口动机并不被要求拥有最少的

4、边数）示缀自动机的最简性质最简性——后缀自动机的最重要性质是：它包含了所冇s的子串的信息。换言Z,对于任意从初始状态t_0出发的路径，如果我们写出所经过边上的标记，形成的子串必须是s的子串。相应地，s的任意子串都对应一条从初始状态t0出发的路径。为了简化说明，我们称了串“匹配”了从初始状态出发的路径，如果该路径上的边标记组成了这一子串。相应地，我们称任意路径“匹配”某一子串，该子串由路径屮边的标记组成。后缀自动机的每个状态都引领-•条或多条从初始状态出发的路径。我们称这个状态有若干匹配这些路径的方法。构建后缀口动机的实例下血给出一些対简单的字

5、符串构建后缀自动机的例子。初始状态被记作to,终止状态用星号(*)标记。toabs=〃abbb〃tob一个线性时间构建后缀自动机的算法在我们描述构建算法Z前，冇必要介绍一些新的概念和简要的证明，它们对理解后缀自动机的概念十分重要。结束位宜endpos,它们的性质及与后缀自动机的联系考虑字符串s的任意非空了串t。我们称终点集合endpos(t)为：s屮所有是t出现位置终点的集合。我们称两个子串t_l和t_2“终点等价”，如果它们的终点集合一致：endpos(t_l)=endpos(t_2)o因此，所有s的非空子串"J以根据终点等价性分成若干类。

6、事实上对后缀自动机，终点等价字符串仍然保持相同性质。换句话说，后缀自动机中状态数等价于所有子串的终点等价类个数，加上初始状态。每个状态对应一个或多个拥有相同终点集合的子串。我们将这一陈述作为假定，然后描述一个基于此假设的，线性时间构建后缀H动机的算法一—正如我们不久后将会看到的，所有后缀白动机的必须性质，除最小性(即最少顶点数)，都将被满足(最小性由Nerode产生，见参考文献)。关于终点集合，我们给出一些简单但重要的事实。引理1.两个非空子串u和w(length(u)<=length(w))是终点等价的,当且仅当u在字符串s屮仅作为w的后缀

7、出现。证明是显然的。(译者注：证明的儿句话我看不懂，编不卜-去了……)引理2.考虑两个非空子集u,w(length(u)<=length(w))。它们的终点集合不相交,或者endpos(w)是endpos(u)的了集。进一步地，这取决于u是否是w的后缀：{endpos(w)Cendpos(u)ifu—sufllxw,endpos(u)Aendpos(w)=0otherwise.证明•假设两个集合endpos(u)和endpos(w)有至少一个公共元素，这就意味着字符串w和u在同一位置结束，即u是w的后缀。因此，在字符串w的每次出现的终点u都会

8、出现，这就意味着endpos(w)包含于endpos(u)。引理3.考虑一个终点等价类。将该等价类中的子小按长度递减排序。排序后的序列中，每个了串将比上一个了串短，