華晨彥，鄒艷珍+，朱子驍，謝 冰

1.北京大學(xué) 信息科學(xué)技術(shù)學(xué)院，北京 100871

2.高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871

3.北京大學(xué)（天津?yàn)I海）新一代信息技術(shù)研究院，天津 300450

基于代碼模式的軟件問(wèn)答文檔檢索優(yōu)化方法*

華晨彥1,2,3，鄒艷珍1,2,3+，朱子驍1,2,3，謝 冰1,2,3

1.北京大學(xué) 信息科學(xué)技術(shù)學(xué)院，北京 100871

2.高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871

3.北京大學(xué)（天津?yàn)I海）新一代信息技術(shù)研究院，天津 300450

Abstract:Developers often need to search related software Q&A documents in Q&A website.In the search results,the Q&A documents which contain good code snippets(usage examples)are preferred.However,how to metric those code snippets in document is still a big challenge.To address this issue,this paper proposes an approach for refining software Q&A document search results based on code pattern.Firstly,code snippets are extracted from each document in the search results.Then,the common code patterns are mined and used to measure the quality of those code snippets.Finally,the documents with high quality are recommended and ranked at the top of the search results.In the experiments,this paper carries out some evaluations with 10 real problems that software developers meet in practice.Compared to the search results of StackOverflow,the proposed approach has an increment of 40%atNDCG@5.

Key words:code pattern;software Q&Adocument;document search

開(kāi)發(fā)人員通常通過(guò)問(wèn)答網(wǎng)站的搜索引擎進(jìn)行相關(guān)軟件問(wèn)答文檔的搜索。在檢索結(jié)果中，包含優(yōu)質(zhì)代碼片段（使用示例）的問(wèn)答文檔往往更受青睞，但如何度量這些文檔中代碼片段的質(zhì)量仍是個(gè)巨大的挑戰(zhàn)。針對(duì)這個(gè)問(wèn)題，提出了一種基于代碼模式的軟件問(wèn)答文檔檢索優(yōu)化方法。該方法能夠基于當(dāng)前檢索結(jié)果，抽取文檔中的代碼片段，分析代碼片段中的公共代碼模式，并基于代碼模式度量文檔中代碼片段的質(zhì)量，從原有檢索結(jié)果中向用戶(hù)推薦高質(zhì)量的軟件問(wèn)答文檔。以軟件開(kāi)發(fā)人員在實(shí)踐過(guò)程中遇到的真實(shí)問(wèn)題為基礎(chǔ)進(jìn)行了實(shí)驗(yàn)，對(duì)比StackOverflow的搜索結(jié)果，所提方法在準(zhǔn)確率指標(biāo)NDCG@5上提升了40%。

代碼模式；軟件問(wèn)答文檔；文檔檢索

1 引言

近年來(lái)，各類(lèi)技術(shù)性問(wèn)答網(wǎng)站（如StackOverflow等）受到了開(kāi)發(fā)者們的喜愛(ài)，這些問(wèn)答網(wǎng)站上產(chǎn)生了大量的軟件問(wèn)答文檔。如何檢索和利用這些軟件問(wèn)答文檔成為軟件復(fù)用領(lǐng)域一個(gè)非常重要的研究問(wèn)題。

很多研究者針對(duì)軟件問(wèn)答文檔檢索問(wèn)題進(jìn)行了研究[1-2]，主要關(guān)注點(diǎn)是對(duì)檢索結(jié)果進(jìn)行優(yōu)化和重排序[3]。例如，Atwood[4]使用StackOverflow的基于軟件問(wèn)答文檔元數(shù)據(jù)的檢索結(jié)果排序方法。該方法通過(guò)軟件問(wèn)答文檔的閱讀量、回答數(shù)量、贊同數(shù)量等指標(biāo)綜合計(jì)算每篇文檔的得分，按得分的高低對(duì)檢索結(jié)果進(jìn)行排序。Ponzanelli等人[5]設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)Eclipse插件PROMPTER。PROMPTER以代碼片段作為查詢(xún)的輸入，考慮了文本相似度（使用tf-idf）、代碼相似度（代碼克?。PI（application programming interface）類(lèi)型相似度、API方法相似度等參數(shù)，加權(quán)平均決定軟件問(wèn)答文檔的最終得分。Williams等人[6]提出了基于遞歸偽相關(guān)反饋策略的相似文檔檢索方法。對(duì)于給定查詢(xún)的結(jié)果列表R，對(duì)R的前k篇文檔遞歸進(jìn)行檢索，通過(guò)遞歸檢索的結(jié)果反饋評(píng)價(jià)原始結(jié)果，從而優(yōu)化檢索結(jié)果。Cha等人[7]提出了基于主題模型的文檔檢索優(yōu)化方法，使用LDA（latent Dirichlet allocation）主題模型給每篇文檔計(jì)算一個(gè)主題分布，根據(jù)查詢(xún)與每個(gè)主題的相關(guān)程度確定文檔在檢索結(jié)果中的排名位置。Zou等人[8]提出的面向軟件的文本檢索方法將問(wèn)題分為6種類(lèi)別，依據(jù)檢索問(wèn)題與檢索結(jié)果是否屬于同一類(lèi)別對(duì)檢索結(jié)果進(jìn)行重排序。

從這些工作可以看出，如何挑選或推薦高質(zhì)量的檢索結(jié)果是當(dāng)前軟件問(wèn)答文檔檢索優(yōu)化的主要目標(biāo)。本文在調(diào)研中發(fā)現(xiàn)，軟件問(wèn)答文檔中包含大量的代碼示例片段，包含代碼片段的問(wèn)答文檔質(zhì)量較高，可以更好地幫助開(kāi)發(fā)者了解或解決遇到的問(wèn)題。但是由于不同文檔討論不同的問(wèn)題，其針對(duì)的開(kāi)發(fā)任務(wù)不同，并且問(wèn)答文檔由不同的人編寫(xiě)，其編碼的語(yǔ)言、風(fēng)格也大不相同，如何度量檢索結(jié)果文檔中代碼片段的質(zhì)量以及如何進(jìn)行檢索結(jié)果重排序仍是個(gè)巨大的挑戰(zhàn)。

為此，本文提出了一種基于代碼模式的軟件問(wèn)答文檔檢索優(yōu)化方法。該方法從解決相同/相似開(kāi)發(fā)任務(wù)的軟件問(wèn)答文檔的代碼片段中，抽取公共的代碼模式，通過(guò)代碼模式度量代碼片段和軟件問(wèn)答文檔的質(zhì)量，由此通過(guò)檢索結(jié)果重排序向用戶(hù)推薦高質(zhì)量的軟件問(wèn)答文檔。

與現(xiàn)有工作相比，本文的主要貢獻(xiàn)包括：

（1）定義了一種面向開(kāi)發(fā)任務(wù)的軟件代碼使用模式，并提出了基于數(shù)據(jù)流圖的代碼模式挖掘方法。

（2）提出了一種基于代碼模式的軟件問(wèn)答文檔檢索優(yōu)化方法。通過(guò)代碼模式度量代碼片段和軟件問(wèn)答文檔的質(zhì)量，給每篇問(wèn)答文檔一個(gè)評(píng)分，并結(jié)合該文檔在原有檢索結(jié)果中的排序進(jìn)行檢索優(yōu)化。

（3）實(shí)現(xiàn)并開(kāi)源了一個(gè)基于代碼模式的軟件問(wèn)答文檔推薦工具。以10個(gè)軟件開(kāi)發(fā)人員在實(shí)踐過(guò)程中遇到的真實(shí)問(wèn)題為基礎(chǔ)進(jìn)行了實(shí)驗(yàn)，對(duì)比了Stack-Overflow的搜索結(jié)果，本文工作在準(zhǔn)確率指標(biāo)NDCG@5上提升了約40%。

本文組織結(jié)構(gòu)如下：第2章介紹了代碼模式的定義和作用；第3章詳細(xì)討論了基于代碼模式的軟件問(wèn)答文檔檢索優(yōu)化方法；第4章通過(guò)實(shí)驗(yàn)驗(yàn)證了方法的有效性；第5章對(duì)本文工作進(jìn)行了總結(jié)。

2 代碼模式

一般來(lái)說(shuō)，軟件問(wèn)答文檔的來(lái)源可分為兩類(lèi)：軟件項(xiàng)目官網(wǎng)與技術(shù)性問(wèn)答網(wǎng)站。軟件項(xiàng)目官網(wǎng)的軟件問(wèn)答文檔由軟件項(xiàng)目的開(kāi)發(fā)人員撰寫(xiě)，準(zhǔn)確度高，結(jié)構(gòu)簡(jiǎn)單，通常采用一問(wèn)一答的形式，但數(shù)量少，覆蓋面狹窄；技術(shù)性問(wèn)答網(wǎng)站的軟件問(wèn)答文檔數(shù)量巨大，且為大量開(kāi)發(fā)人員在實(shí)踐過(guò)程中總結(jié)出的經(jīng)驗(yàn)教訓(xùn)，覆蓋面廣，實(shí)用性高。在這兩類(lèi)問(wèn)答文檔中，為了更好地幫助提問(wèn)者理解回答或解決問(wèn)題，回答者一般都會(huì)在答案中附上相應(yīng)的代碼片段。研究表明，在StackOverflow上的軟件問(wèn)答文檔中，包含代碼片段的文檔數(shù)量約占總文檔數(shù)量的50%！這些代碼片段可能是回答者針對(duì)這一問(wèn)題給出的，或是其曾經(jīng)開(kāi)發(fā)過(guò)的項(xiàng)目中與該問(wèn)題相關(guān)的代碼片段。

在討論相同/相似問(wèn)題的軟件問(wèn)答文檔中，代碼片段（使用示例）往往調(diào)用相同的API方法，或包含一些共同的語(yǔ)句、方法調(diào)用、控制結(jié)構(gòu)，本文將這些共性稱(chēng)為開(kāi)發(fā)任務(wù)的代碼模式（code pattern）。對(duì)于簡(jiǎn)單的開(kāi)發(fā)任務(wù)，這些API可能為單個(gè)對(duì)象的若干方法順序執(zhí)行，然而對(duì)于復(fù)雜的任務(wù)，便會(huì)涉及多個(gè)對(duì)象互相交互，還可能包含復(fù)雜的控制結(jié)構(gòu)。圖1展示了兩個(gè)StackOverflow文檔體現(xiàn)的代碼模式（加粗高亮表示的部分）。該模式是使用JDK的Scanner讀取文件的常用模式。

在問(wèn)答文檔檢索過(guò)程中，這些面向開(kāi)發(fā)任務(wù)的代碼模式將帶來(lái)如下益處：（1）可以度量文檔中代碼片段的質(zhì)量，過(guò)濾不完整或不準(zhǔn)確的示例代碼；（2）可以解決文檔檢索中的模糊性問(wèn)題，如提問(wèn)者對(duì)問(wèn)題的理解存在偏差，提問(wèn)者的問(wèn)題過(guò)于特化等情況。在圖1包含代碼模式的兩篇文檔中，其中文檔1[9]的開(kāi)發(fā)任務(wù)是輸出給定文件中所有符合特定條件的行，文檔2[10]的開(kāi)發(fā)任務(wù)是讀取csv格式的文件。通過(guò)代碼模式的抽取，用戶(hù)在檢索“Scanner read file”時(shí)也可以定位到它們。

Fig.1 Code pattern of reading file using“Scanner”圖1 使用Scanner讀取文件的代碼模式

3 基于代碼模式的軟件問(wèn)答文檔檢索優(yōu)化方法

本文提出了一種基于代碼模式的軟件問(wèn)答文檔檢索優(yōu)化方法。如圖2所示，該方法主要分為三部分：

Fig.2 Framework of refining software Q&Adocument search results based on code pattern圖2 基于代碼模式的軟件問(wèn)答文檔檢索優(yōu)化方法框架

（1）檢索結(jié)果的獲取與解析。根據(jù)用戶(hù)的查詢(xún)獲取與查詢(xún)相關(guān)的軟件問(wèn)答文檔，并解析出其中的代碼片段。

（2）代碼模式的抽取。將代碼片段轉(zhuǎn)換為數(shù)據(jù)流圖，通過(guò)頻繁子圖挖掘算法，在這些數(shù)據(jù)流圖中挖掘出代碼模式。

（3）檢索結(jié)果的優(yōu)化。通過(guò)代碼模式給每一篇軟件問(wèn)答文檔一個(gè)評(píng)分，將所有的軟件問(wèn)答文檔按評(píng)分高低重排序，推薦給用戶(hù)。

3.1 檢索結(jié)果的獲取與解析

本文的軟件問(wèn)答文檔數(shù)據(jù)來(lái)源于StackOverflow，根據(jù)用戶(hù)的查詢(xún)，使用StackOverflow的搜索API進(jìn)行在線(xiàn)搜索，并將結(jié)果下載至本地，便于后續(xù)的解析與處理。StackOverflow的軟件問(wèn)答文檔為HTML格式。HTML使用標(biāo)簽表明文檔的內(nèi)容，依據(jù)嵌套關(guān)系表明文檔的層次結(jié)構(gòu)，通過(guò)特定的標(biāo)簽即可解析出文檔中的代碼片段。

3.2 代碼模式的抽取

本文使用數(shù)據(jù)流圖（data flow graph）表示代碼模式。使用數(shù)據(jù)流圖存在以下兩個(gè)優(yōu)點(diǎn)：一是在面向?qū)ο笳Z(yǔ)言開(kāi)發(fā)過(guò)程中，開(kāi)發(fā)者常常遇到多個(gè)對(duì)象需要互相協(xié)作的場(chǎng)景[11]，使用數(shù)據(jù)流圖可以有效地梳理這種交織關(guān)系；二是開(kāi)發(fā)者對(duì)代碼元素的命名有著各自的喜好，而代碼元素的命名不會(huì)影響代碼實(shí)現(xiàn)的功能。數(shù)據(jù)流圖只關(guān)心每條語(yǔ)句的輸入來(lái)源與輸出去向，可以有效地過(guò)濾代碼元素命名帶來(lái)的干擾。

建立數(shù)據(jù)流圖需要變量的定值-使用關(guān)系，該信息可以通過(guò)靜態(tài)單賦值形式的控制流圖獲得。然而Java語(yǔ)法復(fù)雜，抽象語(yǔ)法樹(shù)的結(jié)點(diǎn)類(lèi)型較多，難以直接轉(zhuǎn)換為控制流圖，并且不同開(kāi)發(fā)人員實(shí)現(xiàn)相同功能的代碼可能使用了不同的語(yǔ)法，存在偏好差異，導(dǎo)致生成了不同的數(shù)據(jù)流圖，最終無(wú)法抽取出代碼模式。為此，需要先將Java語(yǔ)言的代碼片段通過(guò)中間代碼表示，再進(jìn)行后續(xù)操作。

（1）解析代碼片段。在前文中提到不同開(kāi)發(fā)人員在代碼編寫(xiě)過(guò)程中存在偏好差異，本文通過(guò)解析代碼片段，并使用中間代碼表示（intermediate representation，IR）的方式消除這些差異。

現(xiàn)有Java語(yǔ)言的中間代碼生成工具只能應(yīng)用于完整的Java項(xiàng)目，無(wú)法處理代碼片段。因此，本文設(shè)計(jì)與實(shí)現(xiàn)了一個(gè)Java語(yǔ)言的中間代碼生成工具。IR的設(shè)計(jì)主要有兩點(diǎn)：一是能與原語(yǔ)法相對(duì)應(yīng)；二是便于進(jìn)一步處理。在本文的IR設(shè)計(jì)中，產(chǎn)生式主要分為塊級(jí)與語(yǔ)句級(jí)兩個(gè)層次。塊級(jí)產(chǎn)生式對(duì)應(yīng)于控制流圖中的基本塊，便于轉(zhuǎn)換為控制流圖；語(yǔ)句級(jí)產(chǎn)生式對(duì)應(yīng)于一條語(yǔ)句，也是數(shù)據(jù)流圖的結(jié)點(diǎn)。語(yǔ)句級(jí)產(chǎn)生式均為變量賦值的形式，便于定值-使用分析。

（2）轉(zhuǎn)換數(shù)據(jù)流圖。本文使用靜態(tài)單賦值形式（static single form，SSA）的控制流圖來(lái)獲取與建立數(shù)據(jù)流圖所需要的變量定值-使用關(guān)系。

從中間代碼表示轉(zhuǎn)換至流圖只需要針對(duì)控制流語(yǔ)句在相應(yīng)結(jié)點(diǎn)之間添加邊即可。

將控制流圖轉(zhuǎn)換為SSA形式的關(guān)鍵就是對(duì)每個(gè)變量的定值添加版本號(hào)，在其支配邊界處添加φ函數(shù)，并相應(yīng)地更新所有使用的版本號(hào)。計(jì)算支配邊界先使用Lengauer-Tarjan算法[12]計(jì)算出直接支配結(jié)點(diǎn)，再通過(guò)直接支配結(jié)點(diǎn)計(jì)算支配邊界[13]。

將靜態(tài)單賦值形式的流圖轉(zhuǎn)換成數(shù)據(jù)流圖只需要對(duì)應(yīng)每一個(gè)變量的定值結(jié)點(diǎn)、連邊至其所有的使用即可。

（3）挖掘代碼模式。本文將代碼模式表示為數(shù)據(jù)流圖后，該問(wèn)題便可轉(zhuǎn)換為頻繁子圖挖掘問(wèn)題。

頻繁子圖挖掘（frequent subgraph mining）[14]是數(shù)據(jù)挖掘領(lǐng)域的熱門(mén)問(wèn)題之一，基于頻繁子圖挖掘可以發(fā)現(xiàn)大量圖數(shù)據(jù)中的公共模式。簡(jiǎn)單地說(shuō)，給定一個(gè)圖，頻繁子圖挖掘的目的就是找出其中出現(xiàn)最頻繁的子圖。頻繁子圖挖掘的常見(jiàn)應(yīng)用場(chǎng)景包括化合物結(jié)構(gòu)、社交網(wǎng)絡(luò)等。給定圖的集合S={G1=(V1,E1),G2=(V2,E2),…,Gn=(Vn,En)}，頻繁子圖挖掘的完整定義如下。

定義1（圖的大?。┤我饨o定一個(gè)圖G=(V,E)，稱(chēng)G的大小為|V|，記為size(G)。

定義2（子圖）如果?Gi=(Vi,Ei),Gj=(Vj,Ej),Vi?Vj,Ei?Ej，則稱(chēng)Gi包含于Gj，或Gi是Gj的子圖，記為Gi?Gj。

定義3（支持度）任意給定一個(gè)圖G，稱(chēng)G的支持度為|{g|g∈S且G是g的子圖}|，記為support(G)。

定義4（頻繁子圖）圖的集合S的所有頻繁子圖為{g|size(g)≥fsize且support(g)≥fsupport}，其中fsize和fsupport是事先給定的閾值。

gSpan算法[15]是一種基于模式增長(zhǎng)的頻繁子圖挖掘算法。其核心思想是對(duì)圖進(jìn)行dfs編碼和最右擴(kuò)展，通過(guò)最小dfs編碼判斷同構(gòu)。由頻繁子圖的定義可知，若圖G1是頻繁子圖，G2?G1，那么G2也是頻繁子圖。然而對(duì)于代碼模式而言，G2的代表性嚴(yán)格劣于G1，因此本文刪除了這些冗余的結(jié)果。

3.3 檢索結(jié)果的優(yōu)化

軟件問(wèn)答文檔中代碼片段包含的代碼模式數(shù)量越多，該文檔越具有代表性。然而代碼片段的長(zhǎng)度會(huì)影響其包含的代碼模式數(shù)量。因此本文提出了兩個(gè)評(píng)價(jià)軟件問(wèn)答文檔質(zhì)量的方法。

（1）依據(jù)每篇軟件問(wèn)答文檔被接受的答案中的代碼片段包含的代碼模式數(shù)量作為評(píng)分依據(jù)。使用公式表述為：

（2）依據(jù)每篇軟件問(wèn)答文檔被接受的答案中代碼片段數(shù)據(jù)流圖中屬于代碼模式的結(jié)點(diǎn)數(shù)量與總結(jié)點(diǎn)數(shù)量的比值作為評(píng)分依據(jù)。使用公式表述為：

其中，codes(doc)表示文檔doc中的代碼片段集合；ddg(c)表示代碼片段c的控制流圖；patterns為挖掘出的代碼模式集合。

最終的推薦結(jié)果依據(jù)文檔的評(píng)分，評(píng)分越高的文檔，排序越靠前。

4 實(shí)驗(yàn)與案例研究

基于上述工作，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)軟件問(wèn)答文檔推薦工具。該工具目前已經(jīng)在github上進(jìn)行開(kāi)源（https://github.com/woooking/qa_sorting）。下面將以軟件開(kāi)發(fā)人員遇到的實(shí)際問(wèn)題為例，說(shuō)明推薦方法的實(shí)現(xiàn)過(guò)程和效果。

4.1 實(shí)驗(yàn)數(shù)據(jù)

為了檢驗(yàn)本文工作，收集了10個(gè)軟件人員在開(kāi)發(fā)過(guò)程中遇到的問(wèn)題。表1描述了這10個(gè)問(wèn)題對(duì)應(yīng)的開(kāi)發(fā)任務(wù)及其在StackOverflow檢索時(shí)輸入的查詢(xún)條件。譬如，第一行描述了某軟件開(kāi)發(fā)人員現(xiàn)有一個(gè)開(kāi)發(fā)任務(wù)是完成某個(gè)網(wǎng)絡(luò)游戲的后臺(tái)。經(jīng)過(guò)團(tuán)隊(duì)協(xié)商決定使用TCP協(xié)議進(jìn)行網(wǎng)絡(luò)傳輸，但是他并不知道如何創(chuàng)建一個(gè)TCP服務(wù)器。因此，使用“create tcp server”作為查詢(xún)條件在StackOverflow上進(jìn)行檢索，希望得到與創(chuàng)建TCP服務(wù)器相關(guān)的問(wèn)答文檔。

Table 1 Queries used in experiment表1 實(shí)驗(yàn)所用查詢(xún)

對(duì)于每個(gè)查詢(xún)，本文從StackOverflow上獲取文本相關(guān)性排名前10的軟件問(wèn)答文檔。將這些文檔打亂順序交由提出查詢(xún)的軟件開(kāi)發(fā)人員為這些文檔打分，分?jǐn)?shù)范圍是1～5分，評(píng)分依據(jù)為該文檔是否可以解決軟件開(kāi)發(fā)人員的問(wèn)題。

4.2 案例研究

任務(wù)1在StackOverflow上的檢索結(jié)果如表2（左側(cè)）所示?？梢钥吹剑瑱z索結(jié)果中排名第一位的文檔評(píng)分只有1分；前3個(gè)檢索結(jié)果中只有一個(gè)文檔的評(píng)分為5分；而前5個(gè)檢索結(jié)果中也只有一個(gè)文檔的評(píng)分為5分。這樣的檢索結(jié)果將耗費(fèi)用戶(hù)大量的時(shí)間用于文檔瀏覽，降低用戶(hù)的檢索體驗(yàn)。

基于上述檢索結(jié)果，本文從排名前10的包含被接受答案與代碼片段的文檔中總共提取出20段代碼片段。解析這20段代碼片段，并將其轉(zhuǎn)換為數(shù)據(jù)流圖。在這20個(gè)數(shù)據(jù)流圖中進(jìn)行頻繁子圖挖掘，挖掘算法中的閾值fsize和fsupport均設(shè)為3，總共挖掘出3個(gè)代碼模式。圖3展示了其中的一個(gè)代碼模式。

Fig.3 Acode pattern example of“create tcp server”圖3 create tcp server的代碼模式

依據(jù)代碼模式，本文對(duì)每一篇問(wèn)答文檔中的代碼片段進(jìn)行評(píng)分，評(píng)分依據(jù)為文檔中代碼片段包含的代碼模式的數(shù)量。由此對(duì)檢索結(jié)果進(jìn)行重排序，推薦結(jié)果如表2（右側(cè)）所示。可以看到，檢索結(jié)果中排名前4的文檔都為5分，排名第5的文檔也有4分。這樣的檢索結(jié)果可以幫助用戶(hù)準(zhǔn)確快速地定位至高質(zhì)量的軟件問(wèn)答文檔。通過(guò)對(duì)比可以發(fā)現(xiàn)，本文推薦方法可以有效地幫助軟件開(kāi)發(fā)人員解決問(wèn)題。

4.3 對(duì)比實(shí)驗(yàn)

為了更好地驗(yàn)證本文工作，對(duì)上述10組檢驗(yàn)結(jié)果分別進(jìn)行了分析。為了評(píng)價(jià)推薦結(jié)果的好壞，本文選取了信息檢索中常用的指標(biāo)之一NDCG@k[16]。該指標(biāo)的計(jì)算公式如下:

其中，r(i)表示排在結(jié)果第i位的項(xiàng)與查詢(xún)的相關(guān)程度，r(i)越高，相關(guān)程度越大。在本文中相關(guān)程度共分為5級(jí)，最高為4，最低為0；Nk是歸一化參數(shù)，它使得在最佳排序（即r(i)為降序）時(shí)，NDCG@k的值為1。

本文選取NDCG@k作為評(píng)價(jià)指標(biāo)的理由為：

（1）軟件開(kāi)發(fā)人員只有閱讀高質(zhì)量的文檔才能解決開(kāi)發(fā)問(wèn)題，因此在評(píng)價(jià)指標(biāo)中需要體現(xiàn)出高質(zhì)量的文檔比低質(zhì)量的文檔對(duì)結(jié)果的影響性更大。在NDCG@k的公式中，指數(shù)位的r(i)體現(xiàn)了這一點(diǎn)。

（2）高質(zhì)量文檔在推薦結(jié)果中的位置十分重要。在NDCG@k的公式中，體現(xiàn)了這一點(diǎn)，結(jié)果越靠后的文檔被開(kāi)發(fā)者閱讀的幾率越低，對(duì)排序結(jié)果的影響也就越低。

在實(shí)驗(yàn)過(guò)程中，本文對(duì)比了4種問(wèn)答文檔檢索/推薦方法。

（1）StackOverflow：該站點(diǎn)的原始搜索結(jié)果。

（2）pattern_ratio：依據(jù)代碼模式結(jié)點(diǎn)數(shù)與代碼片段結(jié)點(diǎn)數(shù)的比例評(píng)價(jià)文檔質(zhì)量。

（3）pattern_count：依據(jù)代碼片段包含的代碼模式數(shù)量評(píng)價(jià)文檔質(zhì)量的評(píng)分。

（4）replace：僅對(duì)包含被接受答案與代碼片段的文檔使用pattern_count方式評(píng)分，其余文檔的位置保持不變。

實(shí)驗(yàn)結(jié)果如圖4所示。對(duì)比上述4種方法的結(jié)果可以發(fā)現(xiàn)：整體而言，pattern_count方法的效果最佳。相比于StackOverflow的原始結(jié)果，pattern_count方法在NDCG@1（只看第一名）上從60.8%提升至83.3%，在NDCG@5（第一名到第五名）上從52.8%提升至75.1%，提升幅度為40%左右。pattern_ratio的效果略遜色于pattern_count。經(jīng)過(guò)分析發(fā)現(xiàn)，回答者在回答問(wèn)題時(shí)給出的代碼片段往往來(lái)源于其曾經(jīng)寫(xiě)過(guò)的某個(gè)項(xiàng)目，因此會(huì)包含一些冗余代碼，這些代碼無(wú)法構(gòu)成代碼模式，但也不會(huì)影響文檔的質(zhì)量。而pattern_ratio依據(jù)代碼模式結(jié)點(diǎn)數(shù)與代碼片段結(jié)點(diǎn)數(shù)的比例評(píng)價(jià)文檔質(zhì)量，因此會(huì)降低此類(lèi)文檔的評(píng)分。

Fig.4 Result of experiment圖4 實(shí)驗(yàn)結(jié)果

因?yàn)楸疚奶岢龅能浖?wèn)答文檔檢索優(yōu)化方法基于軟件問(wèn)答文檔中的代碼片段，所以最終的推薦結(jié)果只包含代碼片段。為了驗(yàn)證本文方法獲得的效果提升不僅僅是因?yàn)橥扑]了包含代碼片段的文檔，可以對(duì)比replace和StackOverflow兩種方法。replace與StackOverflow的文檔排序區(qū)別僅在于包含代碼片段的文檔，在結(jié)果中，replace比StackOverflow在k=1至5時(shí)均有提升，因此可以證明本文方法獲得的效果提升不僅僅是因?yàn)橥扑]了包含代碼片段的文檔，而是基于代碼模式的軟件問(wèn)答文檔度量方法的確有效。

5 總結(jié)

為了在檢索過(guò)程中幫助用戶(hù)更快地找到包含優(yōu)質(zhì)示例代碼的相關(guān)文檔，本文提出了一種基于代碼模式的軟件問(wèn)答文檔推薦方法，并以10個(gè)開(kāi)發(fā)人員實(shí)際遇到的問(wèn)題為基礎(chǔ)進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了本文方法的有效性。在未來(lái)工作中，將考慮加入更多來(lái)源、類(lèi)型的軟件文檔數(shù)據(jù)，以提升本文方法的適用性；進(jìn)一步改進(jìn)代碼模式挖掘方法，使得檢索系統(tǒng)能更快、更準(zhǔn)確地理解軟件問(wèn)答文檔中的代碼片段。

[1]Wang Xiaoling,Wen Jirong,Luan Jinfeng,et al.A method to query document database by content and structure[J].Journal of Software,2003,14(5):976-983.

[2]Ye Ting,Xie Bing,Zou Yanzhen,et al.Interrogative-guided re-ranking for question-oriented software text retrieval[C]//Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering,Vasteras,Sweden,Sep 15-19,2014.New York:ACM,2014:215-220.

[3]Huang Zhenhua,Zhang Jiawen,Tian Chunqi,et al.Survey on learning-to-rank based recommendation algorithms[J].Journal of Software,2016,27(3):691-713.

[4]Atwood J.What formula should be used to determine“hot”questions?[EB/OL].(2008)[2016-07-18].http://meta.stackexchange.com/questions/11602/what-formula-should-beused-to-determine-hot-questions.

[5]Ponzanelli L,Bavota G,Di Penta M,et al.Mining Stack-Overflow to turn the IDE into a self-confident programming prompter[C]//Proceedings of the 11th Working Conference on Mining Software Repositories,Hyderabad,India,May 31-Jun 1,2014.New York:ACM,2014:102-111.

[6]Williams K,Giles C L.Improving similar document retrieval using a recursive pseudo relevance feedback strategy[C]//Proceedings of the 16th ACM/IEEE-CS on Joint Conference on Digital Libraries,Newark,USA,Jun 19-23,2016.New York:ACM,2016:275-276.

[7]Cha M S,Kim S Y,Ha J H,et al.Topic model based approach for improved indexing in content based document retrieval[J].International Journal of Networked and Distributed Computing,2016,4(1):55-64.

[8]Zou Yanzhen,Ye Ting,Lu Yangyang,et al.Learning to rank for question oriented software text retrieval(T)[C]//Proceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering,Lincoln,USA,Nov 9-13,2015.Washington:IEEE Computer Society,2015:1-11.

[9]Java scanner class help[EB/OL].(2011)[2016-07-18].http://stackoverflow.com/questions/3947761/java-scanner-class-help.

[10]Why does scanner read every other line of CSV file?Java[EB/OL].[2016-07-18].http://stackoverflow.com/questions/36564422/why-does-scanner-read-every-other-line-of-csvfile-java.

[11]Nguyen T T,Nguyen H A,Pham N H,et al.Graph-based mining of multiple object usage patterns[C]//Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering,Amsterdam,Aug 24-28,2009.New York:ACM,2009:383-392.

[12]Lengauer T,Tarjan R E.A fast algorithm for finding dominators in a flowgraph[J].ACM Transactions on Programming Languages and Systems,1979,1(1):121-141.

[13]Cytron R,Ferrante J,Rosen B K,et al.Efficiently computing static single assignment form and the control dependence graph[J].ACM Transactions on Programming Languages and Systems,1991,13(4):451-490.

[14]Inokuchi A,Washio T,Motoda H.An Apriori-based algorithm for mining frequent substructures from graph data[C]//LNCS 1910:Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery,Lyon,France,Sep 13-16,2000.Berlin,Heidelberg:Springer,2000:13-23.

[15]Yan Xifeng,Han Jiawei.gSpan:graph-based substructure pattern mining[C]//Proceedings of the 2002 IEEE International Conference on Data Mining,Maebashi City,Japan,Dec 9-12,2002.Washington:IEEE Computer Society,2002:721-724.

[16]J?rvelin K,Kek?l?inen J.Cumulated gain-based evaluation of IR techniques[J].ACM Transactions on Information Systems,2002,20(4):422-446.

附中文參考文獻(xiàn):

[1]王曉玲,文繼榮,欒金鋒,等.一種通過(guò)內(nèi)容和結(jié)構(gòu)查詢(xún)文檔數(shù)據(jù)庫(kù)的方法[J].軟件學(xué)報(bào),2003,14(5):976-983.

[3]黃震華,張佳雯,田春岐,等.基于排序?qū)W習(xí)的推薦算法研究綜述[J].軟件學(xué)報(bào),2016,27(3):691-713.

Refine Software Q&ADocument Search Results Based on Code Pattern*

HUAChenyan1,2,3,ZOU Yanzhen1,2,3+,ZHU Zixiao1,2,3,XIE Bing1,2,3
1.School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China
2.Key Laboratory of High Confidence Software Technologies,Ministry of Education,Beijing 100871,China
3.Peking University Information Technology Institute(Tianjin Binhai),Tianjin 300450,China

A

TP301

+Corresponding author:E-mail:zouyz@pku.edu.cn

HUA Chenyan,ZOU Yanzhen,ZHU Zixiao,et al.Refine software Q&A document search results based on code pattern.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1591-1598.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1591-08

10.3778/j.issn.1673-9418.1609028

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Key Research and Development Program of China under Grant No.2016YFB1000804(國(guó)家重點(diǎn)研發(fā)計(jì)劃);the National Science Fund for Distinguished Young Scholars of China under Grant No.61525201(國(guó)家杰出青年科學(xué)基金).

Received 2016-08,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-31,http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1652.024.html

HUA Chenyan was born in 1994.He is an M.S.candidate at Peking University.His research interest is software engineering.

華晨彥（1994—），男，上海人，北京大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)檐浖こ獭?/p>

ZOU Yanzhen was born in 1976.She received the Ph.D.degree in software and software theory from Peking University in 2010.Now she is an associate professor at Peking University,and the member of CCF.Her research interests include software engineering,software reuse and information retrieval,etc.

鄒艷珍（1976—），女，遼寧蓋州人，2010年于北京大學(xué)軟件與理論專(zhuān)業(yè)獲得博士學(xué)位，現(xiàn)為北京大學(xué)信息科學(xué)技術(shù)學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)檐浖こ?，軟件?fù)用，信息檢索等。

ZHU Zixiao was born in 1990.He is a Ph.D.candidate at Peking University.His research interests include software engineering,software comprehension and reuse,etc.

朱子驍（1990—），男，湖南郴州人，北京大學(xué)博士研究生，主要研究領(lǐng)域?yàn)檐浖こ?，軟件資源理解與復(fù)用等。

XIE Bing was born in 1970.He received the Ph.D.degree from School of Computer,National University of Defense Technology in 1998.Now he is a professor and Ph.D.supervisor at Peking University,and the senior member of CCF.His research interests include software engineering and formal methods,etc.

謝冰（1970—），男，湖南湘潭人，1998年于國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院獲得博士學(xué)位，現(xiàn)為北京大學(xué)信息科學(xué)技術(shù)學(xué)院軟件所教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)檐浖こ?，形式化方法等。發(fā)表學(xué)術(shù)論文40余篇，主持國(guó)家863重點(diǎn)項(xiàng)目多項(xiàng)，獲國(guó)家科技進(jìn)步二等獎(jiǎng)。