一種面向程序理解的程序語義聚類技術

陳穎

摘要：針對源代碼中一些非結構化的自然語言描述信息進行語義聚類，輔助開發(fā)人員開展程序理解。主要利用自然語言處理技術對程序中的標識符和注釋進行預處理，將程序轉換成詞頻矩陣;然后利用潛在語義索引技術對該詞頻矩陣進行層次聚類，并對每個聚類的標記進行推薦，輔助開發(fā)人員理解程序。在開源項目JEdit上進行驗證，結果顯示對該5萬行規(guī)模的項目代碼進行聚類時耗不足1分鐘。因此，該技術能夠快速對程序進行語義聚類，輔助開發(fā)人員快速理解程序。

關鍵詞：程序理解;語義聚類;潛在語義索引;語義標注

DOI：10.11907/rjdk.191119開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP303文獻標識碼：A 文章編號：1672-7800（2019）010-0062-03

0引言

軟件維護是一個集軟件分析、理解、修改、測試、重新確認于一體的過程。軟件分析和軟件理解是維護過程的第一步，能否準確、迅速、全面地理解程序是決定維護任務成敗的關鍵。程序理解指運用一定的實施方法了解一個程序的功能及目的。程序理解是軟件工程領域的重要組成部分，據(jù)估計，軟件維護中高達60%的時間被用于程序理解。現(xiàn)有程序理解方法大多關注程序結構或外部文檔，忽略了對源代碼中一些非形式化語言的研究，這些諸如變量名、程序注釋等自然語言往往隱藏著軟件系統(tǒng)知識信息和領域信息，通過挖掘這些信息，開發(fā)人員能夠?qū)σ粋€陌生的軟件系統(tǒng)功能特征形成初步理解。

程序聚類可將程序源代碼文件聚合成為模塊，從而更好地理解程序設計，并從源代碼文件中抽取有意義的概念。程序聚類在軟件維護過程中有眾多應用，常用于軟件重新模塊化、軟件分解、軟件演化分析與對象識別等方面。文獻主要關注并分析了聚類活動中的3個方面，即聚類實體抽象描述選擇、描述實體間耦合度量值及聚類算法，以及軟件重新模塊化識別;文獻[10]提出一種轉換框架，能夠?qū)⑶短椎能浖纸廪D換成為平面軟件分解，并可在過程中避免信息丟失;文獻[11]在5個大型開源系統(tǒng)上分別使用6種不同的聚類算法進行聚類實驗，結果表明不同聚類算法具有不同特性，目前自動化聚類算法還需大幅提高效率以提供持續(xù)支持;文獻[14]利用聚類技術針對面向過程的程序代碼進行對象識別，輔助程序?qū)ο蠡D化。

上述研究主要利用程序聚類實現(xiàn)軟件維護等應用，但是并沒有從程序語義聚類的角度出發(fā)進行程序理解。語義聚類可直接用于程序理解。文獻[15]提出將嵌套的軟件分解轉換為平面的軟件分解，并且避免了顯著信息丟失，使程序更容易理解;文獻[16]提出使用潛在語義分析軟件聚類的初步結果，挖掘軟件代碼同文檔中潛在語義信息的關聯(lián)，基于該語義關聯(lián)輔助程序理解;文獻[17]提出一種基于功能需求層次的程序聚類方法，通過需求層次識別相關程序;文獻[18]提出利用模糊形式概念對軟件進行分析和聚類，實現(xiàn)通過軟件分解達到程序理解的目的;文獻[19]提出針對軟件代碼進行聚類，并定義概要模板進行聚類的概要生成。

以上關于程序聚類的工作側重于利用程序聚類對軟件進行分解或借助外部文檔信息輔助程序理解。但實際中對于分解的軟件如果沒有明確的語義標注，則程序理解難度較大;另一方面，在實際軟件開發(fā)過程中，外部文檔信息經(jīng)常不準確、不全面，難以產(chǎn)生有意義的效果。

本文主要利用潛在語義分析技術對代碼進行聚類，同時可實現(xiàn)聚類自動標記，輔助開發(fā)人員理解程序。本文對程序聚類的研究和解釋不建立在外部文檔的基礎上，而是根據(jù)非形式化的靜態(tài)方法進行分析，即使用源代碼內(nèi)部注釋和變量名等文本信息進行分析。具體內(nèi)容包括：通過潛在語義索引（Latent Semantic Indexing，LSI）技術進行程序聚類和解釋，運用潛在語義索引中的奇異值分解（SingularValue Decomposition）對term-document降維，并在三維語義空間和四維語義空間進行聚類分析，通過層次聚類方法得到的樹狀圖輸出聚類結果，并對每個聚類的解釋從單詞和短語兩個方面進行推薦，輔助開發(fā)人員理解程序。

1基礎知識介紹

潛在語義索引（Latent Semantic Indexing）是基于向量空間模型的一種技術，表示詞匯在軟件系統(tǒng)中的含義。LSI將文件模型化，并將其排列成一個term-document矩陣。term-document矩陣A是一個稀疏矩陣。該矩陣大小為mxn，其中m是經(jīng)過處理的單詞數(shù)量，n是文件數(shù)量，矩陣的每個元素a_i，j是在文件d_j中詞匯t_i的頻率。該矩陣的幾何解釋是一組文檔向量由術語度量的向量空間表示。文檔之間的相似性通常被定義為相應向量之間的余弦或內(nèi)積。如果其對應的向量指向同一個方向，則兩個文件被認為是類似的。

LSI以一個源term-document矩陣開始，通過加權函數(shù)加權平衡。奇異值分解（Singular Value Decomposition，SVD）用來把向量空間模型轉換成更小的維數(shù)。該算法盡可能多地保留文檔向量之間的相關距離，將term-document矩陣降維成一個維度大幅縮小的矩陣。

當矩陣A有k個最大奇異值時，利用奇異值分解把矩陣A分解成其奇異值奇異向量，并且用相似矩陣A代替秩為k的矩陣A。此外，不僅低秩的term-document矩陣A′可以計算，而且term-term矩陣和document-document矩陣也能被計算。因此，LSI允許計算term-document、term-term和document-document的相似性。

在使用LSI技術過程中，有一些參數(shù)需要設計，如在一般信息檢索技術中聚類規(guī)模k通常取值200～500，但本文在分析軟件數(shù)據(jù)時，參照已有工作k的取值為20～50。

2程序聚類與解釋

本文方法主要基于Java語言代碼進行分析。首先，分析源代碼信息，包括變量名、方法名以及注釋，再對這些信息進行預處理，從這些信息中提取關鍵詞，以構建需要的term-document矩陣，基于term-document矩陣使用奇異值分解，將term-document降維以提取特征矩陣;其次，通過層次聚類的方法進行聚類，得到關于程序代碼的聚類樹狀圖，再將得到的聚類結果代人聚類標記算法進行標記推薦，實現(xiàn)聚類語義解釋;最后，對整個軟件系統(tǒng)進行聚類標記，實現(xiàn)從語義角度理解整個軟件系統(tǒng)。

2.1程序語義聚類

在信息檢索中，為提高檢索準確率，需要對信息進行預處理，如刪除停用詞、詞干處理等。由于本文主要分析的代碼是基于Java編寫的，因此諸如Java、int等類別的詞均被加入停用詞表;其次，進行詞干處理減少term-docu-ment矩陣維數(shù)，能將一個詞匯的不同形式轉化為相同的詞根，避免同義詞的不同形式帶來語義信息抽取誤差，如achievement→achieve。

本文使用層次化聚類方法，主要采用迭代方法，聚類過程自下而上、由小變大。首先在所有類中選取兩個距離最小的類，則這兩個類先構成一個聚類，然后在其它類中尋找與其距離最小的類以及任意兩個距離最小的類，若前者距離大于后者，則后者成為一個新的聚類，否則增大前者，依次往復，直到處理完所有類即形成第一層次的聚類。第2層次的聚類是運用第1層聚類將各個小的聚類構建成大的聚類;第3層及后續(xù)依次迭代形成。

2.2程序聚類解釋

基于上述聚類結果，對聚類進行標記，協(xié)助開發(fā)人員基于聚類標記的結果理解某個聚類的程序代碼，標記過程如下：

Stepl：找出聚類中每個java文件最高頻的詞;

Step2：對每個聚類最高頻詞進行查重處理：若一個高頻詞在該聚類的n（n>=2）個java文件中出現(xiàn)，則該詞頻率將對每個java文件中該詞出現(xiàn)頻率之和加上（n-1）;其詞頻率賦給第一個出現(xiàn)該詞的java文件，其它都置為0;若n=1，其詞頻等于該詞本身;

Step3：若最終頻率不為零的java文件數(shù)小于5，則該聚類標記數(shù)是不為。的java文件數(shù)，否則為5;

Step4：將利用Step2和Step3得到的頻率作為最高標記輸出;

Step5：重復Stepl、Step2和Step3，直到所有聚類標記過程結束。

3實驗分析

3.1實驗設置

本實驗運行環(huán)境為HP ENVY 15j105tx，擁有CORE i74702QM處理器，8GB RAM。本實驗實驗對象為JEdit，是一個用Java語言開發(fā)的文本編輯器，在GPL下發(fā)布。JEdit 2.4.1一共包含282個Java文件，約5萬行代碼。

3.2實驗結果與分析

首先，分析針對JEdit項目進行程序聚類前的預處理階段時間性能分析，結果如表1所示。結果發(fā)現(xiàn)本文方法每一步所需時間均在30s以內(nèi)，總時間控制在1min以內(nèi)，證明其處理該規(guī)模軟件的時間有效性。

基于實驗結果，距離等于6時聚類效果較好，依此進行聚類結果提取，并將聚類結果輸入開發(fā)的工具中進行聚類解釋和詞語推薦。各個聚類標記和解釋如表2所示，第2列表示各聚類大小，第3列表示該聚類的推薦標記，最后一列是根據(jù)標記得出的解釋。通過聚類解釋，很容易發(fā)現(xiàn)該軟件與文本編輯相關，再加上對短語的分析，更能驗證對程序的解釋，而該軟件確實為一個文本編輯器。

4結語

本文針對程序代碼從程序語義聚類的角度理解程序，提出利用潛在語義分析進行層次聚類，并利用詞語推薦對聚類結果進行標記，實現(xiàn)對程序的有效理解。該技術通過在開源項目JEdit上進行實驗，證明其有效性。

該技術還存在一些缺陷，如語義信息冗余，在今后的工作中，可將生成的標記建為聚類創(chuàng)建cluster-label矩陣，通過計算每個聚類相似度去除冗余語義信息;另外，也可以不局限于潛在語義分析，借助其它信息檢索技術（如主題模型）輔助語義聚類與解釋。