重复程序

Question

我想编写一个代码，可以找到代码文件之间的相似性（也许可以通过百分比或至少 "guess" 找到可以复制哪些文件的相似性），我运行它用于 30 个文件每个文件最多 500 行。我想识别重复文件（或怀疑重复的文件）。

我遇到几个问题：

spacing：一个代码可以有多个空格或换行符
评论：有评论的文件与无评论或不同评论的文件

这 2 个问题我认为我可以通过从代码中删除所有空格、换行符和注释来解决，但后来我遇到了以下问题

试图"hide"相似度的文件，以下面2个C文件为例

代码 1:

void main()
{
    int x;
    int y;
    scanf("%d", &x);
    switch(x)
    {
        case 1:
        //some code
        break;

        case 2:
        //some code
        break;
    }
}

代码2：

#define ONE 1
#define TWO 2
void main()
{
    int a, b;
    scanf("%d", &a);
    switch(a)
    {
        case ONE:
        //some code
        break;

        case TWO:
        //some code
        break;
    }
}

我会感谢任何帮助（可能使用现有工具或通过建议算法）

谢谢。

Answer 1

您可能有兴趣查看 MOSS，斯坦福大学开发的一个系统，它试图准确解决您的问题。

但是，如果您对开发自己的方法感到好奇，这里有一些想法可以解决您目前提到的问题：

将代码解析为 AST，以便您可以轻松地将代码作为数据结构进行操作，并忽略空格等问题。
您可以通过自己重命名变量来检测变量名称的变化，使用某种方案来保证基于声明顺序和作用域的唯一命名。如需一些灵感，请参阅 De Bruijn indices。

重复程序

Duplicate Programs

algorithm

code-duplication

duplicates

text-parsing

approximation