Every plagiarism detector that operates over a corpus larger than a few megabytes faces the same uncomfortable arithmetic. A document of n characters contains roughly n overlapping k-grams. Hashing all of them and storing the result produces an index larger than the corpus itself, which is fine for a homework folder and ruinous for the web. The whole problem of practical fingerprinting reduces to a single question: which hashes do we keep, and which do we throw away, without breaking our ability to detect copies?
The most influential answer to that question is winnowing, introduced by Schleimer, Wilkerson and Aiken (2003) in the paper that also gave the world MOSS, the plagiarism detector that has been running over student programming submissions since 1997. Winnowing is the algorithm sitting underneath an enormous proportion of contemporary similarity detection, and once explained it is genuinely simple. The reason it is worth explaining carefully is that the simplicity is doing real mathematical work: winnowing offers a guarantee that naive sampling schemes cannot match, and that guarantee is the difference between a detector that catches copies and one that hopes to.
The problem winnowing solves
Begin with the standard fingerprinting pipeline. A document is normalised – whitespace stripped, case folded, perhaps comments removed if it is code – and then broken into overlapping k-grams, contiguous substrings of length k. Each k-gram is hashed, typically with a rolling hash so that the hash of the (i+1)th k-gram can be computed from the ith in constant time (Karp and Rabin, 1987). What emerges is a long sequence of integers h1,h2,…,hn, one per position in the document.
If you store all of them, you have an index roughly the size of the document. So you select a subset. The question is how.
The obvious approach, used by Manber’s pioneering sif system, is to keep every hash satisfying h≡0(modp) for some chosen p (Manber, 1994). This is position-independent – a desirable property, because shifting the document by one character should not change which hashes are selected – and on average retains 1/p of the hashes. It is also broken in a specific and important way. There is no upper bound on the gap between selected fingerprints. A long passage may happen to contain no hash that is 0modp, in which case it contributes nothing to the index and any copying within it goes undetected. Schleimer and colleagues found, on a corpus of 500,000 HTML pages, runs of over 29,900 consecutive characters with no selected fingerprint at all – a statistical near-impossibility under uniform random input, but a routine occurrence on real web text, which is full of low-entropy regions (Schleimer, Wilkerson and Aiken, 2003).
This is the gap winnowing closes. The algorithm guarantees that no matter what the input looks like, at least one fingerprint is selected from every window of w consecutive hashes – and therefore that any matching substring longer than a calculable threshold is certain to be detected.
The algorithm
Winnowing in its entirety is one sentence:
In each window of w consecutive hashes, select the minimum. If multiple hashes tie for the minimum, select the rightmost.
That is the whole thing. Slide a window of size w across the hash sequence, one position at a time, and at each step pick the smallest hash inside the window. Save the set of distinct selections as the document’s fingerprints.
To see why this works, consider what happens to a single hash as the window slides over it. Suppose the minimum of window Wi is the hash at position j. As the window advances to Wi+1, position j may still be inside the window – in which case it will very likely still be the minimum, since the odds that a single new hash is smaller than the previous minimum of w values are roughly 1/(w+1). Many overlapping windows therefore select the same fingerprint, and the actual set of distinct fingerprints is much smaller than the number of windows.
On random uniformly distributed input, the expected density – the fraction of hashes selected as fingerprints – is asymptotically w+12. With a window of 100, that is roughly 2% of all hashes retained.
The guarantee
The reason winnowing matters, rather than merely being clever, is the detection guarantee it provides. Set the noise threshold k – the k-gram size, below which matches are dismissed as coincidental – and the guarantee threshold t, the length of match the system promises to find. Then choose the window size
w=t−k+1
Winnowing then guarantees that any substring shared between two documents of length at least t will produce at least one matching fingerprint in both. The proof is short enough to give intuitively: any shared substring of length t spans at least one full window of w consecutive hashes, identical in both documents; the algorithm’s choice depends only on the contents of that window; so both copies select the same fingerprint from it.
This is what Schleimer and colleagues call a local algorithm: the choice of which hash to select from a window depends only on the contents of the window, not on the window’s position in the document or its relationship to anything outside it. Locality is the property that makes the guarantee robust to insertions, deletions and rearrangements – prepending a character to a file shifts every position but does not change which hash is the minimum within any given window.
The paper goes further and proves a lower bound: any local fingerprinting algorithm offering this guarantee must have density at least w+11.5. Winnowing’s w+12 is therefore within 33% of optimal. No clever variant on the same basic idea can do dramatically better, which is one reason the algorithm has remained the default for more than two decades.
A worked example
Consider the lyric “a do run run run, a do run run”, used as the running example in the original paper. After normalisation it becomes the character string
adorunrunrunadorunrunBreaking this into 5-grams produces
adoru, dorun, orunr, runru, unrun, nrunr, runru, unrun, nruna, runad, unado, nador, adoru, dorun, orunr, runru, unrun.
Hashing each (with some hypothetical hash function) gives the sequence
77 74 42 17 98 50 17 98 8 88 67 39 77 74 42 17 98Now apply winnowing with window size w=4. The first window is (77,74,42,17); its minimum is 17. The window slides to (74,42,17,98); still 17. And so on. The full set of selected fingerprints is
17 17 8 39 17– five fingerprints retained from seventeen hashes, with positional information attached to each so that matches can later be highlighted in context. A second document that shares the substring runrunadorun will produce the same minima at the corresponding windows, and the match surfaces. A document that merely happens to share a single 5-gram, but no longer run, almost certainly will not.
The robust variant
The basic algorithm has one failure mode worth knowing about. On low-entropy strings – long runs of a single character, or short repeating patterns – many hashes in a window are identical, which means many ties for the minimum. The “rightmost on ties” rule, which is what keeps the algorithm strictly local, then selects a new fingerprint at almost every step, because each window’s rightmost minimum is in a new position. Density on a string like 0000... approaches 1, which is precisely what the algorithm was designed to avoid.
The fix is the variant Schleimer and colleagues call robust winnowing: when ties occur, prefer the hash that was already selected by the preceding window. This is no longer strictly local – the choice now depends weakly on history – but the detection guarantee survives, because matching substrings still produce matching selections within a bounded distance. Density on a constant string collapses from asymptotically 1 to 1/w, one fingerprint per window-length. MOSS uses robust winnowing in production, and the practical density on a 500,000-page web corpus drops from 0.01986 to 0.01983 – a small improvement on average, but the average conceals the catastrophic worst case that robust winnowing eliminates.
Implementation notes
A production implementation has to be efficient at two things: computing the rolling hash, and finding the window minimum.
For the hash, the standard choice is a Karp–Rabin rolling hash modified so that each character affects every bit of the output. The naive Karp–Rabin formulation lets the final character of a k-gram influence only the low-order bits, which produces poor distribution; the fix is to multiply the previous hash by the base before subtracting the outgoing character and adding the incoming one. The original paper notes that using a non-rolling hash drops fingerprinting throughput by more than a factor of four at k=50, which matters enormously at corpus scale.
For the minimum, the elegant data structure is a monotonic deque (sometimes called the “ascending minima” structure), which yields amortised constant-time updates per window position. In practice, however, the case where the previous window’s minimum is still inside the current window is overwhelmingly common, and a circular buffer with a remembered minimum position handles it in a single comparison; only when the minimum falls off the left edge does the algorithm need to rescan the window. The right-to-left rescan is what implements the “rightmost on ties” rule. The full main loop is perhaps fifteen lines of C.
For 64-bit hashes – necessary once the corpus passes a few hundred million k-grams, to avoid accidental collisions – modular arithmetic over machine words is essentially free. The dominant cost in a real system is not the hashing or the windowing but the index lookup: a typical query fingerprint must be checked against a database of billions of stored fingerprints, which is an information-retrieval problem rather than an algorithmic one.
Choosing k and w
The two free parameters control a three-way trade-off between sensitivity, specificity and storage.
k is the noise threshold: matches shorter than k characters (or tokens, depending on the unit being hashed) cannot be detected at all, by construction. Choose k too low and the index fills with common idioms – “in the case of”, “it is important to note” – that match between unrelated documents. Choose k too high and the algorithm becomes brittle: any local edit within k characters of a match destroys it. The original paper recommends k around 50 characters for prose and somewhat smaller for code; MOSS in practice tunes k per language.
w controls the guarantee. With window size w, any match of length at least t=w+k−1 is certain to be detected; matches between k and t are detected probabilistically. Larger w means stronger insensitivity to local edits and lower storage cost (density falls as 2/(w+1)), at the price of a longer minimum guaranteed match. The practical default of w≈100 with k≈50 produces a guarantee threshold around 150 characters – comfortably below sentence length, comfortably above idiom length.
One useful asymmetry, noted in the original paper but underexploited in many systems: the window size used to build the database does not have to match the window size used at query time. Fingerprinting query documents with a larger window than the database produces a subset of the database fingerprints – fewer lookups per query, at the cost of weaker guarantees. This is how a system can offer a fast approximate scan and a slower exhaustive scan from the same underlying index.
Where winnowing sits in 2026
Twenty-three years after the SIGMOD paper, winnowing remains the workhorse of lexical similarity detection. It is what MOSS uses for code; it is what most academic plagiarism detectors use under the hood for text; it is what git uses (with some adaptation) for similarity-based rename detection; it is the backbone of rsync-style delta compression, and it appears throughout near-duplicate detection on the web. The algorithm has been extended in various directions – to handle approximate matches at the k-gram level, to incorporate semantic information, to operate over learned rather than hash-based representations — but the core idea has survived essentially unchanged. The reason is the one this article opened with: winnowing offers a provable guarantee at near-optimal density, and no alternative built on the same primitive operations has improved meaningfully on either property.
What winnowing cannot do, and was never intended to do, is detect paraphrase. Once an author begins substituting synonyms or restructuring sentences, the k-gram fingerprints diverge from those of the source, and the algorithm – by design – finds nothing. That is a job for the semantic methods that sit above the lexical layer in any modern detection pipeline. But the lexical layer is still doing the heavy lifting on the easy cases, and on the easy cases winnowing is what is doing the work.
Check your work with Viper
Winnowing catches what winnowing was designed to catch. Verbatim reuse, near-verbatim reuse, the long tail of copy-paste with light editing – all of it surfaces cleanly under a well-tuned fingerprint index. What the algorithm cannot see is the passage that has been genuinely reworded, because the fingerprints have moved. Viper plagiarim and AI checker is built for both halves of that problem. The lexical layer scans against an index covering 60 trillion web pages, 16,000-plus open-access journals, millions of internal documents and more than 20 code repositories. The AI detection layer runs separately and currently sits at 99.12% accuracy across Claude, GPT-4, Gemini and the other major models. Coverage spans over 100 languages, pricing starts at 0.16p per credit, and nothing is locked behind a subscription. Try Viper now.
References and further reading:
- Karp, R.M. and Rabin, M.O. (1987) ‘Efficient randomized pattern-matching algorithms’, IBM Journal of Research and Development, 31(2), pp. 249–260.
- Manber, U. (1994) ‘Finding similar files in a large file system’, Proceedings of the USENIX Winter 1994 Technical Conference, pp. 1–10.
- Schleimer, S., Wilkerson, D.S. and Aiken, A. (2003) ‘Winnowing: local algorithms for document fingerprinting’, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 76–85. Available at: https://theory.stanford.edu/~aiken/publications/papers/sigmod03.pdf(opens in new tab).