摘  要： 為了提高代碼文件提取的效率，提出了基于特征詞的關(guān)鍵詞自動(dòng)提取算法（算法一）和基于調(diào)用圖的自動(dòng)提取算法（算法二）用于關(guān)鍵詞的提取，進(jìn)而實(shí)現(xiàn)代碼文件的自動(dòng)提取。將兩種算法應(yīng)用于CLAPACK庫(kù)源文件的精簡(jiǎn)自動(dòng)提取，測(cè)試結(jié)果表明，兩種算法的正確提取率分別是92%和44%，它們能實(shí)現(xiàn)代碼文件的自動(dòng)提取，提高了提取的效率。

　　關(guān)鍵詞： 自動(dòng)提??；關(guān)鍵詞；特征詞；調(diào)用關(guān)系圖；CLAPACK庫(kù)

0 引言

　　近年來(lái)，隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)上的代碼文件越來(lái)越多，尤其是開源軟件的源文件，這些源代碼有利于加深對(duì)軟件的理解，但是由于代碼文件眾多、函數(shù)之間的調(diào)用關(guān)系復(fù)雜等因素，使得程序理解變得異常繁瑣。將實(shí)現(xiàn)特定功能的相關(guān)源文件提取出來(lái)，能夠提高代碼文件理解的效率，同時(shí)也有利于軟件子功能的分離，而代碼文件的自動(dòng)提取一般是根據(jù)關(guān)鍵詞實(shí)現(xiàn)的。

　　關(guān)鍵詞自動(dòng)提取的方法總體上可以分為3類：（1）基于統(tǒng)計(jì)的方法是利用詞的統(tǒng)計(jì)信息（如詞頻）判斷詞的重要程度，它的優(yōu)點(diǎn)是便于理解，可以很容易實(shí)現(xiàn)和推廣，如Li Juanzi等人[1]使用經(jīng)典的TFIDF算法進(jìn)行關(guān)鍵詞的提取，黃磊等人[2]增加了類內(nèi)離散程度這一特征來(lái)改進(jìn)TFIDF算法；（2）基于語(yǔ)義分析的方法則是根據(jù)文本的語(yǔ)義結(jié)構(gòu)進(jìn)行自動(dòng)提取，最具代表性的是索紅光[3]提出的基于詞匯鏈的關(guān)鍵詞提取算法，但是該方法的計(jì)算復(fù)雜性高，實(shí)用性差；（3）基于機(jī)器學(xué)習(xí)的方法則是通過(guò)一定的訓(xùn)練樣本來(lái)獲得自動(dòng)提取模型，進(jìn)行關(guān)鍵詞的自動(dòng)提取，例如TURNEY P[4]將遺傳算法與C4.5決策樹機(jī)器學(xué)習(xí)方法相結(jié)合設(shè)計(jì)出系統(tǒng)GenEx，用于關(guān)鍵詞提取。

　　這些方法只是針對(duì)一份文檔中關(guān)鍵詞的提取有效，但是對(duì)于像CLAPACK庫(kù)、OpenCV庫(kù)等代碼文件關(guān)鍵詞的提取則不適用。本文分別提出了基于特征詞[5]的關(guān)鍵詞自動(dòng)提取算法和基于調(diào)用圖的自動(dòng)提取算法提取關(guān)鍵詞進(jìn)而實(shí)現(xiàn)代碼文件的自動(dòng)提取。以CLAPACK庫(kù)文件的精簡(jiǎn)自動(dòng)提取為例測(cè)試這兩種算法，結(jié)果表明，這兩種算法均可以實(shí)現(xiàn)代碼文件的自動(dòng)提取。

1 兩種自動(dòng)提取算法

　　1.1 基于特征詞的關(guān)鍵詞自動(dòng)提取算法

　　先遍歷代碼文件找到特征詞，再根據(jù)一定的規(guī)則提取關(guān)鍵詞，進(jìn)而實(shí)現(xiàn)代碼文件的自動(dòng)提取。其算法如下：

　　（1）根據(jù)手動(dòng)提取的經(jīng)驗(yàn)找到特征詞集合；

　　（2）打開文檔集合中的一個(gè)起始文件；

　?。?）逐一遍歷文件中的詞語(yǔ)，將這些詞語(yǔ)與特征詞集合逐一進(jìn)行匹配，若匹配成功則根據(jù)一定的規(guī)則移動(dòng)位置指針找出關(guān)鍵詞，否則跳過(guò)，進(jìn)行下一個(gè)詞語(yǔ)的匹配判斷；

　?。?）根據(jù)關(guān)鍵詞與文件名之間的映射關(guān)系找出該關(guān)鍵詞對(duì)應(yīng)的文件名；

　　（5）遍歷整個(gè)文檔集合找出該文件并將其復(fù)制到一個(gè)指定的文件夾下，打開該文件轉(zhuǎn)到步驟（3）；

　?。?）查看自動(dòng)提取的文件是否滿足需求，若不滿足，則修改特征詞集合或修改位置指針的移動(dòng)規(guī)則。

　　1.2 基于調(diào)用圖的自動(dòng)提取算法

　　1.2.1 LLVM簡(jiǎn)介

　　LLVM[6]（Low Level Virtual Machine）是集中研究程序整個(gè)生命周期的編譯器框架。任何語(yǔ)言（C/C++、Java等）都可以先通過(guò)LLVM編譯器的前端轉(zhuǎn)化為L(zhǎng)LVM的中間形式（Intermediate Representation，IR）[7]，再使用LLVM框架轉(zhuǎn)化為其他的形式，進(jìn)而實(shí)現(xiàn)準(zhǔn)確的指向分析、函數(shù)調(diào)用圖的生成等功能。

　　1.2.2 基于調(diào)用圖自動(dòng)提取算法

　　代碼文件中的某些關(guān)鍵詞（如函數(shù)名）可以借助一些工具進(jìn)行定位，根據(jù)定位結(jié)果，再利用計(jì)算機(jī)實(shí)現(xiàn)關(guān)鍵詞的自動(dòng)提取。基于調(diào)用圖的自動(dòng)提取算法就是利用LLVM生成的調(diào)用關(guān)系圖進(jìn)行關(guān)鍵詞的自動(dòng)提取，進(jìn)而實(shí)現(xiàn)庫(kù)文件的自動(dòng)提取，其算法如下：

　?。?）指定生成調(diào)用圖最開始分析的入口函數(shù)；

　　（2）遍歷整個(gè)編譯單元，當(dāng)遇到調(diào)用點(diǎn)轉(zhuǎn)到步驟（3）；

　?。?）如果該調(diào)用處的值為函數(shù)常量，則將該主調(diào)函數(shù)與被調(diào)函數(shù)對(duì)加入directCaller2Calle-eMap中；若該調(diào)用點(diǎn)為間接調(diào)用，通過(guò)指向分析找出該變量指向的所有可能值，將主調(diào)函數(shù)和這些值成對(duì)加入到directCaller2CalleeMap中，同時(shí)將被調(diào)用函數(shù)和調(diào)用點(diǎn)信息記錄到direct-Callee2CSMap中；

　?。?）重復(fù)上述兩步直到遍歷結(jié)束，將所有直接調(diào)用映射directCaller2CalleeMap傳遞給間接調(diào)用映射Caller2CalleeMap；

　?。?）根據(jù)上述函數(shù)調(diào)用關(guān)系，生成調(diào)用關(guān)系圖，逐一讀取生成調(diào)用圖中的文件名，遍歷代碼文件集合找出它們并將它們復(fù)制到一個(gè)指定文件夾下；

　?。?）自動(dòng)判斷提取的文件是否滿足要求，若不滿足則修改調(diào)用圖的生成算法。

2 CLAPACK庫(kù)簡(jiǎn)介及特點(diǎn)

　　2.1 CLAPACK庫(kù)簡(jiǎn)介

　　LAPACK[8]（Linear Algebra Package）是針對(duì)現(xiàn)代高性能計(jì)算機(jī)與共享存儲(chǔ)并行計(jì)算機(jī)設(shè)計(jì)的線性代數(shù)軟件包。原版的LAPACK是用Fortran寫的，為了方便C/C++程序員的使用，就有了LAPACK的C接口CLAPACK。

　　2.2 CLAPACK庫(kù)源文件特點(diǎn)

　　根據(jù)CLAPACK源文件名可以確定函數(shù)實(shí)現(xiàn)的功能以及源文件名與函數(shù)名之間的映射關(guān)系（如sgesv.c和sgesv_等）。通過(guò)函數(shù)名找出定義該函數(shù)的文件名，然后遍歷整個(gè)CLAPACK庫(kù)文件找到該文件。根據(jù)函數(shù)調(diào)用關(guān)系找出所有的函數(shù)名，進(jìn)而提取出它們對(duì)應(yīng)的C文件，遞歸循環(huán)下去，即可完成CLAPACK庫(kù)文件的精簡(jiǎn)提取。

3 兩種算法的實(shí)現(xiàn)

　　將上文中提出的兩種算法應(yīng)用于CLAPACK庫(kù)文件的自動(dòng)提取。sgesv.c[9]源文件實(shí)現(xiàn)的功能是使用LU分解法分解線性方程組，以下是以sgesv.c的自動(dòng)提取為例來(lái)解釋提出的兩種算法。

　　3.1 基于特征詞的關(guān)鍵詞自動(dòng)提取算法

　　代碼文件中特征詞就是特征字符串，該算法通過(guò)查找特征字符串，再提取出關(guān)鍵詞函數(shù)名進(jìn)而提取出源文件。SRC文件夾下是實(shí)現(xiàn)庫(kù)中各個(gè)獨(dú)立功能的起始源文件，其具體算法如下：

　　（1）讀取SRC文件夾下的一個(gè)C源文件（如sgesv.c）；

　　（2）以該文件名（sgesv.c）新建一個(gè)文件夾，并將此C文件（sgesv.c）復(fù)制到指定文件夾下并打開該源文件（sgesv.c）；

　　（3）逐個(gè)字符串進(jìn)行遍歷，若與特征字符串集合#include；extern；*）、；double；void；integer；、；Subroutine；sqrt（doublereal）、；ftnlen）、；VOID；中的任何一個(gè)匹配，則按一定的規(guī)則移動(dòng)位置指針找出所調(diào)用的函數(shù)名，再根據(jù)映射關(guān)系找出定義該函數(shù)的文件名；

　?。?）遍歷整個(gè)庫(kù)文件找出與該文件名相同的C源文件或者頭文件并將它們復(fù)制到新建文件夾（sgesv.c）中；

　?。?）將找到的C源文件打開轉(zhuǎn)到步驟（3）；

　?。?）直到將原始C文件（sgesv.c）遍歷一遍為止，將自動(dòng)提取的庫(kù)文件全部放在新建文件夾（sgesv.c）中，再加入主函數(shù)文件；

　　（7）通過(guò)系統(tǒng)調(diào)用GCC命令進(jìn)行編譯鏈接生成可執(zhí)行性文件；

　　（8）檢測(cè)文件夾（sgesv.c）中是否生成可執(zhí)行性文件，若存在則表明自動(dòng)提取正確，并將SRC中的C原文件名（sgesv.c）寫入到passed.txt，否則寫入到unpassed.txt中；

　?。?）調(diào)用DOS命令，刪除剛加入的main函數(shù)文件和生成的可執(zhí)行性文件；

　?。?0）依次遍歷SRC下的文件名，直到遍歷結(jié)束。

　　其算法流程圖如圖1所示。

　　3.2 基于調(diào)用圖的自動(dòng)提取算法

　　調(diào)用LLVM接口函數(shù)生成調(diào)用關(guān)系圖，這里以函數(shù)sgesv_為例來(lái)解釋該算法。

　　3.2.1 函數(shù)sgesv_生成的調(diào)用圖

　　圖2就是指定起始入口函數(shù)sgesv_利用LLVM生成的調(diào)用關(guān)系圖，從圖中可以看到函數(shù)的定位信息，容易找出關(guān)鍵詞文件名進(jìn)行庫(kù)文件提取。

　　在文本文檔中顯示該調(diào)用圖，代碼如下：

　　digraph{

　　label="sgesv_的函數(shù)調(diào)用圖"；

　　sgesv_[label="sgesv_\n在文件./lapack/sgesv.c中第77行左右定義"]；

　　xerbla_[label="xerbla_\n在文件./lapack/xerbla.c中第35行左右定義"]；

　　...

　　sgetrs_->slaswp_[label="2"]；

　　sgetrs_->f2c_strsm[label="4"]；

　　sgesv_->sgetrs_；

　　}

　　3.2.2 基于調(diào)用圖的自動(dòng)提取算法

　　讀取調(diào)用圖能夠直接獲得被sgesv.c調(diào)用的文件名，然后遍歷整個(gè)庫(kù)文件，找出這些文件并復(fù)制到指定的文件夾下，將提取的文件放到一個(gè)工程中，加入對(duì)應(yīng)的主函數(shù)文件，調(diào)用GCC命令進(jìn)行編譯，檢測(cè)是否生成可執(zhí)行性文件，并以此為依據(jù)判斷是否正確提取。圖3就是基于調(diào)用關(guān)系圖的自動(dòng)提取算法流程圖。讀取多個(gè)調(diào)用圖就能實(shí)現(xiàn)多個(gè)SRC起始源文件的自動(dòng)提取。

4 自動(dòng)提取結(jié)果對(duì)比及討論

　　本文算法一的實(shí)驗(yàn)測(cè)試環(huán)境為：Windows 7系統(tǒng)，2 GB內(nèi)存，Intel酷睿i3-2350M，CPU@2.30 GHz x 4處理器。算法二是先在Linux系統(tǒng)下生成函數(shù)調(diào)用關(guān)系圖，然后在Windows系統(tǒng)下解析調(diào)用圖進(jìn)行提取的，它的實(shí)驗(yàn)測(cè)試環(huán)境為：Ubuntu 13.04系統(tǒng)，4 GB內(nèi)存，Pentium（R）Dual-Core CPU@2.93 GHz處理器；Windows 7系統(tǒng)，2 GB內(nèi)存，Intel酷睿i3-2350M，CPU@2.30 GHz x 4處理器。CLAPACK（3.1.1版）庫(kù)SRC文件夾下源文件有1 537個(gè)，總共分為4類，從4類中各隨機(jī)取出等量的樣本進(jìn)行測(cè)試，結(jié)果如表1所示。

　　從表1可以看出，基于特征詞的關(guān)鍵詞自動(dòng)提取算法和基于調(diào)用圖的自動(dòng)提取算法都可以完成CLAPACK庫(kù)的自動(dòng)提取，它們都可以提高算法代碼文件提取的效率。但是算法一的提取正確率高于算法二，這是因?yàn)樵谒惴ǘ校烧{(diào)用圖的算法目前還不能對(duì)二重指針進(jìn)行定位。但是方法一也有不足之處，它對(duì)于函數(shù)名與文件名不是按照通用規(guī)則進(jìn)行映射的情況不適用，比如函數(shù)f_exit按照通用映射規(guī)則應(yīng)該是在f_exit.c中定義，但它卻是在close.c中定義的。

5 結(jié)論

　　本文提出基于特征詞的關(guān)鍵字自動(dòng)提取算法和基于調(diào)用圖的自動(dòng)提取算法，并將這兩種算法應(yīng)用于CLAPACK庫(kù)的精簡(jiǎn)自動(dòng)提取，結(jié)果表明它們能實(shí)現(xiàn)代碼文件的自動(dòng)提取。算法一中函數(shù)名與文件名不對(duì)應(yīng)以及算法二中二重指針的問(wèn)題都需要以后重點(diǎn)解決。

　　參考文獻(xiàn)

　　[1] Li Juanzi， Fan Qina， Zhang Kuo. Keyword extraction based on TF/IDF for Chinese news document[J]. Wuhan University Journal of Natura1 Sciences，2007，12（5）：917-921．

　　[2] 黃磊，伍雁鵬，朱群峰.關(guān)鍵詞自動(dòng)提取方法的研究與改進(jìn)[J].計(jì)算機(jī)科學(xué)，2014，41（6）：204-208.

　　[3] 索紅光，劉玉樹，曹淑英．一種基于詞匯鏈的關(guān)鍵詞抽取方法[J]．中文信息學(xué)報(bào)，2006，20（6）：25-30.

　　[4] PETER T. Learning to extract key-phrases from text[R]. NRC Technical Report， ERB-1057， 1999：1-43.

　　[5] 劉靜寒，鐘輝.基于特征點(diǎn)匹配的自適應(yīng)目標(biāo)跟蹤算法[J].微型機(jī)與應(yīng)用，2015，34（8）：17-19.

　　[6] 陳泓旭.基于LLVM的程序關(guān)注點(diǎn)影響分析[J].計(jì)算機(jī)與現(xiàn)代化，2014（4）：203-207.

　　[7] 董峰，付宇卓.基于LLVM架構(gòu)的ARM后端移植[J].信息技術(shù)，2007（7）：37-40.

　　[8] 謝幸，李玉成.LAPACK的自動(dòng)并行化工具研究[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2001（2）：130-133.

　　[9] ANDERSON E， BAI Z， BISCHOF C. LAPACK Users′ Guide（第3版）[M]. SIAM，1999.