王其春　趙龍

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

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

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

1 背景簡介

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

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

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

2 方法說明

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

2.1 LAHD

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

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

2.2 三段法

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

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

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

首先，我們在錯誤堆棧中提取了100條數(shù)據(jù)，然后請熟悉堆棧分類的人對這些數(shù)據(jù)進(jìn)分類，然后我們利用K-means [4]算法對這些算法進(jìn)行聚類，在聚類的過程中我們要計(jì)算不同類別之間的距離，我們在這個過程中使用了三種方法來衡量這些類別之間的距離，這三中方法是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 來計(jì)算類名以及函數(shù)名相似度的原因。

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

綜合考慮準(zhǔn)確率以及效率的因素，我們的算法要比其它算法更適用于java錯誤堆棧相似度的計(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.