龙源期刊网 http://www.qikan.com.cn
Java错误堆栈相似度计算
作者：王其春 赵龙
来源：《电脑知识与技术》2014年第21期
摘要：Java错误堆栈自动分类的过程中需要比较错误堆栈之间的相似度，该文根据java错误堆栈的特点，提出了一种适用于java错误堆栈相似度比较的方法，在这个过程中对汉明距离进行了改进，最后我们对此算法进行了详细的实验，实验结果表明这种方法具有很明显的效果。
关键词：相似度； java堆栈分类；聚类
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）21-5031-03 1 背景简介
在服务器端运行的java程序会产生java错误报告，在这些错误报告中包含了大量的java错误堆栈。程序的维护人员会根据这些java错误堆栈对程序进行修改。为了提高解决问题的效率，人们希望能够自动地对错误堆栈进行分类，根据错误堆栈的类别，采取相应的方法解决问题。在这个过程中，会比较错误堆栈之间的相似度。
Java的错误堆栈是由一系列的字符串组成，因此在比较Java错误堆栈之间相似度的时候，往往会用到字符串相似度比较算法。现在字符串相似度方法有很多，比如最长公共子串算法（Longest Common Subsequence 缩写为LCS）[1]，它是根据两个字符串之间最长的公共子串的长度来计算字符串之间的相似度，此算法的算法复杂度为，其中m，n，是两个字符串之间的长度。Leveinshtein Distance 也被称作编辑距离[2]，它是根据由一个字符串变成另外一个字符串所需要的操作数来衡量字符串之间的相似度，这些操作包括插入、删除、更改字符。该算法的算法复杂度也是，其中m，n，是两个字符串之间的长度。汉明距离（Hamming Distance ）[3]也是一种计算字符串相似度的算法。该算法是根据两个相同长度字符串之间对应位置的不同字符的个数来计算字符串之间的相似度。此算法的算法复杂度是，其中m是字符串的长度，但是该算法只适用于两个相同长度字符串之间相似度的比较。这些字符串相似度比较算法广泛地应用于和字符串相关的领域中，但是这些算法并不是针对Java错误堆栈而设计的，java错误堆栈有其自身的特点，以上的字符串相似度比较算法不能很好地衡量错误堆栈之间的相似度。
图1是Java错误堆栈的一个例子，一个java错误堆栈里面包含了很多的字符串，在这里我们称每一行字符串为error trace。在错误堆栈分类的过程中，其实比较的是error trace之间的相似度。在比较error trace 相似度的过程中，如果使用最长公共子串算法或者Levenshtein Distance， 那么这只能比较它们最大的公共部分，并不有很好地说服性，另外在java程序中，如果使用的包的名字或者类的名字更改的话，这会对算法的效果产生很大的影响，并且这些算
龙源期刊网 http://www.qikan.com.cn
法的算法复杂度过高，随着error trace的长度的增加，算法的效率会下降很多，所以这些算法并不能很好地适用java error trace的相似度比较。因此我们提出了一种新的java错误堆栈相似度比较的算法。 2 方法说明
在我们的算法中，我们首先对Hamming Distance进行了改良，使其适用于不同长度字符串之间的相计算。我们称新的算法是Length Adapted Hamming Distance （简称LA Hamming Distance 或者LAHD）。 2.1 LAHD
LAHD算法的核心思想是把两个长度不同的字符串中的长度较长的字符串进行修改，把多余的部分删除掉，然后利用Hamming Distance计算剩余的字符串之间的相似度，然后再加上删除部分的长度，这样就计算出了两个长度不同的字符串之间的相似度。
在图2中详细地描述了LAHD算法的过程。我们用A，B代表两个字符串，其中A的长度要大于B，我们用C代表字符串A除去比字符串B长的那一部分后的子串。那么在图2的例子中，A代表的是org.hibernate.persister.entity， B代表的是 2.2 三段法
Java错误堆栈中包含了很多的error trace，文章上文中提到的算法在计算error trace相似度的时候把error trace当成一个整体而我们设计的算法并不是这样的，一个error trace中包含了包的名字、类的名字以及函数的名字，根据error trace的特点，我们设计出了我们的算法，我们称之为三段法。
在图3中详细说明了我们算法的基本原理。首先我们根据error trace的特点，把error trace进行划分，分为三部分：包名、类名、函数名。然后分别计算这三部分的相似度，每一部分用不同的算法来计算，其中包名之间的相似度是使用Length Adapted Hamming Distance （简称为LA Hamming Distance）来计算的，因为在整个java error trace 中包的名字最长，如果使用其它的两种方法会使算法的效率下降很多。类名和函数名都是使用最长公共子串算法来计算的（原因我们会在实验中说明）。最后对这三部分的相似度进行加权求和（关于各个部分的权值是根据实验得来的，我们会在试验中说明）。这样就可以计算出相似度。 3 实验结果
首先，我们在错误堆栈中提取了100条数据，然后请熟悉堆栈分类的人对这些数据进分类，然后我们利用K-means [4]算法对这些算法进行聚类，在聚类的过程中我们要计算不同类别之间的距离，我们在这个过程中使用了三种方法来衡量这些类别之间的距离，这三中方法是
龙源期刊网 http://www.qikan.com.cn
Single-Linkage [5]，Complete-Linkage [6]， Average-Linkage [6]。最后机器分类的结果与人工分类的结果进行比较，得到机器分类的准确率
我们通过实验，得到了在包名，类名以及函数名的权值分别取0.35，0.40，0.25 的情况下，准确率的值最高。
表一中列出了在不同聚类算法的情况下，我们的算法和其它算法的准确率的信息。通过上表可以看出，我们算法的准确率要明显高于Hamming以及levenshtein距离。而且我们的算法和LCS算法的准确率的差距并不大。这也是我们使用LCS算法而不使用Levenshtein Distance 来计算类名以及函数名相似度的原因。
通过实验，我们得出Levenshtein Distance， Hamming Distance， LCS以及我们算法所花费的时间分别为38.5464ms，0.1661ms，21.5883ms，7.5089ms。可以看出，我们的算法要比Levenshtein Distance以及LCS要高很多。但是要比Hamming Distance要低。
综合考虑准确率以及效率的因素，我们的算法要比其它算法更适用于java错误堆栈相似度的计算。 参考文献：
[1] David Maier.The Complexity of Some Problems on Subsequences and Super sequences[J].J. ACM （ACM Press），1978， 25（2）： 322-336.
[2] Navarro， Gonzalo.A guided tour to approximate string matching[J].ACM Computing Surveys ，2001，33 （1）： 31-88.
[3] Hamming， Richard W.Error detecting and error correcting codes[J].Bell System Technical Journal ，1950，29 （2）： 147-160.
[4] Forgy E W.Cluster analysis of multivariate data： efficiency versus interpretability of classifications[J].Biometrics，1965，21： 768-769.
[5] Sibson R.SLINK： an optimally efficient algorithm for the single-link cluster method[J].The Computer Journal （British Computer Society），1973， 16 （1）： 30-34.
[6] Legendre， P， Legendre L. Numerical Ecology[M]. Second English Edition，1998： 853.