（计算机应用技术专业论文）程序中重复代码的自动检测.pdf

摘要 本文介绍了一个自动的检测程序中非连续参数化重复代码的方法。所作的工作有两 部分，( 1 ) 对b a k e r 的参数化匹配算法进行了改进。把匹配单位由单个的字符变为程序 中的语句，为了配合匹配单位的改变，重新定义了转换函数。经过改进，算法的空间复 杂性得到降低，使之更适于大型程序文本的匹配；( 2 ) 提出了程序碎片合并算法，判断 通过参数化匹配算法找到的重复代码段之间的可合并性，从而能从程序中识别出非连续 的近似重复代码。分析表明：改进的参数化匹配算法的复杂性同程序文件的行数成线性 关系；碎片合并算法的复杂性是o ( n 2 ) 的，其中n 是碎片所在依赖单位的语句个数。 关键字：重复代码；参数化匹配：后缀树：控制依赖；数据依赖 a b s t r a c t i nt h i st h e m sa na u t o m a t i cm e t h o dw h i c hi su s e dt od e t e c tt h ed i s c o n t i g u o u s p a r a m e t e r i z e dd u p l i c a t i o nc o d ei si n t r o d u c e d t h ec o n t e n to ft h ep a p e ri sd i v i d e d i n t ot w op a r t s ( 1 ) a ni m p r o v e dp a r a m e t e r i z e d m a t c h i n ga l g o r i t h mi sc o n s t r u c t e d t h e i m p r o v m e n t i st h a te x t e n d i n gt h em a t c h i n gu n i tf r o mt h ec h a rt o s t a t e m e n t ，a sa r e s u l tt h et r a n s f o r i l lf u n c t i o ni sr e d e f i n e da n dt h ec o m p l e x i t yo ft h ea l g o r i t h mi s d e c r e a s e d ，s oi t i sf i tf o rd e t e c t i n gt h ed u p l i c a t i o nc o d e si nm o r el a r g es c a l e p r o g r a m ( 2 ) af r a g m e n tc o m b i n i n ga l g o r i t h mi sd e s i g n e d t oj u d g et h ec o m b i n e da b i l i t y o ft h ep a r a m e t e r i z e dd u p l i c a t i o nc o d ef r a g m e n tw h i c ha r ef o u n db yt h ef o r m e rm e t h o d ， s ot h ed i s c e n t i g u o u sp a r a m e t e r i z e dd u p l i c a t i o nc o d ei sd e t e c t e d t h ea n a l y s i s i n d i c a t e st h a tt h en e wa l g o r i t h mh a sa na c c e p t a b l ec o m p l e x i t y t h ei m p r o v e d p a r a m e t e r i z e dm a t c h i n ga l g o r i t h mh a sl i n e a rt i m ea n ds p a c ec o m p l e x i t y ，f r a g m e n t c o m b i n i n ga l g o r i t h mh a s0 ( n 2 ) t i m ea n ds p a c ec o m p l e x i t i e s ( n i st h en u m b e ro f s t a t e m e n t so ft h ef u n c t i o nw h i c ht h ef r a g m e n tb e l o n g st o ) k e y w o r d ：d u p iic a tio nc o d e ；p a r a m e t e riz e dm a t c hin g ；s u f fixt r e e ；c e n t r ef d e p e n d e n c e ；d a t ad e p e n d e n c e 堡壁重墨垡里塑! 塾竺型 一 0 前言 o 1 解决程序中代码重复的现实必要性 一个大的软件系统在添加新功能或者做维护时，在程序中引入重复代码非常普遍。 因为在这种情况下，程序员对代码的结构不是很熟悉，为了减少给程序中引入新b u g ，他 不是新写一个程序段而是通过拷贝、粘贴，把实现类似功能的程序段拿过来，再稍加改 动，满足当前需求。这种称为c o p y p a s t e 的编程方法有很大危害： ( 1 ) 拷贝过来的代码也可能是有b u g 的。还没项 ( 2 ) 对重复代码任何一处的修改都必须涉及到其它很多地方，漏改了任何一处就 引入了一个新b u g 。 所以随着时间的推移和系统功能的不断添加，程序中的重复代码越来越多，代码规 模越来越大，程序结构越来越复杂，系统也就越来越难于理解。当其他的程序员为系统 扩充功能时，因为很难理解程序功能，就不得不采取同样的方法一从系统中拷贝实现 类似功能的程序块。这样又增加了重复代码。大部分失败的软件系统到最后都陷入了这 样一个恶性循环，直至很难在系统中添加个新的功能模块。 即使在一个成功的软件系统中重复代码也是很多的( 所谓成功的就是能交付给用户使 用的) 。有统计数字表明，在一个大的软件系统中有大约7 2 3 的代码是重复代码( 大 于3 0 行的代码段) ，尽管这个系统可能已经交付使用，但是这么多重复代码的存在，也是一 个重大的隐患，因为如上所述，它使得程序的维护很困难。 重复代码的危害是显然的。但是在软件开发中却没有有效的方法来控制它，只能凭 着系统设计人员的经验或者程序员的觉悟来手工消除它。 在大型的软件开发组织中，对一个较新领域的软件系统，都是在软件工程实施过程 中( 如迭代过程) ，由系统设计人员根据上一次迭代中的系统代码状况，更改设计。这就 要求设计人员熟悉系统的代码状况。能从重复的代码段中抽取出类或者公共函数，以优 化系统设计。当系统规模较小时，可以通过设计人员阅读代码来发现程序中的重复代码， 但是如果系统规模很大，这种方法就难以胜任了。 此外，对现有系统的维护，或者是原有系统的升级，也需要检测出程序中的重复代 码。如果只凭着程序员对程序的理解去寻找，然后处理，那么不仅费时费力，而且风险 很大，因为程序员的行为会给系统引入b u g 。 随着极限编程方法( e x t r e m ep r o g r a m m i n g ) 在提高软件开发效率、保证软件质量方面 的优点日益得到认可，越来越多的软件开发组织采用极限编程方法。但是极限编程方法要 求的实时重构、代码共享却很难在开发中实施，这是因为程序员很难精确的理解程序中的 代码结构，如果有一个重复代码自动检测工具，将会大大促进极限编程方法的应用。 程序中重复代码的自动检测 0 2 最新研究进展 程序中的重复代码问题，很早就引起了人们的注意。在u n i x 下的d i f f 可以称得上 是一个比较初级的重复代码检测工具，它是基于文本比较的。当然它只能处理最简单的 那种完全相同的代码，而且是两个文件的比较，无法完成自身的比较。实际上重复代 码的检测都要求在一个文件( 一个软件系统) 内进行，显然d i f f 应用的范围是很有限的。 为了实现同文件的比较，m a t t h i a sr i e g e r 和s t e p h a n ed u c a s s e 实现了一个工具 d u p l o c ”1 ，它实现程序文件和其自身之间的逐行比较，得到一个1 3 阶的比较矩阵，n 是程序 文件的行数。在矩阵中，如果n 一= 1 ，则表明文件的第i 行和第j 行相同，如果n 。= o ，则 表明文件的第i 行和第j 行不同；显然矩阵的1 1 = 1 ，即正对角线上全为1 ：如果比较矩阵中 出现同矩阵的正对角线平行。且连续的一个序列如：。= 1 、。= l 、n | 。= 1 、 n 。一。+ k 一1 其中m n ，那么就表明程序文件的第m 彳亍到第m + k 行同程序的第n 行到第n + k 行重 复。 d u p l o c 同d i f f 相比前进了一大步，因为它能检测出一个程序文件中的所有相同的代 码，但是它与d i f f 并没有本质的区别。d u p l o c 依旧使用文本比较方法。显然它只能检测 出程序中连续的完全重复代码，这使得它在实际中的应用较窄，因为在程序中有很多非 连续的完全重复代码。 另外d u p l o c 算法的复杂性较高，对于一个n 行的程序，算法的时间复杂度至少为0 ( n 2 ) ，这就限制了它在较大规模程序中的应用。 为了检测出非连续的重复代码，k o m o n d o o r 和h o r w i t z 提出了一种新的方法一即使 用程序切片技术的重复代码检测方法。在此方法中，首先构造出程序的程序依赖图( p d g ) ， 然后使用文本比较方法，找到重复的某个语句，在p d g 中以这两个重复的语句为中心， 找到同构的p d g 子图，在这两个p d g 子图中，以重复语句所在的节点为起点，分别检索 和这两个节点有对应依赖关系的语句是否是相同的，以找到一个重复的程序切片。据此 可以识别出程序中的非连续的完全重复代码。 k o m o n d o o r 和h o r w i t z 的方法较d u p l o c 有较大进步，但是它的局限性也很大。 首先，它能处理的程序的规模有限；使用这种方法必须先生成程序的p d g 图，然后 通过文本比较找到重复的语句。在p d g 中找出同构的子图，所有这些步骤的复杂性都是 很大的。在“中的例子中，对于一个只有1 万行的程序就用时近两个小时，如果程序的 规模有1 0 万或者1 0 0 万的话，那么此方法的执行时间是让人难以忍受的。 其次，对某些重复代码发现不了：对于下面的程序段( 由于仅仅是为了说明问题， 所以这段程序很简单) ，设语句( 1 ) ( 2 ) 同另外一个函数f 中的语句( n ) ( n + 1 ) 重 复；语句( 3 ) ( 4 ) ( 5 ) 同f 中的( n + 2 ) ( n + 3 ) ( n + 4 ) 重复，如果使用k o m o n d o o r 的方法却无法发现语句( 1 ) ( 5 ) 和f 中的语句( n ) ( n + 4 ) 重复，这是因为 语句( 1 ) ( 2 ) 和语句( 3 ) ( 4 ) ( 5 ) 没有依赖关系，那么它们必然不会存在同一个程 序切片中，所以在检测重复代码时也不会把它们作为一个整体识别出来。 i f ( f t ：却)( 1 ) f t = a r c c t ( f t ，p ) ；( 2 ) 程序中重复代码的自动检测 n u m = n u m * o u t ：( 3 ) p t = n u m + i n ： ( 4 ) r e t u r np t ：( 5 ) 最后，毕竟程序中的完全重复代码的数量较少，程序中更多的是近似重复代码，所 以k o m o n d o o r 的方法能检测出的重复代码还是太少。 为了能够检测出更广意义上的重复代码，贝尔实验室的b a k e r 做了独特的工作。“”。 她提出的参数化后缀树匹配方法，解决了变量名不同的重复代码的检测问题，使得重复 代码的自动检测大大前进了一步。大家知道当从别处拷贝一个程序块到一个方法或者函 数时经常出现变量名冲突，所以需要把程序块中的变量重命名，经过重命名后的重复代 码，使用文本比较方法是无济于事的。b a k e r 的参数化匹配方法解决的就是这种重复代码 的识别问题。 但是这仅仅对连续的近似重复代码有效，对非连续的近似重复代码的识别仍然没有 解决。 0 3 本文所做的工作和结构 我们知道在软件开发中经常使用c o p y - - p a s t e 方法，即编程时对于新增的某个函数 或者功能，程序员不去新写一段来完成，而是从已有程序中拷贝实现类似功能的程序段， 再稍加改动。改动是因为拷贝过来的程序块有一条语句可能没有用，需要删掉，又或者 需要在这个拷贝过来的程序块中加上几条语句；现在这段代码和它原来的模样已经面目 全非了，但是实际上它的大部分还和原来一样，依旧是重复代码，只是重复代码中间夹 杂了一些不相关的语句。 更严重的是程序员在软件开发中对拷贝过来的程序块不仅做文本意义上的修改( 对 部分变量重命名) ，还经常做程序结构( 对某两条语句颠倒顺序) 或者程序行为上的修改。 这时b a k e r 的办法也无能为力了。因为b a k e r 的方法实质上还是基于文本比较的， 丝毫没有涉及到程序的深层次的特点，如程序结构、程序行为等。所以在这种情况下， 它发现的重复代码只是一些很小的碎片，如只有一行或者两行重复。显然如果重复代码 的粒度很小，是没有意义的，因为我们不可能新建一个只有两行代码的新函数。实际上 在使用参数化匹配方法检测重复代码时，检测出来的9 5 重复代码因为粒度太小而不具 有处理的意义“。 本文对“中的参数化匹配算法进行了改进，使得算法更高效；扩充了依赖图的定义， 把控制依赖关系和数据依赖关系分开表示，以利于对出现碎片的函数或者函数的片段进 行分析；提出了一个碎片合并算法，把部分碎片合并成更大的代码段，使无意义的重复 碎片变成有意义的重复代码“，以识别出程序中的非连续近似重复代码，解决了它们不 能解决的问题。 本文是按如下顺序组织的：第一章对程序中出现的几种重复代码进行了分类；第二 章阐述了b a k e r 的参数化匹配算法的思想及我对它算法的改进，并使用了实例来说明它 的执行过程和检测结果；第三章探讨了依赖图的问题，并将其根据我们的应用做了某些 修改，如：在依赖图中只讨论控制依赖和数据依赖，并把数据依赖图单独表示；第四章 程序中重复代码的自动检测 综合了参数化匹配算法和依赖图思想，说明如何使用这两个方法检测出程序中的重复代 码；第五章是结论和展望。 程序中重复代码的自动检测 1 程序中的重复代码 1 1 重复代码分类 程序中的重复代码有很多种，根据它们形态的不同，分为以下几种。 i ) 完全重复的代码 两段代码语句完全相同的情况，这是最简单的一种重复代码。这种代码在程序中有 很多，但长度都不大。 m a t t h i a sr i e g e r 的d u p l o c 就只能检测出这种重复代码。 2 ) 非连续的完全重复代码 完全重复的代码在程序中很常见，但是有时在重复代码之间夹杂一些不相关的语句， 如果把这些不相关的语句放到重复代码的前面或者后面，那么这两段重复的代码就连成一 体，形成了一个更大规模的重复代码。如下面的例子所示，第一段程序的1 、2 两行同第二 段程序的5 、6 两行完全重复；3 、4 两行同7 、8 两行完全重复，使用d u p l o c 只能识别出这样 两段重复代码，但是由于它们的长度很小，没有实际意义。 w h i l e ( i s a l p h a ( e ) ilc = = llc = = i ) 注释 i f ( p = = t o k e n b u f f e r + m a x t o k e n )+ + ( 1 ) p = g r o w t o k e n b u f f e r ( p ) ：+ + ( 2 ) i f ( c = = 一) 一一( 1 ) e = 一： 一一( 2 ) p + + 2c ：+ + ( 3 ) o 2 g e t e ( f i n p u t ) ：+ + ( 4 ) ) w h i l e ( i s d i g i t ( o ) ) i f ( p = = t o k e n b u f f e r + m a x t o k e n )+ + ( 5 ) p 。g r o w _ t o k e n _ b u f f e r ( p ) ：+ + ( 6 ) n u m v a l 2n u m v a l * 2 0 + c 一0 i 一一( 3 ) $ p + + 2c ； + + ( 7 ) c 2 g e t c ( f i n p u t ) ：+ + ( 8 ) k o m o n d o o r 和h o r w i t z 在重复代码识别中使用了程序切片技术，能发现1 、2 实际 上可以移到l 、2 之前，3 1 可以移到5 、6 之前，从而发现1 、2 、3 、4 和5 、6 、7 、8 完 全重复，识别出程序中的非连续完全重复代码。 3 ) 参数化重复代码 翌嬖程窘唆了一些一一对应的参数候选如：变量、常量、成员结构变量之外，其它都 是相同的，这样的重复代码称为参数化重复代码。 程序中重复代码的自动检测 在下面的例子中，除了一一对应的变量名p f i p f h 和结构的成员名l b e a r i n g l e f t 、 r b e a r i n g r i g h t 不同之外，其它的代码完全相同。 f r a g m e n t l ： c o p y n u m b e r ( & p m i n ，& p m a x ， p f i 一 m i n _ b o u n d s i b e a r i n g ， p f i 一 m a x b o u n d s i b e a r i n g ) ： * p m i n + + = * p m a x + + = ，： c o p y n u m b e r ( & p m i n ，& p m a x ，p f i 一 m i n _ b o u n d s r b e a r i n g p f i 一 m a x _ b o u n d s r b e a r i n g ) ： * p m i n + + = * p m a x + + = ，： f r a g m e n t 2 ： c o p y n u m b e r ( & p m in ，& p m a x ， p f h 一 m i n b o u n d s 1 e f t ， p f h 一 m a x b o u n d s 1 e f t ) ： * p m i n + + = * p m a x + + = ，： c o p y n u m b e r ( & p m i n ，& p m a x ， p f h 一 m i n _ b o u n d s r i g h t ， p f h 一 m a x _ b o u n d s r i g h t ) ： * p m i n + + = * p m a x + + = ，： b a k e r 的参数化匹配方法能忽略程序中变量名的不同，而抓住程序中不变的东西如：表 达式、运算符等，完成参数化重复代码的识别。 参数化匹配方法不仅能识别出程序中的参数化重复代码，还能识别出完全相同的代码， 因为完全相同的代码实际上是参数化重复代码的特例。 4 ) 近似重复代码 近似重复代码也称非连续参数化重复代码，它指的是两段代码中有数段语句是参数 化匹配的，但在这些参数化匹配的代码段之间有若干不相关的语句。如果把这些无关语 句提取到参数化匹配的代码段之前或者之后的话，近似重复代码就退化为参数化重复代 码。 f r a g m e n t l ： v o i df 1 ( ) t c n a re ： in t 术p ，t o k e n b u f f e r ，m a x t o k e n ： 注释 w h i l e ( i s a l p h a ( e ) il c= 注释 i f ( p = = t o k e n b u f f e r + m a x t o k e n ) p = g r o w _ t o k e n b u f f e r ( p ) ： i f ( c = = ，_ ) 程序中重复代码的自动检测 c = 一： 水p + + = c ： c = g e t c ( f _ i n p u t ) ： ) r e t u r n ： ) f r a g m e n t 2 ： v o i dr e a d b u f f0 1 c h a rc ： i n t * p o i n t ： i n t t o k e n _ b u f f e r ，t o k e n ： 注释 w h i l e ( i s d i g i t ( c ) ) f 注释 i f ( p o i n t t o k e n b u f f e r + t o k e n ) p o i n t = g r o w _ t o k e n _ b u f f e r ( p o i n t ) n u m v a l = n u m v a l * 2 0 e 一0 4p o i n t + + = c c = g e t c ( f i n p u t ) ： + + + + + + + + + + + + ) ) 如上段程序所示，标“+ + ”号的语句为参数化重复代码，两段参数化重复代码中间 央有可以提取到参数化重复代码之前的无关代码“一一”。显然使用b a k e r 的参数化匹配 方法只能检测出两个参数化重复的碎片，它无法发现这两个碎片可以合并成一个较大的 重复代码块，这正是我们的方法所能解决的问题。 1 2 程序中重复代码产生的原因 深入分析程序中重复代码产生的原因会发现，重复代码只产生于程序开发的两个阶 段开发阶段和维护阶段。 对于一个较新领域的软件系统，”设计人员不可能一开始就得到一个好的设计”。 在最初的几个迭代过程中，系统的设计总存在这样或者那样的问题。要么是某个常用的 公共函数没有定义，要么是没有定义某个应该定义的类，这些问题都使得程序员在书写 程序时，不得不引入重复代码。 在维护阶段，因为维护人员不一定是开发人员，他可能对系统结构和各功能模块理解 不深，因此当修改程序或者给程序添加新的功能模块时，就可能使用c o p y p a s t e 的方 法，在系统中引入重复代码。 、7 程序中重复代码的自动检测 在这两个阶段引入的重复代码各有其不同的特点。在开发阶段，如果开发组内的程 序员很多，那么对于某个设计人员忽略的常用功能模块，不同的程序员可能有不同的实 现，那么此时引入的重复代码之间的差别一般很大，更经常出现的是“近似重复代码” 和“参数化重复代码”。维护阶段引入的重复代码最根本的原因是维护人员对系统理解不 够，当需要修改b u g 或者添加新功能时为了达到尽量少的更改代码的目的( 因为不理解 代码所以不敢大规模的修改代码或者添加新代码) ，都是从系统中拷贝已有的程序块，做 出尽量少的修改，实现所需的功能，这时出现在程序中的是大量的“完全相同的”重复 代码。 1 3 一种新的近似重复代码检测方法 b a k e r 的参数化匹配方法能解决的问题很有限，实际上在一个大规模的程序中，能通 过参数化匹配算法检测出来的参数化重复代码有9 5 是只有少数几行的碎片“1 。另外尽 管b a k e r 对参数化匹配算法做了很大的修改，算法的复杂性也都是线性的，但是由于处 理对象的规模实在太大( 一个大规模程序甚至都上百万行，字符数有上千万甚至上亿个) ， b a k e r 的算法在空间复杂度上还是显得太高了。 为了解决这些问题，首先对参数化匹配算法进行了改进，即把程序中的语句作为一 个匹配单位，而不是仅仅对语句中的字符”“”进行比较，使得算法更适合程序语句间的 匹配。大大降低了算法的空间复杂度，算法的时间复杂度还是线性的。 其次，把在“程序切片”技术中常用的依赖图，应用于重复代码检测中。在使用参 数化匹配算法检测出程序中的参数化重复碎片后，构建碎片所在函数或者函数段的数据 依赖图，以此描述程序内部的数据流关系，然后通过依赖图分析碎片和碎片间夹杂的代 码的关系，判断碎片间的可合并性，如果是可合并的，就识别出了程序中的非连续参数 化重复代码。这种方法使许多无意义的重复代码碎片变成较大的重复代码段，增大了重 复代码的粒度，基本上解决了上面使用参数化匹配算法无法解决的问题。 在接下来的两章中将详细的讨论参数化匹配和依赖图。 程序中重复代码的自动检测 2 参数化匹配 参数化匹配最早在”1 中讨论过，它最初用来判断两个表达式是否“同构”。由于程序 中的参数化重复代码同“同构”表达式在某些方面的类似性，b a k e r 把”中的参数化匹配 经过改进，应用于程序中的“参数化重复代码”的检测。 显然应用对象的改变( 从表达式语句变成程序文件) 给原来的方法带来了新问题，如： ( 1 ) 在表达式匹配中，待匹配字符串的规模很小，只是两个表达式的长度。而在程序 文本的参数化匹配中，字符规模很大，有时甚至有数百万个字符等待匹配，这就要求要对 原来的算法进行改进，以降低算法的复杂度。 ( 2 ) 由于表达式匹配中，作为匹配参数的变量数目较少，最多也就几十个，所以使用 变量对应表实现变量的参数化匹配；而在参数化匹配算法中由于参变量的数目很大，对于 一个大规模的程序。甚至都达到了1 0 5 量级，所以如果再使用以前的方法，在执行时间和空 间上是无法忍受的。 在本文所改进的参数化匹配算法中，使用了参数化后缀树这种数据结构来存储和检测 程序文本，使算法的空间复杂度和时间复杂度降低到一个可接受的程度，为重复代码检测 走向实用奠定了理论基础。 下面各节的内容组织如下：第一节介绍了参数化匹配的基本原理及其相关定义；第二 节介绍了后缀树和参数化后缀树；第三节给出了参数化后缀树的改进算法；第四节是关于 这个参数化后缀树构造算法的时间复杂度和空间复杂度的分析；第五节是参数化后缀树构 造算法的中间状态及运行实例。 2 1 参数化匹配的基本原理 在进行进一步的讨论之前，介绍一下有关参数化匹配的基本定义和定理。 定义1 设和n 是两个相互独立且有穷的字母表。中的字符称为常量，i i 中的符号 称为参数，则( ui i ) 中的字符串就称为参数化字符串也称p s t r i n g 。 定义2 两个p - - s t r i n g 是参数化匹配的也称p - - m a t c h i n g 的，如果这两个p s t r i n g 中的 参数化符号是一对映射的，重命名一个p s t r i n g 中的参数化符号就可以转换为另一个p - - s t r i n g 。例如：如果兀= x ，y ，v ) ，= a ，b ，c ，那么s = a y a v b y v c b v 和t = - a x a y b x y c b y 就是参数化匹配的，因为把s 中的y ，v 分别替换为x ，y 后s 和t 相同。 判断两个表达式是否是使用了同一个公式就用到了参数化匹配，这种参数化匹配很简 单，只涉及到变量和数字，需要匹配的字符串也很短”。显然，判断这样的两个p s t r i n g 是否是参数化匹配的很容易：从左到右的扫描两个p - - s t r i n g ，对其中的参数符建立一个一 一对应的表，直至找到失配符或者完全一一对应。但是这个方法在这里行不通，因为如果 使用它就必须在失配时回溯，而我们需要匹配的文本很大，在大文本比较时使用回溯就意 味着难以承受的时间复杂度和空间复杂度。 为此，定义了p r e y 函数。 程序中重复代码的自动检测 定义3 设n 是非负的整数集，定义一个函数p r e v ：( ui i ) 术一( un ) ，如果 s = b l b 2 b 。，那么p r e y ( s ) = c i c 2 c 。，其中： ( 1 ) c 。= b i ，当b ，时； ( 2 ) c x = o ，如果b t y i 且i 是b 。是在s 中的第一次出现的位置； ( 3 ) c i = i k ，如果b ，n 且b 。是b 。在s 中的上一次出现。 当c 。诺e 时，称其为参数化指针。 例如：对于= 马6 ) 和= 珥巧与j ， ，那么p r e y ( a b u v a b u v u ) = a b o o a b 4 4 2 = p r e y 白b x y a b x y x ) 。 n 中的参数化字符可以! 建立一个表索引，每一个参数符在文本中最后一次出现的位置 也建立一个表索引，那么计算p r e v 函数的时间复杂度就与文本长度成线性关系，空间复杂 度与inl 成线性关系。 使用p r e y 函数就可以较严格的定义参数化匹配。 定义4 p s t r i n gs 和s 是参数化匹配的当且仅当p r e y ( s ) - - - - p r e y ( i ) 。 定义5 如果s = b 山：b 。是p - - s t r i n g ，那么定义p s u b ( s ，i ，j ) = p r e v ( b 。b j ) ， 当i j 时；当j j 一1 ： f ( b ，j ) = b否则。 定义8 程序文本中的“语句”：程序中通常意义上的句子是一条语句，在程序中形如： i f ( c o n d i t i o n s ) 、w h i l e ( c o n d i t i o n s ) 、f o r ( ：) 等都是语句。 0 1i n t j ： 0 2d o u b l ek d o u b l e ： 0 3 i f ( j 0 ) 0 4 k d o u b l e = s q r t ( k d o u b l e ) ： 0 5r e t u r nk d o u b l e ： 在上面的一段示例程序中，第l 、2 、3 、4 、5 行都是语句。 在重复代码检测中，需要匹配的是程序，而程序是按行组织的，对于我们来说，找到 一条语句的一部分与另一条语句的部分或者全部匹配，是没有意义的，我们只关心整个语 句和整个语句之间的匹配，即对我们来说，一条语句才是一个匹配单位。因此有下面的定 义。 定义9 匹配单位：参数化匹配中的最小比较单元。如在字符a t = a b x y a b x y x 的匹配 程序中重复代码的自动检测 过程中，每一次都只比较一个字符，所以在t 的参数化匹配中的匹配单位就是一个字符。在 本文中一个匹配单位就是一条语句也成为句子。 为了研究的方便，限定待匹配程序由c 语言书写，另外我们再对程序的书写规则傲如下 限制： ( 1 ) 程序中的语句是按行组织的： ( 2 ) 如果“：”是行结束符，那么每一行至多有一个“：”： ( 3 ) 形如”i f ( c o n d i t i o n ) ”、“w h i l e ( c o n d i t i o n ) ”、“d o ”、“e l s e ”、“e l s e i f ”、 “c s s e ”、“s w i t c h ”、“f o r ( ：) ”、的语句单列一行； ( 4 ) 当“ ”和“) ”单独行时，把它们合并到上一行中，一行中的“( ，或“) ” 不能超过一个，如果超过一个则不合并； ( 5 )程序中的注释语句忽略不计； ( 6 )程序的中形如“# i n c l u d e ”、“d e f i n e ”等等的预编译语句忽略不计。 显然加以限制后程序中的一条语句就是一个句子。在后面的讨论中，如果不加以特别 声明，所说的字符就是一个匹配单位。 2 2 后缀树和参数化后缀树 参数化后缀树由后缀树“”进化而来，只是根据p s t r i n g 的特点做了适当修改，在讨论 参数化后缀树之前，先看一看后缀树的定义。 后缀树是一种可以高效的进行模式匹配的数据结构，它在字符串匹配、大规模文本检 索、语音识别和分子生物学中的d n a 识别上都有重要应用。 定义1 0 一个树( t r i e ) t 是满足以下条件的具有相同的根的字符串集 s l ，s 2 ，s r ： 1 每一条边都以一个字符为标识，任何兄弟边的标识符都不同。 2 t 中每一个节点v 都对应一个字符串，以p a t h s t r i n g ( v ) 表示，p a t h s t r i n g ( v ) 是从 根到v 所经过边的标识符的连接。 3 如果有p a t h s t f i n g ( v ) 是某个s i 的前缀，那么t 中肯定存在节点v ，且只有一个。 定义11 压缩树( c o m p a c t e dt i l e ) ：在t i l e 中删去儿子数为l 的节点，并把它的标识符 合并至它的儿子上，重复此过程直至t i l e 中的所有的非叶节点的儿子数都大于等于2 ，就得 到了压缩树。 设有一个字符串s ，s i ，s 2 ，s 。是s 的所有后缀，那么s 的后缀树就是所有的叶子 节点的p a t h s t r i n g 分别为s i ，s 2 ，s 。的压缩树。 对于字符串s ，为了在后缀树中表示它，规定： s 的结束符( 即最后一个字符) 不在除了结束位置外任何其它位置出现的字符。 s 的后缀树t 有以下属性： t 1 ：t 中的每个弧都以一个非空的字符串标识； t 2 ：t 中的除了根节点之外的非叶节点都至少有两个儿子： t 3 ：设t 中的某个节点到它的儿子节点的弧的标识符分别为字符串h l ，k ，那么 h l ，h 。的第一个字符必定不同。 程序中重复代码的自动检测 定义1 2 t 是字符串s 的后缀树，s 是s 的字串，v 是t 中的节点，如果p a t h s t r i n g ( v ) = s ， 那么v 就是s 的“轨迹”。 定义1 3 字符串s 的扩展就是以s 为前缀的字符串。那么s 的“扩展轨迹”就是t 中 p a t h s t r i n g 是s 的最短扩展的节点。 定义1 4 字符串s 的“收缩轨迹”就是t 中p a t h s t r i n g 为s 的最长前缀的节点。空串的“收 缩轨迹”是根结点。 设是字母表，s = a 。a ：a | 】是字符串，a 。n s 的子串a 。钆都是s 的后缀，其 中1 i n 。为了研究的方便，定义s 的最后一个字符为唯一的结束符，则有任意后缀都不 是另一后缀的前缀。后缀树实际上是un 上的压缩了的t r i e ( 多路p a t r i c i a 树) ，它表 示了输入字符串的所有后缀“。如图2 - 1 就是一个后缀树，树的每一条弧都以s 的非空子串 标识，非叶节点的度至少为2 ，且它指向其孩子的弧的标识符的前缀各不相同。对于后缀树 中的叶子节点，把从根到此叶子所经过路径弧的标识符串联起来，则是s 的唯一的一个后缀。 由于每个节点至少有两个孩子，因此非叶节点数一定小于叶子节点，又由于叶子结点数为1 3 ， 则后缀树的节点最多为2 n 个。另外因为没有任何一个后缀是另一个后缀的前缀，那么在叶 子节点和后缀间存在一一对应关系。 由p s t r i n g 生成的后缀树就称为参数化后缀树。参数化后缀树的相关定义如下。 定义1 5 如果s 是一个以唯一的中止符$ 结尾的p s t r i n g ( $ 未在s 中除结尾位置外任何 地方出现) ，那么s 的p s u f f i x 树实际上是压缩树( 也是多路p a t r i c i a 树) ，它存储了s 的所 有后缀。 s 的参数化后缀树中弧的标识符是s 的后缀的非空子串非叶节点的度至少为2 ，它指向 其孩子结点弧的标识符的第一个字符不同。对于每个叶子，把从根到叶子的路径上弧的标 识符串联起来，就是s 的一个后缀，因为s 以一个唯一的结束符为结尾，那么任何后缀都不 会是其它后缀的前缀，由于在叶子和s 的后缀树间存在一一对应关系，那么s 的参数化后缀 树的结点数与i s 成线性关系。 例如：p s t r i n gs = u b v b u b v $ ，= a ，b ，$ ，y i = u ，v ) 。s 的后缀树如图2 1 所 示，树中的后缀有o b o b 4 b 4 $ ，b o b o b 4 $ ，o b o b 4 $ ，b o b o $ 等。 定义1 6 对参数化后缀树的任节点v ，定义p a t h ( v ) 为从根结点n v 节点的弧的序列； 定义v 的p a t h s t r i n g 为p a t h ( v ) 中的所有弧的标识符的联接就是句子的一个序列，记为p a t h s t r ( v ) ，显然由于我们的一个匹配单位是一个句子，所以弧的标识符就是句子的序列，节点 v 称为此p a t h s t r i n g 的轨迹；p a t h s t r i n g 的长度就是路径的长度( 句子的个数) ，即路径长度 p a t h l e n ( v ) = p a t h s t r ( v ) 。 我们的参数化后缀树受m c c r e i g h t 的后缀树“”的启发，但是两者有区别，因为m c c r e i g h t 的算法是通常意义上的字符串，而我们要研究的是参数化字符串，参数化字符串具有通常 的字符串所不同的性质。 普通的串的有以下两个重要性质： 如果s 和t 是字符串，a ，b ，c ，d 是字符，那么有： ( 1 ) ( 共同前缀性质) 如果a s = b t ，那么s = t ： ( 2 ) ( 唯一正确上下文性质) 如果a s = b t ，且a s c c b t d ，那么s c = t d 。 因为有以上两个性质，才可能使用称为后缀链的指针来扩展后缀树，方法如下：假设 程序中重复代码的自动检测 有个非叶节点的p a t h s t r i n g 是a ，a 是字符，q 是串，那么它的后缀链就是指向p a t h s t r i n g 是a 的非叶节点，根节点的后缀链还指向根节点。后缀链的定义就基于上述两个性质。 p a t h s t r i n g 为aq 的非叶节点的存在意味着至少有两个不同的字符串具有相同的前缀a n ，性质( 1 ) 保证如果把第一个字符a 从字符串中去掉，那么原来的这些字符串还有公共 前缀q ；性质( 2 ) 保证除了之外，再也没有其它的前缀，这意味着具有p a t h s t r i n g 为 的节点的唯一性。 性质( 1 ) 可以推广到p s t r i n g 上，但是性质( 2 ) 却不能。 图2 一l p s t r i n gs 的后缀树，s = u b v b u b v $ ，p r e y ( s ) = 0 6 0 b 4 6 4 5 f i g u r e 2 1 t h es u f f i xt r e eo fp s t r i n gs ，s = u b v b u b v $ ，p r e y ( s ) = 0 b ) b 4 b 4 $ 定理1 p - - s t r i n g 的共同前缀性质：设s s h t 是p s t r i n g ，并且a ，b un ，如果p r e y ( a s ) - - - - - p r e y ( b t ) ，那么p r e y ( s ) - - - - - p r e y ( t ) 。 证明：显然s 和a s 的区别只是把a 去掉了，那么p r e v ( a s ) 与p r e y ( s ) 的不同就是p r e v ( a s ) 中原来a 的第二次出现的参数化指针变为0 ( 如果参数化指针存在的话) ：p r e v ( b t ) 和p r e v ( t ) 亦然，因为p r e y ( a s ) = p r e y ( b t ) ，所以如果参数化指针存在的话，它们必 然在同一位置，显然当a 、b 从两个字符串中分别去掉的话，这两个参数化指针同时变为0 ， f f p p r e v ( s ) = p r e y ( t ) 。 原命题得证。 p s t r i n g 中性质( 2 ) 的失效是因为p r e v 函数的作用，在去掉某个串的前缀后，它把 部分诈整数变为y o 。例如，如果s = x a b x y a b z ，= a ，b ) 和h = fx ，y ，z 。那么d r e v ( x a b x ) = 0 a b 3 ，p r e y ( y a b z ) = o a b o 。它们有公共前缀o a b ，但是p r e y ( a b x ) = a b o = p r e v ( a b z ) ，此 时性质( 2 ) 失效。 程序中重复代码的自动检测 为了使性质( 2 ) 继续起作用，必须加以严格的限制。 定理2 ( p s t r i n g 中受限的唯一正确上下文性质) s 和t 是长度为k 的p s t r i n g ，且 a ，b ，c ，d u 兀，假设p r e y ( a s ) = p r e v ( b t ) ，且p r e v ( a s c ) p r e y ( b t d ) ，如果 p r e y ( s c ) = p r e v ( t d ) ，那么p r e v ( a s c ) 和p r e y ( b t d ) 中有一个的最后一个字符为k + 】，而另一个的最后一个字符是0 。 证明：显然p r e v ( a s c ) s u p r e v ( b t d ) 只是最后一个字符不同，因为p r