基于TextRank的軟件變更任務(wù)搜索術(shù)語(yǔ)識(shí)別①

王 杉

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

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

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

在本文中,提出了一種基于TextRank 進(jìn)行自動(dòng)識(shí)別并得到軟件變更任務(wù)搜索術(shù)語(yǔ)的方法.TextRank 方法是PageRank 方法的改進(jìn)[6],對(duì)于自然語(yǔ)言文本,其中的文本可被視為詞匯的詞匯或語(yǔ)義網(wǎng)絡(luò).TextRank 技術(shù)被廣泛應(yīng)用于各類(lèi)信息檢索中,例如關(guān)鍵字提取、摘要提取、詞義消歧、詞法分析和其他基于圖的屬于加權(quán)任務(wù).因此該算法適合在特征定位任務(wù)的上下文中進(jìn)行搜索項(xiàng)提取,這是因?yàn)檐浖兏?qǐng)求通常由開(kāi)發(fā)團(tuán)隊(duì)以外的人員進(jìn)行,他們通過(guò)相關(guān)問(wèn)題域的概念和自然語(yǔ)言文本來(lái)表達(dá)需求,并可以使用基于圖的任務(wù)描述來(lái)揭示不同術(shù)語(yǔ)之間的重要語(yǔ)義關(guān)系.其次,TextRank 算法利用圖中術(shù)語(yǔ)的連通性,用于確定該術(shù)語(yǔ)的權(quán)重(即重要性),然后遞歸執(zhí)行該過(guò)程,從而確定出搜索術(shù)語(yǔ).

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

圖1 表1中的變更請(qǐng)求文本圖

并且選取了兩個(gè)主題系統(tǒng)Apache Log4j(日志分析)和Eclipse JDT Debug 中的336 個(gè)變更任務(wù)進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)表明了提出的方法可以返回49.65%的變更任務(wù)相關(guān)結(jié)果(即Java 類(lèi)),平均精度為58.00%,召回率達(dá)63.48%.與Kevic 和Fritz 的方法[2]比較,本文提出的方法在各項(xiàng)評(píng)價(jià)指標(biāo)上有更好的表現(xiàn).因此,本文做了以下工作:

① 展示了TextRank 算法在識(shí)別和獲取軟件變更任務(wù)的相關(guān)搜索術(shù)語(yǔ)中的新用途.

② 通過(guò)一個(gè)涉及兩個(gè)主題系統(tǒng)的軟件變更任務(wù)案例研究,并與Kevic 和Fritz 的現(xiàn)有方法進(jìn)行比較,展示了所提出方法的有效性.

1 方法

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

圖2 所提出方法的示意圖

1.1 變更任務(wù)的數(shù)據(jù)采集

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

1.2 文本預(yù)處理

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

1.3 文本圖開(kāi)發(fā)

在文本預(yù)處理之后,將會(huì)得到一個(gè)句子列表,每個(gè)句子都包含有在語(yǔ)義上很重要的術(shù)語(yǔ)以及與問(wèn)題域相關(guān)的術(shù)語(yǔ),然后使用這些術(shù)語(yǔ)來(lái)描述任務(wù)的開(kāi)發(fā)術(shù)語(yǔ)圖.可以將每一個(gè)術(shù)語(yǔ)表示為圖中的不同節(jié)點(diǎn),并考慮句子中這些術(shù)語(yǔ)的“同現(xiàn)”,作為它們之間語(yǔ)義關(guān)系(依賴關(guān)系)的指征[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),預(yù)處理會(huì)形成一個(gè)有序的術(shù)語(yǔ)短句:“works fine time happen version installed”.轉(zhuǎn)換后的句子會(huì)包含“works fine”、“version installed”等短語(yǔ),這些短語(yǔ)中的術(shù)語(yǔ)在語(yǔ)義上依賴,當(dāng)“窗口大小”以2 作為單詞的語(yǔ)義單位時(shí)[6],可獲得以下關(guān)系:works←→fine,fine←→time,time←→happen,happen←→version,version←→installed.然后將這種關(guān)系表示為文本圖中相應(yīng)節(jié)點(diǎn)之間的鄰接邊.

1.4 TextRank 計(jì)算

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

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

1.5 搜索術(shù)語(yǔ)選擇

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

2 實(shí)驗(yàn)

為了驗(yàn)證本文所提出的方法,將使用了兩個(gè)開(kāi)源的主題系統(tǒng)的變更任務(wù)進(jìn)行實(shí)驗(yàn),分別是eclipse 中的調(diào)試模型插件eclipse.jdt.debug,以及Apache 的日志操作包Log4j.并與一種現(xiàn)有的方法進(jìn)行了比較.

2.1 數(shù)據(jù)集和文件搜索

實(shí)驗(yàn)中,選擇了兩個(gè)開(kāi)源主題系統(tǒng)的變更請(qǐng)求任務(wù).首先從缺陷追蹤數(shù)據(jù)庫(kù)BugZilla 中收集變更任務(wù),分析其BugID(變更任務(wù)的標(biāo)識(shí)),然后根據(jù)BugID 從來(lái)源代碼數(shù)據(jù)庫(kù)GitHub 中找到相應(yīng)的項(xiàng)目(GitHub中,每個(gè)軟件錯(cuò)誤解決和變更請(qǐng)求的提交操作通常會(huì)在其提交消息中提到相應(yīng)BugID).基于此,在Log4j 中發(fā)現(xiàn)了223 次提交,在eclipse.jdt.debug 中發(fā)現(xiàn)了113次提交,共計(jì)336 個(gè)變更任務(wù).

然后,為每個(gè)變更任務(wù)收集變更集(即已更改文件列表),并開(kāi)發(fā)解決方案集.為了搜索變更任務(wù)的文件,采用了基于向量空間模型的搜索引擎Apache Lucene[7].由于項(xiàng)目中的源文件會(huì)包含常規(guī)文本外的內(nèi)容(例如代碼段),那么將對(duì)每個(gè)源文件應(yīng)用有限的預(yù)處理,刪除所有標(biāo)點(diǎn)符號(hào),這就會(huì)將源代碼轉(zhuǎn)換為純文本,有助于搜索引擎更有效地執(zhí)行.啟動(dòng)搜索后,搜索引擎使用布爾搜索模型過(guò)濾語(yǔ)料庫(kù)中的無(wú)關(guān)文件,并應(yīng)用基于tf-idf 的評(píng)分技術(shù)來(lái)返回相關(guān)文檔的排序列表,最后選擇返回的排名前10 以內(nèi)的結(jié)果項(xiàng)進(jìn)行操作.

2.2 評(píng)價(jià)指標(biāo)

為了清晰地評(píng)價(jià)提出方法的效果和性能,會(huì)采用K值平均精確率(MAPK)和平均召回率(MR)兩個(gè)主要指標(biāo),對(duì)搜索結(jié)果進(jìn)行評(píng)價(jià).K值平均精確率用于表示所有搜索結(jié)果的平均相關(guān)精度,即查準(zhǔn)率;平均召回率用于表示搜索到的結(jié)果集的返回率,即查全率.

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

對(duì)兩個(gè)開(kāi)源的主題系統(tǒng)的336 個(gè)變更任務(wù)進(jìn)行了實(shí)驗(yàn),并應(yīng)用解決任務(wù)數(shù)、解決任務(wù)百分比、平均精確率和平均召回率4 個(gè)不同的指標(biāo)進(jìn)行總結(jié).結(jié)果如表2所示.

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

表2 實(shí)驗(yàn)結(jié)果指標(biāo)

為了從其他方面評(píng)估提出方法的性能,還從以下幾個(gè)方面進(jìn)行了實(shí)驗(yàn):

① 使用6 個(gè)搜索詞進(jìn)行查詢,但是查詢結(jié)果在這兩個(gè)主題系統(tǒng)中表現(xiàn)相對(duì)較差.

② 在沒(méi)有預(yù)處理的情況下,基于現(xiàn)有語(yǔ)料庫(kù)重新進(jìn)行了實(shí)驗(yàn),沒(méi)有出現(xiàn)較明顯的性能下降,證明了提出的搜索術(shù)語(yǔ)對(duì)于變更任務(wù)的穩(wěn)健性.

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

④ 將變更任務(wù)調(diào)整為中文描述,按中文文法進(jìn)行預(yù)處理后,該方法仍能以較好的召回率和精度得到搜索結(jié)果,說(shuō)明該方法有良好的語(yǔ)言通用性.

因此,實(shí)驗(yàn)結(jié)果表明,本文提出的搜索詞方法和技術(shù)能完成任務(wù),并且有不錯(cuò)的可靠性、穩(wěn)定性和通用性.

3 結(jié)論和未來(lái)工作

總而言之,本文提出了一種新的基于TextRank 的技術(shù)方法,可以自動(dòng)識(shí)別并得到軟件更改任務(wù)的搜索項(xiàng).通過(guò)來(lái)自兩個(gè)主題系統(tǒng)的336 個(gè)更改任務(wù)的實(shí)驗(yàn)表明,該方法平均可以返回49.65%的變更任務(wù)的相關(guān)結(jié)果(即Java 類(lèi)),平均精度為58.00%,召回率為63.48%.方法能完成預(yù)期目標(biāo),并具有良好的性能.

雖然這些初步研究結(jié)果證明了該方法的潛力,但需要驗(yàn)證更多不同類(lèi)型和變化任務(wù)的主題系統(tǒng),例如更大體量的中文數(shù)據(jù)集等,以期進(jìn)一步改進(jìn)該方法的性能,獲得更好的應(yīng)用前景.