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

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)运行速度非常慢。

有趣的是，用细心的眼睛很容易识别重复的数量（很抱歉这位学生把他的代码当作一个很好的坏例子）：

我确信有一个更聪明的解决方案。

有什么提示吗？

Answer 1

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

• 相似的东西在任何合理的压缩算法下都会得到很好的压缩，例如LZ。在幕后，压缩算法是一个引用其自身的文本，您可以将其提取出来。

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

• 当您看到压缩输出的增量长度增加远小于增量输入时，您会注意到该位置可能有一个 DRY 候选者，而且如果您能弄清楚格式，您可以看到它之前的文本被认为类似于。

• 如果你能弄清楚压缩格式，你就不需要依赖“大小不会增长那么多”的启发，你可以直接拉出参考文献。

• 如果需要，您可以通过预处理输入（例如通过标准化名称）来找到具有不同名称的相似结构。不过我预计这会变得有点混乱，所以这是 v2 功能。预处理还可用于标准化格式。