Java錯(cuò)誤堆棧相似度計(jì)算

王其春　趙龍

摘要：Java錯(cuò)誤堆棧自動(dòng)分類的過程中需要比較錯(cuò)誤堆棧之間的相似度，該文根據(jù)java錯(cuò)誤堆棧的特點(diǎn)，提出了一種適用于java錯(cuò)誤堆棧相似度比較的方法，在這個(gè)過程中對(duì)漢明距離進(jìn)行了改進(jìn)，最后我們對(duì)此算法進(jìn)行了詳細(xì)的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明這種方法具有很明顯的效果。

關(guān)鍵詞：相似度； java堆棧分類；聚類

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）21-5031-03

1 背景簡(jiǎn)介

在服務(wù)器端運(yùn)行的java程序會(huì)產(chǎn)生java錯(cuò)誤報(bào)告，在這些錯(cuò)誤報(bào)告中包含了大量的java錯(cuò)誤堆棧。程序的維護(hù)人員會(huì)根據(jù)這些java錯(cuò)誤堆棧對(duì)程序進(jìn)行修改。為了提高解決問題的效率，人們希望能夠自動(dòng)地對(duì)錯(cuò)誤堆棧進(jìn)行分類，根據(jù)錯(cuò)誤堆棧的類別，采取相應(yīng)的方法解決問題。在這個(gè)過程中，會(huì)比較錯(cuò)誤堆棧之間的相似度。

Java的錯(cuò)誤堆棧是由一系列的字符串組成，因此在比較Java錯(cuò)誤堆棧之間相似度的時(shí)候，往往會(huì)用到字符串相似度比較算法。現(xiàn)在字符串相似度方法有很多，比如最長(zhǎng)公共子串算法（Longest Common Subsequence 縮寫為L(zhǎng)CS）[1]，它是根據(jù)兩個(gè)字符串之間最長(zhǎng)的公共子串的長(zhǎng)度來(lái)計(jì)算字符串之間的相似度，此算法的算法復(fù)雜度為，其中m，n，是兩個(gè)字符串之間的長(zhǎng)度。Leveinshtein Distance 也被稱作編輯距離[2]，它是根據(jù)由一個(gè)字符串變成另外一個(gè)字符串所需要的操作數(shù)來(lái)衡量字符串之間的相似度，這些操作包括插入、刪除、更改字符。該算法的算法復(fù)雜度也是，其中m，n，是兩個(gè)字符串之間的長(zhǎng)度。漢明距離（Hamming Distance ）[3]也是一種計(jì)算字符串相似度的算法。該算法是根據(jù)兩個(gè)相同長(zhǎng)度字符串之間對(duì)應(yīng)位置的不同字符的個(gè)數(shù)來(lái)計(jì)算字符串之間的相似度。此算法的算法復(fù)雜度是，其中m是字符串的長(zhǎng)度，但是該算法只適用于兩個(gè)相同長(zhǎng)度字符串之間相似度的比較。這些字符串相似度比較算法廣泛地應(yīng)用于和字符串相關(guān)的領(lǐng)域中，但是這些算法并不是針對(duì)Java錯(cuò)誤堆棧而設(shè)計(jì)的，java錯(cuò)誤堆棧有其自身的特點(diǎn)，以上的字符串相似度比較算法不能很好地衡量錯(cuò)誤堆棧之間的相似度。

圖1是Java錯(cuò)誤堆棧的一個(gè)例子，一個(gè)java錯(cuò)誤堆棧里面包含了很多的字符串，在這里我們稱每一行字符串為error trace。在錯(cuò)誤堆棧分類的過程中，其實(shí)比較的是error trace之間的相似度。在比較error trace 相似度的過程中，如果使用最長(zhǎng)公共子串算法或者Levenshtein Distance， 那么這只能比較它們最大的公共部分，并不有很好地說(shuō)服性，另外在java程序中，如果使用的包的名字或者類的名字更改的話，這會(huì)對(duì)算法的效果產(chǎn)生很大的影響，并且這些算法的算法復(fù)雜度過高，隨著error trace的長(zhǎng)度的增加，算法的效率會(huì)下降很多，所以這些算法并不能很好地適用java error trace的相似度比較。因此我們提出了一種新的java錯(cuò)誤堆棧相似度比較的算法。

2 方法說(shuō)明

在我們的算法中，我們首先對(duì)Hamming Distance進(jìn)行了改良，使其適用于不同長(zhǎng)度字符串之間的相計(jì)算。我們稱新的算法是Length Adapted Hamming Distance （簡(jiǎn)稱LA Hamming Distance 或者LAHD）。

2.1 LAHD

LAHD算法的核心思想是把兩個(gè)長(zhǎng)度不同的字符串中的長(zhǎng)度較長(zhǎng)的字符串進(jìn)行修改，把多余的部分刪除掉，然后利用Hamming Distance計(jì)算剩余的字符串之間的相似度，然后再加上刪除部分的長(zhǎng)度，這樣就計(jì)算出了兩個(gè)長(zhǎng)度不同的字符串之間的相似度。

在圖2中詳細(xì)地描述了LAHD算法的過程。我們用A，B代表兩個(gè)字符串，其中A的長(zhǎng)度要大于B，我們用C代表字符串A除去比字符串B長(zhǎng)的那一部分后的子串。那么在圖2的例子中，A代表的是org.hibernate.persister.entity， B代表的是

2.2 三段法

Java錯(cuò)誤堆棧中包含了很多的error trace，文章上文中提到的算法在計(jì)算error trace相似度的時(shí)候把error trace當(dāng)成一個(gè)整體而我們?cè)O(shè)計(jì)的算法并不是這樣的，一個(gè)error trace中包含了包的名字、類的名字以及函數(shù)的名字，根據(jù)error trace的特點(diǎn)，我們?cè)O(shè)計(jì)出了我們的算法，我們稱之為三段法。

在圖3中詳細(xì)說(shuō)明了我們算法的基本原理。首先我們根據(jù)error trace的特點(diǎn)，把error trace進(jìn)行劃分，分為三部分：包名、類名、函數(shù)名。然后分別計(jì)算這三部分的相似度，每一部分用不同的算法來(lái)計(jì)算，其中包名之間的相似度是使用Length Adapted Hamming Distance （簡(jiǎn)稱為L(zhǎng)A Hamming Distance）來(lái)計(jì)算的，因?yàn)樵谡麄€(gè)java error trace 中包的名字最長(zhǎng)，如果使用其它的兩種方法會(huì)使算法的效率下降很多。類名和函數(shù)名都是使用最長(zhǎng)公共子串算法來(lái)計(jì)算的（原因我們會(huì)在實(shí)驗(yàn)中說(shuō)明）。最后對(duì)這三部分的相似度進(jìn)行加權(quán)求和（關(guān)于各個(gè)部分的權(quán)值是根據(jù)實(shí)驗(yàn)得來(lái)的，我們會(huì)在試驗(yàn)中說(shuō)明）。這樣就可以計(jì)算出相似度。

3 實(shí)驗(yàn)結(jié)果

首先，我們?cè)阱e(cuò)誤堆棧中提取了100條數(shù)據(jù)，然后請(qǐng)熟悉堆棧分類的人對(duì)這些數(shù)據(jù)進(jìn)分類，然后我們利用K-means [4]算法對(duì)這些算法進(jìn)行聚類，在聚類的過程中我們要計(jì)算不同類別之間的距離，我們?cè)谶@個(gè)過程中使用了三種方法來(lái)衡量這些類別之間的距離，這三中方法是Single-Linkage [5]，Complete-Linkage [6]， Average-Linkage [6]。最后機(jī)器分類的結(jié)果與人工分類的結(jié)果進(jìn)行比較，得到機(jī)器分類的準(zhǔn)確率

我們通過實(shí)驗(yàn)，得到了在包名，類名以及函數(shù)名的權(quán)值分別取0.35，0.40，0.25 的情況下，準(zhǔn)確率的值最高。

表一中列出了在不同聚類算法的情況下，我們的算法和其它算法的準(zhǔn)確率的信息。通過上表可以看出，我們算法的準(zhǔn)確率要明顯高于Hamming以及l(fā)evenshtein距離。而且我們的算法和LCS算法的準(zhǔn)確率的差距并不大。這也是我們使用LCS算法而不使用Levenshtein Distance 來(lái)計(jì)算類名以及函數(shù)名相似度的原因。

通過實(shí)驗(yàn)，我們得出Levenshtein Distance， Hamming Distance， LCS以及我們算法所花費(fèi)的時(shí)間分別為38.5464ms，0.1661ms，21.5883ms，7.5089ms?？梢钥闯?，我們的算法要比Levenshtein Distance以及LCS要高很多。但是要比Hamming Distance要低。

綜合考慮準(zhǔn)確率以及效率的因素，我們的算法要比其它算法更適用于java錯(cuò)誤堆棧相似度的計(jì)算。

參考文獻(xiàn)：

[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.