基于TextRank的軟件變更任務搜索術語識別①

王 杉

(云南大學滇池學院 理工學院,昆明 650228)

軟件工程研究表明,在軟件開發過程中,用于軟件維護和演進的投入占總投入的大約70%?80%[1].在軟件維護期,開發者通常會處理很多軟件變更的請求,這需要確定變更任務在軟件項目中的確切位置(更改的類或方法).變更請求通常是由用戶提出的,因此一般都用自然語言編寫,并且軟件用戶雖然熟悉軟件產品的應用領域,但他們卻很難具備在源代碼中實現功能的能力.另一方面,參與維護的人員也不了解項目的底層架構,他們在識別需要更改的源碼位置也有困難.因此需要進行一種從軟件變更處到源碼位置(類、方法等)的映射,該映射任務通過一個或多個搜索項,從項目內進行搜索,最終得到映射位置,以快速而準確地完成軟件變更任務.

在以往的研究中,有一些嘗試通過搜索查詢以支持開發者進行功能定位任務的方法,例如輕量級啟發式方法[2]、查詢重構或擴展策略[3]、查詢質量分析法[4]、數據字典及挖掘方法[5]等.這些方法都要求開發者能提供可改進的初始搜索查詢,而對于開發者來說,這也是一項繁重的任務.其中,Kevic 和Fritz 提出了一種用于自動識別軟件變更任務的初始搜索項的啟發式模型[2],模型考慮了與搜索頻率、位置、詞性和任務描述術語符號相關的啟發法.該模型在一定程度上解決了上述問題,但也存在兩個不足:首先,模型使用有限數量的變更任務進行訓練,缺乏其他項目的變更任務進行交叉驗證,成熟度和可靠性有限;其次,模型把tfidf 作為主要度量參數,而idf 計算受測試數據集大小的影響,對于不同大小的測試數據集,會造成相同模型呈現不同的表現,并且模型可能需要頻繁的重新訓練以保持其可用性.

在本文中,提出了一種基于TextRank 進行自動識別并得到軟件變更任務搜索術語的方法.TextRank 方法是PageRank 方法的改進[6],對于自然語言文本,其中的文本可被視為詞匯的詞匯或語義網絡.TextRank 技術被廣泛應用于各類信息檢索中,例如關鍵字提取、摘要提取、詞義消歧、詞法分析和其他基于圖的屬于加權任務.因此該算法適合在特征定位任務的上下文中進行搜索項提取,這是因為軟件變更請求通常由開發團隊以外的人員進行,他們通過相關問題域的概念和自然語言文本來表達需求,并可以使用基于圖的任務描述來揭示不同術語之間的重要語義關系.其次,TextRank 算法利用圖中術語的連通性,用于確定該術語的權重(即重要性),然后遞歸執行該過程,從而確定出搜索術語.

例如,在表1中顯示的軟件變更任務可以圖的方式表示為圖1中的文本圖.本文提出的方法分析圖中術語的連通性,計算每個術語的權重(即重要性),然后提取最高權重和最適合的五個術語:Mac,selection,installs,improvement 和JREs,作為搜索任務的初始搜索項進行查詢.

圖1 表1中的變更請求文本圖

并且選取了兩個主題系統Apache Log4j(日志分析)和Eclipse JDT Debug 中的336 個變更任務進行實驗,實驗表明了提出的方法可以返回49.65%的變更任務相關結果(即Java 類),平均精度為58.00%,召回率達63.48%.與Kevic 和Fritz 的方法[2]比較,本文提出的方法在各項評價指標上有更好的表現.因此,本文做了以下工作:

① 展示了TextRank 算法在識別和獲取軟件變更任務的相關搜索術語中的新用途.

② 通過一個涉及兩個主題系統的軟件變更任務案例研究,并與Kevic 和Fritz 的現有方法進行比較,展示了所提出方法的有效性.

1 方法

圖2展示了提出方法的搜索識別技術示意圖和變更任務的基本步驟.接下來將討論該方法涉及的步驟.

圖2 所提出方法的示意圖

1.1 變更任務的數據采集

通常,同戶提供的軟件變更任務是使用自然語言描述的(如表1所示),通過收集了336 個開發實際任務作為數據集進行分析.這些任務用半結構化的方式提交,包含了問題ID、產品、組件、摘要、描述等幾個字段,由于任務變更的具體問題基本都只在摘要和描述中提及,因此分析僅選取最后兩個字段的內容.同時為了保持算法的簡單性和輕量級,也暫時不考慮其他附加到更改任務中的額外信息.

1.2 文本預處理

在這一步驟中,將分析軟件變更請求中的摘要和描述,并在將文本轉化為文本圖之前進行多個預處理.預處理將每個句子視為一個邏輯文本單元,這樣有助于整體任務描述,接下來從每個句子中提取能傳達有用語義或表達軟件問題域的術語,然后從句子里刪除副詞、介詞等非重要詞,并將包含分隔符號(例如“.”)的詞分解為組成它們的更簡單的詞.這樣的分解有助于單獨分析每個概念.例如:”org.eclipse.ui.part.PageBook View.createPartControl”,這個句子包含了一個包名(org.eclipse.ui.part)、一個類名(PageBookView)和一個方法名(createPartControl).需要指出的是,在這里不采用軟件代碼標識符命名規則里常用的“駝峰大小寫”表示法進行拆分,因為變更請求可能包含不同的技術工件,例如庫名、類名、方法名等,這些名稱往往已經使用了“駝峰大小寫”,那么進一步拆分會破壞工件的完整性.

1.3 文本圖開發

在文本預處理之后,將會得到一個句子列表,每個句子都包含有在語義上很重要的術語以及與問題域相關的術語,然后使用這些術語來描述任務的開發術語圖.可以將每一個術語表示為圖中的不同節點,并考慮句子中這些術語的“同現”,作為它們之間語義關系(依賴關系)的指征[6].例如考慮句子“This works fine most of the time,but if you happen to have more than one of the same version of VM installed they are added with the same name”(表1),預處理會形成一個有序的術語短句:“works fine time happen version installed”.轉換后的句子會包含“works fine”、“version installed”等短語,這些短語中的術語在語義上依賴,當“窗口大小”以2 作為單詞的語義單位時[6],可獲得以下關系:works←→fine,fine←→time,time←→happen,happen←→version,version←→installed.然后將這種關系表示為文本圖中相應節點之間的鄰接邊.

1.4 TextRank 計算

為了計算文本圖中每個術語的權重(重要性),方法采用了一種基于Web 鏈接分析的PageRank 改進的TextRank 算法[6].該算法遞歸分析文本圖中每個術語的傳入鏈接和傳出鏈接等細節,并計算其權重W(Vi),如下式所示:

這里,In(vi)表示通過輸入鏈路指向vi的節點集合,Out(vj)表示由vj發出的輸出鏈路指向的節點集合,φ表示阻尼系數.在文本圖中,每條邊都是無向邊(即術語彼此依賴),因此節點入度等于出度.對于φ的取值,通常按一般取值為0.85,然后采用0.25 的默認值初始化圖中每個術語,并開始迭代計算,直到項的分數收斂到0.0001 的極限值或達到最大迭代限制值100.基于TextRank 的推薦機制,如果術語B 以任何方式補充術語A 的語義,則術語A 就推薦術語B[6],那么這個算法將根據文本圖中個的傳入鏈接獲得對術語的推薦,并確定術語的重要性.一旦計算結束,圖中的每個術語都會得到一個分值,該分值可被認為是這個術語在文本中的權重(重要性).

1.5 搜索術語選擇

計算TextRank 后,會根據權重對術語進行排序,并以啟發方式選擇變更任務的搜索術語,其中任務“摘要”和“描述”中的術語最適合作為搜索術語.但是這些字段中的術語存在重疊而不足以形成搜索查詢,因此需對其進行調整.首先在變更任務的摘要中查找權重最高的術語,如果摘要內容太少而無法提供所有條件,那么就從任務描述中收集其余內容.然后基于它們的權重或等級來選擇術語,這些術語是通過遞歸分析文本圖中該術語周圍的術語計算出的.例如表1所示的變更任務,得到搜索項:Mac (權重0.64)、selection (權重0.27)、installs (權重0.27)、improvement (權重0.25)和JREs (權重1.0,來源于描述).

2 實驗

為了驗證本文所提出的方法,將使用了兩個開源的主題系統的變更任務進行實驗,分別是eclipse 中的調試模型插件eclipse.jdt.debug,以及Apache 的日志操作包Log4j.并與一種現有的方法進行了比較.

2.1 數據集和文件搜索

實驗中,選擇了兩個開源主題系統的變更請求任務.首先從缺陷追蹤數據庫BugZilla 中收集變更任務,分析其BugID(變更任務的標識),然后根據BugID 從來源代碼數據庫GitHub 中找到相應的項目(GitHub中,每個軟件錯誤解決和變更請求的提交操作通常會在其提交消息中提到相應BugID).基于此,在Log4j 中發現了223 次提交,在eclipse.jdt.debug 中發現了113次提交,共計336 個變更任務.

然后,為每個變更任務收集變更集(即已更改文件列表),并開發解決方案集.為了搜索變更任務的文件,采用了基于向量空間模型的搜索引擎Apache Lucene[7].由于項目中的源文件會包含常規文本外的內容(例如代碼段),那么將對每個源文件應用有限的預處理,刪除所有標點符號,這就會將源代碼轉換為純文本,有助于搜索引擎更有效地執行.啟動搜索后,搜索引擎使用布爾搜索模型過濾語料庫中的無關文件,并應用基于tf-idf 的評分技術來返回相關文檔的排序列表,最后選擇返回的排名前10 以內的結果項進行操作.

2.2 評價指標

為了清晰地評價提出方法的效果和性能,會采用K值平均精確率(MAPK)和平均召回率(MR)兩個主要指標,對搜索結果進行評價.K值平均精確率用于表示所有搜索結果的平均相關精度,即查準率;平均召回率用于表示搜索到的結果集的返回率,即查全率.

2.3 實驗結果

對兩個開源的主題系統的336 個變更任務進行了實驗,并應用解決任務數、解決任務百分比、平均精確率和平均召回率4 個不同的指標進行總結.結果如表2所示.

從實驗結果表中可以看到,當使用5 個搜索詞時,查詢效果最佳.例如,它們返回了來自Log4j 的223 個更改任務中的107 個(47.98%)的相關結果,以及來自eclipse.jdt.debug 的113 個更改任務中的58 個(51.33%),這是預期良好的.因此,平均而言,該查詢從數據集中檢索63.48%的解決方案,平均精度為58.00%.

表2 實驗結果指標

為了從其他方面評估提出方法的性能,還從以下幾個方面進行了實驗:

① 使用6 個搜索詞進行查詢,但是查詢結果在這兩個主題系統中表現相對較差.

② 在沒有預處理的情況下,基于現有語料庫重新進行了實驗,沒有出現較明顯的性能下降,證明了提出的搜索術語對于變更任務的穩健性.

③ 在變更任務中,不采用TextRank 計算,而是隨機選擇了五個搜索詞進行查詢,結果非常糟糕,從log4j只返回最多52 個任務的相關結果,從eclipse.jdt.debug只返回37 個任務(本文的方法返回了107 個和58 個結果).

④ 將變更任務調整為中文描述,按中文文法進行預處理后,該方法仍能以較好的召回率和精度得到搜索結果,說明該方法有良好的語言通用性.

因此,實驗結果表明,本文提出的搜索詞方法和技術能完成任務,并且有不錯的可靠性、穩定性和通用性.

3 結論和未來工作

總而言之,本文提出了一種新的基于TextRank 的技術方法,可以自動識別并得到軟件更改任務的搜索項.通過來自兩個主題系統的336 個更改任務的實驗表明,該方法平均可以返回49.65%的變更任務的相關結果(即Java 類),平均精度為58.00%,召回率為63.48%.方法能完成預期目標,并具有良好的性能.

雖然這些初步研究結果證明了該方法的潛力,但需要驗證更多不同類型和變化任務的主題系統,例如更大體量的中文數據集等,以期進一步改進該方法的性能,獲得更好的應用前景.