張軒振，李 ?。ㄖ袊茖W(xué)技術(shù)大學(xué) 自動化系，安徽 合肥 230027）

代碼文件的自動提取

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

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

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

0 引言

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

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

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

1 兩種自動提取算法

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

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

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

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

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

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

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

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

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

1.2.1 LLVM簡介

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

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

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

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

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

（3）如果該調(diào)用處的值為函數(shù)常量，則將該主調(diào)函數(shù)與被調(diào)函數(shù)對加入directCaller2Calle-eMap中；若該調(diào)用點為間接調(diào)用，通過指向分析找出該變量指向的所有可能值，將主調(diào)函數(shù)和這些值成對加入到direct-Caller2CalleeMap中，同時將被調(diào)用函數(shù)和調(diào)用點信息記錄到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ù)制到一個指定文件夾下；

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

2 CLAPACK庫簡介及特點

2.1 CLAPACK庫簡介

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

2.2 CLAPACK庫源文件特點

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 自動提取結(jié)果對比及討論

本文算法一的實驗測試環(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)行提取的，它的實驗測試環(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版）庫SRC文件夾下源文件有1 537個，總共分為4類，從4類中各隨機(jī)取出等量的樣本進(jìn)行測試，結(jié)果如表1所示。

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

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

5 結(jié)論

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

［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)鍵詞自動提取方法的研究與改進(jìn)［J］.計算機(jī)科學(xué)，2014，41（6）：204-208.

［3］索紅光，劉玉樹，曹淑英．一種基于詞匯鏈的關(guān)鍵詞抽取方法［J］．中文信息學(xué)報，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］劉靜寒，鐘輝.基于特征點匹配的自適應(yīng)目標(biāo)跟蹤算法［J］.微型機(jī)與應(yīng)用，2015，34（8）：17-19.

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

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

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

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

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

參考文獻(xiàn)

［1］Yang Xiao.水下聲傳感器網(wǎng)絡(luò)［M］.顏冰，劉忠，羅亞松，等譯.北京：國防工業(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］呂長艷，劉廣鐘.基于浮標(biāo)的 3D水聲傳感器網(wǎng)絡(luò)節(jié)點的定位［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）

作者簡介：

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

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

徐明（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

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

2015-05-19）

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

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