代碼文件的自動提取

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

代碼文件的自動提取

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

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

自動提取；關鍵詞；特征詞；調用關系圖；CLAPACK庫

0 引言

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

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

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

1 兩種自動提取算法

1.1 基于特征詞的關鍵詞自動提取算法

先遍歷代碼文件找到特征詞，再根據一定的規則提取關鍵詞，進而實現代碼文件的自動提取。其算法如下：

（1）根據手動提取的經驗找到特征詞集合；

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

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

（4）根據關鍵詞與文件名之間的映射關系找出該關鍵詞對應的文件名；

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

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

1.2 基于調用圖的自動提取算法

1.2.1 LLVM簡介

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

1.2.2 基于調用圖自動提取算法

代碼文件中的某些關鍵詞（如函數名）可以借助一些工具進行定位，根據定位結果，再利用計算機實現關鍵詞的自動提取。基于調用圖的自動提取算法就是利用LLVM生成的調用關系圖進行關鍵詞的自動提取，進而實現庫文件的自動提取，其算法如下：

（1）指定生成調用圖最開始分析的入口函數；

（2）遍歷整個編譯單元，當遇到調用點轉到步驟（3）；

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

（4）重復上述兩步直到遍歷結束，將所有直接調用映射directCaller2CalleeMap傳遞給間接調用映射Caller2CalleeMap；

（5）根據上述函數調用關系，生成調用關系圖，逐一讀取生成調用圖中的文件名，遍歷代碼文件集合找出它們并將它們復制到一個指定文件夾下；

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

2 CLAPACK庫簡介及特點

2.1 CLAPACK庫簡介

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

2.2 CLAPACK庫源文件特點

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

3 兩種算法的實現

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

3.1 基于特征詞的關鍵詞自動提取算法

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

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

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

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

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

（5）將找到的C源文件打開轉到步驟（3）；

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

（7）通過系統調用GCC命令進行編譯鏈接生成可執行性文件；

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

（9）調用DOS命令，刪除剛加入的main函數文件和生成的可執行性文件；

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

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

3.2 基于調用圖的自動提取算法

調用LLVM接口函數生成調用關系圖，這里以函數sgesv_為例來解釋該算法。

圖1 LAPACK庫中算法一的實現流程圖

3.2.1 函數sgesv_生成的調用圖

圖2就是指定起始入口函數sgesv_利用LLVM生成的調用關系圖，從圖中可以看到函數的定位信息，容易找出關鍵詞文件名進行庫文件提取。

圖2 函數sgesv_的部分調用關系圖

在文本文檔中顯示該調用圖，代碼如下：

3.2.2 基于調用圖的自動提取算法

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

圖3 基于調用圖的自動提取算法流程圖

4 自動提取結果對比及討論

本文算法一的實驗測試環境為：Windows7系統，2GB內存，Intel酷睿i3-2350M，CPU@2.30GHz x4處理器。算法二是先在Linux系統下生成函數調用關系圖，然后在Windows系統下解析調用圖進行提取的，它的實驗測試環境為：Ubuntu13.04系統，4GB內存，Pentium（R）Dual-Core CPU@2.93 GHz處理器；Windows7系統，2GB內存，Intel酷睿i3-2350M，CPU@2.30GHz x4處理器。CLAPACK（3.1.1版）庫SRC文件夾下源文件有1 537個，總共分為4類，從4類中各隨機取出等量的樣本進行測試，結果如表1所示。

表1 兩種算法測試結果及對比

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

5 結論

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

［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］黃磊，伍雁鵬，朱群峰.關鍵詞自動提取方法的研究與改進［J］.計算機科學，2014，41（6）：204-208.

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

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

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

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

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

圖8 3種協議吞吐量對比

參考文獻

［1］Yang Xiao.水下聲傳感器網絡［M］.顏冰，劉忠，羅亞松，等譯.北京：國防工業出版社，2012.

［2］FAIR N，CHAVE A D，FREITAG 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，FREITAG 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］呂長艷，劉廣鐘.基于浮標的 3D水聲傳感器網絡節點的定位［J］.微型機與應用，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-），女，碩士，主要研究方向：水下聲傳感器網絡。

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

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

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］.微型機與應用，2015，34（18）：65-68.

2015-05-19）

張軒振（1989-），男，碩士研究生，主要研究方向：網絡新媒體服務系統。

李俊（1973-），男，博士，副教授，主要研究方向：網絡傳播與控制。