代码文件的自动提取

张轩振，李 俊（中国科学技术大学 自动化系，安徽 合肥 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-），男，博士，副教授，主要研究方向：网络传播与控制。