1.本发明涉及代码搜索技术领域，更具体地，涉及一种基于图序列化的代码搜索系统及方法。
背景技术：2.随着互联网技术的发展，开源代码片段的数量在不断增加，而代码搜索可以很大程度上提高软件开发过程中的编码效率，如何利用已有的海量代码片段，有效帮助开发人员直接从代码数据库中准确地搜索与特定编程任务相关的代码片段，成为了软件工程领域的热点问题。在代码搜索的初期研究阶段，大多数的代码搜索方法都是将代码片段视为纯文本序列，使用关键词匹配的方法来衡量代码片段和自然语言之间的相似度。但由于用户的查询语句和代码片段是异构信息，导致基于关键词匹配的代码搜索方法的准确率不尽人意。因此，随着深度学习技术在自然语言处理领域获得显著成效，研究人员逐渐考虑从深度学习的角度来研究代码搜索任务，使用深度学习技术有效学习用户的查询语句所表达的语义信息与代码片段中包含的结构化信息，来提高代码搜索方法的准确率。
3.现有的一种基于深度学习的代码搜索方法deepcs(deep code search)，使用深度学习技术学习代码片段和自然语言的特征，将代码片段与自然语言的特征向量映射到同一个高维空间，并以余弦相似度的方法来判断代码片段和自然语言的相似性程度。但是这种方法在代码片段特征提取过程中仅考虑到代码的文本信息，忽略了代码所特有的图结构信息，导致得到的代码片段特征并不全面，从而降低了代码搜索方法的准确率。而另一种deepcs的改进方法mman(multi-modal attention network)为了使代码片段的特征更加全面，在代码片段特征提取过程中使用图神经网络学习代码的控制流程图信息。但是mman并没有很好地利用代码的图结构信息。一方面，图神经网络适用于节点多的图，而代码片段的控制流程图的节点通常都很少，使用图神经网络不能很好地学习代码的图结构信息；另一方面，由于代码的控制流程图只包含控制依赖关系而不包含数据依赖关系，只使用控制流程图会忽略代码的数据依赖关系。因此，mman的准确率没有得到有效提升。
技术实现要素：4.针对上述现有技术存在的不足，本发明提出一种基于图序列化的代码搜索系统及方法，旨在克服现有技术未充分利用代码图结构中包含的有效信息导致代码搜索准确率低的问题。
5.本发明的技术方案为：
6.本发明第一方面提供一种基于图序列化的代码搜索系统，该系统包括：
7.数据采集模块，用于采集多个原始代码片段，构成原始代码片段集合；
8.代码片段预处理模块，用于对所述原始代码片段集合中的每一代码片段提取相关特征，包括代码片段的方法名序列、代码片段的令牌token序列和代码片段的程序依赖图pdg；
9.图序列转换器g2sc：用于根据代码片段预处理模块提取的程序依赖图pdg学习代码片段的控制依赖关系和代码片段的数据依赖关系，生成富含代码图结构信息的程序依赖图序列，并将所述程序依赖图序列发送给图特征提取模块；
10.方法名特征提取模块，用于将代码片段预处理模块提取的方法名序列输入到双向长短时记忆网络bi-lstm中提取方法名序列包含的特征，获得方法名特征向量并发送给注意力嵌入模块；
11.token特征提取模块，用于将代码片段预处理模块提取的token序列输入到多层感知机mlp中提取token序列包含的特征，获得token特征向量并发送给注意力嵌入模块；
12.图特征提取模块，用于将程序依赖图序列输入到双向长短时记忆网络bi-lstm中提取程序依赖图序列包含的特征，获得程序依赖图特征向量并发送给注意力嵌入模块；
13.注意力嵌入模块，用于接收所述方法名特征提取模块发送的方法名特征向量、所述token特征提取模块发送的token特征向量、所述图特征提取模块发送的程序依赖图特征向量，并为所述方法名特征向量、token特征向量和程序依赖图特征向量分配不同的注意力系数，得到代码片段的融合特征向量并发送给相似度计算模块；
14.自然语言预处理模块，用于通过分词工具对用户输入的查询语句进行分词处理，并过滤掉其中包含的特殊符号，获得自然语言序列并发送给自然语言特征提取模块；
15.自然语言特征提取模块，用于将自然语言预处理模块提取的自然语言序列输入到双向长短时记忆网络bi-lstm中提取自然语言序列包含的特征，获得自然语言特征向量，并将该自然语言特征向量发送给相似度计算模块；
16.相似度计算模块，用于接收注意力嵌入模块输出的代码片段的融合特征向量和自然语言特征提取模块输出的自然语言特征向量，计算所述自然语言特征向量与所有代码片段的融合特征向量之间的余弦相似度，并将余弦相似度最大的若干融合特征向量对应的代码片段作为代码搜索结果，返回给用户。
17.本发明第二方面提供一种基于图序列化的代码搜索方法，该方法包括如下步骤：
18.步骤1：采集代码片段和代码片段所对应的自然语言注释；
19.步骤2：通过分词工具对每一代码片段的自然语言注释进行分词处理并过滤掉分词结果中包含的特殊符号获得每一代码片段的自然语言注释序列d；
20.步骤3：提取每一代码片段的方法名序列m、token序列t和程序依赖图g
pdg
；
21.步骤4：将每一代码片段的程序依赖图g
pdg
输入到图序列转换器g2sc中，利用g2sc学习程序依赖图的控制依赖关系和数据依赖关系，生成富含代码图结构信息的程序依赖图序列p，其中表示所述程序依赖图序列中所有单词的集合，n
p
为程序依赖图序列的单词总数；
22.步骤5：针对每一代码片段，利用方法名特征提取模块提取方法名序列包含的特征获得方法名特征向量vm、利用token特征提取模块提取token序列包含的特征获得token特征向量v
t
、以及利用图特征提取模块提取程序依赖图序列包含的特征获得程序依赖图特征向量v
p
，并采用注意力机制将vm、v
t
和v
p
进行组合得到融合特征向量vc；
23.步骤6：通过自然语言特征提取模块提取每一代码片段的自然语言注释序列d的特征，获得自然语言注释特征向量vd；
24.步骤7：根据每一代码片段的融合特征向量vc和自然语言注释特征向量vd计算相似
度损失函数l(θ)，并根据相似度损失优化更新方法名特征提取模块中的参数、token特征提取模块中的参数、图特征提取模块中的参数、注意力嵌入模块中的参数和自然语言特征提取模块中的参数；
25.步骤8：重复执行步骤5-步骤7，直至相似度损失l(θ)收敛，获得每一代码片段最终的融合特征向量，及具有最优参数的方法名特征提取模块、具有最优参数的token特征提取模块、具有最优参数的图特征提取模块、具有最优参数的注意力嵌入模块和具有最优参数的自然语言特征提取模块；
26.步骤9：当用户输入查询语句q时，通过分词工具对用户输入的查询语句进行分词处理并过滤掉其中包含的特殊符号获得自然语言序列q；
27.步骤10：通过自然语言特征提取模块提取自然语言序列包含的特征，获得自然语言特征向量vq；
28.步骤11：计算自然语言特征向量vq与所有代码片段最终的融合特征向量之间的余弦相似度，将余弦相似度最大的若干融合特征向量对应的代码片段作为代码搜索结果，返回给用户。
29.进一步地，根据所述的基于图序列化的代码搜索方法，所述利用g2sc学习程序依赖图的控制依赖关系和数据依赖关系生成富含代码图结构信息的程序依赖图序列p的方法包括如下步骤：
30.步骤4-1：对于程序依赖图g
pdg
，初始化程序依赖图序列p＝{}，将v1作为程序依赖图序列p的第一个元素p1，并设定程序依赖图序列p的最后一个元素所对应的节点为e
end
；
31.步骤4-2：按照边选取规则递归地从候选边中选择一条边进行扩展，直到所有边均被遍历；
32.步骤4-3：如果遍历的边是控制依赖边，则只将边的始点和终点所对应的属性信息添加到程序依赖图序列p中，如果遍历的边是数据依赖边，则依次将数据依赖边的始点、数据依赖边、以及数据依赖边的终点所对应的属性信息添加到程序依赖图序列p中；
33.步骤4-4、重复步骤4-1至步骤4-3，遍历完所有的有向边，获得程序依赖图序列p。
34.进一步地，根据所述的基于图序列化的代码搜索方法，所述候选边指的是以e
end
为始点的未被遍历的有向边。
35.进一步地，根据所述的基于图序列化的代码搜索方法，所述边选取规则如下：
36.规则a、回溯边在前向边之前被选择，回溯边指的是有向边的终点已经被遍历的边，前向边指的是有向边的终点未被遍历的边；
37.规则b、当存在多个回溯边或多个前向边时，则根据预设优先级，选择控制依赖边或者数据依赖边；
38.规则c、如果在规则b之后仍然不能确定边，则选择终点所对应节点优先级最高的边作为优先扩展边；
39.规则d、如果不存在以e
end
为始点的未被遍历的有向边，则继续遍历以e
end
最近的祖先节点为始点的没有遍历的有向边。
40.进一步地，根据所述的基于图序列化的代码搜索方法，所述利用方法名特征提取模块提取方法名特征向量vm的方法为：在方法名特征提取模块中将代码片段的方法名序列中的每一个单词转为词向量并输入到能学习到时序关系的双向长短
时记忆网络bi-lstm中，并按照公式(1)获得方法名序列m在正向lstm中i时刻的正向隐藏层向量按照公式(2)获得方法名序列m在反向lstm中i时刻的反向隐藏层向量最后根据公式(3)对方法名序列m所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得方法名特征向量vm，具体公式如下；
[0041][0042][0043][0044]
其中，mi为方法名序列的第i个单词，nm为方法名序列m中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表方法名序列的正向和反向lstm神经网络模型以及相关参数；和分别表示方法名序列的正向lstm神经网络模型和反向lstm神经网络模型在i时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数；vm是最终获得的方法名特征向量。
[0045]
进一步地，根据所述的基于图序列化的代码搜索方法，所述利用token特征提取模块提取token特征向量v
t
的方法为：在token特征提取模块中将代码片段的token序列中的每一个单词转为词向量并输入到多层感知机mlp中，并按照公式(4)获得token序列t中每个单词在mlp中的隐藏层嵌入向量最后根据公式(5)对token序列t所有单词的隐藏层嵌入向量进行整合，获得token特征向量v
t
，具体公式如下；
[0046][0047][0048]
其中，tj为token序列t的第j个单词；n
t
为token序列t中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；w
t
是mlp的权重参数；tanh()代表tanh函数；是tj在mlp中的隐藏层嵌入向量；maxpooling()代表最大池化函数；v
t
是最终获得的token特征向量。
[0049]
进一步地，根据所述的基于图序列化的代码搜索方法，所述利用图特征提取模块提取程序依赖图特征向量v
p
的方法为：在图特征提取模块中将代码片段的程序依赖图序列中的每一个单词转为词向量并输入到能学习到时序关系的双向长短时记忆网络bi-lstm中，并按照公式(6)获得程序依赖图序列p在正向lstm中k时刻的正向隐藏层向量按照公式(7)获得程序依赖图序列p在反向lstm中k时刻的反向隐藏层向量最后根据公式(8)对程序依赖图序列p所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得程序依赖图特征向量v
p
，具体公式如下；
[0050]
[0051][0052][0053]
其中，pk为程序依赖图序列p的第k个单词；n
p
为程序依赖图序列p中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表程序依赖图序列p的正向与反向lstm神经网络模型以及相关参数；和分别表示程序依赖图序列p的正向lstm神经网络模型和反向lstm神经网络模型在k时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数；v
p
是最终获得的程序依赖图特征向量。
[0054]
进一步地，根据所述的基于图序列化的代码搜索方法，所述通过自然语言特征提取模块提取自然语言注释特征向量vd的方法为：在自然语言特征提取模块中将代码片段的自然语言注释序列中的每一个单词转为词向量并输入到能学习到时序关系的双向长短时记忆网络bi-lstm中，并按照公式(10)获得自然语言注释序列d在正向lstm中t时刻的正向隐藏层向量按照公式(11)获得自然语言注释序列d在反向lstm中t时刻的反向隐藏层向量最后根据公式(12)对自然语言注释序列d所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得自然语言注释特征向量vd，具体公式如下；
[0055][0056][0057][0058]
其中，dr为自然语言注释序列的第r个单词；nd为自然语言注释序列d中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表自然语言注释序列d的正向与反向lstm神经网络模型以及相关参数；和分别表示正向lstm神经网络模型和反向lstm神经网络模型在r时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数；vd是最终获得的自然语言注释特征向量。
[0059]
与现有技术相比，本发明提出的技术方案具有以下有益效果：
[0060]
本发明系统及方法提出了一种将代码片段的程序依赖图转换为序列的图序列转换器g2sc(graph to sequence converter)，g2sc既可以学习到代码片段的控制依赖关系也可以学习到代码片段的数据依赖关系，并且比图神经网络更适用于节点少的代码图结构。通过g2sc，可以得到富含代码片段图结构信息的程序依赖图序列。同时，本发明系统及方法在特征提取过程中使用注意力机制将方法名特征向量、token特征向量、以及g2sc提取的程序依赖图特征向量进行融合，使得代码的语义和结构信息能够充分表达，特征提取更完整，有效提升代码搜索的准确率。最后，本发明系统及方法使用g2sc、双向长短时记忆网
络将代码片段的程序依赖图的信息映射到较低维度的特征空间中，可节省深度学习中所消耗的大量算力。
附图说明
[0061]
为了更清楚地说明本发明实施例中的具体方式，下面将对实施例中涉及的相关附图做简单说明，下面的附图仅仅是本发明的优选实施例，对于本领域普通技术人员来说，在没有创造性改变的前提下，可以根据这些附图获得其它的附图。
[0062]
图1为本实施方式基于图序列化的代码搜索系统的结构示意图；
[0063]
图2为本实施方式基于图序列化的代码搜索方法的流程示意图；
[0064]
图3为本实施方式利用g2sc生成程序依赖图序列的方法流程示意图。
具体实施方式
[0065]
为了便于理解本技术，下面将参照相关附图对本技术进行更全面的描述。附图中给出了本技术的较佳实施方式。但是，本技术可以以许多不同的形式来实现，并不限于本文所描述的实施方式。相反地，提供这些实施方式的目的是使对本技术的公开内容理解的更加透彻全面。
[0066]
图1为本实施方式基于图序列化的代码搜索系统的结构示意图。如图1所示，所述基于图序列化的代码搜索系统，包括：
[0067]
数据采集模块，用于采集代码片段。本实施方式中具体是，首先通过代码数据采集工具例如github api获取java开源项目的java文件，然后从java文件中提取java方法，每一java方法作为一个原始代码片段，从java文件中提取全部java方法对应的全部原始代码片段构成原始代码片段数据集。
[0068]
代码片段预处理模块，用于对数据采集模块采集的代码片段提取相关特征，包括代码片段的方法名序列、代码片段的令牌(token)序列和代码片段的程序依赖图(program dependency graph，pdg)。
[0069]
图序列转换器(graph to sequence converter，g2sc)，用于根据代码片段预处理模块提取的程序依赖图pdg学习代码片段的控制依赖关系和代码片段的数据依赖关系，生成富含代码图结构信息的程序依赖图序列，并将所述程序依赖图序列发送给图特征提取模块。
[0070]
方法名特征提取模块，用于将代码片段预处理模块提取的方法名序列输入到双向长短时记忆网络bi-lstm(bi-directional recurrent neural network)中提取方法名序列包含的特征，获得方法名特征向量，并将该方法名特征向量发送给注意力嵌入模块；
[0071]
token特征提取模块，用于将代码片段预处理模块提取的token序列输入到多层感知机mlp(multilayer perceptron)中提取token序列包含的特征，获得token特征向量，并将该token特征向量发送给注意力嵌入模块；
[0072]
图特征提取模块，用于将程序依赖图序列输入到双向长短时记忆网络bi-lstm中提取程序依赖图序列包含的特征，获得程序依赖图特征向量，并将该程序依赖图特征向量发送给注意力嵌入模块；
[0073]
注意力嵌入模块，用于接收所述方法名特征提取模块发送的方法名特征向量、所
述token特征提取模块发送的token特征向量、图特征提取模块发送的程序依赖图特征向量，并为所述方法名特征向量、token特征向量和程序依赖图特征向量分配不同的注意力系数，得到代码片段的融合特征向量并发送给相似度计算模块。
[0074]
自然语言预处理模块，用于通过分词工具例如jieba对用户输入的查询语句进行分词处理，并过滤掉其中包含的特殊符号，获得自然语言序列并发送给自然语言特征提取模块。
[0075]
自然语言特征提取模块，用于将自然语言预处理模块提取的自然语言序列输入到双向长短时记忆网络bi-lstm中提取自然语言序列包含的特征，获得自然语言特征向量，并将该自然语言特征向量发送给相似度计算模块；
[0076]
相似度计算模块，用于接收注意力嵌入模块输出的代码片段的融合特征向量和自然语言特征提取模块输出的自然语言特征向量，计算所述自然语言特征向量与所有代码片段的融合特征向量之间的余弦相似度，并将余弦相似度最大的若干融合特征向量对应的代码片段作为代码搜索结果，返回给用户。
[0077]
图2为本实施方式基于图序列化的代码搜索方法的流程示意图。如图2所示，所述基于图序列化的代码搜索方法包括以下步骤：
[0078]
步骤1：采集代码片段和代码片段所对应的自然语言注释；
[0079]
本实施方式中具体是，首先通过代码数据采集工具例如github api获取2016年8月至2020年9月发布的java开源项目包含的java文件，并限定java开源项目的star参数阈值为10，保证获取的java文件的质量；然后从java文件中提取全部java方法作为原始的代码片段，过滤掉没有注释或者非英文注释的java方法，并对剩余的每个java方法截取其注释的第一行内容作为该代码片段的自然语言注释；将最终获得的全部代码数据对进行8:2划分，分别作为训练数据集和评估数据集，其中每个代码数据对都由代码片段和代码片段的自然语言注释组成。
[0080]
步骤2：通过分词工具对每一代码片段的自然语言注释进行分词处理并过滤掉分词结果中包含的特殊符号获得每一代码片段的自然语言注释序列d。
[0081]
本实施方式中，具体是，通过分词工具例如jieba对每一代码片段的自然语言注释进行分词处理，并过滤掉分词结果中包含的特殊符号，得到每一代码片段的自然语言注释序列d，其中，表示所述自然语言注释序列中所有单词的集合，nd为单词总数。
[0082]
步骤3：提取每一代码片段的方法名序列m、token序列t和程序依赖图g
pdg
。
[0083]
本发明实施例中，首先由于java代码片段的方法名是以驼峰规则来命名，因此对于代码片段的方法名，使用驼峰规则对方法名进行分词，得到代码片段的方法名序列m，其中表示所述方法名序列中所有单词的集合，nm为方法名序列的单词总数；然后，对于代码片段中包含的所有文本，以stanfordcore nlp方法进行分词，获得代码片段的分词结果。并且由于java关键字和停用词经常出现在源代码中，不能很好地区分不同的代码片段，因此，移除代码片段分词结果中的java关键字和停用词，得到代码片段的token序列t，其中表示所述token序列中所有单词的集合，n
t
为token序列的单词总数；最后，通过程序依赖图提取工具tinypdg从代码片段中提取程序依赖图g
pdg
。在
程序依赖图中，边的依赖关系包括控制依赖和数据依赖两种，将边的依赖关系为控制依赖的边称为控制依赖边，将边的依赖关系为数据依赖的边称为数据依赖边；对于g
pdg
＝{v,va,ec,ed,e
da
}，表示所述程序依赖图的节点集合，nv为节点总数；表示所述程序依赖图中每个节点的属性信息，每个节点的属性信息指的是节点所对应的语句，表示所述程序依赖图的控制依赖边集合，n
ec
为控制依赖边总数，表示所述程序依赖图的数据依赖边集合，n
ed
为数据依赖边总数。表示所述程序依赖图中每个数据依赖边的属性信息，每个数据依赖边的属性指的是数据依赖边产生数据依赖的变量名称集合；
[0084]
步骤4：将代码片段的程序依赖图g
pdg
输入到图序列转换器g2sc中，利用g2sc学习程序依赖图的控制依赖关系和数据依赖关系，生成富含代码图结构信息的程序依赖图序列p，其中表示所述程序依赖图序列中所有单词的集合，n
p
为程序依赖图序列的单词总数；
[0085]
如图3所示，所述利用g2sc学习程序依赖图的控制依赖关系和数据依赖关系生成富含代码图结构信息的程序依赖图序列p的方法包括如下步骤：
[0086]
步骤4-1：对于程序依赖图g
pdg
，初始化程序依赖图序列p＝{}，将v1作为程序依赖图序列p的第一个元素p1，并设定程序依赖图序列p的最后一个元素所对应的节点为e
end
；
[0087]
步骤4-2：按照边选取规则递归地从候选边中选择一条边进行扩展，直到所有边均被遍历，候选边指的是以e
end
为始点的未被遍历的有向边，边选取规则如下：
[0088]
规则a、回溯边在前向边之前被选择，回溯边指的是有向边的终点已经被遍历的边，前向边指的是有向边的终点未被遍历的边；
[0089]
规则b、当存在多个回溯边或多个前向边时，则根据预设优先级，选择控制依赖边或者数据依赖边；需要说明的是，控制依赖边和数据依赖边之间的优先级并不影响生成程序依赖图序列p的唯一性。在本实施例中，为了确定唯一程序依赖图序列，规定控制依赖边具有更高的优先级，在边选取过程中优先被选择，当存在多个回溯边或多个前向边时，则选择控制依赖边，而不是数据依赖边；
[0090]
规则c、如果在规则b之后仍然不能确定边，则选择终点所对应节点优先级最高的边作为优先扩展边；本发明实施例中，节点的优先级由节点的顺序决定，例如，对于程序依赖图g
pdg
的节点集合v1的优先级高于v2；
[0091]
规则d、如果不存在以e
end
为始点的未被遍历的有向边，则继续遍历以e
end
最近的祖先节点为始点的没有遍历的有向边。
[0092]
步骤4-3：如果遍历的边是控制依赖边，则只将边的始点和终点所对应的属性信息添加到程序依赖图序列p中，如果遍历的边是数据依赖边，则依次将数据依赖边的始点、数据依赖边、以及数据依赖边的终点所对应的属性信息添加到程序依赖图序列p中；
[0093]
本发明实施例中，在生成程序依赖图序列p时，不考虑控制依赖边中包含的信息，因为控制依赖边只表示两个节点之间的控制依赖关系，无其他实际意义；而数据依赖边包含代码片段的变量的传递关系，因此在生成程序依赖图序列p时，会保留数据依赖边中包含
的属性信息。
[0094]
步骤4-4、重复步骤4-1至步骤4-3，遍历完所有的有向边，获得程序依赖图序列p。
[0095]
步骤5：针对每一代码片段，利用方法名特征提取模块提取方法名序列包含的特征获得方法名特征向量vm、利用token特征提取模块提取token序列包含的特征获得token特征向量v
t
、以及利用图特征提取模块提取程序依赖图序列包含的特征获得程序依赖图特征向量v
p
，并采用注意力机制将vm、v
t
和v
p
进行组合得到融合特征向量vc；
[0096]
步骤5-1：对于每一代码片段，利用方法名特征提取模块提取方法名序列m包含的特征获得方法名特征向量vm；
[0097]
在本实施方式中，由于方法名序列存在时序关系，因此在方法名特征提取模块中将代码片段的方法名序列中的每一个单词转为词向量并输入到能学习到时序关系的双向长短时记忆网络bi-lstm中，并按照公式(1)获得方法名序列m在正向lstm中i时刻的正向隐藏层向量按照公式(2)获得方法名序列m在反向lstm中i时刻的反向隐藏层向量最后根据公式(3)对方法名序列m所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得方法名特征向量vm，具体公式如下；
[0098][0099][0100][0101]
其中，mi为方法名序列的第i个单词，nm为方法名序列m中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表方法名序列的正向和反向lstm神经网络模型以及相关参数；和分别表示方法名序列的正向lstm神经网络模型和反向lstm神经网络模型在i时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数；vm是最终获得的方法名特征向量。
[0102]
步骤5-2：对于每一代码片段，利用token特征提取模块提取token序列t包含的特征获得token特征向量v
t
；
[0103]
在本实施方式中，由于token序列不存在时序关系，因此在token特征提取模块中将代码片段的token序列中的每一个单词转为词向量并输入到多层感知机mlp中，并按照公式(4)获得token序列t中每个单词在mlp中的隐藏层嵌入向量最后根据公式(5)对token序列t所有单词的隐藏层嵌入向量进行整合，获得token特征向量v
t
，具体公式如下；
[0104][0105][0106]
其中，tj为token序列t的第j个单词；n
t
为token序列t中的单词总数；ω()是利用
skip-gram方法，将文本中的单词转换成词向量的函数；w
t
是mlp的权重参数；tanh()代表tanh函数；是tj在mlp中的隐藏层嵌入向量；maxpooling()代表最大池化函数；v
t
是最终获得的token特征向量。
[0107]
步骤5-3：对于每一代码片段，利用图特征提取模块提取程序依赖图序列p包含的特征获得程序依赖图特征向量v
p
；
[0108]
在本实施方式中，由于程序依赖图序列存在时序关系，因此在图特征提取模块中将代码片段的程序依赖图序列中的每一个单词转为词向量并输入到能学习到时序关系的双向长短时记忆网络bi-lstm中，并按照公式(6)获得程序依赖图序列p在正向lstm中k时刻的正向隐藏层向量按照公式(7)获得程序依赖图序列p在反向lstm中k时刻的反向隐藏层向量最后根据公式(8)对程序依赖图序列p所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得程序依赖图特征向量v
p
，具体公式如下；
[0109][0110][0111][0112]
其中，pk为程序依赖图序列p的第k个单词；n
p
为程序依赖图序列p中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表程序依赖图序列p的正向与反向lstm神经网络模型以及相关参数；和分别表示程序依赖图序列p的正向lstm神经网络模型和反向lstm神经网络模型在k时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数；v
p
是最终获得的程序依赖图特征向量。
[0113]
步骤5-4：通过注意力嵌入模块为每一代码片段的方法名特征向量vm、token特征向量v
t
和程序依赖图特征向量v
p
分配不同的注意力系数，利用注意力机制融合vm、v
t
和v
p
得到代码片段的融合特征向量vc。
[0114]vc
＝αm×vm
+α
t
×
vt+α
p
×vp
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(9)
[0115]
其中，αm为方法名特征向量vm的注意力系数；α
t
为token特征向量v
t
的注意力系数；α
p
为程序依赖图特征向量v
p
的注意力系数；vc为代码片段的融合特征向量。
[0116]
步骤6：通过自然语言特征提取模块提取每一代码片段的自然语言注释序列d的特征，获得自然语言注释特征向量vd；
[0117]
在本实施方式中，由于自然语言注释序列存在时序关系，因此在自然语言特征提取模块中将代码片段的自然语言注释序列中的每一个单词转为词向量并输入到能学习到时序关系的双向长短时记忆网络bi-lstm中，并按照公式(10)获得自然语言注释序列d在正向lstm中t时刻的正向隐藏层向量按照公式(11)获得自然语言注释序列d在反向lstm中t时刻的反向隐藏层向量最后根据公式(12)对自然语言注释序
列d所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得自然语言注释特征向量vd，具体公式如下；
[0118][0119][0120][0121]
其中，dr为自然语言注释序列的第r个单词；nd为自然语言注释序列d中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表自然语言注释序列d的正向与反向lstm神经网络模型以及相关参数；和分别表示正向lstm神经网络模型和反向lstm神经网络模型在r时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数；vd是最终获得的自然语言注释特征向量。
[0122]
步骤7：根据每一代码片段的融合特征向量vc和自然语言注释特征向量vd计算相似度损失函数l(θ)，并根据相似度损失优化更新方法名特征提取模块中的参数、token特征提取模块中的参数、图特征提取模块中的参数、注意力嵌入模块中的参数和自然语言特征提取模块中的参数。
[0123]
相似度损失函数的具体公式如下：
[0124]
l(θ)＝max(0,∈-cos(vc,vd)+cos(vc,v
d-))
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(13)
[0125]
其中，θ表示方法名特征提取模块中的参数、token特征提取模块中的参数、图特征提取模块中的参数、注意力嵌入模块中的参数和自然语言特征提取模块中的参数之和；∈是机器学习中常用的松弛变量，通常设置为0.05；vc是代码片段的融合特征向量，vd是与vc对应的自然语言注释特征向量，v
d-是以负采样的方式获得的与vc不对应的自然语言注释特征向量，max()是最大值函数。
[0126]
步骤8：重复执行步骤5-步骤7，直至相似度损失l(θ)收敛，获得每一代码片段最终的融合特征向量，及具有最优参数的方法名特征提取模块、具有最优参数的token特征提取模块、具有最优参数的图特征提取模块、具有最优参数的注意力嵌入模块和具有最优参数的自然语言特征提取模块；
[0127]
本发明实施例中，在训练方法名特征提取模块、token特征提取模块、图特征提取模块、注意力嵌入模块和自然语言特征提取模块中的参数时，批处理大小设置为64，每一代码片段的方法名序列m、token序列t、程序依赖图序列p以及自然语言注释序列d的最大长度依次设置为6、20、80和50，低于最大长度的序列用特殊标记《pad》填充到最大长度；对于双向lstm单元，隐藏层的大小设置为256；对于mlp，嵌入向量维度被设置为512；利用adam优化器更新参数。
[0128]
步骤9：当用户输入查询语句q时，通过分词工具对用户输入的查询语句进行分词处理并过滤掉其中包含的特殊符号获得自然语言序列q；
[0129]
步骤10：通过自然语言特征提取模块提取自然语言序列包含的特征，获得自然语言特征向量vq；
[0130]
步骤11：计算自然语言特征向量vq与所有代码片段最终的融合特征向量之间的余弦相似度，将余弦相似度最大的若干融合特征向量对应的代码片段作为代码搜索结果，返回给用户。
[0131]
在本实施例中是将与自然语言特征向量vq余弦相似度最大的10个融合特征向量对应的代码片段作为代码检索结果，返回给用户。
[0132]
为了评估本发明提出的代码搜索方法的准确率，本发明实施例中，采用了两个广泛用于代码搜索的评估指标，平均倒数秩mrr(mean reciprocal rank)和r@w(success percentage at w)。
[0133]
其中mrr是国际上通用的对搜索算法进行评估的指标，mrr的值越高，代码搜索的准确率越高；mrr的计算公式如下：
[0134][0135]
其中，q表示用户的一个查询，q
all
是所有查询q的集合，|q
all
|表示q
all
中包含的查询q的数量，frankq表示查询q的frank值；查询q的frank值指的是，查询q返回的代码检索结果中与查询q相符的结果第一次出现的位置，又称最佳命中排名。
[0136]
r@w表示是排名靠前的w个代码检索结果中可能存在多个正确结果的百分比。r@w的值越高，代码搜索的准确率越高，r@w的计算公式如下：
[0137][0138]
其中，q表示用户的一个查询，q
all
是所有查询q的集合，|q
all
|表示q
all
中包含的查询q的数量，frankq表示查询q的frank值；f()表示判别函数，当f()内的判断语句为真时，f()的返回结果为1；当f()内的判断语句为假时，f()的返回结果为0。
[0139]
为了表明本发明提出的代码搜索方法在准确率上的优越性，在相同的数据集上评估了deepcs，mman和本发明提出的代码搜索方法。评估的数据集包括两个，一个是现有的公开数据集codesearchnet，一个是步骤1获得的评估数据集。在codesearchnet数据集上，代码搜索的评估结果如表1所示；在步骤1获得的评估数据集上，代码搜索的评估结果如表2所示；结果表明本发明提出的代码搜索方法在比起deepcs和mman，在准确率具有良好的优越性。
[0140]
表1、codesearchnet数据集上代码搜索的评估结果
[0141][0142]
表1显示，在codesearchnet数据集上，本发明提出的代码搜索算法在mrr、r@1、r@5和r@10评估指标上比deepcs提高了81％、70％、61％和29％，比mman提高了62％、55％、45％和24％；
[0143]
表2、步骤1获得的评估数据集上代码搜索的评估结果
[0144][0145]
表2显示，在步骤1获得的评估数据集上，本发明提出的代码搜索算法在mrr、r@1、r@5和r@10评估指标上比deepcs提高了100％、150％、90％和30％，比mman提高了63％、92％、43％和16％。
[0146]
上述对本发明的一个实施例进行了详细说明。显然，上述实施例仅仅是本发明的一部分实施例，而不是全部的实施例；上述实施例仅用于解释本发明，并不构成对本发明保护范围的限定。基于上述实施例，本领域技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，也即凡在本技术的精神和原理之内所作的所有修改、等同替换和改进等，均落在本发明要求的保护范围内。
技术特征：1.一种基于图序列化的代码搜索系统，其特征在于，该系统包括：数据采集模块，用于采集多个原始代码片段，构成原始代码片段集合；代码片段预处理模块，用于对所述原始代码片段集合中的每一代码片段提取相关特征，包括代码片段的方法名序列、代码片段的令牌token序列和代码片段的程序依赖图pdg；图序列转换器g2sc：用于根据代码片段预处理模块提取的程序依赖图pdg学习代码片段的控制依赖关系和代码片段的数据依赖关系，生成富含代码图结构信息的程序依赖图序列，并将所述程序依赖图序列发送给图特征提取模块；方法名特征提取模块，用于将代码片段预处理模块提取的方法名序列输入到双向长短时记忆网络bi-lstm中提取方法名序列包含的特征，获得方法名特征向量并发送给注意力嵌入模块；token特征提取模块，用于将代码片段预处理模块提取的token序列输入到多层感知机mlp中提取token序列包含的特征，获得token特征向量并发送给注意力嵌入模块；图特征提取模块，用于将程序依赖图序列输入到双向长短时记忆网络bi-lstm中提取程序依赖图序列包含的特征，获得程序依赖图特征向量并发送给注意力嵌入模块；注意力嵌入模块，用于接收所述方法名特征提取模块发送的方法名特征向量、所述token特征提取模块发送的token特征向量、所述图特征提取模块发送的程序依赖图特征向量，并为所述方法名特征向量、token特征向量和程序依赖图特征向量分配不同的注意力系数，得到代码片段的融合特征向量并发送给相似度计算模块；自然语言预处理模块，用于通过分词工具对用户输入的查询语句进行分词处理，并过滤掉其中包含的特殊符号，获得自然语言序列并发送给自然语言特征提取模块；自然语言特征提取模块，用于将自然语言预处理模块提取的自然语言序列输入到双向长短时记忆网络bi-lstm中提取自然语言序列包含的特征，获得自然语言特征向量，并将该自然语言特征向量发送给相似度计算模块；相似度计算模块，用于接收注意力嵌入模块输出的代码片段的融合特征向量和自然语言特征提取模块输出的自然语言特征向量，计算所述自然语言特征向量与所有代码片段的融合特征向量之间的余弦相似度，并将余弦相似度最大的若干融合特征向量对应的代码片段作为代码搜索结果，返回给用户。2.一种基于图序列化的代码搜索方法，其特征在于，该方法包括如下步骤：步骤1：采集代码片段和代码片段所对应的自然语言注释；步骤2：通过分词工具对每一代码片段的自然语言注释进行分词处理并过滤掉分词结果中包含的特殊符号获得每一代码片段的自然语言注释序列d；步骤3：提取每一代码片段的方法名序列m、token序列t和程序依赖图g
pdg
；步骤4：将每一代码片段的程序依赖图g
pdg
输入到图序列转换器g2sc中，利用g2sc学习程序依赖图的控制依赖关系和数据依赖关系，生成富含代码图结构信息的程序依赖图序列p，其中表示所述程序依赖图序列中所有单词的集合，n
p
为程序依赖图序列的单词总数；步骤5：针对每一代码片段，利用方法名特征提取模块提取方法名序列包含的特征获得方法名特征向量v
m
、利用token特征提取模块提取token序列包含的特征获得token特征向
量v
t
、以及利用图特征提取模块提取程序依赖图序列包含的特征获得程序依赖图特征向量v
p
，并采用注意力机制将v
m
、v
t
和v
p
进行组合得到融合特征向量v
c
；步骤6：通过自然语言特征提取模块提取每一代码片段的自然语言注释序列d的特征，获得自然语言注释特征向量v
d
；步骤7：根据每一代码片段的融合特征向量v
c
和自然语言注释特征向量v
d
计算相似度损失函数l(θ)，并根据相似度损失优化更新方法名特征提取模块中的参数、token特征提取模块中的参数、图特征提取模块中的参数、注意力嵌入模块中的参数和自然语言特征提取模块中的参数；步骤8：重复执行步骤5-步骤7，直至相似度损失l(θ)收敛，获得每一代码片段最终的融合特征向量，及具有最优参数的方法名特征提取模块、具有最优参数的token特征提取模块、具有最优参数的图特征提取模块、具有最优参数的注意力嵌入模块和具有最优参数的自然语言特征提取模块；步骤9：当用户输入查询语句q时，通过分词工具对用户输入的查询语句进行分词处理并过滤掉其中包含的特殊符号获得自然语言序列q；步骤10：通过自然语言特征提取模块提取自然语言序列包含的特征，获得自然语言特征向量v
q
；步骤11：计算自然语言特征向量v
q
与所有代码片段最终的融合特征向量之间的余弦相似度，将余弦相似度最大的若干融合特征向量对应的代码片段作为代码搜索结果，返回给用户。3.根据权利要求2所述的基于图序列化的代码搜索方法，其特征在于，所述利用g2sc学习程序依赖图的控制依赖关系和数据依赖关系生成富含代码图结构信息的程序依赖图序列p的方法包括如下步骤：步骤4-1：对于程序依赖图g
pdg
，初始化程序依赖图序列p＝{}，将v1作为程序依赖图序列p的第一个元素p1，并设定程序依赖图序列p的最后一个元素所对应的节点为e
end
；步骤4-2：按照边选取规则递归地从候选边中选择一条边进行扩展，直到所有边均被遍历；步骤4-3：如果遍历的边是控制依赖边，则只将边的始点和终点所对应的属性信息添加到程序依赖图序列p中，如果遍历的边是数据依赖边，则依次将数据依赖边的始点、数据依赖边、以及数据依赖边的终点所对应的属性信息添加到程序依赖图序列p中；步骤4-4、重复步骤4-1至步骤4-3，遍历完所有的有向边，获得程序依赖图序列p。4.根据权利要求3所述的基于图序列化的代码搜索方法，其特征在于，所述候选边指的是以e
end
为始点的未被遍历的有向边。5.根据权利要求4所述的基于图序列化的代码搜索方法，其特征在于，所述边选取规则如下：规则a、回溯边在前向边之前被选择，回溯边指的是有向边的终点已经被遍历的边，前向边指的是有向边的终点未被遍历的边；规则b、当存在多个回溯边或多个前向边时，则根据预设优先级，选择控制依赖边或者数据依赖边；规则c、如果在规则b之后仍然不能确定边，则选择终点所对应节点优先级最高的边作
为优先扩展边；规则d、如果不存在以e
end
为始点的未被遍历的有向边，则继续遍历以e
end
最近的祖先节点为始点的没有遍历的有向边。6.根据权利要求1所述的基于图序列化的代码搜索方法，其特征在于，所述利用方法名特征提取模块提取方法名特征向量v
m
的方法为：在方法名特征提取模块中将代码片段的方法名序列中的每一个单词转为词向量并输入到能学习到时序关系的双向长短时记忆网络bi-lstm中，并按照公式(1)获得方法名序列m在正向lstm中i时刻的正向隐藏层向量按照公式(2)获得方法名序列m在反向lstm中i时刻的反向隐藏层向量最后根据公式(3)对方法名序列m所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得方法名特征向量v
m
，具体公式如下；，具体公式如下；，具体公式如下；其中，m
i
为方法名序列的第i个单词，n
m
为方法名序列m中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表方法名序列的正向和反向lstm神经网络模型以及相关参数；和分别表示方法名序列的正向lstm神经网络模型和反向lstm神经网络模型在i时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数；v
m
是最终获得的方法名特征向量。7.根据权利要求1所述的基于图序列化的代码搜索方法，其特征在于，所述利用token特征提取模块提取token特征向量v
t
的方法为：在token特征提取模块中将代码片段的token序列中的每一个单词转为词向量并输入到多层感知机mlp中，并按照公式(4)获得token序列t中每个单词在mlp中的隐藏层嵌入向量最后根据公式(5)对token序列t所有单词的隐藏层嵌入向量进行整合，获得token特征向量v
t
，具体公式如下；，具体公式如下；其中，t
j
为token序列t的第j个单词；n
t
为token序列t中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；w
t
是mlp的权重参数；tanh()代表tanh函数；是t
j
在mlp中的隐藏层嵌入向量；maxpooling()代表最大池化函数。8.根据权利要求1所述的基于图序列化的代码搜索方法，其特征在于，所述利用图特征提取模块提取程序依赖图特征向量v
p
的方法为：在图特征提取模块中将代码片段的程序依赖图序列中的每一个单词转为词向量并输入到能学习到时序关系的双
向长短时记忆网络bi-lstm中，并按照公式(6)获得程序依赖图序列p在正向lstm中k时刻的正向隐藏层向量按照公式(7)获得程序依赖图序列p在反向lstm中k时刻的反向隐藏层向量最后根据公式(8)对程序依赖图序列p所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得程序依赖图特征向量v
p
，具体公式如下；，具体公式如下；，具体公式如下；其中，p
k
为程序依赖图序列p的第k个单词；n
p
为程序依赖图序列p中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表程序依赖图序列p的正向与反向lstm神经网络模型以及相关参数；和分别表示程序依赖图序列p的正向lstm神经网络模型和反向lstm神经网络模型在k时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数；v
p
是最终获得的程序依赖图特征向量。9.根据权利要求1所述的基于图序列化的代码搜索方法，其特征在于，所述通过自然语言特征提取模块提取自然语言注释特征向量v
d
的方法为：在自然语言特征提取模块中将代码片段的自然语言注释序列中的每一个单词转为词向量并输入到能学习到时序关系的双向长短时记忆网络bi-lstm中，并按照公式(10)获得自然语言注释序列d在正向lstm中t时刻的正向隐藏层向量按照公式(11)获得自然语言注释序列d在反向lstm中t时刻的反向隐藏层向量最后根据公式(12)对自然语言注释序列d所有时刻的正向隐藏层向量和反向隐藏层向量进行整合，获得自然语言注释特征向量v
d
，具体公式如下；下；下；其中，d
r
为自然语言注释序列的第r个单词；n
d
为自然语言注释序列d中的单词总数；ω()是利用skip-gram方法，将文本中的单词转换成词向量的函数；和代表自然语言注释序列d的正向与反向lstm神经网络模型以及相关参数；和分别表示正向lstm神经网络模型和反向lstm神经网络模型在r时刻的正向隐藏层向量和反向隐藏层向量；concat()表示两个向量的串联函数；maxpooling()代表最大池化函数。
技术总结本发明提供了一种基于图序列化的代码搜索系统及方法，涉及代码搜索技术领域。本发明系统及装置通过图序列转换器G2SC学习代码片段的控制依赖关系和数据依赖关系，获得富含代码片段图结构信息的程序依赖图序列，并且比图神经网络更适用于节点少的代码图结构；在特征提取过程中使用注意力机制将方法名特征向量、Token特征向量、以及G2SC提取的程序依赖图特征向量进行融合，使得代码的语义和结构信息能够充分表达，特征提取更完整，有效提升代码搜索的准确率；使用G2SC、双向长短时记忆网络将代码片段的程序依赖图的信息映射到较低维度的特征空间中，可节省深度学习中所消耗的大量算力。算力。算力。
技术研发人员：印莹 李晶莹 时宇岑 赵宇海
受保护的技术使用者：东北大学
技术研发日：2022.07.26
技术公布日：2022/11/1
