Question: I am a programming teacher, and I would like to write a script that detects the amount of repetition in a C/C++/Python file. I guess I can treat any file as pure text. The script's output would be the number of similar sequences that repeat. Eventually, I am only interested in a DRY's metric (how much the code satisfied the DRY principle). Naively I tried to do a simple autocorrelation but it would be hard to find the proper threshold. 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();   So I am looking at different strategies... I also tried to compare the similarities between each line, each group of 2 lines, each group of 3 lines ... 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)  In the following, we can identify some repetition at a glance: 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()   Why not using: d = np.exp(np.array(d))   Thus, difflib module looks promising, the SequenceMatcher does some magic (Levenshtein?), but I would need some magic constants as well (0.7)... However, this code is > O(n^2) and runs very slowly for long files. What is funny is that the amount of repetition is quite easily identified with attentive eyes (sorry to this student for having taken his code as a good bad example):  I am sure there is a more clever solution out there. Any hint?

Answer: I would build a system based on compressibility, because that is essentially what things being repeated means. Modern compression algorithms are already looking for how to reduce repetition, so let's piggy back on that work.  Things that are similar will compress well under any reasonable compression algorithm, eg LZ. Under the hood a compression algo is a text with references to itself, which you might be able to pull out.  Write a program that feeds lines [0:n] into the compression algorithm, compare it to the output length with [0:n+1].  When you see the incremental length of the compressed output increases by a lot less than the incremental input, you note down that you potentially have a DRY candidate at that location, plus if you can figure out the format, you can see what previous text it was deemed similar to.  If you can figure out the compression format, you don't need to rely on the "size doesn't grow as much" heuristic, you can just pull out the references directly.  If needed, you can find similar structures with different names by pre-processing the input, for instance by normalizing the names. However I foresee this getting a bit messy, so it's a v2 feature. Pre-processing can also be used to normalize the formatting.