python - 如何衡量两个 python 代码块之间的相似性？

Question

许多人会想衡量代码相似性以发现剽窃，但我的目的是将一组 Python 代码块(比如对同一编程问题的答案)归为不同的类别，并区分学生采用的不同方法。

如果您知道如何实现这一目标，请在此分享，我将不胜感激。

Answer 1

您可以选择任何您喜欢的方案，基本上对代码块的内容进行哈希处理，并将具有相同哈希值的代码块归入同一类别。

当然，结果相似的结果在很大程度上取决于您如何定义散列函数。例如，一个真正愚蠢的哈希函数 H(code)==0 会将所有内容放在同一个容器中。

一个困难的问题是找到一个哈希函数，以一种在自然意义上看起来相似的方式对代码块进行分类。经过大量研究，没有人找到比当我看到它们时我会知道它们是否相似更好的判断方法。

您肯定不希望它依赖于布局/缩进/空白/注释，或者对这些稍作更改就会对 block 进行不同的分类，即使它们的语义内容相同。

人们通常使用三种主要方案来查找重复(或相似)代码:

• 基于指标的方案，通过计算指标计算各种类型的运算符和操作数来计算哈希值。 (注意:这使用词汇标记)。这些通常仅在功能级别运行。据我所知，没有基于此的实用工具。

• 基于词法的方案，将输入流分解为词素，将标识符和文字转换为固定的特殊常量(例如，将它们视为未区分的)，然后基本上对 N-gram(N 个标记的序列)进行哈希处理这些序列。许多克隆检测器基本上都是基于这个想法；它们工作得很好，但也会找到愚蠢的匹配项，因为没有什么强制与程序结构边界对齐。顺序

   return ID; }  void ID ( int ID ) {
  

是一个 11 克，经常出现在类似 C 的语言中，但显然不是有用的克隆)。结果是往往会出现误报，例如，您在没有匹配项的情况下获得了声称的匹配项。

• 基于抽象语法树的匹配(对子树进行哈希处理)，它通过使用直接表示语言结构的 AST 自动将克隆与语言边界对齐。 (我是这方面的原始论文的作者，并基于这个想法构建了一个商业产品 CloneDR，请参阅我的简历)。这些工具的优势在于它们可以在匹配过程中匹配包含不同长度标记序列的代码，例如，一个语句(任意大小)被另一个语句替换。

本文提供了对各种技术的调查:http://www.cs.usask.ca/~croy/papers/2009/RCK_SCP_Clones.pdf .它表明基于 AST 的克隆检测工具似乎最有效地产生人们认为是相似代码块的克隆，这似乎是 OP 特别感兴趣的关键；见表 14。

[有匹配控制和数据流图的基于图的方案。他们应该可以产生更好的匹配，但显然在实践中并没有做得更好。]