自动代码检查

数据挖掘 机器学习 r nlp word2vec 类似文件
2021-09-22 14:48:25

我在机器学习方面有一些经验,主要是聚类和分类器。但是,在 NLP 方面,我还是个新手。

也就是说,我知道处理自然语言所涉及的所有各种问题和困难,例如词性、歧义、否定检测等。我还知道某些表示文本的模型,例如词袋和词向量表示。

虽然我遇到的具体问题是文本问题,但在我看来这不是自然语言问题。相反,我需要比较 1000 多个编程代码文件,以确定它们之间的相似程度。

与我们删除停用词的自然语言处理不同,我们非常关心诸如歧义和否定范围等问题,编程代码没有歧义,至少对于保留关键字,例如“function”,“if ”、“else”、“while”、“end”,核心数学函数和其他运算符(例如“log”、“sin”、“tanh”等)也没有任何歧义。

对于我的问题,我们可以假设所有文件都使用相同的编程语言(比如说 R),并且我们还假设每个编程文件最多包含 250 行代码。

最初的目标是生成一个相关矩阵,显示代码文件彼此之间的相似程度。

在我看来,有两种方法可以解决这个问题:

  1. 快速而简单我建议从每个文本文件中删除:

    • 所有评论,因为我对每个开发人员的个人评论不感兴趣
    • 所有多余的空格,即删除所有格式,确保保留字和代码块之间只有一个空格

    这是我在一个简单的解决方案中要做的唯一预处理。

    然后我建议使用 Doc2Vec 模型将每个文件简化为单个向量,然后通过计算相关系数将各个向量相互比较。

    对于人们来说,这对于一个非常快速和简单的解决方案来说是否合理?如果不是,请告知您将进行哪些其他预处理和/或您将使用什么模型来表示文件。

  2. 更高级简单化解决方案的一个直接缺陷是它过于幼稚。例如:

    • 如果代码 A 和代码 B 具有完全相同的代码(即执行完全相同任务的相同函数,并且所有变量和对象名称相同),但代码 A 的函数与代码 B 文件中列出的顺序略有不同,那么这两个代码文件的逐行比较显然会显示出差异。但是,如果文件 B 中的代码被“重新排序”以使函数的顺序与文件 A 完全相同,那么就不会有任何差异。

    • 代码 A 和代码 B 在逻辑上可以完全相同(即执行逻辑上相同操作和输出的相同数量的函数),只是对象、变量和函数名称不同(毕竟这是每个编码员的主观选择)那么我们又会有很大的不同。例如,在代码 A 的文件中有一个名为 MyFunction(a,b) 的函数,而在代码 B 的文件中有一个名为 CopyMyFunction(x,y) 的函数。现在,如果两个函数执行完全相同的操作(例如,两个输入值的总和),那么逻辑上代码是相同的——只是变量名称不同。

    • 最后是一个更复杂的版本。假设代码 A 的文件中有一个名为 MyAverage(a,b) 的函数执行操作,并作为输出 d 返回:

      c = a + b

      d = c/2

      假设在代码 B 的文件中还有一个名为 MyAverage(a,b) 的函数,它执行相同的计算但只需一步,即

      c = (a + b)/2

      从逻辑上讲,这两个函数产生完全相同的输出,尽管代码 A 分 2 步完成,而代码 B 分 1 步完成。

    以上显然只是可能遇到的问题类型的一些示例。

目的不是确定是否存在抄袭或代码部分是否已从一个代码文件复制到另一个代码文件。相反,如果随后在一个代码文件中发现了严重错误(错误或逻辑错误),那么我需要一种方法来确定在其他代码文件中发生相同错误的可能性有多大,即该错误是否通过从文件中复制而自行传播归档?

人们将如何处理更高级的问题?例如,要解决最后一个问题(即确定两段代码在逻辑上是否等价),我可以看到两种解决方法:

  • 重命名变量和替换。因此,在代码 A 中,由于变量 c 被定义为“a + b”,因此可以通过添加括号将其代入变量 d 的表达式中。替换后,变量 d 可以重命名为变量 c。在这种情况下,代码 B 将与代码 A 相同。
  • 模拟输出。在更复杂的功能中,上述技术可能并不总是有效。相反,如果在给定相同输入的情况下两个函数的输出相同,我们是否可以推断出两者的逻辑在一定的置信度内必须相同?这样做的问题是模拟数百万个输入肯定会非常耗时且昂贵。

除了上述之外,我不知道如何解决这个问题。

关于使用的方法和/或资源有什么想法吗?

我很高兴被引导到有关该问题的良好参考或资源。

2个回答

您可以从MOSS (Measure Of Software Similarity)开始。它可以在一组软件文档中找到类似的软件文档。它有几个很好的特性——空白不敏感、噪声抑制和位置无关。它基于文档指纹识别的更一般概念,其中由文档构造散列。比较文档哈希值。Winnowing 论文中有更技术性的解释

是一篇涵盖其他技术的评论论文,例如 Levenshtein 字符串编辑距离、RTED - 树编辑距离的稳健算法和图形编辑距离。

另一种可能还没有那么先进的替代方法是深度学习系统与输出修改的某种组合,以提供“相似可能性”。

这篇论文Code2vec这篇论文对代码进行了神经网络训练,以可扩展的方式将其编码为向量,以预测其属性,然后根据论文执行一些任务。可以想象,如果您有符合您想要训练的标准的“标记”代码,那么 NN 可能是值得研究的东西(至少从远处)。Code2vec 介绍似乎更适合更复杂示例的问题,因为能够以类似于语言的方式预测输出和比较代码(因为有很多 NN 架构在总结和情感分析方面做到这一点)。