（计算机软件与理论专业论文）压缩后缀数组构造算法的改进.pdf

中山大学硕士学位论文 胝缩后缀数组构造算法的改进 压缩后缀数组构造算法的改进 专业：计算机软件与理论 硕士生：高娜 指导教师：农革 摘要 给定一个有穷字符集，假设s 是由中的n 个字符组成的文本串，p 则是由中的m 个字符组成的模式串。模式匹配就是查找模式串p 在文本串s 中符合特定条件的所有出 现。在巨大数据集的模式匹配问题中，采用索引机制可以有效地提高匹配速度。在建 立索引的过程中，要考虑查找速度和空间开销的平衡，既要保证较高的查找速度又要 有合理的空间开销。 后缀数组作为一种常用的文本索引机制，因其简单的结构和较好的空间效率，已 成为模式匹配算法的基础数据结构。但是，它也有着文本索引机制共有的缺陷：实现 快速查询的算法仍使用了较多的空问。为了解决这一问题，g r o s s 洱口v i t t e r 对后缀数组 进行压缩，在实现o ( m l o g i i n + l o g 西n ) 的查找时间的同时，最多只需要( 一1 + o ( 1 ) ) n l o gj i 位的存储空i 日j 。其中为任意常数，且0 睚1 。 本文提出了一种新的构造压缩后缀数组的方法：对原文本串s 每l o g n 位一组进行 划分，每组只保存一个绝对地址，把后缀数组的存储空间降为0 ( n ) 位。同时，结合 b w t 变换的性质，把b w t ( s ) 数组每l o g n 个字符分为一组，各分组内每个不同字符只 保存一个绝对位置，将每个字符平均所占空间降为o ( 1 ) 位，从而有效解决空间瓶颈问 题。 关键字：压缩后缀数组，文本索引，字符串查找，模式匹配，b w t 变换 中山人学硕士学位论文压缩后缀数组构造算法的改进 an e w a l g o r i t h m f o rc o m p r e s s e ds u m x a r r a y c o n s t r u c t i o n m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：n ag a o s u p e i v i s o r ：g en o n g a bs t r a c t l e tsb eat e x to fl e n 酵hna n dpb eap a t t e mo fl e n 班hm ，b o t hs t r i n g so v e raf i x e d f i n i t ea l p h a b e t t h ep a t t e mm a t c h i n gi st of i n da l lo c c u r r e n c e so fpi nsw h i c hs a t i s f i e s s o m ec r i t e r i a b yu t i l i z i n gi n d e xs c h e m ei nl a r g e - s c a l ep a t t e mm a t c h i n ga p p l i c a t i o n s ，w e c a na c h i e v ef a s t e rm a t c h i n gs p e e d w h e nc r e a t i n gi n d e xs t r u c t u r e ，w es h o u l dc o n s i d e rt h e b a l a n c eb e t w e e ns e a r c hs p e e da n ds p a c ec o s tt os a t i s f yt h en e e do fs p a c e e f ! e i e n tt e x t i n d e x i n gm e t h o d st h a ts u p p o r tf - a s ts t “n gs e a r c h i n g s u f j f i xa r r a y a sac o m m o nt e x ti n d e x i n gs c h e m e ，h a sb e e nan e wh o t s p o ti nt h es t r i n g p a t t e mm a t c h i n ga l g o r i t h mb e c a u s eo fi t sc o m p a c ts t r u c t u r ea n de m c i e n ti m p l e m e n t a t i o n h o w e v e r ，w h e na p p l i e do n t ol a 唱e - s c a l ep a t t e mm a t c h i n ga p p l i c a t i o n s ，i ts t i l lh o l d st h e c o m m o nd r a w b a c kf o rt e x ti n d e x i n gs c h e m e s ：t h es t o r a g ec o s ti sv e r ys i g n i f i c a n tf o rt h e s h e e rv o l u m ea l t h o u g hi ts u p p o i r t saf a s ts t r i n gs e a r c h i n g t bs o l v et h i sp r o b l e m ，g r o s s ia n d t t e rp r o p o s e dac o m p r e s s e ds u m xa r r a ya n da c h i e v e do ( m l o g l l n + l o g 讨n ) s e a r c ht i m e u s i n ga tm o s t ( 一1 + o ( 1 ) ) n l o g l ib i t so fs t o m g ef o ra n yc o n s t a n to 冬1 i nt h i sp 印e r ，w ep r o p o s ean e wc o n s t m c t i o nm e t h o df o rc o m p r e s s i n gs u m xa r r a y b y d i v i d i n gt h eo r i g i n a lt e x ts t r i n gsi n t os e v e r a lg r o u p s a n de a c hg r o u pc o n s i s t so fl o g n s y m b o l s ，ag r o u pc a ns t o r eo n l yt h ei n d e xa d d r e s so ft h el a s ts y m b o l ，r e s u l t i n gi nt h a tt h e s t o r a g es p a c eo fs ac a nb er e d u c e dt o0 ( n ) b i t s m e a n w h i l e ，b yu t i l i z i n gt h ep r o p e i r t i e so f b u l l r o w s w h e e l e rt r a n s f o r mo ns ，i e b w t ( s ) ，w ed i v i d eb w t ( s ) i n t og r o u p s ，w h e r ee a c h 中山人学硕t 学位论文 爪缩后缀数纽构造算法的改进 g r o u pc o n s i s t so fl o g ns y m b o l s i ne a c hg r o u p ，w es t o r eo n l yt h ea b s o l u t i o nl o c a t i o no ff i r s t d i s t i n c tc h a r a c t e r si nt h eg r o u p c o m b i n i n gt h e s et w om e t h o d s ，w ec a ns t o r et h eo v e r a l ls a u s i n gat o t a ls p a c eo fo ( n ) b i t s k e yw o r d s ：c o m p r e s s e ds u f h xa r r a y ，t e x ti n d e x i n g ，s t r i n gs e a r c h i n g ，p a t t e mm a t c h i n g ， b u r r o w s w h e e l e rt r a n s f o r i l l l v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成 果。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：高翱p 日期：沙，3 年r 月p 日 。 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即： 学校有权保留学位论文并向国家主管部门或其指定机构送交论文 的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆、院系资料室被查阅，有权将学位论 文的内容编入有关数据库进行检索，可以采用复印、缩印或其他 方法保存学位论文。 学位论文作者签名： 而刍咿 日期：洳莎年月宕日 导师签名： 日期：伽留 彩曰 中山大学硕上学位论文压缩后缀数组构造算法的改进 1 1 研究背景和现状 第一章引言 给定一个有穷字符集，假设s 是由中的n 个字符组成的文本串，p 是由中的 m 个字符组成的模式串。文本查找通常有三种类型：( 1 ) p 是否为s 的子串? ( 2 ) p 在s 中共出现几次? ( 3 ) p 在s 的什么位置出现? 查找的实质是一个模式匹配过程，也就是用 户指定的模式串与给定的、称为主串的原文本相匹配的过程，如果两者匹配，则查找成 功，否则查找失败。模式匹配问题是计算机科学中的一个基本问题，即在一个较大的文 本中，查找模式字符串的出现情况i lj 。一般而言，文本就是要编辑的文档，而模式字符 串往往由用户来指定。 模式匹配算法在其中起着非常重要的作用。一个高效的模式匹配算法，可以极大地 提高查找的效率和质量，提高程序的响应性能。当然这种算法的应用远远不止于此，其 研究内容在信息检索、模式识别等众多领域均有重要价值，在拼写检查、语言翻译、数 据压缩、搜索引擎、入侵检测、内容过滤、计算机病毒特征码匹配以及基因序列比较等 应用中都有着重要的作用【l j 。 模式匹配，最直观的思想是：枚举可能的子串，然后顺序扫描原文本进行串匹配， 在所有解中找到最优的。大家熟悉的算法，包括k n u t h 。m o 玎i s p r a t t 算法、c o m m e n t z w a l t e r 算法以及b o y e r - m o o r e 等基于子串的算法，基于自动机的算法等，它们都采用这种简单的 顺序扫描思想。使用这类算法之前，不需要对文本信息做任何形式的预处理，当用户进 行查询时，直接对指定的文本串内容顺序扫描每个文件，在文本中进行字符串的简单匹 配。大家所熟知的k m p 字符串模式匹配算法，是第一个接近线性时间复杂度的单模式匹 配算法，该算法由k n u t h 、m o h i s 和p r a t t 首次提出【2 1 并进一步优化【3 】，可以在o ( m + n ) 的时 间内用o ( m ) 的空间完成对文本的扫描。该算法的基本思想是通过一个窗口在字符串上滑 动，利用前一次检查的信息，从而跳过了一些不必要检查的位置。方法比较简单，容易 实现。1 9 7 5 年，a h o 和c o r a s i c k 提出了第一个基于自动机的多模式匹配算法【4 】及其改进算 中山大学硕士学位论义 骶缩后缀数组构造算法的改进 法【3 2 】。随后出现了一系列的相关算法，比如压缩存储空间基于位图的算法【5 1 、反向构建 自动机引入跳跃的启发式方法【6 1 等。1 9 9 4 年，w u 和m a n b e r 提出了采用h a s h 方法的基于后 缀匹配方法，同时采用移位来加速比较7 】f 8 】。这两种方法是当前主流的软件实现的多模 式匹配算法。 这种基于子串的匹配算法最明显的缺点就是不适合文本非常巨大的情况。随着文本 长度的增加，这类算法的查找效率就成为一个很大的问题。特别是当文本规模达到一定 数量级的时候，这类算法已经不能满足实际的需要了。例如在面对w 曲上的大量数据时， 传统的模式匹配算法因为过于重视精确度而导致查找效率低下。 为了提高查找速率和空间利用率，t u c k 等人提出了这样一种解决方法【5 】：在文本中建 立一种便于查找的数据结构索引。当文本规模非常庞大而且相对稳定的时候，如果 文本数掘库都相对稳定，不需要快速更新，例如w 曲搜索引擎和期刊数据库中的文档信 息，建立索引这种数据结构来替代缓慢的顺序扫描过程，可以大大提高查找速度。我们 可以把索引理解为一个可以快速随机访问其内部字符的数据结构，它将原始数据处理成 一个高效的交差引用的查找结构以便于快速查找。索引隐含的概念类似于一本书最后的 索引，可以让我们快速找到讨论指定主题的页面。 目前已有的文本索引机制，都有很高的空间占用率。以后缀数组为例，每o ( 1 0 9 n ) 位 就需要0 ( n ) 存储字。索引的大小以原文本的0 ( 1 0 9 i l n ) 倍递增。而互联网上快速增加的在 线信息、生命科学中庞大的基因库，都迫切需要一种能实现快速查找而空间开销又少的 文本索引方法。 1 2 文本索引的瓶颈问题 索引和查找是密不可分的，建立索引时必须不断地执行查找操作。使用索引方法进 行查找时，首先对原文本进行预处理，建立文本的索引结构，以达到较快的查询速度。 一般的索引结构，是以文本为标准建立的，即记录的是文本中所有单词出现的情况。 而用户在进行查找时，都是输入关键字进行查询，所以使用这种索引结构，在查询某一 中山大学硕士学位论文压缩后缀数组构造算法的改进 关键字时往往需要遍历所有的索引【9 】。当索引量非常大时，效率会成为一个很大的问题。 另外，提高查询效率是以消耗一定的系统资源为代价的，索引要单独占据空间，因此索 引不能盲目建立，必须要有统筹的规划，一定要在“加快查询速度”与“降低空间开销” 之间做好平衡。例如给定一个包含n 个字符的文本，后缀树虽然是有效的全文索引方法， 但是需要4 n l o g n 到6 n l o g n 位的空间来存储索引，后缀数组原则上只需n l o g n 位，但是因为 要与最长公共前缀配合使用，所以实际需要3 n l o g n 位【l o 】。 在许多的实际应用中，空间复杂度才是主要的瓶颈，而不仅仅是查找效率。后缀树 排序算法因为主要用数据结构中“树”的结构去产生最后的排序结果j ，功能性虽强， 但简单性不足，并且占用的计算时间和空间都太大，难以满足要求；后缀数组占用的计 算时间并不大，计算也很简单，但占用的空间仍比较大，所以后缀数组技术不宜直接应 用，还必须对它加以改进，减少索引占用的空间大小。 算法的空间复杂度，主要是考虑算法所占有系统资源的情况。在算法设计过程中， 应从多方面考虑，减少算法所占用的系统资源。总体来说，应从两方面入手：一是数据 结构，即算法中所用到的所有数据，不论是中间数据量还是全程数据量，应考虑它们的 实际范围，根据它们的实际范围，定义适当的数据类型；二是从算法方面考虑，可以用 空间复杂度低的算法来替代空间复杂度高的算法。当然，这样做也是有代价的，可能会 提升算法的时间复杂度。我们要具体问题具体分析，寻求时间复杂度和空问复杂度的平 衡，选择问题的最佳算法。 在过去的十年间，出现了许多理论上或是实践上降低空间复杂度的算法。总体来讲， 可以划分为三类。第一类是降低常量参数，如1 9 9 3 年m a n b e r 和m y e r s 的后缀数组算法 【1 2 】，2 0 0 2 年a b o u e l h o d a 等人提出的扩展后缀数组【1 3 】。第二类是重构优化，如2 0 0 1 年 m 酞i n e n 提出的简约后缀数组1 1 4 j 。还有一类是抽象优化，即利用尽可能少的空间完成一 个给定抽象数据结构定义的功能操作。这早的空问通常是以位来度量的，并且往往跟文 本串的熵成f 比。全文索引就属于这一类。在实际应用中，创建后缀数组的时间和空间 开销较大，这一问题成了它在各个领域进一步推广的瓶颈。因此必须对它加以改进，减 少索引占用的空间大小。2 0 0 0 年，g r o s s i 和t t e r 提出一种新的数据结构压缩后缀 数组f 1 5 1 ( c o m p r e s s e ds u m xa 1 1 r a y s ) 是这类的典范。压缩后缀数组这一全新的数据结构，可 以有效解决后缀数组丌销空间大的缺点。另一方面，压缩后缀数组由于支持对子串的查 中山大学硕十：学位论文胜缩后缀数组构造算法的改进 找使得功能性更强。 1 3 本文的研究意义和结构 通过前两节的介绍，我们可以这样定义模式匹配问题：给定一个模式串p ，查找它 在文本串s 中的出现情况：是否出现，何处出现，出现几次等。常规的顺序查找思想简 单，实现效率却很低，尤其在文本规模较大的情况下，一般用文本索引来代替。而常有 的文本索引结构，如后缀树，虽然可以实现快速的查找，却消耗了太多的内存空间。后 缀数组作为后缀树的一种演化，可以轻松实现后缀树的全部功能，结构更为简单，只是 空间开销率仍然不理想。于是，对后缀数组的压缩就成了解决索引空间开销问题的主要 方法。这也是本文研究的意义所在。本文从g r o s s i v i t t e r 提出的压缩后缀数组构造方法【1 5 】 出发，探讨了一种新的构造方法，并通过实验证实了该方法的可用性和空间复杂度方面 的优势。这将有效解决文本索引中的空间开销问题，进一步优化文本索引机制的性能。 全文结构如下： 第一章介绍课题研究的背景和现状，结合文本索引中存在的问题，阐述算法研究的 意义。 第二章详细介绍常用的文本索引技术，并对其性能优劣进行分析比较。 第三章引入压缩后缀数组的概念，具体分析压缩后缀数组的常规构造方法及其性能， 并介绍了在实际应用中的改进。 第四章提出新的压缩后缀数组构造思想，并通过实例演示了算法的原理。 第五章对本文提出的算法进行详细的性能分析，并与现有算法进行了比较。 最后对整篇文章的做了总结，回顾论文提出的解决方案，分析优点和不足，指出进 一步研究的方向。 4 中山大学硕上学位论文压缩后缀数组构造算法的改进 第二章文本索引技术介绍 使用文本索引机制来解决字符串模式匹配问题，在实际建立索引的过程中，还需 要考虑一些更为具体的细节，比如需要采用什么样的数据结构建立索引，如何构造这 些索引以及如何存储这些索引等。因为所选用的这些具体细节的优劣将直接影响系统 存储空间利用率和运行速度( 包括构造索引的速度和利用索引进行查找的速度) 。在面 对海量信息建立索引时，考虑记录大小的时候要具体到字节中的位，这样彳能达到比 较合理可行的空间膨胀比( 即原文数据大小和它的索引大小的比值，这个比值的大小 关系到系统占用硬盘资源的大小以及查询的速度) 。合理的数据结构将使得查询过程更 加迅速。 2 1 后缀树( s u m xt r e e ) 2 1 1 后缀树介绍 为了更好地理解后缀树，我们先来看一种被称为t r i e 的数据结构。t r i e 树是一种用 于快速查找的多叉树结构，把要查找的关键词看作一个字符序列，根据这一序列构造 用于查找的树结构。在t r i e 树上进行查找类似于查阅英语词典。t r i e 的每一条边都对 应一个字符。在t r i e 中查找字符串s 时，只需依次枚举s 的每个字符，同时从t r i e 的根节点丌始选择相应的边往下遍历。如果枚举完的同时到达t r i e 的叶子节点，说明 s 存在于t r i e 中。如果未到达叶子节点或者枚举中途发现没有任何对应的边，说明s 没有被包含在t r i e 中。我们可以将t r i e 所有只有一个子结点的节点都和父节点合并， 进行压缩。事实上，后缀树就是一个压缩后的而e ，存储了字符串所有的后缀。 具体来说，后缀树是一个包含一个根节点的有向树，该树恰好带有n 个叶子，这 些叶子被赋予从1 到n 的标号。每一个内部节点( 根除外) 都至少有两个子节点，而 中山人学硕_ j 学位论文压缩后缀数纽构造算法的改进 且每条边都用s 的一个非空子串来标识。出自同一节点的任意两条边的标识不会以相 同的字符开始。后缀树的关键特征是：对于任何叶子节点i ，从根节点到该叶子节点 所经历的边的所有标识串联起来后恰好拼出s 的从i 位置开始的后缀，即s i m 】。树 中节点的标识被定义为从根到该节点的所有边的标识的串联。 后缀树的概念最早是由w e i n e r 于1 9 7 3 年提出的】，之后又由m c c r e i 曲t 在1 9 7 6 年和u k k o n e n 在1 9 9 2 年和1 9 9 5 年加以改进完善，从此以后，又出现了大量关于后缀 树的研究文献。后缀树的引入主要是针对字符串的高效查找：子串查找、最长重复子 串、最长公共子串、回文子串等。它支持有效的字符串匹配和查询。这种数据结构对 于在同一个目标文本中查找多个模式字符串非常适合，在网络搜索中是主流算法，这 方面的研究也已经比较成熟。 后缀树的主要缺点是，由于采用了“树”这种数据结构，导致生成过程比较复杂， 而且在查询的时候要求信息库中的文本必须可用，所需空间较大。尽管后缀树在高速 查找方面非常有效，这种方法得到的索引数据结构却至少要n 个字或者o ( n l o g n ) 位， 在最坏情况下要占用2 8 n 个字节的存储空间【1 0 1 ( n s 2 3 2 ) ，所占空i 、日j 过大。 2 1 2 后缀树的改进 许多使用后缀树结构的算法都面临着空间丌销过大这一问题。最常见的解决方法 是降低常量系数，采取空间与时问的折衷方案，或者使用稀疏后缀树的变种来存储后 缀的子集：当模式串的出现与建立了索引的后缀的前缀有关系时，可以实现高效的查 询。这类变种在节省空间的同时却使得随机查找过程变得困难，在最坏情况下，需要 0 ( m + n ) 的时间，与扫描整个文本所需要的时间一样。这就违背了使用索引机制的初衷 降低查找时间。还有一些这样的索引技术，如k a r k k a i n e n 提出的时间复杂度为o ( m ) 的l e m p e l 一z i v 索引1 1 6 j ，在查找长度小于l o g n 的模式串时，只需o ( n ) 位的空间，但是对 于更长的模式串，则需要o ( n l o g n ) 位。最近的一些相关研究，是以j a c o b s o n 建立的2 n 位改进树为基础的【l7 | ，对这种树进行扩展，将其优化为可以用n l o g n + o ( n ) 位空间，实 现o ( m + l o g l o g n ) 查找时间的后缀树【1 8 】。m u n r o e t a l 利用这种改进的后缀树19 1 ，实现了只 需n l o g n + o ( n ) 位却达到o ( m ) 查找时间的算法。后缀数组符合j a c o b s o n 表示理想化抽象 6 中山人学硕上学位论文压缩后缀数纽构造算法的改进 数据结构的通用框架【2 8 】，是一个存放了将一个串的所有后缀按字典序排序后的结果的 数组。该算法的特点是所有的数据都储存在数组这种数据结构中，所有操作比较简单。 在众多的后缀数组算法中处于主流的是l a r s s o n 等人提出的快速后缀排序算法【9 1 ，该算 法占用8 字节的存储空间，最坏情况下达到0 ( n l o g n ) 的时间复杂度。 2 2 后缀数组( s u m xa r r a y ) 后缀数组( s u m xa r r a y ) 是一种较新的建立索引的方法。按照后缀树的先根遍历顺 序存储后缀即得后缀数组。具体来讲，后缀数组是一个这样的一维数组：保存1 n 的 某个排列s a f l 】，s a 【2 ，s a 【n 】，并保证s u f f i x ( s a 【i 】) s u m x ( s a i + 1 】) ，1 n 。 也就是将s 的n 个后缀按照“字典顺序”从小到大排序之后，把排好序的后缀在原串 s 中的起始位置顺次放入s a 中。s a i 】是按“字典顺序”排在第i 位的后缀在原文本 串s 中的开始位置。通过对字符串的编码，可以用后缀数组进行字符串集序列的处理。 它具有较高的查找效率，并且更适合范围查找、模糊查找等较复杂的查找方式。 后缀数组是1 9 9 3 年由m a n b e r 和m y e r s 作为替代后缀树的一种文本索引结构提出 的【佗】，他们给出了构造思想，利用o ( n ) 的额外空问，在0 ( n l o g n ) 时间内同时构造出后 缀数组及最长公共前缀信息数组l c p ，定位查找响应时问为o ( m + l o g n ) ，而枚举查找 时间为0 ( m + l o g n + o c c ) ，但是没有详细的算法实现。之后，a b o u e j h o d a 等人【2 i j 将时间复 杂度进一步优化到0 ( m + o c c ) ，并进行了实验验证。这也是目前最理想的后缀数组构造 算法。 后缀数组最适合在海量信息中进行查找操作，因为处理的数据量异常庞大，必须 充分考虑到时【、日j 复杂度和空间复杂度之间的平衡。后缀数组与后缀树的思想相同，但 是比后缀树更容易编程实现，能够实现后缀树的功能而时i 、日j 复杂度也不逊色，并且它 比后缀树所占用的空间小很多【1 0 】。简单的结构，高效的实现使得后缀数组的应用前景 广阔，因此受到越来越多的关注，在基因组分析、文本压缩、字符检索等应用领域都 表现出了极大的潜力。但在实际应用中，创建后缀数组的时间和空间开销仍然较大， 必须对它加以改进，才能在实际应用中发挥更大作用。 中山大学硕士学位论文压缩后缀数组构造算法的改进 2 3 压缩后缀数组( c o m p r e s s e ds u m xa r r a y ) 压缩后缀数组，是后缀数组的压缩表示形式，由g r o s s i 和v i t t e r 在2 0 0 0 年提出。 实验证明在最坏情况下，这种索引机制最多只需要( 1 + o ( 1 ) ) n l o g i j 位的存储空间，就 可以实现o ( m l o g i i n + l o g 酊n ) 的查找时间，其中为任意常数，且o s 1 【1 5 j 。 压缩后缀数组有效地解决了后缀数组空间开销大的问题，并且由于它支持对子串 的查找使得应用范围更加广阔。其研究内容使得后缀数组技术在文本数据库( 电子式百 科全书、网上词典等) 、w 曲搜索引擎( g o o g l e 、a l t a v i s t a 等) 、生物信息学( 基因数据库 等) 等领域有了更为重要的应用。在后续章节中，将对压缩后缀数组的构造过程进行 详细介绍，并对构造算法迸行性能分析。 中山人学硕：学位论文压缩后缀数组构造算法的改进 第三章压缩后缀数组的构造及应用 3 1 基本概念和符号定义 字符集1 2 】：一个字符集是一个建立了全序关系的集合，也就是说，中的任意 两个不同的元素0 c 和p 都可以比较大小，或者a p ，或者p p ) 。字符集 中的元素称为字符。 字符引1 2 】：一个字符串s 是将n 个字符顺次排列形成的数组。s 的第i + 1 个字符 表示为s 【i ( 这里我们规定o i n ) 。 子串【】2 】：字符串s 的子串s i j 】，i 匀，表示s 串中从i 到j 这一段，也就是顺次排 列s i 】s i + l 】s d 形成的字符串。子串s 【i j 】的长度表示为l e n ( s 【i j 】) ，显然l e n ( s ) = n 。 后缀【1 2 】：后缀是指从某个位置i 开始到整个串末尾结束的一个特殊子串。字符串 s 的从i 开头的后缀表示为s u m x ( s ，i ) ，也就是s u m x ( s ，i ) = s i n - 1 】。 字符串比较【1 2 】：即通常所说的字典顺序比较，也就是对于两个字符串u 、v ， 令i 从1 开始顺次比较u i 】和v 【i 】，如果相等则令i 加1 ，否则如果u i 】 v ( 也就是v l e n ( u ) 或者l e n ( v ) 仍未比较出结果，那么如果l e n ( u ) v 。从字符串的大小比较的定义来看，s 的两个开头 位置不同的后缀u 和v 进行比较的结果不可能是相等，因为u = v 的必要条件l e n ( u ) = l e n ( v ) 在这里不可能满足。 本文约定一个字符集和一个字符串s ，设l e n ( s ) = n ，并且s 以一个不属于字符 集的特殊字符$ 结尾，其他字符都属于，$ 小于中的任何一个字符。对于约定的 字符串s ，从位置i 开头的后缀直接写成s u m x ( i ) ，省去参数s 。 9 3 2g r o s s i v i t t e r 构造方法 2 0 0 0 年，g r o s s i 和v i t t e r 提出了压缩后缀数组这种数据结构【15 1 ，2 0 0 3 年加以改进 【2 2 】。本章节将详细描述g r o s s i v i t t e r 构造算法的思想和实现过程。 3 2 1 后缀数组的构造与查找 我们设定字符集= a ，b ，c ) 。以字符串s = a b b a c b a b a a c a b c a $ ，为例，构造s 的后缀 数组s a 。 1 根据上一节的定义，得到下标与后缀的对应关系如图3 1 所示： su f f i x i abbacbabaacabca $ 0 b bacbabaacabca $ bacbabaacabca $ acbabaacabca $ cbabaacabca $ babaacabca $ abaacabca $ baacabca $ aacabca $ acabca $ cabca $ abca $ bca $ ca $ a $ $ 图3 1 卜标与后缀的对应关系图 2 3 4 5 6 7 8 9 m 挖 h 中山大学硕卜学位论文压缩后缀数组构造算法的改进 2 对s 的所有后缀进行字典排序，结果如图3 2 所示。 s or t e ds u f f i xi $l5 a $l4 aacabca $8 aba acabca $6 abbacbabaacabca $o abca $l l acabca $9 acbabaacabca $3 baacabca $7 baba acabca $5 bacbabaacabca $2 bbacbabaacabca $1 bca $ l2 ca $l3 cabca $lo cbabaacabca $4 图3 2 字典排序后的斤缀 3 把指针下标依次存入后缀数组s a 中，如图3 3 所示。 图3 3 后缀数组存储图 4 在已经排好序的后缀数组中对字符串进行查找操作，可以通过二分查找实现。 图3 4 描述了查找模式串b a c b a b a a c a b c a $ 的过程。其中数字箭头表示操作的顺序。 3 2 2 压缩后缀数组的构造 图3 4 后缀数组奄找过稃 压缩后缀数组支持以下两种基本操作： ( 1 ) 压缩操作c o m p r e s s ：把一个后缀数组s a 进行压缩； ( 2 ) 查找操作l o o k u p ( i ) ：给定( 1 ) 中得到的压缩表示形式，返回值s a 【i 】。 压缩后缀数组的主要性能指标是执行l o o k u p 操作的查询时间，压缩后缀数组占用 的总内存空间和c o m p r e s s 压缩操作的预处理时间。 压缩后缀数组构造的一般步骤是( 其中i l o = n ，s a o = s a ) 【1 5 】： 第一步：生成一个有n k 位的位数组b k ，如果s a k i 】是偶数，则b k i 】= 1 ；反之， 如果s a k 【i 】是奇数，则b k 【i 】= o ； 1 2 第二步：定义一个函数、| ，k ，如果s a k 【i 】是奇数并且s a k d 卜s a k 【i 】+ 1 ，、i ，k ( i ) _ j ；否 中山大学硕- j 学位论文 压缩后缀数组构造算法的改进 则v k ( i ) = i ，其中1 i n k 。如果、i ，k ( i ) _ j ，就可以得出b k i 】= 0 和b k d 】- 1 。所以、l ，k 函数 的取值可以用如下的公式表示： l 吵k = 0 若s a “u 碧萧数且s a “j 】= s a “i 】+ l ； ( 3 1 ) 第三步：定义函数r a l l l ( k ，用它来计算b k 中1 的数目。r a n k k d 】等于b k 中前j 位中 的l 的数目； 第四步：将s a k 中所有的偶数都除以2 ，结果组成一个新的关于 o ，1 ，n k + l 。1 ) 的 排列的数组s a k + i ，其中n k + l = n k 2 = n 2 。+ 1 。 通过上面四个步骤，后缀数组s a 的长度就可以减半。经过l 步，其中l = l o g l o g n 之后，后缀数组s a 的长度就减为原来的1 2 l 。通过以下公式，就可以从s a l 得到原 来的后缀数组s a 。 s a k 【i 】。2 s a k + i 【m n k k ( 帆( i ) ) 】+ ( b k 【i 一1 )( 3 2 ) 这是个递归调用的过程。在整个压缩过程中，第k 级( 0 s k l ) 的b k 、v k 和r a n l ( k 都需要保存下来，但s a k 则不需要保存。在最后一级即k = l 时，s a l 保存下来，而b l 、 v l 和r a n k l 就不再需要了。从公式3 2 可以看出从s a l 检索s a 的过程是一个递归过 程，所以检索函数l o o k u p 也是一个递归过程，用伪代码表示如下所示： 图3 5s a 还原过程伪代码 例如，给定字符串s = a b b a c b a b a a c a b c a $ ，字典排序后得到初始后缀数组s a o 。按 照上述四个步骤，对s a o 进行压缩。分别计算数组b o 、函数r a n l ( o 和函数、i ，o 。经过第 四步得到一个新的数组s a l ，它存储的是原字符串s 中起始于偶数位置的后缀指针， 如s a l 3 】0 表示字典排序后，偶数位中排名第四的后缀从原串s 的第2 木0 = 0 个位置开 始。从s a o 中我们看到，偶数位的字典排名为1 4 ，8 ，6 ，0 ，2 ，1 2 ，1 0 ，4 。排名第 四的后缀下标为0 。可见从s a l 可以f 确地还原s a o 。具体如图3 6 所示。 1 4 l0l234567891 0l l1 21 31 41 5 sabb a cb a baacabc a $ s a o 1 5 1 48 6 0 1 1 93 75 2l 1 2 1 3 1 04 b o 0ilil0ooo010l0l1 r a n l ( 0 0l23444444556678 o l2 3 41 2 1 4 1 5 23 1 01 01 2l1 41 5 s a l 7430l652 图3 6 ( a ) 压缩后缀数组的构造过程 lo1234567 s a l 743ol652 b 1 0lolo101 r a n k l 01l 22334 、i ，1 0ll37 557 图3 6 ( b ) 压缩后缀数组的构造过程 中山人学硕上学位论文 压缩后缀数组构造算法的改进 l0l23l0l10 s a 2 2o3l s a 3 los a 4o b 2 11o 0 b 3 0l b 4 l r a n k ，l222 r a n k 3 01r a n k 4l 、i ，2 0 l20 、l ，3 ol 、i ，4 o 3 2 3 构造算法性能分析 图3 6 ( c ) 压缩斤缀数组的构造过程 分析g r o s s i 和v i t t e r 的压缩后缀数组构造算法之前，我们先引入下面的定理1 1 1 5 】， 在2 0 0 0 年，k u n i h i k os a d a k a n e 证明了该定理中的复杂度问题【2 6 】。 按照第三章描述的构造算法，在第l 层得到的后缀数组s a l 最多包含n l o g n 个输 入，所以最多需要n 位存储空间。我们用小于2 n 位的空间保存显式的位向量b o ，b 一 b l 1 ，同样保存隐式的向量r a n k o ，r a n k l ，r a n k l 1 和、i ，o ，、i ，l ，、i ，l - l o 如果能够 在常数级时问内获得隐式的r a n k k 和、i ，k ，那么通过公式3 2 ，每一层的l o o k u p 都可以 达到常数级，整体时间可以达到o ( 1 0 9 l o g n ) 。对于0 2 的一般字符集，得到定理2 【1 邹。 定理2 ( 一般字符集) 给定由长度为n 1 的字符集中的字符串建立的后缀数组s a ： ( 1 ) c o m p r e s s 压缩操作可以用( 1 + i o g i o g 舯) n l o g f f + 5 n + o ( n l o g i o g n ) = ( 1 + n l o g l o gj i n ) n l o g i l + o ( n ) 位，0 ( n l 0 9 1 i ) 的预处理时间米实现，以便每i ! 久调 用l o o k u p ( i ) 函数一j 用o ( 1 0 9 l o g i l n ) 的时间。 ( 2 ) c o m p r e s s 压缩操作可以用( 1 + 。) nl o g i j + 2 n + o ( n l o g l o g n ) = ( 1 + “) n l o g i i + 0 ( n l o g l i ) 位，o ( n l o g i i ) 的预处理时间来实现，以便每次调用l o o k u p ( i ) 函数占用o ( 1 0 9 5 l l n ) 的时间，其中是任意一个| 司定值并且o s 1 。对l l - o ( 1 ) ， 空间范罔降为( 1 十。) n l o g i i + o ( n i o g l o g n ) = ( 1 + 。) n l o g i i + o ( n ) 位。 按照字符串关联度为o 的熵h o s l o g i i ，重新声明第二条定理，可以得到s 。h o n + o ( n ) 位。关于如何得到关联度为h 的熵，即h h n + o ( n l o g l o g n l o g f f n ) 位( 这里h h i o ) ， g r o s s i 、g u p t a 和v i t t e r 已经给出方法【2 7 1 。当我们需要记录几个相近的输入，比如字符 串模式匹配中的枚举，l o o k u p 函数可以提高运算速度。令l c p ( i j ) 表示后缀s a 【i 和s a d 的最长公共前缀的长度，约定当i n 时，l c p ( i j ) = 一o 。如果l c p ( i - 1 ，j ) 和 l c p ( i ，j + 1 ) 都严格小于l c p ( i ，j ) ，我们就说s a 中的下标序列i ，i + l ，j 是最大的。 s a 中最大的序列对应着模式串t 的所有出现。 对于1 0 0 k u p ( ) 的处理有如下的定理3 【1 5 j ： 1 6 中山大学硕十学位论文 压缩后缀数组构造算法的改进 定理3 ( 1 0 0 k u p 的批处理) 在定理1 、2 中提及的任意一种情况，通过额外的o ( n l o g i i ) 位空间和j - i + 1 次调用l o o k u p ( ) 的批处理过程：1 0 0 k u p ( i ) ，l o o k u p ( i + 1 ) ，l o o k u 刚) ，其中i ， i + l ，i 是最大序列，得剑总的复杂度： ( 1 ) 当l c p ( i ，j ) = o ( 1 0 9 1 + 8 n ) 时，o ( j i + ( 1 0 9 n ) 1 + 8 ) ( 1 0 9 i l + l o g l o g n ) ) 的时间复杂 度，也就是s a i 】和s a d 】所对应的后缀有共同的o ( 1 0 9 1 + 6 n ) 个前缀字符。 ( 2 ) 当l c p ( i ，j ) = o ( 1 0 9n ) 时，o ( j i + n “) 的时间复杂度，也就是s a i 】和s a d 】 所对应的后缀有共同的0 ( 1 0 9n ) 个前缀字符。其中g 【是常量，且0 仅 l 。 通过对该构造算法的分析，得出这样的结论：算法用于查找的时间为 o ( m i n m l o g i i ，m + l o g n ) ) ，所需空间为( 。+ o ( 1 ) ) n l o g i i