（计算机软件与理论专业论文）最小公共字符串划分问题的算法研究.pdf

- j扣 iylllll1lllll7ll9llll1llll3lllll5lll4llll 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：缉 日期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：越导师签名：烂日期：三型么。r 弓 啊j1 山东大学硕士学位论文 目录 摘要i a b s t r a c t r i 第1 章绪论1 1 1 背景介绍1 1 2 相关知识2 1 2 1 反转排序简介”2 1 2 2 最小公共整数划分简介“3 1 2 3 后缀树简介”4 1 3 本文组织结构4 第2 章最小公共字符串划分问题复杂性6 2 1 基本概念与定义6 2 2 最小公共字符串划分问题的复杂性7 2 32 最小公共字符串划分问题的1 1 0 3 7 一近似算法l o 2 43 最小公共字符串划分问题的4 一近似算法1 2 2 5 本章小结1 3 第3 章最小公共字符串划分问题近似算法与评测1 4 3 1 贪心算法1 4 3 1 1 贪心算法介绍1 4 3 1 2 贪心算法评测1 8 3 2n o v e l 贪心算法1 9 3 2 1n o v e l 贪心算法介绍1 9 3 2 2n o v e l 贪心算法评测2 1 3 3e d u c a t e d 贪心算法2 1 3 3 1e d u c a t e d 贪心算法介绍2 1 3 3 2e d u c a t e d 贪心算法评测- 2 4 3 4 碰集算法2 5 b i l 【 山东大学硕士学位论文 3 4 1 碰集算法介绍2 5 3 4 2 碰集算法评测2 9 3 5 本章小结”2 9 第4 章定界贪心算法3 0 4 1 定界贪心算法主要步骤3 0 4 2 定界贪心算法近似度分析3 2 4 3 定界贪心算法时间复杂度分析3 4 4 4 实验结果一3 4 4 5 本章小结3 5 第5 章最小公共字符串划分问题的实用求解算法3 6 5 1k 最小公共字符串划分问题最优解算法3 6 5 1 1 算法描述3 6 5 1 2 算法正确性证明3 8 5 1 3 算法时间复杂度3 9 5 2 随机回溯算法4 0 5 2 1 随机回溯算法描述4 0 5 2 2 随机回溯算法性能4 2 5 3 本章小结4 2 第6 章总结与展望4 3 6 1 工作总结一4 3 6 2 问题展望4 4 参考文献4 5 致谢”5 0 攻读硕士期间发表的学术论文目录5 1 攻读硕士期间参与科研项目情况5 2 ， 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h i i i c h a p t e r1i n t r o d u c t i o n 1 1 1b a c k g r o u n d 1 1 2r e l a t e dk n o m e 电e - 2 1 2 1i n t r o d u c t i o no f s o r t i n gb yr e v e r s a l 2 1 2 2i n t r o d u c t i o no f m i n m u mc o m m o ni n t e g e rp a r t i t i o n 3 1 2 3i n t r o d u c t i o no fs u f f i xt r e e 4 1 3t h es t r u c t u r eo f t h i sp a p e r 4 c h a p t e r2t h ec o m p l e x i t yo f m i n m u mc o m m o ns t r n gp a r t i t i o np r o b l e m 。- - - 。6 2 1t h eb a s i cc o n c e p t sa n dd e f i n i t i o n s 6 2 2t h ec o m p l e x i t yo f m i n m u mc o m m o ns t r i n gp a r t i t i o np r o b l e m 7 2 31 1 0 3 7 - a p p r o x i m a t i o nf o r2 - m c s pp r o b l e m 1 0 2 44 - a p p r o x i m a t i o nf o r3 - m c s pp r o b l e m 1 2 2 5c o n c l u s i o no f t h i sc h a p t e r 1 3 c h a p t e r3a p p r o x i m a t i o na l g o r i t h mf o rm i n m u mc o m m o ns t r i n gp a r t i t i o np r o b l e m a n de v a l u a t i o n 1 4 3 1g r e e d ya l g o r i t h m 。1 4 3 1 1i n t r o d u c t i o no f g r e e d ya l g o r i t h m 1 4 3 1 2e v a l u a t i o no fg r e e d ya l g o r i t h m 1 8 3 2n o v e lg r e e d ya l g o r i t h m 1 9 3 2 1i n t r o d u c t i o no f n o v e lg r e e d ya l g o r i t h m 。1 9 3 2 2e v a l u a t i o no f n o v e lg r e e d ya l g o r i t h m 2 1 3 3e d u c a t e dg r e e d ya l g o r i t h m 2 1 3 3 1i n t r o d u c t i o no f e d u c a t e dg r e e d ya l g o r i t h m 2 1 3 3 2e v a l u a t i o no f e d u c a t e dg r e e d ya l g o r i t h m 2 4 l r 山东大学硕士学位论文 3 4h i t t i n gs e ta l g o r i t h m 2 5 3 4 1i n t r o d u c t i o no f h i t t i n gs e ta l g o r i t h m 2 5 3 4 2e v a l u a t i o no f h i t t i n gs e ta l g o r i t h m 2 9 3 5c o n c l u s i o no f t h i sc h a p t e r 2 9 c h a p t e r4d e l i m i t a t i o nn o v e la l g o r i t h m 3 0 4 1t h ep r o c e s so fd e l i m i t a t i o nn o v e la l g o r i t h m 3 0 4 2a n a l y s i so f d e l i m i t a t i o nn o v e la l g o r i t h m 3 2 4 3t i m ec o m p l e x i t yo f d e l i m i t a t i o nn o v e la l g o r i t h m 3 4 4 4e x p e r i m e n t a lr e s u l t s 3 4 4 5c o n c l u s i o no f t h i sc h a p t e r 3 5 c h a p t e r5u s e f u la l g o r i t h mf o rm i n m u m c o m m o ns t r i n gp a r t i t i o np r o b l e m 3 6 5 1o p t i m a la l g o r i t h mo fk - m i n m u mc o m m o ns t r i n gp a r t i t i o np r o b l e m 3 6 5 1 1d e s c r i p t i o no f a l g o r i t h m 3 6 5 1 2p r o o fo f a l g o r i t h mc o r r e c t n e s s - 3 8 5 1 3t i m ec o m p l e x i t yo fa l g o r i t h m 3 9 5 2r a n d o mb a c k t r a c k i n ga l g o r i t h m 4 0 5 2 1d e s c r i p t i o no f r a n d o mb a c k t r a c k i n ga l g o r i t h m 4 0 5 2 2p e r f o r m a n c eo f r a n d o mb a c k t r a c k i n ga l g o r i t h m 4 2 5 3c o n c l u s i o no ft h i sc h a p t e r 4 2 c h a p t e r6c o n c l u s i o na n dp r o s p e c t 4 3 6 1c o n c l u s i o n 4 3 6 2p r o s p e c t 4 4 r e f e r e n c e s 4 5 a c k n o w l e d g e m e n t s 5 0 p a p e r sp u b l i s h e d 5 l p r o j e c t sp a r t i c i p a t e di n 5 2 l v j 山东大学硕士学位论文 摘要 字符串对比是计算机科学的一个基本问题，在基因组比较、文本处理与压缩 等实践中有着广泛应用。近几年，最小公共字符串划分( m c s p ) 问题得到越来 越多算法与复杂性研究者的关注。m c s p 问题要求将字符串彳与b 划分为公共 子串，使划分后么中的每一段都与b 中某一段相对应，且划分得到的公共子串 数目最少。在基因组比较研究中，须将两个基因组分别看作字符串，计算两个字 符串的最小公共字符串划分，从而建立两个基因组中基因的对应关系。 要将字符串4 和b 划分为公共子串，彳中每个字符出现的次数必须与口中 此字符的出现次数相同。如果每个输入字符串中的字符最多出现k 次，就称此问 题为缸最小公共字符串划分( 缸m c s p ) 问题。2 - m c s p 问题已经被证明是n p h a r d ， 并且是a p x h a r d 。目前最好的2 - m c s p 问题近似算法的近似度为1 1 0 3 7 ，3 - m c s p 问题的近似度为4 ，k - m c s p 问题近似度为o 。 本文首先讨论以往m c s p 问题研究结果，编程实现已有的贪心算法、n o v e l 贪心算法、e d u c a t e d 贪心算法以及碰集算法，并进行测试实验。在此基础上，分 析评测各个算法的优缺点。 然后针对缸最小公共字符串划分问题，设计实现了一个新算法：定界贪心近 似算法。定界贪心算法是在碰集算法的基础上改进而成，算法具有o 的算法 近似度以及o ( ，z ) 的时间复杂度。同时大量实验数据表明，定界贪心算法与碰集 算法相比具有更好的计算性能。在实际测试实验中，未曾遇到定界贪心算法性能 不如碰集算法性能好的实例。 最后设计实现了m c s p 问题的最优解算法与随机回溯算法。令m 代表输入 字符串中不同元素的个数，n 代表字符串的长度，最优解算法可以在o ( ! ) ”刀) 的时间内计算出知最小公共字符串划分问题的一个或者所有最优解，对评估其他 近似算法的实际运行效果有着重要作用。随机回溯算法具有很高的灵活性，既可 以求出最优解，也可以根据实际要求在短时间内求出较好的解，两种算法都具有 较高的实用价值。最后，对最小公共字符串划分问题进行了总结与展望。本文主 要创新工作为： ( 1 ) 设计实现了解答最小公共字符串划分问题的新近似算法，性能好于原 l气 山东大学硕士学位论文 有近似算法。 ( 2 ) 设计实现了解答最小公共字符串划分问题的最优解算法和随机回溯算 法，对于最优解实际求解和近似算法评测具有重要价值。 关键词：最小公共字符串划分；反转排序；贪心算法 1， 譬1 一 l i i - a b s t r a c t s t r i n gc o m p a r i s o ni sab a s i cp r o b l e mi nt h ec o m p u t e r s c i e n c e i tw a sw i d e l yu s e d i nt h ea r e ao fg e n o m ec o m p a r i s o n ，t e x tp r o c e s s i n ga n dc o m p r e s s i o ne ta l i nr e c e n t v e a r s ，m em i n i m l l n lc o m m o ns t r i n gp a r t i t i o n ( m c s p ) p r o b l e mh a sb e e np a y e dm o r e a n dm o r ea t t e n t i o nb ya l g o r i t h ma n dc o m p l e x i t yr e s e a r c h e r s t h em c s pp r o b l e m a i m sa tf i n d i n gac o m m o np a r t i t i o na b o u tt h ei n p u ts t r i n ga a n dbw i t ht h em i n i m u m n u m b e ro fb l o c k s ，a n de a c hb l o c ko f ah a so n ec o r r e s p o n d e n c eb l o c ki nt h es t r i n gb a f t e rp a r t i t i o n i nt h er e s e a r c ho fg e n o m ec o m p a r i s o n ，i tm u s t b el o o k e da st w os t n n g s a n dc o m p u t et h e i rm i n i m u mc o m m o ns t r i n gp a r t i t i o n t od e t e m i n et h er e l a t i o n s h i p b e t w e e nt h et w og e n e s t od i v i d es t r i n gaa n dbi n t oc o m m o ns u b s t r i n g s ，t h en u m b e ro fo c c u r r e n c e so f e a c hc h a r a c t e ri nt h es t r i n gam u s tb es a m ea s t h en u m b e ri nt h es t r i n gb t h e p r o b l e mi sd e f i n e da sk - m c s pp r o b l e m ，w h e ne a c hc h a r a c t e ro c c u r sa tm o s tk t a m e s i ne a c hi n p u ts t r i n g 2 - m c s pp r o b l e mi s n o to n l yn p - h a r db u ta l s oa p x - h a r d p r e s e n f l y , t h e 印p r o x i m a t i o nr a t i oo ft h eb e s ta p p r o x i m a t i o na l g o r i t h mf o r2 - m c s p p r o b l e mi s1 1 0 3 7 ，a n dt h er a t i oo f 3 m c s p p r o b l e m i s4 ，a tt h es a m et i m et h er a t i oo f k - m c s pp r o b l e mi so ( 动 t h i sp a p e rd e s c r i b e st h ep r e v i o u sf i n d i n g so fm c s pp r o b l e m ，a n dd o e sa l o to f e x p e r i m e n t a b o u tg r e e d ya l g o r i t h m ，n o v e lg r e e d ya l g o r i t h m ，e d u c a t e dg r e e d y a l g o r i t h ma n dh i t t i n gs e ta l g o r i t h mt h a th a v eg o o dp e r f o r m a n c e o n t h i sb a s i s ，t h e r e a r ed e t a i l e dd e s c r i p t i o na n de v a l u a t i o nf o re v e r ya l g o r i t h m t h e nan e wa l g o r i t h m d e l i m i t a t i o ng r e e d ya l g o r i t h m i s d e s i g n e d f o r 缸m i n i m u mc o m m o ns t r i n gp a r t i t i o np r o b l e m t h i sa l g o r i t h mi sb a s e do nt h eh i t t i n g s e ta l g o r i t h ma n di sd o n et oi m p r o v e t h ea p p r o x i m a t i o nr a t i oo f t h ea l g o r i t h mi s0 ( k ) ， a n di tc a na c c o m p l i s hi no ( n ) a tt h es a m et i m e ，al a r g en u m b e ro f e x p e r i m e n t a ld a t a s h o w st h a tt h ed e l i m i t a t i o ng r e e d y a l g o r i t h mh a sb e t t e rr e s u l t st h a nt h eh i t t i n gs e t a l g o r i t h m i no u ra c t u a lt e s te x p e r i m e n t s ，e a c hi n s t a n c ec a l lb ec o m p l e t e db e t t e rb y d e l i m i t a t i o ng r e e d ya l g o r i t h mt h a nh i t t i n gs e ta l g o r i t h m t h e nt h e r ei sa no p t i m a la l g o r i t h ma n dr a n d o mb a c k t r a c k i n g a l g o r i t h mw a s 山东大学硕士学位论文 d e s i g n e d t h eo p t i m a la l g o r i t h mc a nc o m p u t eo n eo ra l l o p t i m a ls o l u t i o no f k - m i n i m u mc o m m o ns t r i n gp a r t i t i o np r o b l e mi no ( ( 尼! ) ”刀) ，w h e nm i sd e f i n e da st h e n u m b e ro fd i f f e r e n te l e m e n t si nt h ei n p u ts t r i n g ，a n d 刀i sd e f i n e da st h el e n g t ho f t h e i n p u ts t r i n g t h eo p t i m a la l g o r i t h mi sv e r yi m p o r t a n tf o ra s s e s s m e n to fo t h e r a p p r o x i m a t i o na l g o r i t h m r a n d o mb a c k t r a c k i n ga l g o r i t h mh a sah i g h f l e x i b i l i t y i tc a n c o m p u t et h eo p t i m a ls o l u t i o n ，a n dc a ng e tag o o ds o l u t i o ni nas h o r tt i m ea c c o r d i n gt o t h ea c t u a ld e m a n d s b o t ho p t i m a la l g o r i t h ma n dr a n d o m b a c k t r a c k i n ga l g o r i t h mh a v e ah i g hp r a c t i c a lv a l u e f i n a l l y , t h e r eh a v eac o n c l u s i o na n d p r o s p e c t sa b o u tm i n i m u m c o m m o n s t r i n gp a r t i t i o np r o b l e m t h em a i nr e s u l t so ft h i sp a p e ra r eb e l o w ( 1 ) d e s i g na n di m p l e m e n tan e wa p p r o x i m a t i o na l g o r i t h mt oa n s w e rt h e m i n i m u mc o m m o n s t r i n gp a r t i t i o np r o b l e m ，w h i c hi sb e t t e rt h a n o r i g i n a l a p p r o x i m a t i o na l g o r i t h m ( 2 ) d e s i g na n di m p l e m e n ta no p t i m a la l g o r i t h ma n dr a n d o mb a c k t r a c k i n g a l g o r i t h mt oa n s w e rt h em i n i m u mc o m m o ns t r i n gp a r t i t i o np r o b l e m ，w h i c hh a v ea g r e a tv a l u et oc o m p u t eo p t i m a ls o l u t i o na n de v a l u a t eo t h e ra p p r o x i m a t i o na g o r i t h m k e y w o r d s ：m i n i m u mc o m m o ns t r i n gp a r t i t i o n ；s o r t i n gb yr e v e r s a l ；g r e e d y a l g o r i t h m 务 11 弧 - 囔 山东大学硕士学位论文 1 1 背景介绍 第1 章绪论 字符串对比是计算机科学中的一个基础问题，在计算生物学、文本压缩与处 理等方面有着广泛应用。而作为计算生物学的重要组成部分，基因重组问题近几 年得到广泛研究。 基因重组是指由于不同的d n a 链断裂与链接而导致d n a 片段交换与重组，进 而形成新d n a 分子的过程。从广义上讲，任何造成基因变化的基因交流过程，都叫 做基因重组，而狭义的基因重组仅指涉及d n a 分子内断裂一复合的基因交流。2 0 世纪8 0 年代末科学研究表明，基因重组是生物演化过程中的重要特征，也是动 植物进化的重要模式，在生物进化、生物种族分类以及生物制药等领域都有重要 研究价值。基因重组的过程虽然复杂，但是基本变换却只有三种：反转( r e v e r s a l ) 变换，交换( t r a n s p o s i t i o n ) 变换和移位( t r a n s l o c a t i o n ) 变换【1 1 。反转变换 是指将一段基因的子序列顺序完全颠倒过来，如果基因序列本身带有符号，则将 所有符号取反。交换变换是指将基因的两段相邻子序列位置交换，交换变换不改 变基因子序列原有的符号。移位变换是指两个基因的两段相邻子序列位置交换后 再将其中一段反转组成新的基因，三种不同操作的问题复杂度不同。 与反转排序紧密相关的是最小公共字符串划分( m i n i m u mc o m m o ns t r i n g p a r t i t i o n ) 问题。在基因组比较研究中，须将两个基因组分别看作字符串，计算 两个字符串的最小公共字符串划分，从而建立两个基因组中基因的对应关系。对 于字符串彳的划分产口1 4 2 ，a 脚) 和字符串b 的划分舻徊l 恳，b 肌 以及关 系r = ，兰) ，如果存在排列a 满足对任意的f 【1 ，朋】都有( 4 ，b 。m ) 纯就称 此为字符串彳、曰的公共字符串划分。m c s p 问题就是找到彳、b 尺寸最小的公 共字符串划分，显然，答案是不唯一的。如果输入字符串中的每个字符最多出现 k 次，就称此问题为缸m c s p 问题。x c h e n 等已经证明m c s p 问题与反转排序 问题有着密切联系【2 1 。 归_ 山东大学硕士学位论文 1 2 相关知识 1 2 1 反转排序简介 反转排序( s o r t i n gb yr e v e r s a l ，s b r ) 问题是用字符串中的字符来代表不同 的基因，用反转距离来衡量两个基因序列的相似度，在基因序列对比研究中发挥 着重要作用 3 , 4 , 5 1 。反转排序问题有两个版本，一个是每个字符串中的字符仅出现 次，即1 - s b r 问题【6 】；另一版本是字符串中的每个字符最多出现k 次，称此问 题为k - s b r 问题m 。有符号序列的s b r 问题是多项式时间可解的引，并且为了 降低算法的运行时间，许多学者进行了深入研究1 9 , 1 0 1 。目前已有的最快算法的时 间复杂度是o k 刀l o gn ) h i 。而无符号序列的1 - s b r 问题是n p h a r d 问题【1 2 1 ， c h r i s t i e 给出了一个近似度为1 5 的近似算法【”】，而后p b e r m a n 给出了1 3 7 5 近 似算法【1 4 1 ，这也是目前已经知道的近似度最好的算法。对于k - s b r 问题，c h e n 等研究表明当k 2 时，有符号序列的k - s b r 问题是n p h a r d 1 5 1 ，毫无疑问，无 符号序列的k - s b r 问题也是n p h a r d 。目前，有符号序列的2 - s b r 问题和3 - s b r 问题都存在近似度为o ( 1 ) 的近似算法【1 6 ，1 7 1 。对于移位操作，当基因组带有符号时 是多项式可解的 1 8 , 1 9 , 2 0 】，当基因组是无符号时此问题为n p h a r d 问题2 1 1 ，目前已 知的最好近似度为1 7 5 2 2 1 。对于基因组的交换排序，目前已经存在多个1 5 近似 算法 2 3 , 2 4 , 2 5 】，而最好的近似度为1 3 7 5 t 2 6 1 。 与此紧密相关的是最小公共字符串划分( m i n i m u mc o m m o ns t r i n gp a r t i t i o n ) 问题，同s b r 问题一样，m c s p 问题也分有符号序列和无符号序列两种。当输 入为有符号序列时，问题采用兰关系，当输入为无符号序列时，问题采用= 关系。 同时，对无符号序列m c s p 问题还定义了另外一个版本r e v e r s e dm c s p ( 砌肥s p ) 问题，采用兰关系进行比较【2 7 】。 对于有符号序列么、b ，其最小公共字符串划分与最小反转距离已经证明存 在常数倍数关系，因此m c s p 问题被用来处理s b r 问题。当七2 时，有符号序 列和无符号序列的k - m c s p 问题是n p h a r d t 2 8 1 ，甚至是a p x h a r d 。c o r m o d e 和 m u t h u k r i s h n a n 首先给出了m c s p 问题的一个o ( 1 0 9 刀l o g 牛刀) - 近似算法，c h e n 等 给出了2 - m c s p 问题的1 5 近似算法，接着g o l d s t e i n 等给出了2 - m c s p 问题的 1 1 0 3 7 近似算法和3 - m c s p 问题的4 近似算法 2 9 , 3 0 娜1 。c h r o b a k 等人给出了 a 一z 山东大学硕士学位论文 2 - m c s p 问题的近似度为3 的贪心近似算法，同时他还证明了4 一m c s p 问题的贪 心算法近似度至少为q ( 1 0 9n ) ，而k - m c s p 问题的近似度为嘶0 4 3 ) 到o b n 6 9 ) 之 剐3 2 1 ，d a nh e 随即给出一个改进贪心算法，提高了算法的计算性能3 3 1 。p e t r k o l m a n 等人给出了缸m c s p 问题的e d u c a t e d 贪心算法，并证明近似度为 o ( k 2 ) 3 4 1 ，而随后他们又给出了k - m c s p 问题的碰集算法，将近似度提高到 o ( 尼) p5 1 ，这是目前已有的近似度最好的k - m c s p 问题近似算法。 1 2 2 最小公共整数划分简介 最小公共整数划分( m c i p ) 问题与m c s p 问题紧密相关。k 最小公共整数 划分问题( k - m i n i m u mc o m m o ni n t e g e rp a r t i t i o n ) 是由c h e n 等引入的新组合优 化问题郾1 ，与反转排序问题和多序列比对问题一样，是计算生物学中的热点问 题。如果一个正整数集合 _ ，一脚) 满足气2 刀，就称此集合为刀的一个划 分，用p ( 疗) 来表示。对于一个正整数集合f 胆- - 1 ， ，称集合产u 尸( t ) 为集合s 的整数划分。给定集合墨，瓯，如果集合r 满足对于任意的f ( 1 ，功，t 是s 的一个整数划分，就称丁是s ，& 的公共整数划分。若丁是所有公共整数 划分中最小的一个，就称丁为最小公共整数划分。例如，对于集合s l = 2 ，3 ， 5 ) 与蔓= 2 ，4 ，4 ) ， 2 ，3 ，l ，4 ) 和 2 ，2 ，1 ，1 ，4 ) 都是& ，s ：的公共整数 划分，并且可以验证 2 ，3 ，1 ，4 是s ，是的最小公共整数划分。 集合墨，s 。有公共整数划分的充分必要条件是每个集合中整数相加的总 和都相等，满足这个条件的集合称为相关集合。显然，其最小公共整数划分不具 有唯一性，可能同时具有多个。c h e n 等证明了当元2 时，k - m c i p 是n p h a r d 3 6 1 ， 并且给出了2 - m c i p 问题的5 4 近似算法和k - m c i p 问题的3 k ( k - 1 ) ( 3 k - 2 ) 近似算 法。随后，d a v i dpw o o d r u f f 给出了k - m c i p 问题的0 6 1 4 k - 近似算法【3 7 1 ，而z h a o 等给出了k - m c i p 问题的0 5 6 2 5 k - 近似算法【3 引。 3 m， 山东大学硕士学位论文 1 2 3 后缀树简介 后缀树是一种能有效支持字符串匹配和查询问题的数据结构，能够解决众多 的字符串问题。一个由m 个字符所组成的字符串s 所构造的后缀树就是一颗具 有根节点和恰好m 个叶节点的有向树，叶子节点标有1 到m 的标号。除根节点 以外的内部节点都至少具有两个子节点，并且每条边都是s 的一个非空子串。图 1 1 中示意了字符串”b o o k ”的后缀树。用椭圆来表示内部节点，矩形表示叶子节 点，该例子中有4 个叶子，被标号为l 到4 ，终止字符在图中被省略。 图1 1b o o k 后缀树示意图 后缀树具有以下几个重要特征：对于任何叶子节点i ，从根节点到该节点所 经历的路径串联恰好是字符串s 从第i 个字符开始的后缀，即字符串p ，司； 出于同一个内部节点的两条边不会具有相同的开头标识。后缀树的主要用途有以 下几种：第一，查找某个子串是否在字符串中出现；第二，指定某个子串在字符 串中出现的次数；第三，找出字符串中最长的重复子串；第四，找出两个字符串 的公共子串。文中公共字符串查找都用后缀树来实现。 1 3 本文组织结构 本文首先介绍以往m c s p 问题的研究结果，并对目前性能比较好的贪心算 法，n o v e l 贪心算法，e d u c a t e d 贪心算法以及碰集算法等近似算法进行描述并进 行实验测试，在此基础上点评了各个算法的优缺点。 然后设计了近似度为o ( k 1 的定界贪心近似算法，这是关于缸最小公共字符 4 曩 _一l 串划分问题的新近似算法。与目前已知的近似算法相比，拥有更好的计算性能， 并且巧妙的采用后缀树来实现算法，有效的降低了算法运行时间。随后设计实现 m c s p 问题的最优解算法与随机回溯算法。最优解算法可以计算出髓最小公共字 符串划分问题的一个或者所有最优解，对评估其他近似算法的实际运行效果有着 重要作用。随机回溯算法具有很高的灵活性，既可以求出最优解，也可以根据实 际要求在短时间内求出较好的解，两种算法都具有较高的实用价值。 最后，对m c s p 问题进行了总结与展望。 5 山东大学硕士学位论文 第2 章最小公共字符串划分问题复杂性 2 0 0 4 年，a v r a h a mg o l d s t e i n 和p e t rk o l m a n 证明当后2 时，五m c s p 问题是 n p - h a r d ，并设计了2 最小公共字符串划分问题的1 1 0 3 7 近似算法和3 最小公共 字符串划分问题的4 近似算法。本章首先介绍最小公共字符串划分问题的基本概 念与定义，然后对m