检测“相似”源代码的集群

机器算法验证 假设检验 聚类
2022-03-22 22:52:54

假设我有 400 名学生(在一所大大学里)必须做一个计算机科学项目,并且他们必须独自工作(没有学生群体)。一个项目示例可以让“在 fortran 中实现快速傅立叶变换算法”(我知道,这听起来并不性感,但这让我的问题更简单)。我是纠正者,我想发送例程来检查是否有学生群体提出了“太相似而无法真正独立编写”的实现。

这是对集群的无监督搜索。我认为问题更多是关于使用哪些属性,而不是使用哪种聚类算法。我要做的第一件事是逐字母直方图。理想情况下,由于作弊者比这更聪明,我最终会尝试精心选择字母的随机排列,看看是否存在与字母直方图(带有排列)的良好匹配。还有那些不探索代码结构的人,只有字母的边缘分布......你有什么解决方案?是否有专门针对该问题的现有软件或软件包?(实际上在我过去的计算机科学老师声称他们有那种类型的工具,但我现在怀疑他们有一些非常简单的东西)

我猜软件开发的律师也有这类问题(不是 1000 名学生,而是 2 个大代码……这让事情变得更难了)?

2个回答

显而易见的预处理步骤是合并真正相同的文件。

之后的关键是规范化在某个时候,学生将开始重构代码、重命名变量等。或者改写评论。字母直方图受此影响太大(另外它会捕获很多语言属性)。

一种常见的技术是使用特定于语言的解析器并将源代码转换为抽象语法树。然后从中提取特征。并且也许并行地分别分析评论。

然后是基于行的“最长公共子序列”方法。如果您在单行上具有相当好的相似性,则可以搜索任意两个文件的最长公共子序列。这也将产生许多匹配。

在反抄袭界,我之前遇到过“图同构”的概念。也许你也可以看看。

LCS - 最长公共子序列也是可能的。但是尝试比较所有这些解决方案,看看什么是最好的:)