代碼文件的自動(dòng)提取

張軒振，李 俊（中國(guó)科學(xué)技術(shù)大學(xué) 自動(dòng)化系，安徽 合肥 230027）

代碼文件的自動(dòng)提取

張軒振，李 俊
（中國(guó)科學(xué)技術(shù)大學(xué) 自動(dòng)化系，安徽 合肥 230027）

為了提高代碼文件提取的效率，提出了基于特征詞的關(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)提取，提高了提取的效率。

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

0 引言

近年來(lái)，隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)上的代碼文件越來(lái)越多，尤其是開(kā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決策樹(shù)機(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）打開(kāi)文檔集合中的一個(gè)起始文件；

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

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

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

（6）查看自動(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)提取，其算法如下：

（1）指定生成調(diào)用圖最開(kāi)始分析的入口函數(shù)；

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

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

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

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

（6）自動(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寫(xiě)的，為了方便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ù)制到指定文件夾下并打開(kāi)該源文件（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ù)的文件名；

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

（5）將找到的C源文件打開(kāi)轉(zhuǎn)到步驟（3）；

（6）直到將原始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）寫(xiě)入到 passed.txt，否則寫(xiě)入到unpassed.txt中；

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

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

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

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

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

圖1 LAPACK庫(kù)中算法一的實(shí)現(xiàn)流程圖

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

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

圖2 函數(shù)sgesv_的部分調(diào)用關(guān)系圖

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

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)提取。

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

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

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

表1 兩種算法測(cè)試結(jié)果及對(duì)比

從表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)解決。

［1］Li Juanzi，F(xiàn)an 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］索紅光，劉玉樹(shù)，曹淑英．一種基于詞匯鏈的關(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.

圖8 3種協(xié)議吞吐量對(duì)比

參考文獻(xiàn)

［1］Yang Xiao.水下聲傳感器網(wǎng)絡(luò)［M］.顏冰，劉忠，羅亞松，等譯.北京：國(guó)防工業(yè)出版社，2012.

［2］FAIR N，CHAVE A D，F(xiàn)REITAG L，et al.Optical modem technology for seafloor observatories［C］.Proceedings of IEEE OCEANS′05 Confernce，2006：18-21.

［3］CATIPOVIC J A.Performance limitations in underwater acoustic telemetry［J］.IEEE Journal of Oceanic Engineering，1990，15（3）：205-216.

［4］PARTAN J，KUROSE J，LEVINE B N.A survey of practical issues in underwater networks［C］.Proceedings of the 1st ACM International Workshop on Underwater Networks， 2006：17-24.

［5］KILFOYLE D B，BAGGEROER A B.The state of the art in underwater acoustic telemetry［J］.IEEE Jourand of O-ceanic Engineering，2000，25（1）：4-27.

［6］CAR G A，ADAMS A E.ACMENet：an underwater acoustic sensor network for real-time environmental monitoring in coastal areas［J］.IEEE Proceedings of Radar，Sonar，and Navigation 2006，153（4）：365-380.

［7］STOJANOVIC M，F(xiàn)REITAG L.Multichannel detection for wideband underwater acoustic CDMA communications［J］. IEEE Journal of Oceanic Engineering，2006，31（3）：686-695.

［8］RAPPAPORT T S.Wireless communications：principles and practice［M］.New Jersey：Prentice Hall，1996.

［9］MOLINS M，STOJANOVIC M.Slotted FAMA：a MAC protocol for underwater acoustic networks［C］.Proceedings of IEEE OCEANS′06 Conference，2006：16-19.

［10］呂長(zhǎng)艷，劉廣鐘.基于浮標(biāo)的 3D水聲傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位［J］.微型機(jī)與應(yīng)用，2013，32（22）：48-50.

［11］APPLEGATE D L，BIXBY R E，CHVATAL V，et al. The traveling salesman problem：a computational study［M］. Princeton University Press，2007.

（收稿日期：2015-04-27）

作者簡(jiǎn)介：

智納納（1987-），女，碩士，主要研究方向：水下聲傳感器網(wǎng)絡(luò)。

劉廣鐘（1962-），男，博士，教授，主要研究方向：水下聲傳感器網(wǎng)絡(luò)、分布式計(jì)算。

徐明（1977-），男，博士，副教授，主要研究方向：水下聲傳感器網(wǎng)絡(luò)。

Automatic extraction of the code file

Zhang Xuanzhen，Li Jun
（Department of Automation，University of Science and Technology of China，Hefei 230027，China）

In order to improve the efficiency of the extraction of the code files，we propose automatic extraction of feature words of keyword-based algorithm（algorithm I）and automatic extraction algorithm based on the call graph（algorithm II）for keyword extraction，thus achieving code files automatic extraction.The two algorithms are applied to the automatic extraction of CLAPACK library source files.Results show that the extraction rate of correct of the two algorithms are 92％ and 44％，and they can automatically extract the code files and increase the extraction efficiency.

sautomatic extraction；keywords；feature string；call graph；CLAPACK library

TP391.9

A

1674-7720（2015）18-0065-04

張軒振，李俊.代碼文件的自動(dòng)提?。跩］.微型機(jī)與應(yīng)用，2015，34（18）：65-68.

2015-05-19）

張軒振（1989-），男，碩士研究生，主要研究方向：網(wǎng)絡(luò)新媒體服務(wù)系統(tǒng)。

李?。?973-），男，博士，副教授，主要研究方向：網(wǎng)絡(luò)傳播與控制。