一种海量源码分析检索的新方法,搜索引擎论文

一种海量源码分析检索的新方法,搜索引擎论文代码的重用性在软件工程领域是一个很重要的课题。通过面向对象分析、模块化编程，开发者能够很大程度地提升代码的重用性。但在详细编码时，仍然会碰到很多在方式方法层面上需要重用的情况。考虑如寻找一段可直接使用的寻路算法，或者是矩阵打包算法。这些具有特定功能的源码在当前通过关键字搜索的方式下很难在海量源码中被搜索到。原因有3个:1)源码中变量名的命名法通常使用缩写，并以大写字母进行分词，如preNode，inＲect等，而用户进行搜索输入的关键字更偏向自然语言，如previousnode，inputrect。这导致很多源码无法通过关键字匹配算法匹配。2)在Sourceforge或者Github即便存在匹配的关键字，更多的搜索结果是头文件或接口，很少有实际可用的源码。3)自然语言存在同义词问题，语义相近的源码会由于无法被字符串匹配而错过。如用户输入drawnode，draw(vertex［］v)就不会被搜索到。文献通过以语义网络为文本关键字建立近义词索引的方式方法，改善了文本搜索问题中近义词无法被关键字匹配算法所匹配的问题。本文将该方式方法运用于源码搜索，并结合传统的程序分析技术，提出一种海量源码分析的新方式方法，解决上文提到的源码搜索碰到的3方面问题。1、相关工作1．1基于关键字的海量源码搜索引擎传统源码搜索引擎采用关键字匹配的算法，如Github的代码搜索服务，其优势是搜索迅速，能够用通用的文本搜索引擎检索源码，而缺陷如引言所述，无法匹配源码中的缩写，以及搜索结果大部分是无数据流的方式方法声明。1．2基于自然语言的源码定位EmilyHill在基于自然语言的源码定位方面做了很多建设性的工作。其主要目的为了解决软件开发经过中由于缺少文档而导致的软件维护困难问题，帮助开发者更方便地定位系统模块，了解系统构造。其核心思想是通过分析制定项目，为项目中的标识符建立源码索引，如strtPt:startpoint，srcNode:sourcenode。最后通过用户输入的自然语言词素与标识符拓展后的词素进行匹配到达源码定位的目的。2、分析及搜索方式方法描绘叙述本文将EmilyHill的自然语言源码定位应用于海量数据，并构建一个包含海量源码变量使用关系与词素拓展集的数据库。在这里之上运用关键字匹配算法定位相关源代码。2．1源码identify缩写拓展到自然语言单词本文提出一种树状单词树用以解决将标识符从缩写到完好词素的拓展算法。如此图1所示。构造完成的单词树是一种包含所有英语词素的树状数据构造，华而不实每个节点有且仅有一个字符信息，并附带标志位isWord，华而不实自顶向下的途径表示一个词素序列，当节点上isWord被标记时，代表途径到此为止构成的序列是一个完好词素。图1以．作为完好词素标记。以下为节点数据构造的定义：如此图2所示，对一棵单词树T，插入词素w1w2wn的经过如下:令T［wi］表示字符wi在第i层对应的节点。则T［w1］是根节点下字符为w1的节点。假使不存在，则开创建立对应节点。对每个wk，k＞1，寻找T［wk－1］节点下能否存在字符为wk的节点，假使存在，则T［wk］为该节点，若不存在则开创建立字符为wk的子节点。图1所示为在一棵空单词树上插入act，active，activity，black，actual几个词后的示意图。将全词素列表的每条词素按上述算法插入一棵空树，最后得到的结果即包含全词素的单词树。在已建立的单词树基础上，对标识符I拓展完好词素备选集的问题可划归为树途径搜索问题，令I［i］表示I中第i个字符，知足条件的途径必须依次(不必连续)包含内容为I［1］，I［2］，I［3］，，I［n－1］字符的节点，并以isWord标记为true的节点终止，该问题是一个深度优先搜索问题。图1示例中，对actv寻找完好词素拓展集合的结果即为{activity，active}。下面为词素扩展经过伪代码。经过:Node［］expand(root，I，offset)。输入:root表示自然语言单词树根节点，I表示要拓展的标识符字符串，offset表示I的起始偏移量。返回:Node［］表示每条知足要求的途径的最后节点，该节点isWord必须为true。通过该算法获得的节点集合对每个节点不断访问parent即可获得该节点对应的完好途径，即一个完好词素。2．2海量数据库建立基于语义的搜索经过如此图3所示。本文的核心思想是通过分析海量源码，建立源码数据库，数据库中包含源码中标识符之间的关系，以及标识符对应的完好词素的扩展。源码中标识符的关系主要包含下面2点:1)方式方法与变量的附属关系;2)同一方式方法体内变量的使用关系。以上2点主要通过传统的程序分析方式方法建立，本文使用的工具是JavaCC，对源代码进行静态的语法分析，最后以关系型数据库MySQL持久化分析结果。2．3搜索算法令函数Similarity(wi，wj)代表S中2个单词的语义近似度，其值域为［0，1］，该值的获取方式方法通过Dis-coWiki数据库，其构造如此图4所示。最后按降序排列的方式方法结果集合即为搜索结果。3、测试结果及分析实验从功能及性能2方面进行评测，通过不同难度的测试用例，统计使用者对本引擎的搜索结果与Github搜索结果匹配度进行比照以评价引擎的可用性。3．1搜索用例测试测试用例实验主要通过提供4组不同难度的测试用例，并召集10位志愿者分别在Github上与在本引擎上搜索测试用例，并将前10条结果匹配率作为反应进行比拟。当结果中包含详细源码，源码标识符内容与输入所匹配时，算作一条匹配结果。测试用例1:寻找图表绘制API相关源码。根据本文定义的格式，以{chart;draw;}作为输入。测试用例2:本例采用实现较为多样化的最大流问题作为搜索。以{source，stream;max;}作为关键字进行查询。测试用例3:本例作为测试用例2的比照测试，以更精准的{source，flow;max;}搜索最大流算法。该测试用例主要测试语义近似对搜索结果的影响。测试用例4:寻路算法寻找，输入{start;find，path;}。由图5、图6可知，在匹配度上，4组测试用例中本文的搜索结果均高于Github，在实验中，Github的搜索结果大部分是接口声明，本文的搜索结果均包含匹配关键字的数据流，具有可工作源码。在语义近似的测试用例上，如最大流问题的stream与flow，没有flow关键字时，Github不存在匹配的结果，而本文的方式方法在前10项搜索结果中仍然包含匹配的源码。4项测试的比拟中，本文提出的方式方法搜索结果均强于Github的搜索结果。3．2性能测试该测试根据参数扩展集最大容量maxArg、被影响参数扩展集最大容量maxAffected、调用图搜索的最大深度d、词汇泛用性v为基准对搜索引擎性能进行评估。测试结果如表1所示。表1中的数据表示清楚，参数和被影响参数对搜索时间影响是线性的，被影响参数系数更大，原因是被影响参数集合大小决定了调用图搜索的复杂度。而深度的增加对时间的增加是高于线性的，由于广度优先搜索每多搜一层其元素将是上一层的k倍，k取决于节点的平均子节点数量。单词的泛用性，高的指object等泛用名字，低的指词义信息详细的名词，对搜索时间影响得非常大，原因是单词泛用性决定了搜索引擎构筑的语义网络的出度，进而影响备选集的容量。4、结束语本文通过结合程序分析与语义网络，通过大数据分析的方式方法，为源码中的标识符建立使用关系。本文基于缩写拓展算法，设计适用于程序标识符缩写的自然语言单词拓展算法。通过使用自然语义近似网络，将用户的