基于程序向量樹和聚類的學(xué)生程序算法識別方法

魏 敏，張麗萍，閆 盛

(內(nèi)蒙古師范大學(xué) 計算機科學(xué)技術(shù)學(xué)院，內(nèi)蒙古 呼和浩特 010022)

0 引 言

程序理解是對程序分析、抽象、推理從而獲取程序特征和知識的過程，它在軟件開發(fā)、復(fù)用和維護(hù)中占據(jù)重要作用[1]。程序算法識別是開發(fā)人員理解程序的重要步驟之一，是指針對程序代碼識別出其所蘊含的程序算法[2]，例如給定一個程序代碼，通過算法識別可以推斷出該程序使用了冒泡排序算法。然而，實現(xiàn)相同算法的不同程序語法表示形式可能不同[3]，這使得人工分析無法滿足復(fù)雜的程序算法識別需求。

本文以函數(shù)粒度作為基本單元，結(jié)合程序詞法和語法結(jié)構(gòu)特征，提出一種基于程序向量樹和聚類的學(xué)生程序算法識別方法AR-PVTK(algorithm recognition based on program vector tree and k-means)。基本思路是：首先解析學(xué)生程序生成單詞序列和抽象語法樹，獲取程序詞法和語法結(jié)構(gòu)信息；其次針對單詞序列訓(xùn)練word2vec模型得到程序單詞的實數(shù)向量，結(jié)合抽象語法樹構(gòu)造程序向量樹(program vector tree，PVT)，融合程序特征，并進(jìn)一步優(yōu)化樹結(jié)構(gòu)；最后利用改進(jìn)的遞歸自動編碼器(improved recursive auto encoder，IRAE)模型獲取程序表示并執(zhí)行聚類，將使用相同算法的程序映射到向量空間中相近的位置，從而完成算法識別。該方法可以自動化識別程序算法，不僅能提高識別準(zhǔn)確度，更能節(jié)省人工識別成本。

1 相關(guān)工作

在20世紀(jì)80年代，程序算法識別研究興起，目的是通過分析程序來評估一段代碼中所包含的算法行為和功能，在程序優(yōu)化、程序理解等方面具有重要意義。

早期時候，程序算法識別工作采用傳統(tǒng)基于知識表示的方法。該類方法需要選擇合理的表達(dá)方式對算法本質(zhì)特征進(jìn)行描述，然后基于算法表示建立模板庫通過模式匹配完成算法識別，但是此方法在建立和維護(hù)模板庫時費時費力。后來，基于信息檢索技術(shù)的識別方法出現(xiàn)，主要利用非代碼的文本信息，如程序代碼中包含的函數(shù)名、注釋以及對應(yīng)的設(shè)計文檔，輔助完成程序算法識別工作。該類方法不僅依賴注釋、相關(guān)代碼文檔的支持，還對程序書寫格式具有嚴(yán)格要求，因此識別準(zhǔn)確度較低。

近年來，機器學(xué)習(xí)技術(shù)為PLP帶來新途徑，能夠在更深層次挖掘源代碼數(shù)據(jù)特征并獲取程序的抽象表示[4,5]，因此這一階段主要以程序特征分類的方法[6,7]進(jìn)行程序識別。王甜甜等[8]提出了一種基于結(jié)構(gòu)化度量向量的聚類方法，以從大量現(xiàn)有程序中快速識別結(jié)構(gòu)相似的程序，為缺陷程序提供修復(fù)建議。Zhang等[9]提出了一種基于過程挖掘的源代碼相似度檢測方法，該方法充分考慮源代碼運行時的動態(tài)特征，通過收集程序運行的日志，使用過程挖掘來獲得這兩段源代碼的流程圖，通過計算這兩個流程圖的相似度來衡量兩段源代碼的相似度。譚丁武等[10]重點關(guān)注源代碼的數(shù)據(jù)流、控制流信息，并結(jié)合語法結(jié)構(gòu)信息構(gòu)造代碼圖，利用門控神經(jīng)網(wǎng)絡(luò)(gated graph attention neural network，GGANN)學(xué)習(xí)程序的分布式表示實現(xiàn)程序分類。此外，還有使用代碼相似度檢測[11]的方法，即認(rèn)為使用相同算法的程序具有高度相似性。高蕾等[12]基于代碼相似性設(shè)計一種聚類算法，該算法可以針對給定編程任務(wù)的所有正確解決方案自動生成聚類。實驗結(jié)果表明，聚類算法可以成功獲取數(shù)據(jù)集中的獨特聚類。夏之陽等[13]首先對代碼進(jìn)行程序切片、變量替換等預(yù)處理，然后利用Bi-LSTM網(wǎng)絡(luò)(bi-directional long short-term memory)對代碼提取特征表示，計算漏洞模板和待測代碼相似度判斷漏洞。該類方法可以提取代碼語義信息，能夠檢測更高級別的代碼克隆，但同樣具有構(gòu)建PDG和比較子圖同構(gòu)時代價較大的問題。史志成等[14]提出一種基于卷積和雙向循環(huán)神經(jīng)網(wǎng)絡(luò)的代碼特征提取模型CVRNN，通過卷積神經(jīng)網(wǎng)絡(luò)提取代碼的語法結(jié)構(gòu)特征信息，通過雙向循環(huán)神經(jīng)網(wǎng)絡(luò)提取代碼的序列信息。該方法無需人工參與就可以很好地學(xué)習(xí)程序表示，應(yīng)用在代碼分類任務(wù)中，優(yōu)于較多已有的用于代碼特征提取的深度學(xué)習(xí)模型。本團隊在代碼克隆方面也展開過大量研究。王亞芳等[15]提出基于圖像相似度的代碼克隆檢測方法，將處理好的源代碼轉(zhuǎn)化為圖像，利用Jaccard 距離和感知哈希算法進(jìn)行相似性識別，可以在6款開源軟件上取得較好檢測效果。

對比以上研究，基于程序特征分類的方法主要關(guān)注程序的自身特性，能夠?qū)θ我獬绦蛩惴ㄌ崛√卣鬟M(jìn)行分析，也不依賴代碼相關(guān)數(shù)據(jù)，使用深度學(xué)習(xí)模型提取代碼特征還能緩解人工壓力，提高識別準(zhǔn)確率，因此具有良好的擴展性。

2 基于程序向量樹和聚類的學(xué)生程序算法識別方法

本節(jié)主要介紹提出的基于程序向量樹和聚類的學(xué)生程序算法識別方法，如圖1所示，主要包括以下4個步驟。

(1)特征提取。從在線編程實踐平臺上針對不同類別的編程問題，收集與其相對應(yīng)的正確的學(xué)生程序代碼，構(gòu)成學(xué)生程序集，然后將每個學(xué)生程序處理成單詞序列和抽象語法樹，以獲取程序的詞法和語法結(jié)構(gòu)特征；

(2)程序向量樹構(gòu)造。針對所有程序的單詞序列利用統(tǒng)計語言模型(statistical language model，SLM)學(xué)習(xí)單詞的分布式嵌入表示得到單詞向量，然后在抽象語法樹的基礎(chǔ)上，賦予葉子節(jié)點對應(yīng)單詞的向量表示，完成程序向量樹的構(gòu)造，再進(jìn)一步去除無用節(jié)點，優(yōu)化樹結(jié)構(gòu)；

(3)向量編碼與聚類。結(jié)合程序向量樹采用改進(jìn)的遞歸自動編碼器模型，由下至上逐層將非葉子節(jié)點編碼成定長向量，以根節(jié)點的向量表示作為程序向量表示，再對程序向量執(zhí)行k-means聚類，將使用相同算法的程序按照特征表示相近程度劃分到同一類別；

(4)獲取算法識別結(jié)果。通過以上步驟，相同編程問題的學(xué)生程序根據(jù)使用的算法不同被分別歸類，至此完成程序算法識別工作。

2.1 程序特征提取

程序可以看作是單詞和符號組成的文本序列，可以對程序單詞進(jìn)一步表示學(xué)習(xí)挖掘單詞間的語義相似關(guān)系。本文首先將學(xué)生程序處理成單詞序列，為了進(jìn)一步降低數(shù)據(jù)稀疏性，對數(shù)值型和字符型常量分別抽象為同一記號，具體替換說明見表1。

此外，程序語言相比于自然語言還具有嚴(yán)格的強結(jié)構(gòu)性、長依賴性和可執(zhí)行性等特殊屬性。AST[16]是對程序語義和語法分析后得到的一種樹形表現(xiàn)形式，記錄了程序的語法規(guī)則和執(zhí)行順序，在程序理解相關(guān)研究中起著重要的作用。AST包含了葉子節(jié)點和非葉子節(jié)點兩種節(jié)點類型以及各節(jié)點之間的父子關(guān)系，其中葉子節(jié)點代表標(biāo)識符，非葉子節(jié)點代表語法結(jié)構(gòu)體，非葉子以及葉子節(jié)點共同描述了程序執(zhí)行的數(shù)據(jù)流和控制流信息。本文使用Eclipse提供的軟件開發(fā)工具包JDK(Java development kit)創(chuàng)建所有Java程序代碼的抽象語法樹，提取程序的語法結(jié)構(gòu)和語義特征，用于后續(xù)向量編碼工作。

2.2 程序向量樹構(gòu)造

程序向量樹(PVT)是基于程序抽象語法樹改造后的一種變體，由AST中各葉子節(jié)點被賦予對應(yīng)的單詞向量表示而得來，它可以為后續(xù)合成程序向量提供支持。PVT完整地保留了程序代碼的語法結(jié)構(gòu)信息，同時去除了個別無用節(jié)點，加入了具有語義信息的單詞表示，可以有效規(guī)避語法形式的多樣化。本文要解決的程序算法識別問題關(guān)鍵在于識別具有等價的語法結(jié)構(gòu)形式的程序，因此針對程序代碼的表示也使用程序向量樹的方法，具體步驟如圖2所示，包括詞向量訓(xùn)練和程序向量樹生成。

2.2.1 詞向量訓(xùn)練

針對程序代碼而言，詞嵌入(word embedding)是一種將程序文本中的單詞轉(zhuǎn)換成數(shù)字向量的方法。與one-hot編碼的表征方式相比，分布式表示能夠較好地涵蓋程序單詞的語義信息，也不會產(chǎn)生高維度編碼稀疏的問題，具有相似上下文的兩個單詞使用分布式表示可以被映射到向量空間中相近的位置。例如“for”和“while”，它們在單詞使用上雖然有所不同但表達(dá)意思類似，因此在向量空間的位置也相近。

本文利用獲取到的程序單詞序列，使用最經(jīng)典的word2vec詞嵌入模型，在語料庫上訓(xùn)練得到程序單詞連續(xù)、稠密的向量表示。該模型由Mikolov等[17]提出，主要包括跳字模型(skip-gram)和連續(xù)詞袋模型(continuous bag of words，CBOW)。本文選擇skip-gram模型，該模型由輸入、映射和輸出3層網(wǎng)絡(luò)模型構(gòu)成，如圖3所示，它利用中心詞來推斷上下文中一定窗口內(nèi)其它單詞出現(xiàn)的條件概率，并與已經(jīng)存在的單詞進(jìn)行比對，最小化損失函數(shù)值來達(dá)到參數(shù)的優(yōu)化，實現(xiàn)較好的訓(xùn)練效果。

最終，得到3370個長度不等的單詞序列，詞匯表中共有796個獨特的單詞，每個單詞被表示為296維度的實數(shù)向量。

2.2.2 程序向量樹生成

完成AST的提取，賦予AST葉子節(jié)點對應(yīng)單詞的向量表示就可以得到PVT。圖4(a)、圖4(b)和圖4(c)分別是一個Java方法示例和其對應(yīng)的抽象語法樹以及PVT。

但是，通過分析AST發(fā)現(xiàn)，一些節(jié)點并不含有程序語義信息，它們對判斷程序相似性的作用較小，因此應(yīng)該被去除，來進(jìn)一步減小樹規(guī)模、統(tǒng)一樹結(jié)構(gòu)。完滿二叉樹是所有非葉子節(jié)點的度均是2的特殊二叉樹，抽象語法樹是多叉樹結(jié)構(gòu)，如果將無用節(jié)點去掉，將AST轉(zhuǎn)化為完滿二叉樹，則能解決上述問題。本文將使用DLC[18]中提出的25種和曾杰等[19]補充的7種完滿二叉樹生成規(guī)則對AST進(jìn)行轉(zhuǎn)換，可以涵蓋ArrayType、EnumDeclaration、AnnotationTypeDeclaration等32種節(jié)點類型的處理，處理后的抽象語法樹具有相同的樹結(jié)構(gòu)，即非葉子節(jié)點都有0或者2棵子樹。轉(zhuǎn)化方法根據(jù)非葉子節(jié)點的度數(shù)分為3種。

(1)等于1：判斷該節(jié)點與其孩子節(jié)點類型的重要性，將二者合并保留重要的節(jié)點類型。

(2)等于2：不作處理。

(3)大于2：按照設(shè)計的規(guī)則提取相關(guān)葉子節(jié)點，去除無用節(jié)點，添加人工定義的非葉子節(jié)點構(gòu)建二叉樹，對于再次出現(xiàn)的葉子節(jié)點數(shù)目是1的非葉子節(jié)點，繼續(xù)執(zhí)行(1)。

上述過程將AST轉(zhuǎn)換為完滿二叉樹，相應(yīng)的PVT也是完滿二叉樹的結(jié)構(gòu)，這一結(jié)構(gòu)保證每個非葉子節(jié)點都有相同的子樹數(shù)量，為生成非葉子節(jié)點向量提供方便。

2.3 向量編碼與聚類

本節(jié)在程序向量樹的基礎(chǔ)上，結(jié)合加權(quán)編碼機制，利用遞歸自動編碼器模型得到固定長度的向量表示，然后針對程序向量進(jìn)行聚類分析，將使用相同程序算法的學(xué)生程序劃分為同一類，完成學(xué)生程序算法識別任務(wù)，具體流程如圖5所示。

2.3.1 向量編碼

(1)

在非葉子節(jié)點向量編碼過程中用到的加權(quán)編碼機制，基本思路是：對于每一個非葉子節(jié)點，擁有的左右子樹哪棵子樹包含的葉子節(jié)點數(shù)目越多，它所承載的程序信息就越豐富，理所應(yīng)當(dāng)被賦予更高的權(quán)重系數(shù)。因此，對于任意一個非葉子節(jié)點，根據(jù)以上描述，定義一致的加權(quán)編碼策略：非葉子節(jié)點以及它兩個孩子節(jié)點的向量表示分別為qvector、vector1和vector2，通過遍歷AST得到對應(yīng)子樹的葉子節(jié)點數(shù)量是n1和n2(當(dāng)子樹中只包含一個葉子節(jié)點則設(shè)置為1)，那么能夠得到qvector的向量表示為式(2)

(2)

2.3.2 k均值聚類

向量聚類將使用相同算法的程序按照特征表示相近程度劃分到同一類別。本文采用基于距離的k均值聚類算法(k-means clustering algorithm)實現(xiàn)上述操作，該算法具有計算速度快、魯棒性強等優(yōu)點?；舅枷胧牵涸诮o定k值和k個初始類簇中心點的情況下，通過迭代不斷調(diào)整聚類中心或者達(dá)到設(shè)定的迭代次數(shù)，最終將數(shù)據(jù)集中的個體劃分為k類，每個類稱作一個“簇(cluster)”，同一簇中的個體更相互接近或相關(guān)，不同簇中的個體更遠(yuǎn)離或不同。以下是該算法的詳細(xì)描述。

假設(shè)給定包含了n個數(shù)據(jù)樣本的數(shù)據(jù)集X，X的每個樣本點xi擁有d個維度的屬性。k-means算法的目標(biāo)是將n個樣本依據(jù)樣本間的相似性劃分為k類組成集合，每個樣本屬于且僅屬于離它自身距離最小的類簇，其中樣本點xi到類簇ck的中心點pk的歐氏距離采用式(3)進(jìn)行計算

(3)

k-means聚類的反復(fù)迭代過程描述為以下步驟。

(1)設(shè)定初始中心點的個數(shù)k，選取數(shù)據(jù)空間中的k個樣本點作為初始聚類中心。

(2)將每個樣本點根據(jù)它們與k個聚類中心的歐氏距離，將其劃分到最近的聚類中心(最相似)所對應(yīng)的類。

(3)更新聚類中心：將每個類別中所有樣本點對應(yīng)的均值作為該類別新的聚類中心，計算目標(biāo)函數(shù)的值。

(4)判斷聚類中心和目標(biāo)函數(shù)的值是否發(fā)生改變，若不變，則輸出結(jié)果，若改變，否則返回(2)。

本文將2.3.1節(jié)得到的程序向量表示輸出到后綴名為.csv文件，文件每一行代表一條數(shù)據(jù)，即一個Java程序所對應(yīng)的向量表示，共計3370條數(shù)據(jù)。

3 實驗分析

3.1 數(shù)據(jù)集與評價指標(biāo)

3.1.1 數(shù)據(jù)集

為了準(zhǔn)確而客觀地評價本文方法，從在線編程實踐平臺篩選10類編程問題，每類收集200～500個學(xué)生程序，共計3370個正確程序，包含排序、遞歸、查找、哈希表和動態(tài)規(guī)劃等算法知識。為了使實驗數(shù)據(jù)集真實且有效，選擇依據(jù)是：①按照學(xué)生作答人數(shù)選擇數(shù)量較多的編程問題，這在一定程度上說明該類題型具有代表性，也保證了數(shù)據(jù)的真實性與多樣性。②為保證每類編程任務(wù)收集的程序功能是相同的，選取通過OJ(online judge)平臺測試的程序代碼，即能夠解決問題的正確程序。針對每類問題，以函數(shù)粒度作為研究對象進(jìn)行實驗，每類編程任務(wù)的問題名稱、程序數(shù)量、總代碼行數(shù)和功能描述等具體信息見表2。

表2 實驗數(shù)據(jù)

3.1.2 評價指標(biāo)

本文使用的實驗數(shù)據(jù)采用人工的方法標(biāo)記其所屬類別，通過調(diào)整蘭德系數(shù)(adjusted rand index，ARI)、調(diào)整互信息(adjusted mutual information，AMI)和Fowlkes-Mallows指數(shù)這3個指標(biāo)來衡量程序算法識別的結(jié)果。

調(diào)整蘭德系數(shù)ARI常被用來描述一個集合中的元素真實分類與預(yù)測分類的吻合程度，ARI的取值區(qū)間為[-1,1]，即ARI值越大，說明方法具有更強的區(qū)分能力，聚類效果越好，ARI的詳細(xì)定義及計算公式請參見文獻(xiàn)[20]。

互信息MI用來計算兩個集合之間的相關(guān)性，調(diào)整互信息AMI用來衡量兩個數(shù)據(jù)分布的吻合程度，AMI的取值范圍是[-1,1]，AMI值的大小與聚類的準(zhǔn)確性呈正相關(guān)，二者詳細(xì)定義及計算公式請參見文獻(xiàn)[21]。

FMI指數(shù)(fowlkes mallows index，F(xiàn)MI)是針對訓(xùn)練集和驗證集數(shù)據(jù)之間求得的查全率和查準(zhǔn)率的幾何平均值，即式(4)。該指標(biāo)同樣也是數(shù)值越大，聚類的結(jié)果越準(zhǔn)確

(4)

3.2 實驗結(jié)果及分分析

3.2.1 4種程序向量生成方法聚類效果對比實驗

由于業(yè)界缺少類似的方法，所以針對本文提出的基于程序向量樹和聚類的學(xué)生程序算法識別方法AR-PVTK進(jìn)行組內(nèi)評估驗證。本文將從調(diào)整蘭德系數(shù)(ARI)、調(diào)整互信息(AMI)和FMI這3個指標(biāo)進(jìn)行驗證，以檢驗AR-PVTK方法的有效性。

為驗證本文提出的AR-PVTK方法在獲取程序向量表示時的有效性，我們分別對比了未使用加權(quán)和使用不同權(quán)重計算方法后的聚類效果(即方法1～方法4)。通過實驗得到各方法的分類性能對比見表3～表6。

方法1：利用所有節(jié)點向量的平均值作為程序向量表示。

方法2：利用TF-IDF[22]計算非葉子節(jié)點類型的詞頻，作為對應(yīng)節(jié)點的權(quán)重系數(shù)，從而生成程序向量。

方法3：TF-IDF基礎(chǔ)上加入非葉子節(jié)點的位置信息并進(jìn)行歸一化處理，從而生成程序向量。

方法4：利用子樹的葉子節(jié)點數(shù)目的權(quán)重計算規(guī)則而生成的程序向量，即本文的AR-PVTK方法。

表3 基于均值節(jié)點向量方法的分類性能/%

表4 基于TF-IDF加權(quán)方法的分類性能/%

表5 TF-IDF加入節(jié)點位置信息方法的分類性能/%

表6 本文AR-PVTK方法的分類性能/%

表3～表6分別記錄了10類編程問題使用方法1、方法2、方法3和方法4后，在ARI、AMI和FMI指標(biāo)上的得分情況。從實驗結(jié)果可以看出，本文方法AR-PVTK的分類性能優(yōu)于均值節(jié)點向量方法和另外兩種TF-IDF方法，表明利用子樹的葉子節(jié)點數(shù)目的權(quán)重計算規(guī)則生成的程序向量可以更準(zhǔn)確地獲取到程序信息，因此可以得到較好的分類結(jié)果。

表7顯示了數(shù)據(jù)集在使用了4種方法后，在ARI、AMI和FMI指標(biāo)上的平均得分情況。從實驗結(jié)果可以看出，方法2、方法3以及AR-PVTK方法分類性能均優(yōu)于方法1，說明加入權(quán)重后，所有程序聚類的準(zhǔn)確率均有提高，驗證了樹節(jié)點類型與所在位置的不同，它所涵蓋的程序信息不同，貢獻(xiàn)的信息量也存在一定差異。因此，針對一些重要節(jié)點需要通過加入權(quán)重值來適當(dāng)調(diào)整特征向量來提高聚類的性能。此外，由表7還可以看出，本文方法AR-PVTK在ARI、AMI和FMI值較基于均值節(jié)點向量的方法提升幅度較大，較基于TF-IDF加權(quán)的方法分別提升22.24%、17.65%和13.52%，較TF-IDF加入節(jié)點位置信息的方法分別提升18.5%、17.1%和11.89%。通過比較4種方法分類性能評價的平均值可以看出，本文方法在ARI、AMI和FMI指標(biāo)上均獲得了最佳的效果，驗證了本文方法在程序表示方面的有效性。

表7 4種不同方法的分類性能/%

3.2.2 聚類實驗結(jié)果

圖7給出了使用本文方法在不同編程任務(wù)上執(zhí)行程序算法分類后的實驗結(jié)果。以“最大子序和”編程問題為例，即Lab1，對其聚類結(jié)果進(jìn)行詳細(xì)分析。如聚類結(jié)果所示，該問題每個簇中分別有72、64、128個解決方案，通過人工對這些程序代碼的分析，發(fā)現(xiàn)C1、C2和C3中解決方案的邏輯結(jié)構(gòu)基本一致。首先初始化結(jié)果值，然后利用循環(huán)不斷比較、更新子序列值，最后打印最大子序和。C1和C2中的解決方案主要使用“動態(tài)規(guī)劃算法”進(jìn)行問題求解，前者通過判斷當(dāng)前最大連續(xù)子序列和對結(jié)果是否存在增益影響進(jìn)行子序列更新，后者通過尋找規(guī)律總結(jié)狀態(tài)方程進(jìn)行求解，C3中的解決方案則是使用“暴力法”利用雙層循環(huán)累加選出最優(yōu)解。

以上實驗結(jié)果可以看出，本文方法能夠針對相同編程問題的眾多學(xué)生程序，通過程序詞法和語法結(jié)構(gòu)特征自動化識別出解決該問題的不同程序算法，繼而進(jìn)一步為學(xué)生和教師提供問題求解方案。

3.2.3 算法推薦實驗及結(jié)果

本節(jié)將算法識別結(jié)果應(yīng)用在程序算法推薦任務(wù)當(dāng)中，向?qū)W生提供編程問題的多個解決方案，并對方法的有效性進(jìn)行人工評估。

(1)程序算法推薦

本文使用Lucene全文檢索技術(shù)，通過關(guān)鍵詞匹配完成推薦。實現(xiàn)過程包括3部分：編程問題描述預(yù)處理，創(chuàng)建索引，以及基于關(guān)鍵詞搜索。

首先，編程問題描述預(yù)處理。對于編程問題描述執(zhí)行文本標(biāo)準(zhǔn)化和去除停用詞等操作。主要包括去除文本中的標(biāo)點符號，使用Lucene檢索包中封裝好的分詞模塊進(jìn)行分詞，以及刪除停用詞，如 “的”、“地”等詞。其次，創(chuàng)建索引。以某一類編程問題作為一個搜索單位，并創(chuàng)建對應(yīng)文檔(Document)，Document主要包含兩個域(Field)，分別是問題名稱和描述。最后，基于關(guān)鍵詞搜索。利用算法識別結(jié)果構(gòu)建程序算法庫，建立編程問題描述和多個解決方法的一對多關(guān)聯(lián)關(guān)系。針對用戶輸入的自然語言形式的問題查詢語句同樣執(zhí)行文本處理操作，然后通過關(guān)鍵詞搜索的方法匹配到解決該類問題的程序算法。

(2)推薦結(jié)果

針對程序算法推薦方法的有效性，采用人工小組進(jìn)行評估。協(xié)助本次實驗的參與者是8名具備3年程序設(shè)計課程經(jīng)驗的助教以及15名在校學(xué)生，針對以上10類編程問題，參與者在閱讀并比較每一類問題的算法推薦結(jié)果后完成評估問題。針對助教人員的問題如下，評估結(jié)果采用Likert scale五級量表，1(非常不同意)至5(非常同意)，以下記為A～ E，對應(yīng)分值為1、0.5、0、-0.5和-1。

Q1：程序算法推薦方法是否有助于提高學(xué)生的算法應(yīng)用能力和問題求解能力。

Q2：程序算法推薦方法是否可以輔助教師進(jìn)行編程教學(xué)。

統(tǒng)計結(jié)果見表8，在Q1問題上，由P1=0.35>0可知，大約87.5%的參與者認(rèn)為算法推薦方法有效。在Q2問題上，由P2=0.3>0可知，大約75%的參與者認(rèn)為算法推薦方法可以促進(jìn)編程教學(xué)，換言之，學(xué)生在不同類簇中的解決方案基本上可以代表編程問題的典型解決方案，并且可以在教學(xué)內(nèi)容上為教師提供輔助性的教學(xué)資源。

表8 統(tǒng)計結(jié)果1

針對在校學(xué)生也調(diào)查了對算法推薦結(jié)果的反饋，這些學(xué)生都曾經(jīng)完成過這10類問題。給學(xué)生的問題如下：

Q3：程序算法推薦方法是否有助于改善程序編寫、提高算法思維。

Q4：通過編程問題的算法反饋結(jié)果是否可以得到其它求解方法的啟發(fā)。

統(tǒng)計結(jié)果見表9，在Q3問題上，由P3=0.5>0可知，66.7%的學(xué)生認(rèn)為算法推薦結(jié)果。在Q4問題上，由P4=0.7>0可知，80%的學(xué)生表示在閱讀了問題的其它解決方案后可以獲得新的靈感，20%的學(xué)生認(rèn)為大多數(shù)解決方案除了處理輸入數(shù)據(jù)的方式不同外，在解決問題的方法上沒有明顯的區(qū)別，受到啟發(fā)的效果不強烈。

表9 統(tǒng)計結(jié)果2

從問卷調(diào)查的結(jié)果中可以看出，大部分的參與者對程序算法推薦方法持肯定態(tài)度，認(rèn)為通過程序算法推薦的手段為學(xué)生提供“一題多解”的算法實現(xiàn)，能夠培養(yǎng)學(xué)生的算法思維與問題求解能力，并為算法教學(xué)提供指導(dǎo)作用。

4 結(jié)束語

本文提出了一種基于程序向量樹和k-means聚類的學(xué)生程序算法識別方法。利用程序向量樹融合程序單詞的詞法信息和程序的語法結(jié)構(gòu)信息，提高了對學(xué)生程序算法識別的準(zhǔn)確率。本文方法應(yīng)用在程序算法推薦任務(wù)中，可以很好地為教師和學(xué)生提供多樣化的編程問題解決方案。

程序算法識別實現(xiàn)了程序算法的自動化理解，在教育教學(xué)和程序優(yōu)化等方面具有廣闊的應(yīng)用前景。將程序算法識別應(yīng)用于編程學(xué)習(xí)領(lǐng)域，一方面可以協(xié)助教師對學(xué)生群體學(xué)習(xí)情況的監(jiān)測，了解學(xué)生對編程方法的掌握情況，為科學(xué)施教提供良好的決策，另一方面從學(xué)生程序數(shù)據(jù)出發(fā)，挖掘算法知識和求解方法更符合學(xué)生的認(rèn)知規(guī)律，能夠給予學(xué)生編程啟發(fā)。將程序算法識別應(yīng)用于程序優(yōu)化問題，可以為開發(fā)者尋找在語義上保持一致的程序優(yōu)化方案，將性能較差的程序替換性能較好的程序，提升程序執(zhí)行效率。

本文方法仍然存在諸多不足。其一識別的程序語言種類單一，主要針對Java編程語言的學(xué)生程序，優(yōu)化樹結(jié)構(gòu)的規(guī)則也只對Java程序有效，不能遷移到其它語言程序的識別任務(wù)中。其二，本文方法主要針對使用單個方法實現(xiàn)的編程問題，以函數(shù)為粒度提取程序特征，無法應(yīng)用于多個方法組合調(diào)用的編程問題。在未來，可以進(jìn)一步豐富識別的程序語言種類，同時對于調(diào)用多個方法的編程問題提取關(guān)鍵代碼語句形成組合程序用以提取重要特征。