算法在程序代码相似度度量中的应用

《算法在程序代码相似度度量中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据2008年3月第39卷第2期内蒙古大学学报(自然科学版)JournalofInnerMongoliaUniversityMar．2008V01．39No．2文章编号：1000一1638(2008)02—0225—05最长公共子序列算法在程序代码相似度度量中的应用‘于海英，赵俊岚(内蒙古财经学院计算机信息管理系，呼和浩特010070)摘要：阐述了最长公共子序列算法在程序代码结构相似度度量中的应用，列举了两种计算最优值和一种获取最长公共标识符子序列的算法．根据最优值得到结构相似度值，进而可以查

2、找出结构相似程序对．最后探讨了程序代码相似度的实际应用．关键词：最长公共子序列算法；最优值；结构相似度；最长公共标识符子序列中图分类号：TP391．72文献标识码：A一种程序语言，对于同一逻辑的表达形式往往是多样的．还有可能一些人为了节省时间和力气，将别人的程序采用编辑手段，作一些文本的改变(简单的改变如改变代码注释或改变变量名，稍复杂一些如等价控制结构的替换(如用“while”循环替换“for”循环))．可以肯定的说，这些更改都是表面的，是少量的，而程序中内含的属性和结构是没有改变的n3．本文主

3、要探讨通过对程序对利用一定的手段进行比较以查找出这样的相似程序的方法．1最长公共子序列1．1最长公共子序列定义最长公共子序列(LongestCommonSubsequence，LCS)。3是将两个给定字符串分别删去零个或多个字符，但不改变剩余字符的顺序后得到的长度最长的相同字符序列．给定字符串X、Y、Z，Z称为X和Y的最长公共子序列是指Z是X和Y的公共子序列，且对于X和Y的任意公共子序列W，都有lWI<=IZI．求最长公共子序列问题为动态规划问题。’．动态规划算法的基本思想“’是：将待求解的问题分

4、解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解．动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质．而最长公共子序列问题正好具有这样的性质，证明见文献[3]．1．2最优值计算及最长公共子序列获取最长公共子序列的长度为最优值．要找出字符串X_--和y_--的最长公共子

5、序列，可按以下方式递推地进行：当x。=y。时，x卜．一，和Y，⋯。一。的最长公共子序列加上X。(--y。)即为X和Y的一个最长公共子序列．当x。≠y。时，必须解两个子问题，即找出X卜．一，和Y的一个最长公共子序列及X和Y卜一。的一个最长公共子序列．这两个公共子序列中较长者即为X和Y的一个最长公共子序列，而这两个子问题都包含一个公共子问题，即计算X卜。一。和Y卜一。的最长公共子序列．·收稿日期：2007·09—18作者简介：于海英(1976～)，女，内蒙古赤峰人，讲师，硕士．主要研究方向：计算机教育

6、应用．万方数据226内蒙古大学学报(自然科学版)2008焦用初值为0的c(m+1，n+1)数组记录整个计算过程中的最优值矩阵，用c(i，j)记录序列Xi和Yj的最长公共子序列的长度，其中Xi一，Yj=．当i=O或j--o时，空序列是X；和Yj的最长公共子序列，故c(i，j)=O．其他情况下，可自底向上建立递推关系如下：f0当i=0或J=0时f(i，歹)=．{f(i+1，_f+1)+l当i，．『>0且z，一YJ时公式1【max(c(i，J+1)，c

7、(i+1，歹))当i，歹>0且而≠"时最后，c(O，o)即为两个字符串的最优值．由递推关系结合动态规划算法很容易写出自底向上计算最优值c(i，j)的算法LCS—LENGTH及自顶向下获取最长公共子序列算法LCS(见下文)．2程序代码结构相似度度量程序代码相似度是利用一定的检测手段度量程序代码间的相似程度．程序代码相似度的度量手段很多，如属性计数(Accuse03、EdwardL．Jones的方法∞等)和结构度量(Plague订’、YAP系列工具∞’9’、SIMn∞等)的方法．但单纯的属性计数法抛弃

8、了太多的程序结构信息，导致错误率太高，因此将属性计数和结构度量相结合来改善错误率．不同的人思考角度不同，度量策略和算法也不同，本文以现有条件为基础采用了属性计数和结构度量相结合的方法，涉及属性相似度和结构相似度的获取，但仅就利用最长公共子序列算法对结构相似度的度量问题作详尽阐述．2．1最长公共标识符子序列首先每一个程序被读入内存并进行分解，将程序代码按程序语句自顶向下和代码行从左向右的顺序分解为操作符和操作数标识符n’，忽略注释、空行和空格．操作符标识符包括源程序设计语言的关键字、