How Noplag detects plagiarism: winnowing fingerprints, explained

The hard part of plagiarism detection isn't comparing two documents — it's comparing one document against more than 150 million of them, fast enough that a check finishes while you're still looking at the progress bar. The open-source Noplag engine solves that with an algorithm from a 2003 Stanford paper: winnowing, the same family of technique behind MOSS, the code plagiarism detector that computer-science departments have used for decades.

This post walks through how it works. Everything here is implemented in the public engine, so you can read the production version alongside the toy one below.

The problem: exact search is too brittle, full comparison too slow

Naive approaches fail in one of two ways. Searching for exact sentences breaks the moment a copier changes one word or a line break moves. Computing a proper alignment between your document and every candidate is accurate but hopeless at corpus scale — you'd need to run a diff against more than 150 million documents per check.

Fingerprinting splits the difference. Instead of storing text, we store a small set of hashes per document — chosen so that any two documents sharing enough consecutive text are guaranteed to share at least one hash. Matching becomes a set-intersection problem, which a database index handles in milliseconds. Only the handful of candidates that share fingerprints go on to the expensive, character-exact alignment stage.

Step 1: normalize and shingle

First the text is normalized — lowercased, punctuation and whitespace collapsed — so trivial edits don't change the fingerprints. Then it's split into overlapping word sequences called k-grams (shingles):

def shingles(words: list[str], k: int = 5):
    for i in range(len(words) - k + 1):
        yield i, " ".join(words[i : i + k])

With k=5, the sentence "the quick brown fox jumps over the lazy dog" produces "the quick brown fox jumps", "quick brown fox jumps over", and so on. Each shingle is hashed to a 64-bit integer. Copy any five-word run verbatim and you've copied a shingle — and its hash.

Step 2: winnow

Storing every shingle hash would work, but it's a lot of hashes — roughly one per word. Winnowing keeps a fraction of them while preserving the detection guarantee. Slide a window of w consecutive hashes over the document and keep the minimum hash in each window:

def winnow(hashes: list[int], w: int = 16):
    picked = set()
    for i in range(len(hashes) - w + 1):
        window = hashes[i : i + w]
        # rightmost minimum, per the original paper
        j = max(
            range(len(window)),
            key=lambda x: (window[x] == min(window), x),
        )
        picked.add((i + j, window[j]))
    return picked

The minimum of a window barely moves as the window slides, so consecutive windows mostly pick the same hash — the selection is sparse. But because every window contributes its minimum, the guarantee holds:

Any match at least w + k − 1 words long shares at least one fingerprint with the original — no matter where it starts.

That's the property that makes retrieval trustworthy. It's not "we'll probably find it." Matches longer than the threshold cannot evade the index.

Step 3: intersect, then verify

Each document's fingerprints live in a Postgres index. A check fingerprints your text the same way, intersects against the corpus, and ranks candidate documents by how many fingerprints they share. Only those candidates — a few dozen, not a few million — proceed to full alignment, which recovers the exact matched passages with character positions on both sides. Fingerprints find the needle's haystack; alignment finds the needle.

One production wrinkle worth knowing: some five-word shingles are so common ("in the case of the") that they match half the corpus and carry no signal. The engine tracks document frequency and drops these non-discriminative fingerprints at query time — the same reason web search engines ignore stop words.

What this design honestly can't do

Winnowing detects verbatim and near-verbatim copying — text that survives normalization with five-word runs intact. Rewrite a passage sentence by sentence in your own words and the shingles change completely; the fingerprints won't match. We say this plainly everywhere: paraphrase and semantic detection are roadmap work built on different machinery (near-duplicate hashing, then embedding retrieval), and they'll ship when they pass our published evaluation, not before.

If you want to go deeper, the engine docs cover the full pipeline, and the parameters above — k, w, the frequency filter — are all configurable in a self-hosted deployment.