如何检测文本文件中几乎重复的数量？

Question

我是一名编程老师，想写一个脚本来检测 C/C++/Python 文件中的重复次数。我想可以把任何文件都看作纯文本。

此脚本的输出将是重复出现的相似序列数量。最终，我只对 DRY 指标感兴趣（代码满足 DRY 原则的程度）。

我尝试过简单的自相关，但很难找到合适的阈值。

u = open("find.c").read()
v = [ord(x) for x in u]
y = np.correlate(v, v, mode="same")
y = y[: int(len(y) / 2)]

x = range(len(y))
z = np.polyval(np.polyfit(x, y, 3), x)

f = (y - z)[: -5]
plt.plot(f)
plt.show();

我正在研究不同的策略...... 我还尝试比较每行、每组2行、每组3行之间的相似性......

import difflib
import numpy as np

lines = open("b.txt").readlines()
lines = [line.strip() for line in lines]

n = 3
d = []
for i in range(len(lines)):
    a = lines[i:i+n]
    
    for j in range(len(lines)):
        b = lines[j:j+n]
        if i == j: continue # skip same line
        group_size = np.sum([len(x) for x in a])
        if group_size < 5: continue # skip short lines
        ratio = 0
        for u, v in zip(a, b):
            r = difflib.SequenceMatcher(None, u, v).ratio()
            ratio += r if r > 0.7 else 0        
        d.append(ratio)
        
dry = sum(d) / len(lines)

在下面，我们可以一眼看出一些重复的内容：

w = int(len(d) / 100)
e = np.convolve(d, np.ones(w), "valid") / w * 10
plt.plot(range(len(d)), d, range(len(e)), e)
plt.show()

为什么不使用：

d = np.exp(np.array(d))

因此，difflib 模块看起来很有前途，SequenceMatcher 做了一些魔法（Levenshtein？），但我还需要一些魔法常数（0.7）... 然而，这段代码是 > O(n^2)，对于长文件运行非常慢。

有趣的是，通过细心的观察，重复的次数可以很容易地被识别出来（很抱歉将这位学生的代码作为好坏示例）:

我相信肯定有更聪明的解决方案。

有什么提示吗？

- nowox

---

• 有一个完整的领域，涉及如何做人类觉得容易但我们无法弄清楚如何让计算机做到（机器学习）• 尽管存在一些现有的“代码抄袭检查器”程序，但可以从那里开始研究。 - user202729

你真的只想分析构建代码中的抄袭。如果他们甚至没有将其达到构建状态，那么为什么要费心呢？为什么他们会发送无法构建的代码。 - BNazaruk

我不想检测抄袭。 - nowox

重复的东西会很容易被压缩，对吧？那么您可以使用一个压缩函数来进行驱动，每次添加一段文本后查看其压缩效果如何。如果您添加了一堆行，但在压缩形式下几乎没有占用更多的空间，那么这可能就是一个DRY候选对象。 - Carlos

对我来说，_这个例子_中的代码重复更多是一种风格问题，而不是真正的问题。重复的代码是不同的#if变体，因此这种风格使得单独查看其中一个变体比尝试编织不同#if路径的结果更容易。显然，你不希望人们通过使它们虚假地不同来欺骗重复检查器。 - Hans Olsson

Answer 1

我会基于可压缩性构建一个系统，因为这本质上就是重复出现的东西。现代压缩算法已经在寻找如何减少重复，所以让我们借鉴这项工作。

相似的东西在任何合理的压缩算法下都会良好地压缩，例如LZ。在底层，压缩算法是一段引用自身的文本，你可能可以提取出来。

编写一个程序，将行 [0:n] 馈送到压缩算法中，将其与 [0:n+1] 输出长度进行比较。

当你看到压缩输出增量的长度比输入增量大得多时，你要记下这个位置可能有DRY候选项，如果你可以弄清楚格式，你可以看到它被认为与哪些先前的文本相似。

如果你能确定压缩格式，你就不需要依赖于「大小增长不那么多」的启发式方法，你可以直接提取引用。

如果需要，你可以通过预处理输入来查找具有不同名称的类似结构，例如通过规范化名称。然而，我预见这可能会变得有点混乱，所以这是v2功能。预处理也可用于规范化格式。

- Carlos

---

从可能非常复杂的系统中轻松提取指标的好方法。 - Neil

你是将窗口向下滑动，还是始终将比较窗口的起始位置保持在第0行？此外，我怀疑规范化可能非常关键，因为您希望压缩性的任何变化都来自逻辑结构，而不是像变量和方法名称等噪声。 - bob

现代压缩算法是否也是这样工作的呢（我不知道，这是一个诚实的问题）？也就是说，如果你添加了越来越多的行，并且你得到了一个很大的压缩跳跃，那么你知道这是因为最近的行高度重复，而不是压缩算法想出如何更好地压缩整个文件直到该点，感谢最新的行？ - bob

好问题，我怀疑有不止一种方法可以做到。 - Carlos

Answer 2

看起来你正在选择一条漫长的路。我不会走那条路。

在分析之前，我会考虑尝试压缩代码。这可以完全消除变量名称、额外空格、格式和甚至轻微的逻辑重组等影响。

另一种方法是比较学生的字节码。但这可能不是一个很好的主意，因为结果很可能需要进一步清理。

Dis是一个有趣的选项。

我最可能停留在比较他们的AST上。但对于短函数，ast 可能会出现误报。因为它们的结构可能太相似了，所以请考虑使用其他一些简单的东西检查短函数。

此外，我会考虑使用Levenshtein距离或类似的东西来计算学生的字节码/源代码/AST/dis之间的差异。这将是什么？几乎是O(N^2)？不应该有问题。

或者，如果需要，可以将其更复杂化，计算学生A的每个函数与学生B的每个函数之间的距离，并突出显示距离太短的情况。但这可能不是必须的。

通过简化和规范化输入，更多的算法应该会返回良好的结果。如果一个学生足够优秀，可以拿别人的代码并重组变量、逻辑甚至改进算法，那么这个学生已经足够理解代码，可以在未来无需帮助地使用和保护它。我想，这就是老师希望学生之间交换的帮助类型。

- BNazaruk

Answer 3

您可以将其视为输入本身与最长公共子序列问题的变体，其中不允许每个元素与自身匹配。这保留了标准算法的最优子结构，因为它可以被表述为非传递性的“相等”，而算法从不依赖于传递性。

因此，我们可以编写以下简单实现：

import operator

class Repeat:
  def __init__(self,l):
    self.l=list(l)
    self.memo={}

  def __call__(self,m,n):
    l=self.l
    memo=self.memo
    k=m,n
    ret=memo.get(k)
    if not ret:
      if not m or not n: ret=0,None
      elif m!=n and l[m-1]==l[n-1]:  # critical change here!
        z,tail=self(m-1,n-1)
        ret=z+1,((m-1,n-1),tail)
      else: ret=max(self(m-1,n),self(m,n-1),key=operator.itemgetter(0))
      memo[k]=ret
    return ret

  def go(self):
    n=len(self.l)
    v=self(n,n)[1]
    ret=[]
    while v:
      x,v=v
      ret.append(x)
    ret.reverse()
    return ret

def repeat(l): return Repeat(l).go()

您可能想通过删除空格（除了字母之间的空格），删除注释，或者用标准化标签替换每个唯一标识符来规范化代码行。您还可以省略像在 C/C++ 中的 } 这样的琐碎行以减少噪音。最后，对称性应该只允许处理例如 m>=n 的情况。

当然，这个问题也有"真正的"答案和真正的研究！

- Davis Herring

Answer 4

挑战框架：我不确定你应该这样做

对于你自己来说，这将是一个有趣的编程挑战，但如果你打算将其用作教学工具，我不确定是否合适。从DRY原则中，“重复”的定义并不明确，很难在计算机程序中进行全面测试。人类的定义是基本上“在适当的层次上未正确抽象代码，通过某种类型的代码重复表现出来，无论是重复精确块还是重复相同的想法，或者介于两者之间”，我认为目前没有人能够使它良好运行，以便将其用作教授DRY方面良好习惯的工具而不会混淆学生或教授不良习惯。因此，我认为现在这是人类的工作，因为对我们来说很容易，但对计算机来说很难，至少现在是这样...

话虽如此，如果你想尝试一下，首先要为自己定义要捕捉的错误的要求，它们将是什么样子，好的代码看起来像什么，并定义可接受的假阳性和假阴性率，并在各种代表性输入上测试你的代码，验证你的代码是否足够适合你的预期用途。但我猜你真正想要的不仅仅是简单的标记重复标记，如果你想有成功的机会，我认为你需要清楚地定义你要寻找的内容以及如何衡量成功，然后验证你的代码。如果教学工具没有真正教授正确的课程，它可能会造成很大的伤害。例如，如果你的工具只是鼓励学生混淆他们的代码，以便它不被标记为违反DRY，或者如果该工具不标记错误的代码，那么学生就会认为它是可以的。或者，如果它标记了实际上编写非常好的代码。

更具体地说，哪些重复类型是可以接受的，哪些是不可以接受的？在代码中重复使用“if”或“for”或其他语法是好还是坏？变量和函数/方法是否可以具有相同的子字符串名称（例如average_age、average_salary等）？在重复多少次之后，应该进行抽象，并且在进行抽象时需要什么样的抽象以及在什么层次上（例如一个简单的方法，或一个functor，或一个完整的其他类，或一个完整的其他模块）？更多的抽象总是更好，还是完美有时会成为按时按预算的敌人？这是一个非常有趣的问题，但也是一个非常困难的问题，老实说我认为这是一个研究问题，这就是我提出挑战框架的原因。

编辑： 如果你一定想要尝试这个工具，你可以将其作为一个教学工具。不一定是按照你原来的意图，而是通过展示你在创建工具时编写的DRY代码的坚持，并通过向学生介绍DRY的细微差别和自动化代码质量评估的缺点，透明地告诉他们有关你的质量评估工具限制的方式来引入这些知识。我不会像一些教授使用抄袭检测工具那样使用它，将其视为数字神谕，对学生代码质量的评估毫无争议。这种方法可能会对学生造成更多的伤害而不是好处。

- bob

Answer 5

我建议采用以下方法：假设重复行至少应为3行。然后我们对每3行进行哈希。如果哈希重复，则写下它出现的行号。最后，将相邻的重复行号连接在一起，以获得更长的序列。

例如，如果您在第100-103行和第200-203行上有重复块，则会得到{HASH1:(100,200), HASH2:(101,201)}（第100-102行和第200-202行将产生相同的值HASH1，而HASH2覆盖了第101-103行和第201-203行）。当您连接结果时，它将生成一个序列（100,101,200,201）。在其中找到单调子序列，您将得到((100,101),(200,201))。

由于没有使用循环，因此时间复杂度是线性的（哈希和字典插入都是O(n)）。

算法：

逐行读取文本 按以下方式进行转换： - 去除空格 - 去除空行，并保存映射到原始文本以备将来使用

对每3行转换后的文本进行合并，并计算其哈希值 过滤出哈希值重复超过一次的行（这些是至少重复3行的内容） 找到最长的连续序列，并呈现重复的文本

代码:

from itertools import groupby, cycle
import re

def sequences(l):
    x2 = cycle(l)
    next(x2)
    grps = groupby(l, key=lambda j: j + 1 == next(x2))
    yield from (tuple(v) + (next((next(grps)[1])),) for k,v in grps if k)

with open('program.cpp') as fp:
    text = fp.readlines()

# remove white spaces
processed, text_map = [], {}
proc_ix = 0
for ix, line in enumerate(text):
    line = re.sub(r"\s+", "", line, flags=re.UNICODE)
    if line:
        processed.append(line)
        text_map[proc_ix] = ix
        proc_ix += 1

# calc hashes
hashes, hpos = [], {}
for ix in range(len(processed)-2):
    h = hash(''.join(processed[ix:ix+3])) # join 3 lines 
    hashes.append(h)
    hpos.setdefault(h, []).append(ix)  # this list will reflect lines that are duplicated

# filter duplicated three liners 
seqs = []
for k, v in hpos.items():
    if len(v) > 1:
        seqs.extend(v) 
seqs = sorted(list(set(seqs)))

# find longer sequences
result = {}
for seq in sequences(seqs):
    result.setdefault(hashes[seq[0]], []).append((text_map[seq[0]], text_map[seq[-1]+3]))

print('Duplicates found:')
for v in result.values():
    print('-'*20)
    vbeg, vend = v[0]
    print(''.join(text[vbeg:vend]))
    print(f'Found {len(v)} duplicates, lines')
    for line_numbers in v:
        print(f'{1+line_numbers[0]} : {line_numbers[1]}')

- igrinis

---

那么，接近但不完全重复的情况怎么办——用不同的变量或不同的比较值改变逻辑块的重复？另外，长度大于或小于三行的块的重复怎么处理？ - bob

在预处理阶段，可以通过应用语法解析器来解决变量名称和/或常量更改等代码微小变化的问题。处理后的代码不必遵守语言规则，因此在C++中，花括号可能会被删除，变量名称可以设置为相同等。长度大于三行的块通过连接重复序列来处理（请参见示例）。短于3行的序列不实际报告，但从理论上讲，可以对每一行进行哈希。算法并没有真正改变。 - igrinis