（计算机软件与理论专业论文）最长公共子序列算法的改进和优化.pdf

中山大学硕士论文 最长公共f 序列算法的改进和优化 最长公共子序列算法的改进和优化 专业：计算机软件与理论 硕士生：孙冉 指导教师：农革副教授 摘要 一个给定字符串的子序列是在该字符串序列中删除0 个或者多个元素后得 到的序列。给定序列x = 毛，而，) 和y = m ，奶，蚝 ，设它们是定义在字符 集= q ，c r 2 ，嚷) 上的两个字符串，最长公共子序列( 简称l c s ) 问题就是 找出关于x 和y 的公共子序列中长度最长的子序列 在求解l c s 问题的众多算法中，由r i c k 提出的算法【1 5 , 1 6 】有着良好的性能， 该算法后来被g o e m a n 和c l a u s c n 做了进一步的优化和改进1 2 】。改进后算法的空 间复杂度为线性复杂度o ( n s ) 。然而当该算法应用于大规模序列( 如遗传基因序 列) 以及n l c s 问题的时候，空间依然会成为算法的瓶颈。如2 0 0 1 年4 月u c u s 人类基因组计划发布了人类基因序列，共包含2 8 亿对碱基，相应的字符串序列 为6 g ，如果用g o e m a n - c l a u s e nl c s 算法求解此问题时需要9 6 g 的存储空间， 而9 6 g 的空间已经超出了普通计算机的内存空间。因此空间的优化成了实践中 迫切需要解决的问题。 本文针对g o e m a n - c l a u s c nl c s 算法进行空间改进和优化，做了下面几点工 作：( 1 ) 对g o e m a n c l a u s e n 算法中的辅助数组的空间冗余进行优化；( 2 ) 对 辅助数组利用e l i a s 算法进行压缩；( 3 ) 对e l i a s 算法做进一步的优化和改进， 使辅助数组的数据压缩比进一步提高。改进后的算法保持了g o e m a n c l a u s e n 算 法的线性空间复杂度，但相对于原算法，空间得到了很大的节省，有效的克服了 l 中山大学硕士论文最长公共了序列算法的改进和优化 l c s 算法应用于大部分遗传基因序列和n l c s 问题时的空间瓶颈，但改进后的 算法对比原算法，时间性能上有一些损失，但是在面对大规模序列时候，空间因 素显得更为突出。 关键字：l c s 算法，基因序列，空间复杂度，压缩算法，优化 中ij j 大学硕上论文 最长公j 子序列算法的改进和优化 a l g o r i t h m sf o rl o n g e s tc o m m o ns e q u e n c e ：t h e i m p r o v e m e n ta n c io p t i m i z a t m n - 1 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 ：r a ns u n s u p e r v i s o r ：g en o n g a b s t r a c t a s u b s e q u e n c eo fx i sas e q u e n c eo fs y m b o l so b t a i n e db yd e l e t i n gz e r oo rm o r e c h a r a c t e r sf r o mx l e t x = 一，恐o6 ) a n dy = 乃，y 2 ，y b et w os t r i n g so v e r a na l p h a b e t = q ，o s o fs i z es t h el o n g e s tc o m m o ns u b s e q u e n c e ( l c s ) p r o b l e mi st of i n dac o m m o ns u b s e q u e n c eo fxa n dyt h a ti so ft h eg r e a t e s tl e n 班h a m o n gt h ea l g o r i t h m su s e df o rl c sp r o b l e m ，r i c k sm e t h o dh a sag o o d p e r f o r m a n c e ，a n di th a sb e e no p t i m i z e db yg o e m a na n dc l a u s e n t h ea l g o r i t h m s s p a c ec o m p l e x i t yc a na c h i e v eal i n e a rc o m p l e x i t yo fo ( n ) h o w e v e r , i ft h i sm e t h o di s a p p l i e dt oc o m p u t et h el c s f o rl a r g e s c a l es e q u e n c e s ( s u c ha ss o l v i n gt h eg e n e t i c s e q u e n c e ) o rn l c s ，t h er e q u i r e ds p a c er e m a i n sab o t t l e n e c ki nt h el c sa l g o r i t h m i n a p r i l2 0 01 ，t h eh u m a ng e n o m ep r o j e c tu c u sp u b l i s h e dt h eg e n es e q u e n c ew h i c h c o n t a i n sat o t a lo f2 8b i l l i o np a i r so fb a s e so fw h i c ht h ec o r r e s p o n d i n gs e q u e n c eo f t h es t r i n gw i l lr e a c h6 g - b y t e s oi ft h eg o e m a n c l a u s e nl c s a l g o r i t h mu s e dt os o l v e t h i sp r o b l e m ，i tw i l ln e e da r o u n d9 6 gb y t e ss t o m g es p a c e h o w e v e r , t h ec a p a c i t yo f 9 6 gb y t e sh a sa l r e a d ye x c e e d e dt h em e m o wa v m l a b l ei nm o s to f g e n e r a lc o m p u t e r t h u sh o wt oo p t i m i z et h es p a c eu s a g eh a sb e c o m ea na r g u m e n tt a s k 1 l i 中l l i 大学硕士论文最长公其予序列算法的改进和优化 i nt h i s p a p e r , t oi m p r o v e a n d o p t i m i z e t h e s p a c er e q u i r e db y t h e g o e m a n c l a u s e nl c sa l g o r i t h ms p a c et h ef o l l o w i n gw o r kh a sb e e nd o n e ：( 1 ) t o o p t i m i z et h es p a t i a lr e d u n d a n c yo fa u x i l i a r ya r r a y so ft h eg o e m a n - c l a u s e na l g o r i t h m ； ( 2 ) t oc o m p r e s st h ea s s i s ta r r a ya n dt h er e s u l t sa r r a yu s i n gt h ee l i a sc o m p r e s s i o n a l g o r i t h m ；( 3 ) t om a k e f u r t h e ro p t i m i z a t i o na n d i m p r o v e m e n t sf o rt h ee l i a sa l g o r i t h m t o g e t ah i g h e rc o m p r e s s i o nr a t i o w h i l et h e i m p r o v e da l g o r i t h mk e e p st h e g o e m a n - c l a u s e na l g o r i t h m sl i n e a rs p a c eb o u n d ，w eg e tam o r ee f f e c t i v e l ym e t h o d w i t hah i g h e rc o m p r e s s i o nr a t i of o rt h es p a c eb o t t l e n e c ko ft h el c sp r o b l e mw h e n t h i sm e t h o di su s e dt os o l v em o s t o ft h eg e n e t i cs e q u e n c e s ， k e y w o r d s ：l c sa l g o r i t h m ，g e n e t i cs e q u e n c e ，c o m p r e s s i o na l g o r i t h m ，s p a c e c o m p l e x i t y ，o p t i m i z a t i o n i v 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 h 学位论文作者签名：才扩舻 日期：如年cf 月f 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 保密论文保密期满后适用本声明。 学位论文作者签名：aa 冉 导师签名： 日期：年 月日 中i “大学硕上论文最长公共了序列算法的改进和优化 第一章引言 1 1 研究的背景和现状 1 1 1 研究背景 一个给定字符串的子序列是在该字符串序列中删除0 个或多个元素后得到 的序列。序列y = y l , y 2 ，以) 是序列x 的子序列是指存在一个严格递增的下标 序列 ，之， 使得对于所有的，= l ，2 ，七有：y j = 。对于给定的两个序列x 和y ，若序列z 既是x 的子序列又是y 的子序列，称z 是序列x 和y 的公共子 序列。所有公共子序列中最长的那个序列称它为最长公共子序列【。 l c s 算法应用于很多的研究领域，如字符串的编辑距离、生物分子学中判断 判断氨基酸的相似性以及基因序列模型【2 l 等问题。在这些相关的问题中，l c s 算 法的执行效率的好坏和空间效率的高低，可以极大影响求解相关问题的效率和质 量。当然l c s 的应用远远不止这些，其研究内容在数据压缩、模式识别、内容 过滤、病毒库的匹配、信息检索都有重要的作用【3 】。 1 1 2 研究的现状 l c s 问题早在7 0 年代已经开始被很多学者研究。w a g n e r 、f i s c h e r 使用动态 规划算法来求解l c s ，该算法的时间复杂度为o ( m n ) ，空间复杂度为o ( m n ) 【4 】。 在此基础上出现了很多其他的l c s 求解算法，算法的效率在不断提高，但这些 算法时间复杂度在最坏的情况下为q ( 掰刀) 。其中具有代表性的算法有h u n t 和 s z y m a n s k i 的算法【5 】该算法的时间复杂度是d ( o + 刀) 1 0 9 刀) ，s 代表字符种类。 因此当j 很小的时候，该算法的执行效率将很高。但是该算法时间复杂度在最坏 的情况下会达到o ( n 2l o g n ) 。在此基础上，在1 9 8 0 年m a s e k ，p a t e r s n 发表的改 中山大学硕士论文最长公j 二f 序列算法的改进和优化 进算法时间复杂度降低到o ( m n l o g n ) ， 空间复杂度相对原来的算法保持不变嘲。 此后针对l c s 问题的研究出现了两类算法：一种情况是当l c s 的长度p 很 长的时候，对这种情况很多学者给出了自己的解决方法1 7 - 1 0 1 ，其中具有代表性的 算法有m a y e r 在1 9 8 6 年发表的l c s 算法【7 1 。该算法的时间复杂度为o ( n ( n + l p ) 或o ( n ( m + l p ) ) ，算法的空间复杂度为o ( m p ) 或者o ( n p ) 。另一种情况是当l c s 的长度p 较短的时候，针对这种情况，很多学者也做出了研究l j 4 1 ，其中具有代 表性的算法有a p o s t o l i c 在1 9 8 7 年发表的算法【3 】。该算法的时间复杂度为 d ( 刀( p + 1 ) ) 或d 沏( p + 1 ) ) ，算法的空间复杂度为o ( m p ) 或o ( n p ) 。 相对前述算法，r i c k 发表的算法 1 5 , 1 6 1 更加灵活且算法的执行效率也更好。他 提出了一种适用于上述两种情况下的算法。该算法的时间复杂度为 o ( n s + m i n ( m p ，p ( n p ) ) ) ，相对于前述算法，该算法拥有更好的时间复杂度性能， 但其空间复杂度在最坏的情况下为q ( 所刀) 。后来该算法被c l a u s e n 和g o e m a n 做 了进一步的优化【2 】，改进算法的空间复杂度为o ( n s ) 。因此c l a u s e n g o e m a n 算法 有着良好的时空性能。 1 1 3 研究的意义 自2 0 0 1 年人类基因图谱被破解以来，生物学有了一个重要的研究领域一 基因序列模型1 7 - 2 0 ( p a t t e r n si nb i o l o g i c a ls e q u e n c e s ) ，该问题的求解就是建立在 l c s 和s c s 算法的基础上 2 1 , 3 0 - 3 2 1 。针对这样一个特定的问题，l c s 问题的应用 环境发生了极大的变化，空间因素成为了算法的瓶颈。在应用上述l c s 算法来 解决该问题的时候，我们需要面对一个现实问题算法需要的存储空间应该是 普通计算机能提供的内存空间。 2 0 0 1 年4 月u c u s 人类基因组发布了人类基因序列，共包含2 8 亿对碱基1 3 s 1 其中相应的字符串序列将达到6 g 。如果每个位置坐标需要一个整数类型来存储， 2 中山大学硕士论文最长公共子序列算法的改进和优化 算法需要的空间将达到9 6 g 字节，而9 6 g 字节已经远远超出了普通计算机能提 供的内存空间。同样，在n l c s 问题的求解中，空间因素也会成为算法的瓶颈。 因此在保持线性空间复杂度时的空间优化成了实践中迫切需要解决的问题。 1 2 论文的任务和贡献 本文主要针对l c s 算法应用于大规模字符串序列( 如在1 1 3 中提到的遗传 基因序列) 的l c s 求解时遇到的空间瓶颈问题进行研究，对c l a u s e n g o e m a nl c s 算法做出改进和优化，其主要内容如下： ( 1 ) 优化g e o m a n c l a u s e 算法中的辅助数组：通过对算法的研究，我们认 识到该算法空间的主要分配给四个位置标示数组- i ，e 衄o s ，r i g h t p o s ，t o p p o s 和b o t t o m p o s f 2 1 ，这四个数组其中的数据冗余度很高，我们对这几个数组冗余做 出优化，优化后的数组在使用效果上与原数组并没有任何差别。另外由于l e f t p o s 与r i g h t p o s 以及t o p p o s 与b o t t o m p o s 这两对数组在位置标示上的相似性，我们 可以分别用两个数组r o w p o s 和c l o u m n p o s 来代替以节省空间。 ( 2 ) 压缩辅助数组和结果数组：对辅助数组和结果数组t h r e s h 2 j 做进一步 的分析可知，两个数组是由严格递增的数字组成的序列。对于有序序列进行压缩 已经有过很多研究，在本文中将使用e l i a s 算法【2 5 , 2 6 1 对其进行压缩，e l i a s 在压缩 有序序列上良好的性能可以极大的改善g e o m a n c l a u s e 算法的空间使用情况。且 该压缩算法的使用并不会影响g e o m a n - c l a u s e 算法的时间复杂度。最后我们用实 验数据来对比分析改进后的算法和原算法的时间和空间复杂度上的差别。 ( 3 ) 对e l i a s 压缩算法做进一步的改进：当e l i a s 算法应用于这个具体问题 时，对剩余位参数和压缩过程做进一步的优化和改进，改进后的算法可以得到更 好的空间压缩比。 本文的主要贡献为： ( 1 ) 对g e o m a n c l a u s e n 算法中的辅助数组l e r p o s ，r i g h t p o s ， b o t t o m p o s 数组的数据冗余做出优化和改进，提高了空间效率。 3 中山大学硕士论文 最长公j 二f 序列算法的改进和优化 ( 2 ) 对冗余处理后的辅助数组和结果数组使用e l i a s 算法做存储压缩，获得 了极高的空间压缩比，缓解了l c s 问题应用于大规模基因序列时的空间瓶颈问 题，且改进后的算法保持了g e o m a n c l a u s e n 算法的时间复杂度，对此论文从理 论和实验两个方面做出了验证。 ( 3 ) 对e l i a s 算法做进一步的优化和改进，获得了更高的数据压缩比。对此 论文也从理论和实验两方面做出了验证。 1 3 论文的组织结构 论文的主要分为六章，其结构和相关的主题章节如下： 第1 章：主要介绍论文的研究背景、研究内容、研究现状及论文研究的现实 意义。对论文所做的主要工作和论文的贡献做出了阐述。最后介绍了论文的组织 结构。 第2 章：介绍l c s 问题的相关问题。其中包括l c s ，s c s 和生物模式的问 题，n l c s 问题及l c s 替代问题近似的l c s 问题。 第3 章：详细的介绍g e o m a n c l a u s e n 的l c s 的求解算法，分析该算法在应 用到大规模遗传基因序列中的空间瓶颈，分析了该算法的空间使用情况和缺陷。 第4 章：详细阐述了改进算法的原理：包括优化g e o m a n - c l a u s e n 算法的空 间冗余，使用e l i a s 算法对其进行压缩，对e l i a s 算法做进一步的优化和改进后从 理论上分析了改进后的算法的空间使用情况。并用具体的实例演示了改进算法的 原理。 第5 章：算法性能对比实验：首先从理论上对比分析了g e o m a n c l a u s e n 算 法和改进算法的时间复杂度和空间复杂度，然后用实验数据来对比分析两者的时 间和空间使用情况。 展望 第6 章：总结和展望：对论文所做的工作做出概括，并对进一步的工作做了 4 中山大学硕上论文最长公共子序列算法的改进和优化 第二章l c s 相关问题介绍 2 1l c s 、s c s 和生物模式 s c s 即最短公共父序列( s h o r t e s tc o m m o ns u p e r s e q u e n c e s ) ，对于给定两个 序列x ，y ，如果能够在这两个序列中通过添加0 个或多个字符得到一个相同的 序列，这个相同的序列就被称为序列x ，y 的公共父序列，在所有父序列中长度 最短的那个称为最短公共父序列【2 2 】。 l c s 和s c s 求解算法一起应用在生物学的很多研究中，其中较为重要的研 究领域是生物模式( p a t t e r n sb yb i o l o g i c a ls e q u e n c e s ) 。生物模式揭示了生物遗传 序列之间存在的某种关系【2 2 】。 在生物遗传学中，生物器官的d n a 和蛋白质序列中总是包含着某些重要的 模式，这些模式揭示了父代和子代之间的某种联系父代和子代有着某种程度 的强烈的相似性f 2 2 1 。另外这些模式对这些器官的特定功能起着非常重要的作用。 研究表明生物的遗传序列中会频繁出现某些模式，它们组成了d n s 和蛋白质序 列中的重要区域，这些模式在生物学上称作生物模式吲。 对生物模式的研究，很多学者已经做了很多工作，其中很多学者提出了很多 算法来优化求解生物模式的过程【2 1 2 2 1 ，比较重要的一个方向是利用l c s ，s c s 和生物模式的特定关系来研究此问题。其中具有代表性的算法有p a l s 算法，这 个算法是k a n gn i n g 等人在2 0 0 6 年提出来的【2 2 1 。p a l s 算法的原理可以简单陈 述为：首先得到一序列生物序列的l c s 和s c s ，然后通过l c s 、s c s 和遗传序 列的对比，来提取生物模式。 由此我们可以看出l c s 算法的重要性，它是求解生物模式算法的基础，l c s 算法的效率的提高将极大的改善p a l s 算法的效率。 5 中i i i 大学硕上论文最长公共了序列算法的改进和优化 2 2n l c s 问题 l c s 问题的一般定义是：对于两个给定输入序列，求解它们的最长公共子序 列。但是在很多情况下，我们需要研究n ( n 2 ) 个输入序列的l c s 。这就是通 常所说的n l c s 问题【2 3 1 ，n l c s 问题研究的是一组输入序列中存在的某种联系 犯3 】 o 一般情况下，输入序列的长度为kb y t e s ，对于这样的输入序列，空间复杂 度为o ( n s ) 的l c s 算法需要的空间较少，空间因素对于算法来说是次要的考虑因 素。而在相同情况下，考虑n l c s 问题的时候，空间因素就会凸显出来。n l c s 求解算法一般是建立在l c s 算法基础上，其基本原理是：用递归的方法将n 个 输入序列分成每两个序列一组，对每一组用l c s 算法求解出l c s ，对求出来的 结果继续分组，再求解，直到最后只剩下一个序列为止。所以当n 很大的时候， 同时求解的l c s 的分组会很多，需要的空间会很多，由此优化l c s 算法的空间 成为求解n l c s 问题的基础。 2 3 近似的l c s 在一般的求解l c s 问题中，要求我们求出的是一个精确的l c s ，即给定两 个输入序列，要求求出其精确的最长的公共子序列。然而在现实的应用中，l c s 是被用来揭示输入序列之间的某种联系，有时候揭示这种联系并不一定需要准确 的l c s ，某种相似的l c s 足以揭示出这种联系，所以在很多情况下我们只需要 求出输入序列的近似的l c s 2 4 1 。 如果近似解能够反映出和精确解相同的效果，求解l c s 的近似解相对于求 解精确的l c s 来讲有很多优点。一般来说，近似解算法的时空性能相对于精确 的l c s 算法会有很大的提高；并且当输入序列很长的时候，工程上的时间和空 间效果就会很明显的体现出来。所以对于很多问题尤其是对l c s 的结果精度要 求不高的情况下，用求解l c s 的近似解来代替原来的l c s 算法，可以提高算法 的效率【2 3 , 2 4 1 。 6 中山大学硕上论文最长公共r 序列算法的改进和优化 第三章l c s 的构造算法 3 1l c s 问题的重新描述 在第一章中我们给出了l c s 问题的详细描述，在讨论具体的算法之前，我 们首先用数学语言来重新定义l c s 问题。 匹配：对于序列x = 五，而，毛) 和y = m ，y 2 ，) ，当& = 乃时，我们将 有序对( k ，j ) ( 1 k m ，1 j ) 称作一个匹配。 集合m ：它是一个建立在肌奉行上的一个所有匹配的矩阵。如当 x = c b a b b a c a c ，y = a b a c b c b a 时，m 如图3 1 ( a ) 所示。 ( a ) 图3 1( a ) 匹配矩阵( b ) l c s 链 ( b ) 偏序集：它是一个定义在以刀上的偏序集， ( 七，) “( 七，) 当且仅当 k 七， ，。 7 中山大学硕上论文最长公共予序列算法的改进和优化 匹配链c ：c m ，是一个序对组成的集合，匹配链c 中的每个序对满足 条件若n ，p 2 c ，则p j 段或者仍 n + l f ) ：第n + l i 列中的从第i + l 行开始的到第m i 行结 束的所有元素。 8 i i j 学倾论文最k 公越r 序列算法的嫂进l 优化 当1 f - 卅1 2 1 ，上述四个向量如图3 - 2 ( a ) 所示 在此基础上，我们定义 t 9 = u 月r ，p = u j g l j ，b 。= u b s , r “= u r 对于l = l ，2 ， 肼2 1 ，我们构造四个集合链一。一，a 8 。和a 即，这几个集 合是由r 9 ，p ，b “，月“分解而得到，或者说他们足丁9 ，r ，b 9 ，月9 的子集。其详细 的构造过程我们将在后面描述。 我们用符号0 来表示一一个子集a 其中1 u p “= i l ( 一含有的元 素的个数) 。对于爿，一纠，a 我们同理可以定义出口ib 。以及他们的结 束序数e “。，p ，p 8 。此外我们定义s “，它用来将a 7 一，a “分割成两部分：一部 分包含其中基数小于s 脚的子集链掰，群7 ，另一部分则包含剩下的部分其中 这一部分将在算法的下一个过程中不断被更新。同理我们可以定义 ：s 肌，来分割 8 - - 8 ，- 。 i234 56789 l2 cbabbacaccb 叮】 喜o i f 三 ao t 1 t 2 r t 3 p 巨凼帮 ! 垦： b 1 r 1 an 西n o 3456789 abbacac 月。 。 - b ) 一 ! ! 博 旧 - | d i 学硕论文 最长公j ，序列算法的改进和优化 123 45 6 7 89 cbabbac a c _ o j t jf 月j 2 123456 7 8 9 cbab bacac _ - 9 4 ，4 盯 ：r ，j 州 。 r 2 p_ 4 。r 胆4 4 。 l c 3 一毡 西。 e 4 囊，4 、| 。 景，4 1 。 4 4 12345678 9 cb ab ba cac _ 一9 一，3 t , jf a l , 3 ! ! ” 牟。1 r ，3 f 4 ：4 和 ” d ) 123456 789 cbabba cac 一9 寸 u 鼻o u i 寸 乱o 、jo - o o 图3 - 2( a ) 分解m ( b ) 一( e ) 构造匹配链的过程( f ) 晟终的分解结果 图3 - 2 ( b ) ，( c ) ，( d ) 和( e ) 展示了当f = 1 ，2 ，3 和4 时，从匹配矩阵分解 得到匹配链的过程。图中矩形框出的部分表示m 中剩余的还没有被分解的匹配 矩阵，在我们每一步的构造过程中，相互对应的两行和两列将被分解出来，分解 出来的两行两列用来更新a r , 一“。舢，4 。依次进行下去，如图( f ) 最终会得 i o 酽 群 一 霹 o 旷 。 寸 u a 认 吼 j 7 中l i l 大学硕士论文最长公共子序列算法的改进和优化 到匹配链c ，即l c s 3 2 2r i c k 算法的过程 在算法的整个构造过程中，我们首先要定义这样一个函数：对于任意的两个 匹配链( 如图3 - 2 ( c ) 中的群一，4 2 ) c ，d m ，定义函数： 1 p ( c ，d ) = a civ p 2 d ：1 ( 易 仍) ) 函数护是用来求匹配链c 中相对于匹配链d 中不可比的那部分元素。当 i p ( c ，d ) = c ，我们称c 相对于d 不可比。当伊( a ，d ) = p 1 ) ，我们称元素p l 相对于d 不可比。下面我们详细介绍分解m 得到匹配链c 的过程 初始时，令彳0 = 管0 = a o b p = 鬈0 = a ，令s t o = s l o = s 晟o = s 甩o = 1 ，令 p r o = 矿o = p b o = p r ，。= o 。f r o mi = lt o r m 2 1 ，当”= s 死h p r 卜1 时，首先计 算丁，然后用r 来更新鬈，- 衙。= 彳j - 1um ( r n m ，鬈q ) 。当u = 1 s 巩卜1 - 1 时，衙。= j - 1 。同理我们可以计算钟”，钟”，钟”。下面我们给出求解匹配链 彰”，彰”，钟”，群j 的伪代码，如图3 - 3 所示。 中山大学硕上论文最长公共了序列算法的改进和优化 ( a ) d e t e r m i n ea 7 的伪代码 1 2 中山大学硕上论文最长公j 子序列算法的改进和优化 ( b ) d e t e r m i n ea ，的伪代码 ( c ) d e t e r m i n e 露的伪代码 1 3 中山大学硕上论文最长公共子序列算法的改进和优化 ( d ) d e t e r m i n ea r ，的伪代码 图3 3( a ) ( d )m 分解过程伪代码 在从m 分解得到”，群”，钟”，臂的过程中，r i c k 算法定义了一种关于 鬈”，群”，鬈”，。完备性的检查方法。定义鬈。的t l c o m p l e t e 为：。中存在一 个匹配( 后，) 满足条件1 七，j ，同 理计算出群1 = ( 勺1 ) ，( 6 ，1 ) ) ，彳1 = ( 8 ，3 ) ，( 8 ，6 ) ，( 8 ，8 ) ) ，钟k ( 4 ，9 ) ， ( 6 ，9 ) ) 当i = 2 ，我们计算出t 2r i m = ( 2 ，2 ) ，( 2 ，4 ) ，( 2 ，5 ) ) ，如图3 - 2 ( c ) 所示。 s 亿j = 1 ，= 1 ，则有群2 = 彳”u w ( s ，群1 ) ，其中m ( s ，群1 ) = 伊( r 2 厂、m ，群。) ， 贝, 0 i p ( s ，彳1 ) = ( 2 ，2 ) ，则群2 是在原来的群1 中增加( 2 ，2 ) ，则群2 = ( 2 ，2 ) ( 3 ，1 ) ， ( 6 ，1 ) ，( 8 ，1 ) ) 。而4 2 则等于剩余的s 是 ( 2 ，4 ) ，( 2 ，5 ) 。同理可以更新4 。， 群2 以及群2 管2 群2 管”。 当i i = 3 ，管3 = ( 3 ，6 ) 与鬈2 出现了完备性冲突一4 3 与管2 连个集合 不可比。此时就将管2 加入到集合d 豫中。 当i = 4 ，依次类推。 3 3g e o m a n c l a u s e n 的优化l c s 算法1 2 i g e o m a n - c l a u s e n 在详细分析r i c k 的l c s 构造算法原理后得出结论：每一步 1 9 中1 1 1 人学硕士论文最长公共子序列算法的改进和优化 运算过程中新增的向量中存储了对问题的最后求解没有帮助的信息或者说是冗 余的信息。对于每一个向量如4 ”，其中对算法有用的匹配点是最左边的匹配点 ( 3 ，1 ) ，而其它两个点可以省出。根据这一结论，每个向量实际只需要存储一 个匹配点，从而可以节省空间。因此g e o m a n c l u a s e nl c s 算法定义数组 t h r e s h t u 来存放匹配链结果： t h r e s h t u 】：= m i n ll3 k ：( 尼，z ) 名。) 结果数组n s h t 【u 】中记录了匹配连。最左边的那个匹配点的列号。图3 - 2 ( b ) 中t h r e s h t 1 】= 3 ，图3 2 ( d ) 中t h r e s h t 1 = 2 ，t h r e s h t 2 = 3 。 而为了每一步更新t h r e s h t u 数组g e o m a n c l u a s e nl c s 算法辅助数组 l e f t p o s ：l e f t p o s 是定义在g x 1 ：刀+ l 】上的集合，其中占是原序列x ，y 中出现的 所有字符的集合。l e f t p o s 的定义如下： l e f t p o s x ，z 】- m i n n + 1 u j i ，n y j = c ) ) l e f t p o s x ，】表示的是序列y 中第z 元素后( 含第z 元素) 最早出现字符x 的 位置值，当第，元素后( 含第，元素) 没有出现字符x ，令l e f l p o s x ，】_ n + l 。我 们用一个例子来说明l e 邱o s 辅助数组，当y = a b a c b c b a 时，其l e f i p o s 值如图 3 7 所示 a333666881 01 0 b2244 5 1 01 01 01 01 0 c1777777991 0 图3 7l e f l p o s 值实例 中山大学硕士论文最长公共子序列算法的改进和优化 利用l e f l p o s ，g e o m a n - c l u a s e nl c s 算法给出了t h r e s h t u 的求解实现，其 求解伪代码如图3 8 所示。 图3 - 8t h r e s h t u 的更新程序伪代码 对于”，钟。和。n - y d a 定义类似的数组t h r e s h l 、t h r e s h b 、t h r e s h r 。用它 们来替代群”，钟j 和。的处理过程。与t h r e s h t u 和l e f i p o s 类似， 于t h r e s h l 、 t h r e s h b 、t h r e s h r 同理可以定义t o p p o s 、r i g h t p o s 、b o t t o m p o s ： t o p p o s x ，k 】：= m i n m + l u yik j m x j = c ) ；( 1 k m + 1 ) r i g h t p o s x ，】：= m a x 0 u j 1 1 j ：( 0 ；( o k m ) 类似于t h r e s h t u 的更新程序，可以得到t h r e s h l 、t h r e s h b 、t h r e s h r 的更 新程序，综合四个替代程序得到优化后的主程序伪代码，如图3 - 9 所示。 2 1 中山大学硕上论文最长公共子序列算法的改进和优化 中山大学硕上论文最长公共子序列算法的改进和优化 中1 1 1 人学硕上论文最长公共r 序列锋法的改进和优化 中山大学硕士论文最长公共j f 序列算法的改进和优化 中山人学硕_ 上论文 最长公共予序列算法的改进和优化 图3 - 9g e o m a n - c l a u s e n 主程序伪代码 3 4 算法的性能分析 我们详细分析g e o m a n c l a u s e 算法的构造可以得出结论：算法所需的主要空 间由辅助数组l e f i p o s 、t o p p o s 、r i g h t p o s 、b o t t o m p o s 以及结果数组t h r e s h t 、 t h r e s h l 、t h r e s h b 、t h r e s h r 组成。结果数组的存储空间为d ( 刀) ，辅助数组l e f t p o s 、 t o p p o s 、r i g h t p o s 、b o t t o m p o s 所需的空间与字符序列中出现的字符种类有关， 字符种类s = h 。辅助数组所需要的空间为o ( n s ) ，则g e o m a n - c l a u s e 优化算法的 空间复杂度为o ( n s ) 。当序列字符种类远远小于字符序列长度时，算法的时间复 2 矗 中i l j 大学硕士论文 最长公共子序列算法的改进和优化 杂度是o ( n ) 。 g e o m a n c l a u s e 算法保持r i c k 算法时间复杂度不变，即 o ( n s + m i n m p ，p ( n p ) ) ) 。尽管时间复杂度没有改变，但由于g e o m a n - c l a u s e 算 法引入了辅助数组剔除了空间冗余且提高了访问效率。时间复杂度在局部还是得 到了优化。g e o m a n c l a u s e 用实验证明了这一点。 中山入学硕l j 论文最k 公共了序列算法的改进和优化 第四章新的l c s 构造算法 4 1e l i a s 数据压缩算法 4 1 1e l i a s 算法思想 p e t e re l i a s 提出了一种对于数字序列的数据压缩算法【2 5 , 2 6 1 ，这种算法与一般 数据压缩算法的侧重点不同。普通的数据压缩算法往往被设计成一种通用的算 法，能同时处理不同种类的数据的压缩，如英文字符、中文字符、数字等，然而 数据处理范围的扩大，造成了数据的压缩比性能的损失。 e l i a s 数据压缩算法是针对数字序列的压缩，因为其针对的特定对象，数据 压缩比较高。算法的核心原理是：将数字序列分成若干个有序的序列，然后对这 些有序序列进行数据压缩。由于有序序列的特殊性，其数据压缩比相对于普通序 列会明显提高。 4 1 2e l i a s 压缩算法的原理【2 5 ，2 6 】 设有一组递增的有序序列s = s ：，屯，) ，元素的个数为s 。算法的基本 步骤为：首先取序列s 中每个元素的前z 个b i t 组成一个新的序列q = g l ，q ：，g ，吼) ，其中z = 1 0 9 s j 。然后取每个数的剩余的b i t 组成的另一个序列 r = ，吒，吩，0 ) 。因为序列s 是递增的有序序列，则序列q 也为递增的有序 序列，即o q h - - q h + 。 吼，其中1 办 0 。例如第三个元素9 2 - q l = 3 ，则第三个元素为0 0 0 1 。经过上面 的步骤，序列s 转换成了两个位序列r 和q 。 若序列s 是一个递减序列，其压缩原理相同，只需要将序列q 的存储方式 o 中山人学硕l j 论文 最k 公共了序列算法的