（计算机应用技术专业论文）程序代码相似度度量研究.pdf

中文摘要 计算机程序代码相似度的自动度量，不仅可以帮助教师检查学生作 业中的抄袭现象，还可以辅助实现作业批改或试卷评阅的自动化，对程 序代码版权的辅助鉴别也具有很重要的现实意义。 本文讨论了目前常用的程序代码相似度度量技术：属性计数技术和 结构度量技术，并介绍了几个国外已有的程序代码抄袭检测系统。 本研究主要是针对程序代码进行相似度度量，由于程序设计语言固 有的特性，如：语言成分较少，针对每门具体的语言都只有有限多个关 键字，结构简单等，且国外的相关技术也比较成熟，所以与自然语言文 本相似度的度量相比要简单一些。 本研究设计了一个实验系统，主要用于检查用c c + + 语言编写的程 序代码文件之间的相似度。 实验系统首先对程序代码作预处理，去掉对相似度度量结果无影响 的成分，如程序中的注释、空行以及文字部分等。然后扫描预处理后的 程序代码并对其作简单的语法分析，将其转换为包含程序结构信息的标 记字符串。考虑到系统的扩展性，所以使用了x m l 文档描述程序设计语 言的语法，即用x m l 文档定义什么是标记以及程序代码与标记字符串之 间的转换规则。最后通过g s t ( g r e e d ys t r i n gt i l i n g ) 字符串匹配算法对 得到的标记字符串作比较，并根据比较结果给出它们之间匹配程度的数 值表示，以此作为程序代码相似度的度量值。该值越大说明程序代码越 相似，存在抄袭的可能性也越高。g s t 算法的一个最大优点是，程序代 码中某些代码段位置的变化并不影响最终的匹配结果。对于相似度度量 结果值较高的程序对，实验系统会根据用户的选择自动打开每对程序代 码文件，并用醒目的颜色标记出相似或相同的代码段。 最后，用两组实验数据对实验系统进行了简单的验证和分析。一组 是学生程序作业中的一部分代码文件，一组是通过手工添加复制代码段 或修改原程序的方式设置的。验证结果表明，该实验系统能检测到实验 数据集中大部分的相似代码。 关键词：程序代码，相似度，度量，g s t 算法 a b s t r a c t a u t o m a t i c a l l ym e a s u r i n gt h es i m i l a r i t i e sa m o n gp r o g r a mc o d et h r o u 【g h c o m p u t e rc a l ln o to n l yh e l pt e a c h e r st od e t e c tp r o g r a mp l a g i a r i s m , b u ta l s o c a na u t o m a t i c a l l yc o r r e c tp r o g r a m m i n ga s s i g n m e n t sa n dp a p e r s i th a s i m p o r t a n tr e a l i s t i cm e a n i n gf o rd i s c r i m i n a t i n gt h ec o p y r i g h to f p r o g r a mc o d e t h i st h e s i sd i s c u s s e st h ep r e s e n tt e c h n i q u e so fm e a s u r i n gt h es i m i l a r i t i e s a m o n gp r o g r a m s ：s t r u c t u r em e t r i c sa n da t t r i b u mc o u n t i n g i ta l s oi n t r o d u c e s s e v e r a lf o r e i g ns y s t e m st od e t e c tp l a g i a r i s mi nas e to f p r o g r a m s t h i sr e s e a r c hi sm a i n l ya b o u th o wt om e a s u r et h es i m i l a r i t i e sa m o n g p r o g r a m s t h ep r o g r a m m i n gl a n g u a g eh a sc o n n a t u r a lc h a r a c t e r i s t i c s ，s u c ha s h a v i n gl e s sl a n g u a g ee l e m e n t s ，h a v i n gs e v e r a ll i m i t e dk e yw o r d st oe v e r y l a n g u a g e ，a n dh a v i n gs i m p l es t r u c t u r e s m o r e o v e ri ti sm o r em a t u r ei nt h i s f i e l da b r o a d s oi ti ss i m p l e rc o m p a r i n gt ot h em e a s u r i n gs i m i l a r i t yo ft h e n a t u r a ll a n g u a g et e x t t h i sr e s e a r c hd e s i g n sa ne x p e r i m e n t a ls y s t e mw h i c hi sm a i n l yu s e dt o m e a s u r et h es i m i l a r i t i e sa m o n gp r o g r a m sw h i c ha r ew r i t t e ni nc c + + p r o g r a m m i n gl a n g u a g e f i r s t ，t h ee x p e r i m e n t a ls y s t e mp r e - p r o c e s s e st h ep r o g r a mc o d ea n d r e m o v e st h eu n a f f e c t e de l e m e n t si nm e a s u r i n gr e s u l t s ，s u c ha sc o m m e n t s ， b l a n kl i n e sa n dl i t e r a ls t r i n g se t c t h e nt h es y s t e ms c a n sa n dp a r s e se a c ho f t h ep r o g r a m s ，a n dt o k e n i z e st h ep r o g r a mc o d ei n t ot o k e ns t r i n gt h a tc a n r e p r e s e n tt h ep r o g r a ms t r u c t u r e c o n s i d e r i n gt h ee x p a n s i b i l i t yo ft h es y s t e m , s ot h ex m ld o c u m e n ti su s e dt od e s c r i b et h el a n g u a g eg r a m m a r t h i si st o s a y , x m ld o c u m e n ti su s e dt od e f i n ew h a tat o k e ni sa n dt od e f i n ew h a t c o n v e r t i n gr o l e sf r o mp r o g r a mc o d et ot o k e ns t r i n ga r e l a s t ，i tc o m p a r e st h e t o k e ns t r i n g st h r o u g hg s ta l g o r i t h mw h i c hi su s e dt oc o m p a r et w os t r i n g s ， a n dc a l c u l a t e st h es i m i l a r i t yv a l u e st h r o u l g ht h em a t c h i n gr e s u l t s t h i sv a l u e w i l ls h o wh o ws i m i l a rt w op r o g r a m sa r e t h eh i g h e rt h ev a l u e sa r e ，t h em o r e s i m i l a rt h ep r o g r a m sa r e i ti sm o r ep o s s i b l et h a tt h ep r o g r a mi sc o p i e d t h e r e i sa na d v a n t a g eo fg s ta l g o r i t h mi st h a tt h et r a n s f o r m a t i o no fc o d es e g m e n t s p o s i t i o nd o e s n ta f f e c tt h el a s tm a t c h i n gr e s u l t s t ot h ep a i ro fp r o g r a m sw i t h h i g h e rs i m i l a r i t yv a l u e s ，t h es y s t e mc a no p e nt h e f i l e so fe a c hp a i ro f p r o g r a m sa c c o r d i n gt ot h eu s e r sr e q u e s ta n dm a r kt h es i m i l a ro rt h es a m e c o d es e g m e n t sw i t hc o l o r f u lm a r k f i n a l l y , i tv e r i f i e sa n da n a l y z e st h es y s t e mu s i n gt w ot e s t e dd a t as e t s t h ef i r s td a t as e ti sap a r to fc o d ef i l e so fs t u d e n t sp r o g r a m m i n ga s s i g n m e n t s a n o t h e rd a t as e ti s c o p i e d o rm o d i f i e dt h e o r i g i n a lp r o g r a mb yh a n d e m p i r i c a lr e s u l t si n d i c a t et h a tm es y s t e m c a nf i n dm o s ts i m i l a rc o d es e g m e n t s b e l w e e nt h et w od a t as e t s k e y w o r d s ：p r o g r a mc o d e ，s i m i l a r i t y ，m e a s u r e m e n t ，g s ta l g o r i t h m 图表、公式及算法目录 图2 1 抄袭程序代码修改的难度等级图7 图2 2 软件系统p 与q 之间的相似性一8 图4 1x m l 文件的格式3 6 图4 2 语法分析算法3 8 图4 3 实验系统的主界面4 3 图4 _ 4 相似程序对之间相似的代码段4 4 图5 1 实验系统对程序集a 相似度度量值分布情况4 7 图5 2j p l a g 对程序集b 相似度度量值分布情况4 7 表5 1 实验系统及j p l a g 对程序集b 的相似度度量结果4 8 公式2 1 8 公式3 1 2 3 公式3 2 2 3 公式3 3 2 8 公式3 - 4 2 9 公式3 5 2 9 公式3 - 6 2 9 公式3 7 2 9 公式3 8 2 9 公式3 - 9 2 9 公式3 1 0 3 0 算法3 1g s t 算法的伪代码2 2 算法3 2r k r g s t 算法的最高层伪代码2 5 算法3 3r k r g s t 算法模式扫描过程( s c a n p a t t e m ) 2 6 算法3 4r k r g s t 算法作记号过程( m a r k s t r i n g s ) 2 8 内蒙古帅池人学倾i j 学位论史 1 1 研究背景 第一章绪论 各类院校里开设的程序设计类课程，旨在通过不断地编程练习提高学生的程序设 计能力，为将来从事程序设计、软件开发或相关工作打下一个坚实的基础。然而，随 着程序设计类课程作业量的增加，部分学生由于没有学好课程或者出于偷懒的目的， 会抄袭其他学生的作业。在这种情况下，教师在批改学生作业的同时，还要在大量的 程序源代码文件里检查抄袭现象，这些都极大地增加了他们的工作量，有时甚至很难 通过教师的手工操作完成。为此，对教授计算机程序设计类课程的教师来说，检查学 生作业中的抄袭现象，或判断学生程序作业与给定标准答案的接近程度，即实现程序 代码相似度的自动度量，不仅可以帮助教师检查程序代码抄袭问题，还可以辅助实现 作业批改或试卷评阅的自动化。 此外，当程序代码出现版权争议时，特别是软件系统中部分代码出现版权争议时， 通过人工检查代码文件是否存在抄袭几乎是不可能的。在这种情况下，如果能通过计 算机自动、快速地在大量代码文件中检查哪些部分是相似或相同的，就可完成人工几 乎不可能完成的任务。所以，程序代码相似度的自动度量还可以辅助鉴别程序代码的 版权归属。 该研究主要是针对计算机程序代码进行相似度度量，由于计算机语言是形式语 言，与自然语言相比要简单的多，再加上其固有的特性，如：语言成分少，针对每门 具体的语言都只有有限多个关键字、结构简单等等，所以与自然语言文本相似度的度 量相比要简单一些，而且国外程序代码相似度度量的相关技术也已经比较成熟。 目前，程序代码相似度度量的技术主要有：属性计数技术和结构度量技术，由于 属性计数技术没有考虑程序的结构，只是统计了程序中一些属性信息，所以随着程序 抄袭或复制难度的不断提高，其度量结果的准确性就会下降。结构度量技术考虑了程 序的结构特征，度量结果比较真实地反映了程序之间的相似性。而且，国外大部分成 功的程序代码抄袭检查系统都采用了结构度量技术，所以本研究将采用结构度量技 术。首先对程序代码作预处理，去掉对相似度度量结果没有影响的部分，如无用的空 程序代码相似成度量研究 格、空行、注释语句等，接着扫描经预处理后的代码文件，并对其作简单的语法分析， 将其转换为表示程序结构的标记字符串，再通过特定的匹配算法对得到的字符串作比 较，并给出它们之问匹配程度的数值表示，以此作为程序代码相似度的度量值。该值 越大说明程序代码越相似，存在抄袭的可能性也越高。对于相似度度量结果值较高的 程序对，系统会根据用户的选择自动打丌每个程序对并标记出相似或相同的代码行， 以帮助用户迸一步检查程序代码的抄袭程度。 1 2 国内外研究现状 1 2 1 国外情况 国外对程序代码相似度的度量研究主要集中在程序代码的抄袭检测上。早在2 0 世纪7 0 年代，国外就有学者开始研究程序复制检测的技术和软件。 1 9 7 6 年，h a l s t e a d “1 首先提出了用属性计数的方法检测程序代码的抄袭问题，1 9 7 7 年，o t t e n s t e i n ”1 使用h a l s t e a d 的方法设计了最早的自动程序抄袭检测系统，这个系统 用于检测f o r t r a n 语言编写的源程序之间的抄袭。 为了得出更准确的度量结果，人们在开发的度量系统中不断增加所统计的程序属 性，如：统计程序中循环的数量、过程的数量等等。这些系统随着时间的推移变得越 来越复杂了。比如，在系统中增加了比较两个程序中控制流结构的数量等，如f a i d h i 和r o b i n s o n “1 的抄袭检测系统。同样，g r i e r “1 也使用属性计数技术设计了程序抄袭 检测系统a c c u s e ，1 9 9 6 年，v e r c o 和w i s e ”3 对该系统进行了测试后指出，仅仅增加程 序中的统计属性的数量并不能改善度量结果的准确性，因为该方法没有太多的考虑程 序的结构信息。因此。v e r c o 和w i s e 提出了结合程序的结构度量来检测程序抄袭。 目l j ，大部分程序抄袭检测系统都使用了结构度量技术，或者同时使用了结构度 量与属性计数技术。如d o n a l d s o n “1 的抄袭检测系统就同时使用了结构度量和属性计 数技术，p l a g u e ”1 ，s i m ”1 ，y a p 3 。1 等抄袭检测系统无一例外的都使用了结构度量技术。 p a r k e r “”和c l o u g h “等人分别对上述的各种程序复制检测方法作了详细的介绍和评 述。除了这两种度量技术外，还有人提出了用神经网络来检测程序代码复制问题”“a 国外有很多比较成熟的程序代码抄袭检测系统，均以互联网网络服务的形式提供 给用户使用，如j p l a g 1 ，m o s s “，s h e r l o c k “，c o d e m a t c h “”等。 2 内茹古帅彳| ：l 人学坝i 学位论义 1 2 2 国内情况 1 9 8 8 年，中国人民警官大学的张文典和任冬伟“”丌发了一个p a s c a l 语言程序 抄袭检测系统。在该系统中，将p a s c a l 语言属性分为四大类：控制类、变量类、 运算符类及标准过程类。首先，它的统计模块接收p a s c a l 语言源程序，并统计源 程序中的上述四种属性，存入数掘文件。其次，其比较模块首先比较所有程序的四个 总属性值，如果两个程序的四个总属性值差的绝对值均小于相应总属性的标准偏差， 就认为这两个程序有相似可能，为其作上“可能相似”标记，并将其文件名输出。然 后，再比较有相似可能程序的各个属性值，如果两个程序相应属性之差的绝对值小于 该属性的标准偏差，则计算： 订= 矗+ d f ，其中 豇为两个程序间相似属性的统计值， d f 为属性的权值( 由用户根据问题确定其值) 。在比较完两个程序的所有属性，计算 出最后的船值后，再计算s i m i l a r = h i t m ，其中s i m i l a r 为两个程序的相似程度，m 为比较的属性的个数。当两个程序间的相似程度，即s i m i l a r 值大于某一闽值时，说 明这两个程序是相似的。 此外，国内对程序代码相似度的度量研究主要集中在程序设计类课程主观题的自 动评分研究上“”“。如：文献【2 2 】在源代码在线测评系统中用到了代码抄袭检测技术， 但只简单地使用了属性计数技术，统计了每个程序中的如下六个属性：代码行数上， 词数矽，字符数c ，词汇量n = 操作符的种类数目+ 操作数的种类数目，长度n = 所有操作符的总数+ 所有操作数的总数，容量v = n l o g ，( h ) ，由此组成一个六维向 量( 上矿，c ，月，n ，矿) 。然后计算每两个程序所得到的此向量之间的几何距离，将计算结 果作为程序之间相似度的度量值。 总之，国外对程序代码相似度的度量研究已开展了较长时间，也取得了一些成果， 度量技术也比较成熟。然而，国内在这方面的研究却开展甚少，而且主要集中在程序 设计课程主观类试题自动评分系统的研究上。 1 3 研究意义 在高等院校里，程序设计类课程与基础理论课不同，其实践性很强，培养的是学 生的实际动手能力，需要通过不断地编程练习柬提高学生的程序编制能力。此外，任 何用计算机语言编制的程序都必须输入计算机，然后通过编译、运行来测试其正确性 程序代码相似度度量f 究 及有效性，这个固有的特性决定了其必须以电子载体的形式存在，这就为抄袭者提供 了很大的方便，抄袭者只需要通过复制、粘贴，并在此基础上作修改、加工操作即可 完成自己的作业。这样，教授该类课程的教师面临一个很大的问题就是，如何快速有 效地在大量学生作业罩检查出潜在的抄袭现象。 本研究的目的，就是开发一个程序代码相似度自动度量的实验系统，该系统可以 在较短时间内，从提交给它的大量学生作业中计算出每两个程序之间的相似度度量 值，根据该值可以判断每对程序间的相似程度，该值越大说明程序代码越相似，存在 抄袭的可能性也越高。对于相似度度量结果值较高的程序对，系统会根据用户的选择 自动打开该程序对并标记出相似或相同的代码行。此外，实验系统还可以计算学生作 业与给定标准代码间的相似度度量值，由该值可以判断学生所写代码的标准化程度， 即用于自动批改程序作业或评阅试卷。 另外，当程序代码出现版权争议时，特别是当软件系统中部分代码出现版权争议 时，通过人工检测代码文件是否存在抄袭几乎是不可能的。在这种情况下，如果能通 过计算机快速i 自动地在大量代码文件中检测那些部分是相似的或相同的，就可完成 人工几乎不可能完成的任务。所以，该研究对于程序代码版权的辅助鉴别也具有很重 要的现实意义。 1 4 研究内容 对于给定的两个或多个程序代码文件，需要尽可能快速准确地计算出每两个程序 之间的相似度度量值。由于c c + + 语言是国际上广泛流行的高级计算机程序设计语 言，所以本课题将主要以c ，c + + 语言为研究对象。该研究的主要内容如下： 1 程序代码预处理 对于提交给系统的程序代码，首先需要对其做预处理，去掉那些对最终相似度度 量无影响的信息，如程序中的注释语句、连续的空格、空行以及文字部分等，这样可 以减小程序代码的长度，从而缩短计算相似度所用的时间。预处理的方法不是很复杂， 只要扫描一遍源程序，删除程序中的上述信息即可。 2 标记化预处理后的程序代码 4 内蒙古! | | l 范人学坝i ：学位论义 首先，基于c c + + 语言的语法规则，用x m l 文件定义什么是标记，以及从c c + + 语言关键字等元素到标记字符串的转换规则。然后，程序根掘从x m l 文件中读入的 规则，扫描预处理后的程序代码，并对其作简单的语法分析，将程序转换为标记字符 串序列。在应用比较算法对得到的字符串比较之前，再将标记字符串里的每个标记转 换为单一字符，这样每个程序就减小到一个较小的字符串，这样就可缩短度量相似度 所用的时间。 3 比较标记字符串，并给出每两个程序之间匹配结果的数量表示，以此作为最 终的相似度度量值 将程序代码转换为标记字符串后，字符串匹配成了计算程序间相似度的关键步 骤，该研究将采用稍作改进的r k r - g s t ( r u n n i n gk a r pr a b i ng r e e d ys t r i n gt i l i n g ) 算法匹配对应的标记字符串。r k r g s t 算法的一个优点是，对于文本串r 和模式串 p ，某些子串位置的变化不影响最终的匹配结果，这样，程序中代码段位置的变化就 不会影响最终相似度的计算结果。另外，时间复杂度与其他算法相比也有所下降。 1 5 本文的组织结构 本文共分为六章，各章内容如下： 第一章为绪论部分，首先介绍了本研究的研究背景，接着详细讲述了国内外的研 究现状，最后介绍了该研究所涉及的主要内容和研究意义。 第二章介绍了程序代码相似度的定义，并概述了用于度量程序代码相似度的相关 技术以及几个程序抄袭检测系统。 第三章首先详细介绍了该研究将要用到的字符串匹配算法g s t 及r k r g s t 算 法，并对r k r - g s t 算法作了简单的改进。然后对该研究将要用到的x m l 作了简要 的介绍。 第四章详细讲解了程序代码相似度度量实验系统的设计与实现。 第五章用实验程序集对实验系统进行了测试和分析。 第六章对本研究的工作进行了总结，并指出了实验系统的不足，提出了今后进一 步的研究内容。 5 程序代码州似度度量1 0 d r 第二章程序代码相似度度量概述 上一章中介绍了课题的研究背景、国内外研究现状以及研究意义。本章将详细介 绍程序代码相似度度量的相关知识、度量技术以及现有抄袭检测系统。 2 1 程序抄袭描述 随着计算机技术的不断发展，各类高等院校里广泛开展了程序设计类课程，结果 也导致了抄袭现象的不断蔓延。过去，有抄袭想法的人不得不去查阅大量资料，同时 不得不将自己需要的部分用笔记载下来，在这个过程中，他们也能够学到一些有用的 东西。而在现代社会，计算机与网络技术不断普及，电子载体的资料越来越多，为抄 袭者提供了很大方便。特别是计算机程序，源代码必须以电子载体的形式存在，所以 相对来说，计算机程序代码比较容易获取。所以，抄袭很容易发生。 国外对程序代码相似度的度量研究主要集中在程序代码的抄袭检测上。f a i d h i 和 r o b i n s o n 。1 用图形的形式描述了修改别人程序代码的难度级别，如图2 1 所示。 从图2 一l 可知，l 0 级的抄袭最简单，不对原程序作任何修改而直接把别人的代 码原样复制，l 1 级是修改原程序中的注释语句，l 2 级是修改原程序中的标识符，如 变量的名字等，l 3 级是在不影响程序正确运行的情况下改变程序中变量声明的位置， i a 级是用过程定义代替过程调用语句，这几个级别的抄袭也比较简单。l 5 与l 6 级 的抄袭就比较复杂了，如果能达到这个级别的修改水平，说明学生己经掌握了相关的 程序设计知识。 同样，j o n e sl e d w a r d ”也给出了抄袭转换原来程序的1 0 个难度级别：逐 字原样拷贝原程序；更改注释语句；更改空行及程序的格式；重命名标识 符；调整代码块中语句的顺序：调整代码块中变量声明的位置；改变表达 式语句中操作符和操作数的顺序；改变数据类型；增加多余的语句或变量； 用等价的控制结构替换原控制结构。 j o ya n dl u c k “”将这些抄袭转换分成了两类：一类是不依赖于程序结构的词汇级 抄袭，另一类是需要较多技巧的“结构级”抄袭。j o n e s 的l 到7 绒转换以及f a i d h i 6 内蒙占帅范人学坝l 学位沦史 和r o b i n s o n 的l 1 到l 5 级转换都属于词汇级的抄袭转换。j o ya n dl u c k 的“结构级” 抄袭对应他们更高级别的抄袭转换，即j o n e s 的8 到l o 级以及f a i d h i 和r o b i n s o n 的 l 6 级。 图2 一l 抄袭程序代码修改的难度等级图 其实，对于学生特别是初学者来说，其作业程序中大部分抄袭都很简单，都属于 词汇级的，也就是大部分抄袭都集中在f a i d h i 和r o b i n s o n 以及j o n e sl 。e d w a r d 描述 的前几个级别。所以，学生作业中的代码抄袭现象较容易检查到。 2 2 程序代码相似度的定义 判断一个程序是否是从另外一个程序复制而来，实质上也是对这两个程序的相似 性进行度量，根掘度量结果给出一个相似度的数值表示，再由这个数值判断这两个程 序之间是否存在抄袭。 t y a m a m o t o ，m m a t s u s h i t a ，tk a m i y a 和k i n o u e 1 给出了两个软件系统相似 7 程序代码相似度度量究 度的定义。对于两个软件p 和q ，p 由元素且，p ：，k ，组成，用集合表示为： a ，p ：，k ，) ，同样，q 由元素q 。，g ：，k ，吼组成，用集合表示为 q lg ：，k ，q 。 。这里 的元素且，p 2 ，k ，以和g 。，q 2 ，k ，吼可以是软件p 和q 中的文件或代码行。 假设我们能够求出只与q , o - m a x m a t c ht h e n im a t c h e s 卜 m a t c h ( m ，n ，) ) im a x m a t c h 卜， e n d e n d e l l d f o r a l lm a t c h ( m ，n ，m a x m a t c h ) m a t c h e sd o e l l d f o rj 七- 0 m a x m a t c h 一1d o lm a r k ( p + ，) m a r k ( l + ：) e n d t i l e s + - t i l e sum a t c h ( m ，月，m a x m a t c h ) u n t i lm a x m a t c h = m i n i m u m m a t c h l e n g t h r e t u r nt i l e s 算法3 一lg s t 算法的伪代码 算法结束后，相似度的值就可用公式2 - 1 计算得到。公式2 - 1 如下 s = 世型等惭唑， 如果将模式串p 和文本串t 的长度以及“t i l e s ”的大小代入公式2 - 1 ，则相似度 的值为： 2 2 ：，4，0，o，m坦hm博侈加扰丝拼筋拍 内复古帅池人学f i ! i ! i j 学位沦立 s = 洲 这引，e s l - 3 1 2 时间复杂度分析 ( 公式3 - 1 ) ， ( 公式3 2 ) 。 在算法3 一l 中，s c a n p a t t e m 阶段的循环比m a r k s t r i n g s 更费时间，因为该阶段共有 ( p i m m l ) ( 1 p l m m l ) 次比较，这里， m m l 是最小匹配长度 m i n i m “m m a t c h l e n g t ha 然而，对模式串的长度来说，仅产生之壶个“t i l e ”可在线 l pj 形时间内完成，因此，m a r k s t r i n g s 阶段能在线性时间内执行完。 1 最坏情况 为了简化计算，假设l p i - i t i = ”，即文本串和模式串的长度相同。最坏情况下， 在每次循环中，算法仅能找到一个最大匹配。郎找到比前一次循环中找到的标记串更 短的标记串。最后找到的匹配长度为1 ( 当m m 三= 1 时) ，且正好到了剩余的字符 串的最尾端。这意味着三个循环都被完全执行。在最坏情况下，k 次循环共覆盖一个 长度为刀：。丛粤尘的字符串，对于长度为斤的字符串，大约需要荔次不同的匹配。 在最后一次循环中，当最大匹配为第一个长度时，且两个串中的每个串都仅有一 个位黄匹配，则只有一次比较是必需的。前一步中为第二个长度、有三个未作记号的 标记处会有两个位置匹配，为了找到这个匹配位置，在最坏情况下必有2 2 对比较， 相应地有2 2 2 次标记的比较。再前一步第三个长度的匹配中，循环中6 个未作记号 的标记内，存在四个可能的匹配位置，需要3 。4 2 个标记作比较。 以此类推，对一个长度为k 的匹配来说，需要比较的次数为 七( 妻+ ， 2 - k 2 - k + 2 ) 2 0 既然对所有字符串的循环次籼于等于4 9 ，所以 比较次数的极限为切2 。 程序代码相似j 盘度量，c 所有万次循环比较中对j i 求和，比较总次数的上限是：芝砌2 = 1 , 1 3 + 、手丹1 2 。 i = 1 l 二 即在最坏情况下，该算法的时间复杂度为o ( n 3 ) 。 2 最好情况 即使在最好情况下，算法的时问复杂度也改善不了多少。最好情况发生在所比较 的两个字符串完全不同：虽然如此，j p 中每一个标记也要和丁中的每一个标记比较一 次。h i r l 次比较的时间复杂度为o ( n 2 ) ，这里盯= m a x ( i p l ，i 丁i ) 。 从前面的讨论可以很明显地看出，尽管g s t 算法是比较有效的字符串比较算法， 但对于较长的字符串来说，却并不是很有效。r u n n i n gk a r p - r a b i ng r e e d ys t r i n gt i l i n g ( 以下简称r k r g s t ) 算法对g s t 算法作了改进。r k r - g s t 算法并没有改变原来 算法在最坏情况下的时间复杂度，但是算法的平均时间复杂度却改进到了o ( n ) 。下 面对r k r g s t 算法作详细地介绍与分析。 3 2 r u n n i n gk a r p r a b i ng r e e d ys t r in gt iii n g 3 2 ，1 算法描述和伪代码 r u n n i n gk a r p r a b i ng r e e d ys t r i n gt i l i n g 算法是基于非常有名的字符串匹配算法 k a r p ，r a b i n “”。受基于映射( 散列) 排序技术的启发，1 9 8 7 年图灵奖获得者k a r p 教 授和著名学者r a b i n 教授合作，在m m 研究与发展杂志上介绍了一种直观、快速的 k a r p r a b i n 串匹配随机算法( 简称k r 算法) 。算法十分简单，但是却非常高效。该算 法的基本思想是把长度为坍的模式串看作是一个键( k e y ) ，而把文本串中每1 7 1 个字符 也看作是一个键。如果能够定义一个散列函数把这些键都映射为它们对应的散列值， 那么显然只有那些与模式串具有相同散列值的文本字段才有可能与模式串匹配，这是 一个必要条件。k a r p 和r a b i n 给出了在线性时间内计算散列函数的有效方法。 通过以下方法修改字符串匹配算法k r ，r k r g s t 算法扩展了原来的g s t 算法： 不对整个模式串计算一个单独的散列值，而是对每一个长度为w 从只到 p 用未作记号的模式串的子串计算一个散列值。同样，计算未作庀号从到t ，文 本串子串的散列值。前面已经提到，该计算可以在线性时间内完成。 内蒙古帅范人学顾i 学位论文 比较上一步得出的每一个模式串和文本串的散列值。如果相等，表明两个子 串可能匹配，接着通过逐个比较每一个标记来检查是否匹配。这样，利用映射表通过 散列值的比较将时间复杂度从o ( n 2 ) 减少到了一个常量时间。 这里的参数w 被称为搜索长度，且在算法的每一次循环后将逐步减少，直到等于 最小匹配长度。 算法3 - 2 给出了r k r - g s t 算法的最高层伪代码。该算法很简单，因为它是基于 g s t 算法的，所以类似于g r e e d ys t r i n gt i l i n g 算法。算法的主要不同是s c a n p a t t e r n 步 骤，r k r - g s t 是在确定的大小上找到所有的最大匹配。 1 s e a r c h l e n g t hw 一i n i t i a l s e a r c h l e n g t h 2s t o p 卜如s e 3 r e p e a t 垃是在这次循环中找到的最大的最大匹配的大小 k 卜s c a n p a t t e r n ( w ) i f 上m 缸 2 wt h e n f ，相当长的字符串，不用标记为“t i l e ”，用更大的试一下 w 4 - - - 三m e l s e 从在队列中取出的匹配中产生“t i l e ” m a r k s t r i n g s ( w ) i fw 2 m i n i m u m m a t c h l e n g t ht h e nw4 - - wd i v2 e l s ei fw m i n i m u m m a t c h l e n g t ht h e nw 扣m i n i m u m m a t c h l e n g t h e l s es t o p + - 舰p 1 3u n t i ls t o p ； 算法3 2r k r - g s t 算法的最高层伪代码 在r k r g s t 最高层算法中，首先是给搜索长度赋了一个初值，这是该算法与 g s t 算法之间的另一个不同点。算法的主要循环从s c a n p a t t e m 过程开始，这个过程 返回w 的一个新值。如果找到了一个较长的最大匹配，算法自动从一个等于新长度的 搜索长度重新开始。否则，算法接着开始执行这样一个过程，该过程为找到的最大匹 配中所有未作记号的标记作记号。这个作记号的过程是通过m a r k s t r i n g s 过程完成的。 4 5 6 7 8 9 m n 他 程序代码相似度度量州究 作记号过程结束后，如果w 的值被更新为比最小匹配长度更小的新值，算法就结束了。 否则，算法从w 的这个新值丌始继续执行。 7 8 9 l o f o r e a c hu n m a r k e dt o k e nto ftd o i fd i s t a n c et on e x tt i l eswt h e n im o v ent of i r s tu n a r k e dt o k e na f t e rn e x tt i l e e l s e i c r e a t ek rh a s h v a l u ef o rs u b s t r i n gl l i ia d dt oh a s h - t a b l e e u d e u d f o r e a c hu n m a r k e dt o k e n 己o f i fd i s t a n c e t on e x t t i l e w 尸d o t h e n m o v e mt of i r s tu n m a r k e dt o k e na f t e rn e x tt i l e e l s e c r e a t ek rh a s h - v a l u ef o rs u b s t r n g 只只l c h e c kh a s h t a b l ef o r 只己。ik rh a s h v a l u e f o r e a e hh a s h t a b l ee n t r yw i t he q u a lh a s h e dk rh a s h - v a l u ed o k 2wt h e n l 放弃扫描，从新的w = t 重新开始 lr e t u r n ( k ) e l s e r e c o r dn e wm a x i m a l m a t c h e l l d e n d e u d e n d r e t u r n ( 1 e n g t ho fl o n g e s tm a x i m a l 。m a t c h ) ； 算法3 - 3r k r g s t 算法模式扫描过程( s c a n p a t t e r n ) 算法3 - 3 是s c a n p a t t e r n 过程的伪代码，这个过程的主要部分就是散列过程。 s c a n p a t t e m 过程扫描文本文档中从到t 。的文本串中未作记号的字符串并为其 产生散列值。当这个过程执行完成后，会生成所有未作记号的标记的映射表，所有未 他n ”m 他 加 ”鸵”m舶拍”船 内蒙古师范人学颂l 。学位论义 作记号的子串的欧度都等于w 。 随后，为每一个从只到巳。的模式串生成散列值，并将其与文本串的散列值 作比较，即在前一步中产生的映射表中查找每一个模式串的散列值，如果找到了一个 相等的，算法就试图扩展这个匹配。相等的子串( 有相同散列值的标记串) 的检测过 程从s c a n p a t t e m 延期到了m a r k s t r i n g s 过程。文献 4 4 y 9 的推论结果显示，k r 的散列 过程很少发生冲突，且m a r k s t r i n g s 过程中逐个元素的匹配也很有效。这个过程返回 找到的最大的最大匹配的长度。 用于记录最大匹配的数据结构是双向队列。每个队列记录相同长度的最大匹配， 队列列表的次序是按匹配长度递减排列。每个队列里用一个指针指向最近添加的最大 匹配，因为很有可能下一个最大匹配的匹配长度与最后一个记录的相同或相近，因此 可以很方便地被记录到该队列的最后或接近该队列的队列里。 算法3 _ 4 描述了m a r k s t r i n g s 过程的伪代码。除了使用了一个比线性链表更合适 的队列外，该算法使用了和原来g s t 算法相同的结构。此外，像前面讨论的一样， 该过程中也作了相等字符串的测试。 为了检查散列值相等的那些子串是否真正的相等，