（计算机软件与理论专业论文）后缀数组诱导排序算法的优化.pdf

中山大学硕士论文 后缀数组诱导排序算法的优化 专业：计算机软件与理论 硕士生：赵明先 指导教师：农革副教授 摘要 后缀数组构造算法是建立大文本全文索引最主要的方法之一，在网络w e b 搜索以及生物信息学( 基因数据库) 等领域，有极其重要的应用。由于这方面应用 处理的数据是数于亿计的字符，高效的后缀数组构造算法对于数据库索引的建立 至关重要。 本文基于对一种新的诱导排序算法的分析，针对其使用空间过多，分析了诱 导过程三个重要性质，在此基础上优化了类型数组的存储并改进了诱导过程，实 现了优化后诱导排序过程算法，并从理论上证明了诱导过程的正确性；然后分析 了l m s 字符的一个重要性质，在此基础上完善了l m s 字符信息的存储，接着结 合诱导排序构造后数组算法思想实现了后缀数组构造算法。 本文中改进的新算法，在不引入额外空间的情况下，找到消去类型数组存储 空间的方法且增加的时间消耗甚微。为了验证优化后诱导排序算法的可行性及其 运行效率，我们对所实现的诱导排序构造算法与k s 、k a 和i s 算法进行对比实 验，在c a l l t e r b u 巧和m a n z i n j f e r r a 西n a 数据集上进行验证和性能分析。实验结果 显示优化后实现的构造后缀数组算法执行时间比k a 算法快3 0 9 ，比k s 算法 快2 1 8 2 ，实验数据表明优化后诱导排序算法可在节省算法存储空间的同时， 有效的保持算法执行效率，显示优化后的诱导排序算法具有较好的时间空间性 能。 关键字：诱导排序，分治递归，后缀数组，类型数组，算法设计 后缀数组诱导排序算法的优化 o nt h eo p t i m 娩a t i o no fa ni n d u c e d s o r t i n gs u 毋6 区 a r r a y c o n s t r u c t i o na l g o r i t h m m 面o r ：c o m p m e rs o 小a r ea n dt h e o 巧 n 锄e ：m i n g x i a nz h a o s u p e r v i s o r ：g en 0 n g a b s t r a c t s u m x a r 】r a yc o n s n c t i o na l g o r i t l l h l ，a so n eo ft l l em o s ti i l l p o i r t a n tm e m o d sf o r b i g 矗j ut e x ti n d e x i n g ，h a ss i g n i f i c a n ta p p l i c a t i o n si nt h ef i e l do fi n t e m e ts e a r c l l i n g ， b i o l o g i c a li n f o r n l a t i o ns c i e n c e s ( g e n o m ed a t a b a s e ) a n ds oo n s i n c et 1 1 ep r o c e s s i n g d a t ai so r e nm e a s u r e di nb i u i o n so fc h a r a c t e r s ，t od e s i g nam o r et i m e - s p a c ee m c i e n t a l g o r i t h mf o rd 撕b a s ei n d e x i n gi so fg r e a ti m p o n a i l c e i nt h j s t h e s i s ，、e删y z ear e c e n t l yp u b l i s h e di n d u c e d s o r t i n ga l g o r i 也m a i m m i n ga to v e r c o m i n gi t ss h o r t a g eo fe x c e s s i v eu s eo fs p a c e ，w ep r e s e n tt h r e e i m p o m i n tp r o p e r t i e so ft h ep f o c e s so fi n d u c t i o n ，b a s e do nt h e s e ，w eo p t i m i z et h e s t o r a g eo ft y p ea r r a y ，i m p r o v et h e i n d u c t i o np r o c e s s ，a n dt h e n c a r r yo u t i t s i m p l e m e n t a t i o n a r e rt h a t ，w ep r o v et h a tt h ep r o c e s so fo p t i m i z e di n d u c e d s o r t i n gi s c o r r e c t f u n h e m o r e ，w eo p t i m i z et h es t o r a g eo fl m sc h a r a c t e r si o n n a t i o nb y r e v e a l i n ga ni m p o r t a n tp r o p e r t yo fl m sc h a r a c t e r s c o m b i n gw i t ht h ei d e ao ft h e i n d u c e d s o r t i n gc o n s t m c t i o na l g o r i m mo fs u m xa r r a y ， w ea l s oi m p l e m e n to u r o p t i m i z e da l g o r i t l l n l t h eo p t i m i z e da l g o r i 伽np r o p o s e di nt h i sp a p e rc a na v o i du s i n gt h e 咖e 卸7 锄dw i t h o u ti n t r o d u c i n ga d d i t i o n a lm e m o r 乳、v h a t st h em o s ti n t e r e s t i n gi s 也a ti t i n c r e a s e sn m n i n gt i m es l i g h t l y i no r d e rt ov e r i 母t h ef e a l s i b i l i t yo ft h eo p t i m i z e d i n d u c e d 。s o r t i n ga l g o r i t h m ，as e r i e so fe x p e r i m e n t sa r ec a r r i e do u tt oe v a l u a t et h e p e r f b 姗a n c e so ft h e s ea l g o r i t h m s ，i n c l u d i n gk sa l g o r i t h m ，k aa l g o r i t l l ma n di s a l g o r i t w i mt h es a m ec o n f i g u r a t i o n1 1 l i 】n i n g o nt h ec a n t e r b u r ya n d m a n z i l l i f e r r a g i n ac o r p u s t h ee x p e “m e n t a lr e s u i t ss h o wt h a t ， m eo p t i m i z e d i n d u c e d s o n i n ga l g o r i t b mg a i n sa ni n c r e a s ei ns p e e do f3 0 9 o v e rt h ekaa l g o r i t a n d218 2 o v e rt h ek sa l g o r i t h m t h ee x p e r i m e n t a ld a t as h o w st h a tt h eo p t i m i z e d i i l d u c e d s o r t i n ga l g o r i t h mn o to i l l ys a v e st h es p a c eo fs t o r a g e ，b u ta l s oh a sa ne 伍c i e n t p e r f o 订1 1 a n c ei nt h et i n l e k | 猡 w o r d s ： i n d u c e d - s o r t i n g ，d i v i d e a i l d - c o n q u e r ， s u 伍xa r r a y ，t y p e螂 a l g o r i t d e s i g n 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：叁最先 日期：上时年多月j 日 学位论文使用授权书 本人完全了解中山大学有关保留、使用学位论文的规 定，即：学校有权保留学位论文并向国家主管部门或其指定 机构送交论文的电子版和纸质版，有权将学位论文用于非赢 利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：趣明兄 日期：j 绰箩月了日 导师签名： 日期：伽铲 日 中山大学硕士论文 1 1 研究背景 第一章引言 随着网络的发展和基因图谱的破解，在浩瀚的网络资源及庞大的d n a 系列 中获取所需要的信息成为学者们研究的热点【l j 。浩瀚的网络资源及庞大的d n a 系列，可以看作是一个大文件，而要查找的信息以及要处理的d n a 系列就是一 个模式字符串，那么以上问题可以简化为这样一个模型：在一个长度为n 的大文 本字符串t 中，查找或者获取长度为m 的模式串p 的信息。这里所说的查找， 通常有三种类型【1 】：1 ) p 是否出现在t 中? 2 ) p 在t 中共出现几次? 3 ) p 在t 的 什么位置出现? 而且这里所说的查找必需支持多次高效的特点。网络资源是人们 所共享的，也就是说这种查询要满足谁都可以去获取自己想要的信息；基因信息 学中，重复分析在学习、分析和比较整个基因组具有重要的作用，例如获取重复 基因片的特征或者基因识别中1 2 】，都需要反复研究d n a 系列的特征。很明显， 在这种应用环境下，简单字符串模式匹配算法根本不能满足需求，一般来说，在 这么庞大的文件中进行多次高效的查询一定要借助于特定的数据结构。针对这种 情形，学者们提出了多种文本索引结构，其中比较流行的有【l j ：倒排文件、后缀 树以及后缀数组。 应用在网络查询中的结构就是倒排文件，倒排文件【3 j 是对关键字索引的排 列，其中每个关键字对应包含它的文本。倒排文件对索引文本是非常有效的，例 如英文文件，可以把它分解为一个个单词的集合，然后我们根据这些单词就能有 效的找到这个文件。但是对于其他非英文文件或者d n a 文件，这种索引就不方 便了，因为倒排文件是单词级别的索引f l j ，而一个模式匹配不一定是对一个完整 的单词进行查询，所以倒排文件适应的环境是很有限的。 后缀树【4 】是另外一种流行的文件索引技术，后缀树是对一个文本的所有后缀 建立以树形结构为基础的数据结构。后缀树允许我们查询文本的任意后缀，也就 是说它对文本的每个位置都进行索引，所以后缀树是一种全文索引技术。后缀树 后缀数组诱导排序算法的优化 1 4 主要研究工作及论文组织结构 1 4 1 主要研究工作 本文对后缀数组构造算法的出现、发展、主流构造算法思想、发展趋势和应 用进行了研究。在分析现存先进的后缀数组构造算法的基础上，深入研究了诱导 排序构造后缀数组算法的诱导排序过程。针对其中的不足，分析了诱导排序过程 三个重要性质，在此基础上优化了类型数组的存储并改进了诱导过程，从理论上 证明了改进诱导过程的正确性，以极少的时间消耗减少了d ( 刀) 的空间存储，同 时还实现了优化的诱导排序过程。文章还对现有先进的诱导排序构造后缀数组算 法进行研究，分析了l m s 字符的一个重要性质，在此基础上完善了消去类型数 组后，l m s 字符信息存储问题，然后结合优化的诱导排序过程实现了一个新的 诱导排序构造后缀数组算法，并对实现的构造算法与现今最有效的三个后缀数组 构造算法进行实验验证及对比，从而证明了新的诱导过程的正确性以及实现的诱 导排序算法的有效性。 1 4 2 论文组织结构 本文共分五章。 第一章引言部分介绍了后缀数组的研究背景，并主要描述了后缀数组构造 算法的出现、发展情况、发展趋势、应用及研究意义。最后对论文研究内容和组 织结构进行了说明。 第二章详细介绍了后缀数组构造算法思想，并对三大主流构造算法性能进 行了分析与对比。 第三章在深入分析诱导排序构造后缀数组算法的诱导过程基础上，分析了 诱导过程三个重要性质，在此基础上详细描述了在消去类型数组后，诱导排序过 程的改进以及步骤，从理论上证明了改进诱导过程的正确性，实现了优化后诱导 6 中山大学硕士论文 排序过程；文章还对现有先进的诱导排序构造后缀数组算法进行研究，分析了 l m s 字符的一个重要性质，在此基础上完善了消去类型数组后l m s 字符信息存 储问题。然后用实现的诱导过程结合i s 算法【2 7 】构造后缀数组思想实现一个后缀 数组构造算法。最后对实现的后缀数组构造算法评价其时间空间性能。 第四章将优化后实现的后缀数组构造算法与现今先进的后缀数组构造算法 k a 、k s 和i s 算法进行对比实验，验证优化后诱导过程的正确性，以及算法在 消去类型数组的基础上保持执行效率的能力，从而使实现的算法能够应用于实 践，并比较它们的空间消耗。 第五章总结文章并提出有待改善的地方。 7 后缀数组诱导排序算法的优化 第二章后缀数组算法介绍 2 1 符号和名词介绍 字符集【5 1 一个字符集是一个建立了全序关系的集合，也就是说，中 的任意两个不同的元素a 和卢都可以比较大小，要么a 卢，要么卢 卢) 。字符集中的元素称为字符。 字符串【5 1s 一个字符串s 是将n 个字符顺次排列形成的数组，n 称为s 的 长度，表示为l e n ( s ) 。s 的第i 个字符表示为s i 】，s = 【x 。也屯一l $ 】，其中 $ 代表小于任何源文本字符的文本结束符。 子串【5 1s i j 】字符串s 的子串s i j 】，i 0 的后缀j ，把i 放在桶的当前头位置并且头位置向前移一位， 1 0 后缀数组诱导排序算法的优化 的额外空间存储( 用来存储i s a 整型数组) ，算法时间复杂度为d 0 l o g 刀) ，但实 际上算法比m m 算法运行快很多。 上面只是列举了部分倍增算法的实现思想，从算法k m r 到l s ，算法都是 基于这种思想实现的，说明这期间算法一直围绕这种倍增思想实现，虽然算法在 实现上一直在进步，但始终没有实质型的改变，下面讨论诱导拷贝思想实现的后 缀数组构造算法。 2 2 2 诱导拷贝算法系列介绍 这类算法设计很巧妙，通过排列好的字符后缀直接推出未排列或者全部后缀 的顺序，所以排列是快速的。不过根据排列选定的字符后缀方法的不同，算法的 时间复杂度也有所不同。而非递归实现的诱导拷贝算法系列往往最坏时间复杂度 是d 研21 0 9 ”) ，这类算法空间消耗大部分都是轻量级的。下面介绍几种典型的诱 导拷贝算法思想。 h n o h 和h t 趾a k a 【1 2 1 在s 算法的基础上引进了舳类型的概念，他的算法 思想是先排列b 型的后缀，然后由排列好的类型b 的顺序排列类型a ，具体做 法是这样的，先根据第一个字符把所有类型b 后缀放入相应的桶中，多于两个 字符的桶用多键快速排序算法排列，再由排列好的类型b 后缀排列类型a 后缀， 为了排列a 型后缀及所有字符的后缀，从左向右扫描s a ，对扫描到的后缀位置 i - s a 【j 】，假如i 1 是还未排列的a 型后缀，那么我们把i 1 放入对应的桶当前头 位置中并把当前头位置向前移一位。这样一直扫描到最后把所有字符的后缀排列 完全。除了排列b 型字符后缀，其他过程算法时间都是线性的，而排列b 型字 符后缀最坏情况是d 21 0 9 刀) 时间，所以算法整体最坏时间复杂度为d 21 0 9 刀) ， 但实际上，i t 算法执行速度是比较快的。而且算法使用的额外空间远小于n b y t e s ，所以算法也是轻量级的。 j s e w j 曲【1 3 】于2 0 0 0 提出了一个诱导拷贝算法。其算法思想是这样的：首 先线性排列字符串s 的2 前缀，在5 中，每个2 前缀组都用头数组分界，也用 来区分1 前缀组。那么1 前缀都对应一个前缀字符a ，现假设1 前缀排列好了， 1 2 后缀数组诱导排序算法的优化 我们选择的一个数) ，使用稍微改变的t s q s 方法排列。m f 算法实际运行时比较 快，使用的额外空间也小于nb y t e s ，但在最坏情况下需要d ( ，z 21 0 9 ，z ) 运行时间。 上面只是就几个诱导拷贝排序的算法思想做一个简单的介绍，诱导拷贝算法 设计往往比较巧妙，在实际运行中也比较快，使用的空间也大都是轻量级的，所 以在后缀数组构造算法中比较常见，但是这类算法在最坏情况下时间复杂度往往 比较大，甚至达到d ( 聆2l o g ，z ) ，所以在很多情况下，其算法运行不稳定。现今理 论上时间复杂度最好的是分治递归系列算法，其最坏时间消耗是线性的，相对来 说运行比较稳定，下面讨论基于分治和递归思想实现的后缀数组构造算法。 2 2 3 分治与递归算法系列介绍 分治和递归系列算法是现今最先进的后缀数组构造算法系列，它的主要思想 是：选取部分子串，按一定的线性方法排列它们，然后根据排好的顺序给选定的 字符子串命名，产生一个缩短的字符串，然后递归排列缩短字符串直到能够直接 计算出它们的后缀顺序，再一步步返回到选定字符子串并排列其后缀顺序，最后 根据排好的选定字符后缀排列未选定的字符子串后缀，最终得到所有字符的后缀 序列。下面就几个典型代表详细介绍每种算法思想。 d k 飚m ，j s s 疏，h p a r k 和k p a r k 【1 9 1 于2 0 0 3 年提出一个线性时间构造 后缀数组的算法，算法思想如下：一个大小为n 的字符串s ，先排列奇数位的后 缀数组5 ，把奇数位的一对子串( s 2 f 一1 】，研2 f ) ( 对每个1 f 刀2 ) 通过基数排 序排列，这可以在线性时间完成，假如排列后的系列没有相同的，也就是说通过 前两个字符就可确定奇数位后缀的顺序，那么就可以直接下面的计算，否则根据 排列的顺序命名各后缀得一个新的缩短串s ，递归构造字符串s 的后缀，再一 步步返回就可以得到各奇数位后缀的序列；因为一个偶数位后缀可以表示为 【s 2 i 】，是】，而是的相互顺序可以从瓯中获得，那么用基数排序法可以在线 性时间排列各偶数位后缀；最后，归并和阻。归并步骤是k s p 算法的核心 且都比较复杂，所以在实际的使用中不常见和本算法也没有太大的关联，所以不 1 4 中山大学硕士论文 做详细介绍，详细介绍可以参考文献【1 9 】。因为在算法的每一步都是线性时间的， k s p 算法时间复杂度为d ( ，| ) 。由于这个算法的归并步骤比较复杂，至今尚未有一 个有效的实现，所以在实际的使用中很少用到。 j k 诎菹i 1 1 e n 和p s a l l d e r s 【2 0 1 于2 0 0 3 年也提出了一个线性构造后缀数组的算 法，算法主要思想也是分治和递归，但他选取的字符是每三个字符一组的子串 s 瞰+ 2 】( 其中f 3 0 ) ，排列这些子串也是用基数排序法，根据排列顺序对每 三个字符一组的子串s 儿f + 2 】命名得到缩短字符串s ，假如所有子串都有不同 的名字，那么继续下一步，否则递归构造s 后缀数组，然后一步步返回，这样就 可以排列好所有i 位( f 3 0 ) 的后缀顺序，因为所有i 位( ，3 = o ) 可以看成是一 对( s i ，s + 1 ) ，而s + l ( 对f 3 = o ，( i + 1 ) 3 = 1 ) 是已经排列好的后缀，这样通过多键 基数排序可以得到各i ( f 3 = o ) 位的后缀数组顺序，最后归并两排列好的后缀即 归并i ( f 3 0 ) 和j ( 歹3 = o ) 位的后缀，相对k s p 算法，k s 算法的归并比较简 单，对i 3 = 1 的后缀，我们把s 和墨分别看成( s i 】，s + ) 和( s d 】，邑+ ，) ，因为 ( i + 1 ) 3 _ 2 、( j + 1 ) 3 = 1 ，所以s + 1 和sj + l 的相互关系已经知道，对i 3 _ 2 的后缀， 我们把s 和s ，分别看成( s i 】，s 【i + 2 】，s + 2 ) 和( s d 】，s 【j + 1 】，s ，+ 2 ) ，因为( i + 2 ) 3 = 1 、 ( j + 2 ) 3 = 2 ，所以s + ：和s m 的相互关系已经知道，这样可以在线性时间归并两有 序后缀数组。k s 算法较k s p 算法，设计简单和空间消耗小。 所有算法的时间复杂度可以用一个递归公式丁( 刀) = 丁( - 2 ，z 3 ) + d ( 刀) = d ( 玎) 表示。k s 声称空间复杂度为d ( 堋) 另外需要d 0 v ) 的额外空间( 这里 1 ，= d ( 石) ) 。 图2 1 采用文献 2 0 】中例子的形式演示了k s 算法构造字符串s = t s h s i m s i l l 】【i l i 的后缀数组的排序过程。首先在第4 行对所有i 位( f 3 o ) 三个字 符一组的子串用基数排序法排列好，当不能直接得出所有i 位( f 3 0 ) 三个字符 一组的子串的后缀排序时，如第5 行所示，由于存在两对相同的子串，所以递归 后缀数组诱导排序算法的优化 图2 1 k s 算法应用于排列字符串s = t s i i i l s i m s m m i 排列所选定的子串，否则直接计算第下步；最后根据得到的选定子串的后缀顺序 如第7 行所示，得出所有i ( i 3 一o ) 位的后缀顺序，并对两个排列好的子串归并 为字符串s 的后缀数组，如第1 1 行所示。 p k o 和s a l u r u 【2 2 】也在同一年发表了他们的后缀数组构造算法。k a 算法 和前两种算法选取的子串不同，它选取的是s 型的后缀，它算法的主要思想是： 先排列好所有的s 型后缀，再根据排列出的s 型后缀诱导出所有字符的后缀。k a 算法排列s 型后缀也是用递归的方法，不过在构造缩短子串进行递归前，是用一 种特殊的结构来排列s 型子串并对其命名，这种结构称为s d i s t a i l c e 数组和列表， 借助于这样一个结构，能够排列所有的s 型子串并对相应的s 型子串命名得到 新缩短字符串s ，当s 中字符都不同时，可以直接构造s 的后缀，否则递归计 算s 的后缀，最后从s 的后缀排列所有字符的后缀。值得一提的是，根据s 的 后缀顺序能知道s 型对应字符的相对顺序，p k o 和s a l u i 【2 刁引理2 告诉我 1 6 中山大学硕士论文 o o 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 l2 3456 7 8901 njt ttjt tjt$ ssss s 型后缀顺序： 桶$ 第二步后 1 1 11962 j n ( 962 ) 1 ( 962 ) 1 ( 962 1 f 962 l 位置 字符串s 类型 s 型字符后缀顺序 t 45 7 81o ) 后缀数组s a o 45 7 8 3 0 8 4 7 5 3 ) o 8 5 743 图2 2 演示k a 算法从排好的s 型后缀排列所有字符后缀 们s 后缀两元素的相对关系和s a 中两元素的相对关系是一样的。总体来说k a 算法相对前面的算法在时间空间性能方面都有所改善，只借助了s d i g c a l l c e 数组 和列表这样的结构，增加了一定的空间消耗。 据k a 所说，算法时间复杂度为：丁( 刀) = 丁( _ 珂2 ) + d ( 拧) = d ( ，z ) ，对于一个 不大于2 3 2 的字符串，需要3 nb y t e s 加上1 2 5 nb y t e s 的额外空间。 k a 算法最大的亮点就是诱导排序过程的提出，其诱导过程如上图2 2 所示 ( 采用文献 2 2 】中例子形式) ，我们对s = 玛t t t i t i ；j t $ 演示k a 算法诱导排序的过程。 算法首先把所有的字符分为l 型和s 型并用上面所说方法把所有的s 型子串后 缀排列好如第4 行所示。现在根据排列好的所有s 型字符用诱导排序法排列所有 的字符后缀：首先看到第6 行，从左向右扫描s a ，第一个扫描到的是s a 0 】- 1 l ， 根据诱导方法下一个要排列的就是s 【s a 0 一1 】= t ，那么我们把1 0 放入t 桶当前 头位置且把当前头位置加向前移一位，然后扫描到s a 1 】- 9 ，因为s s a 1 】- 1 】= t ， 所以把8 放入t 桶当前位置且当前位置向前移一位，按照这种方式一直扫描 到s a 9 】- 4 ，因为s s a 9 】- 1 ：t ，所以把3 放入t 桶当前位置且当前位置向后 移一位，到这里所有的字符都排列好了，排列好的字符串s 的所有后缀顺序如第 9 行所示。 k a 算法的核心在于根据排列好的所有s 型后缀排列所有字符的后缀，这种 1 7 后缀数组诱导排序算法的优化 排序与i t 算法中根据b 型顺序排列a 型后缀有点类似：从左向右扫描后缀数组 a ，对每一个a 【i 】，假如a i 一1 是l 型的，把a i 一1 】移到当前桶开始位置且把当 前位置向前移一位，因为这种诱导排序算法简单易懂且效率极高，只需要少量的 辅助空间就可以一遍扫描排列所有的字符，所以很多学者对这种方法进行了研究 并提出了很多改进，i s 算法【2 7 1 提出的后缀数组构造算法对诱导过程进行了很大 的改进，其算法思想是这样的：算法结合诱导拷贝排序和分治与递归思想，为缩 短问题选择的是l m s 子串，利用诱导排序对所有选定l m s 子串并根据排列的 顺序命名每个l m s 字符后缀得到一个新的字符串s ，这样原字符串s 缩短为字 符串s ，。假如s ，中所有元素都不同，那么直接计算s 。的后缀数组；否则递归构造 s ，的后缀数组s a ，然后一步步返回直到计算出s ，的后缀数组s a l 。最后用类似 的诱导排序从s a l 排列出字符串s 的所有字符的后缀顺序，得到字符串s 的后缀 数组s a 。i s 算法较之前的算法明显有以下优点：使用巧妙的诱导排序方法排列 所选定的l m s 字符后缀；所选定的字符是l m s 字符，较其它分治递归算法， 缩减速度明显加快；对诱导过程进行了改进，加快了排序的速度。所以算法同时 具有分治递归和诱导拷贝思想的优点，在时间和空间上有了很大改进，不过除了 所必须的空间外，算法还引入了类型数值等结构。 i s 算法时间复杂度为：丁( 刀) = 丁( 胛2 ) + d ) = d ( 刀) ；除了构造后缀数组所 必需的空间外，算法使用了类型数组结构，空间利用率较高，空间复杂度为 d ( 疗l o g ，z ) 。 1 8 后缀数组诱导排序算法的优化 桶$ 和桶i 的当前位置；第二步，排列所有s 型字符，从左向右扫描s a ， 对每个s a 【i 】，假如s s a 【i 】1 】是l 型的，把s s a i 】- 1 的下标放入对应桶的当前 头位置且向右移一位头位置。如第l o 行所示，对s a 【0 】- 8 ，其s s a 【0 - 1 】字符是 l 型且属于p 桶，所以把小标s a 【o 1 放入p 桶当前头位置。这样一直扫 描到最后；诱导第三步，排列所有s 型字符，从右向左扫描s a ，对扫描到的每 个s a i ，假如s 【s a i 】- 1 】是s 型字符，那么把字符s s a i 】- 1 】的下标放入对应桶 当前末位置且向左移一位末位置。如第2 4 行所示，对s a 8 ，s 【s a 【8 - 1 】是s 型 字符且属于i 桶，所以把s s a 8 】1 】放入i 桶当前末位置且把当前末位置 向左移一位。这样一直到最后如第3 4 行所示，最后给所有l m s 字符按它们排列 的顺序命名，如第3 6 行所示。 2 3 算法性能分析与对比 上一节介绍了后缀数组构造算法，根据算法思想把它们分为倍增算法、诱导 拷贝算法和分治与递归算法，现对三种算法的性能进行简单的分析与对比。 倍增系列算法时间复杂度一般为d l o g ，2 ) 。其构造过程一般是这样：首先 对后缀的k 前缀进行排序，再利用m s d 基数排序和多关键字快速排序等方法， 在线性时间直接推出其后缀的2 k 前缀排序系列，所以一步就可以排列其2 k 的前 缀，接着下一步就是4 k 前缀，一直到最后2 肼，z 就可以排列所有的后缀。这样 经过- 1 0 9 咒 步对k 前缀进行排序，每一步时间复杂度为d 0 ) ，所以算法总体时 间复杂度为d ( ”l o g 玎) ，因为这类算法一般是对后缀的k 前缀排列，并借助于一 定的结构计算2 k 前缀的顺序，所以空间复杂度一般比较大且与具体算法实现有 关。 诱导拷贝算法设计往往非常巧妙，其思想大体是这样的：首先按一定的方法 排列选定的后缀，然后根据排列好的后缀直接排列未排列的字符后缀，这种排列 一般不需要额外的辅助空间而且在d ( ，2 ) 时间排列好。诱导拷贝算法时间消耗主 要集中在排列采样的字符后缀上，采样的方法不同，算法的时间复杂度也不同。 中山大学硕士论文 2 2 节介绍的诱导拷贝算法排列选定的后缀一般是采用普通的字符串排列算法， 例如多键快速排序算法等，所以最坏时间复杂度一般比较高，有些甚至达到 d ( 刀2l o g 刀) 。但是这类算法在实际使用中，算法执行往往比较快，而且一般使用 的额外空间是常数级的，也就是说算法是轻量级的，所以这类算法比较常用。不 过诱导拷贝算法有个最大缺点，其算法执行不稳定，对不同的字符串其执行速度 差别很大。 分治与递归系列算法时间复杂度为d ( 刀) 。其构造过程一般是这样：首先选 定特定的子串作为缩短的字符串对象，按一定的方法给选定的子串排序，假如能 够直接得出所有字符的后缀，跳到第三步；否则递归构造缩短字符串的后缀，最 后由构造好的缩短字符串后缀排列未选定后缀的字符串后缀以及所有字符的后 缀，因为整个算法过程中都是线性的，所以时间复杂度为d ( 疗) 。其空间消耗主 要在如何排列选定的子串上，除去存储后缀数组的4 nb y t e s 和存储要排列的字符 串的nb y t e s 空间，空间消耗主要在于存储字符表( 即子串和模式串的字母集) 、 存储所选取的子串以及有些算法中的字符类型，这类算法空间复杂度大致是 d l o g 聆) 。但不同的算法，其空间消耗差别也很大。 通过以上三种后缀数组构造算法的对比，容易得出倍增算法利用各后缀之间 的关系，用d ( 刀) 时间根据后缀的k 前缀排列各后缀的2 k 前缀，虽然算法时间和 空间复杂度较其他两者有一定的差距且现今使用不多，但这类算法最早提出利用 各后缀之间的关系构造后缀数组，给后来的后缀数组构造算法发展指明了一个方 向；诱导拷贝算法巧妙的应用各后缀之间的特殊关系，通过排列的部分后缀有效 的计算其他部分后缀的关系，这种计算不同于倍增算法的根据后缀的k 前缀排列 各后缀的2 k 前缀，只是通过简单诱导就能得出后缀的确定顺序。诱导拷贝算法 空间消耗较其它两者较优，空间复杂度一般是轻量级的，也就说只需要常数级的 额外空间；而分治递归算法是通过采样缩减原问题，把一个大问题分成一个个小 问题，然后把处理好的小问题结果应用到解决大问题，所以诱导算法的最坏时间 复杂度为最好的d ( 刀) ，其执行往往很稳定且理论上较其它两者快。现今最优秀 的算法是这两者算法思想的结合，比较典型的有k a 算法和i s 算法。i s 算法总 2 】 后缀数组诱导排序算法的优化 体思想采用分治递归，排列选定的字符后缀以及由排列好的字符排列所有字符的 后缀都采用诱导拷贝算法思想，是这两类算法思想的有效结合。本文的写作目的 就是在其算法基础上，降低其空间消耗，在保证算法线性执行时间的同时，使算 法的理论空间复杂度接近轻量级。 中山大学硕士论文 第三章后缀数组算法的优化及算法实现 通过前两章介绍，我们知道在k a 算法和i s 算法中引进了字符类型这个概 念也就是l 和s 型字符( l 和s 型字符及类型数组具体定义见2 1 节) 且线性构造 后缀数组算法的理论空间复杂度接近轻量级是后缀数组构造算法的发展趋势。本 文的写作目的就是在k a 和i s 算法的基础上，讨论优化类型数组的方法。因为 类型数组主要服务于诱导排序过程，所以先介绍上述算法的主要框架，并详细描 述其诱导排序过程。 3 1 新诱导算法介绍 i s 算法与k a 算法有所不同，不仅采样和诱导过程有所改进，而且把诱导应 用于排列l m s 子串上，在时间和空间上较后者都有大大的改善。算法结合分治 与递归和诱导拷贝两种后缀数组构造思想，其主要思想是：为缩短问题选择的是 l m s 子串，利用诱导排序对所有选定的l m s 子串排列并根据它们的排列顺序命 名每个l m s 子串，这样原字符串s 缩短为字符串s ，。假如s ，中所有元素都不同， 则可以直接计算s 。的后缀数组；否则递归构造s 。的后缀数组s a ，然后一步步返 回直到计算出s 。的后缀数组s a l 。最后用类似的诱导排序方法从s a l 排列出字符 串s 所有字符的后缀数组s a 。 诱导排序过程是以上两算法的精华，下面列出前者的诱导排序过程口7 】。其 诱导排列l m s 子串的第一步是把所有s 中l m s 子串根据它们首字母放进s a 的 对应s 型子桶中，这一步中同一个桶中的l m s 子串的排列顺序可以是任意的； 第二步是排列l 型字符后缀，找到每个桶的头位置，从左向右扫描后缀数组s a ， 对扫描到的删 刀，假如s 黝 f 】一1 】是l 型的，把副 f 】一1 根据首字母放到相应桶 的当前头位置且当前位置向右移一位；诱导排列的第三步是排列所有的s 型字 符，从右向左扫描s a ，对扫描到的剐 f 】，假如s 删 力一l 】是s 型，把删【司一1 放 中山大学硕士论文 整体性能。 3 2 2 诱导算法的几个重要性质 在介绍诱导算法的性质之前，先介绍一个概念：l m l 字符。 定义3 1 ( l m l 字符) 字符s i 】，i 【1 ，n _ 1 】，当s 【i 】是l 型字符且s 【i - 1 】是s 型 字符，那么字符s 嘲是l m l 字符。 很明显，l m l 字符的定义与l m s 字符的定义是对称的。诱导排序的第二步 是根据l m s 字符后缀排列所有的l 型字符，那么由l 、s 型字符定义的对称型， 第三步根据l m l 字符可以排列所有s 型字符。 下面讨论l m s 字符的一个重要性质。 性质3 1 字符串s 的所有l m s 字符s i ( 当s i 】是哨兵时，s i + 1 】不存在，而 哨兵一定是l m s ，这里不判断哨兵) 只在以下两种情况下出现： 1 ) s 【i 】 s i 一1 】且s 【i 】 s i + 1 】； 2 ) s i 】 s 嘲( 这里是 比较a s c i i 值或者字典顺序) ，就能断定s 【i - 1 】是l 型字符。现判断s 【i 】是s 型字 符，只有以下两种情况s i 】是s 型字符： 1 )s i 】 s 【i 】 且s i 】 s 【i 】，也就是说s i - 1 】是l 型字符，s 【i 】 是s 型字符，由l m s 字符定义，s 【i 】是l