Deduplication in Large Text Corpora

Deduplication is three problems wearing one name, and the reason people get poor results is that they solve the easy one and assume they have finished. Hashing catches identical bytes. Almost nothing in a real corpus is identical bytes.

Three kinds of duplicate

Why bother. For a retrieval corpus, duplicates crowd out the result set: ask for the top ten and get the same passage ten times, which reduces the answer’s evidence base to one document while costing ten chunks of context. For training data, the deduplication literature is the reason this is standard practice — Lee et al., “Deduplicating Training Data Makes Language Models Better” (2021), sets out both an exact-substring method built on a suffix array and a near-duplicate method built on MinHash, and Kandpal et al. (2022) tie duplication in training data to memorisation and therefore to privacy exposure.

Exact, and the normalisation it needs

“Byte-identical” is doing a lot of work. Two copies of the same text differ by a BOM, by CRLF versus LF, by NFC versus NFD composition of accented characters, by non-breaking spaces, by trailing whitespace. Normalise before hashing or the exact pass finds almost nothing:

import hashlib, re, unicodedata

ZERO_WIDTH = dict.fromkeys(map(ord, "\u200b\u200c\u200d\ufeff\u00ad"), None)

def canonical(text: str) -> str:
    text = unicodedata.normalize("NFKC", text)   # fi -> fi, NFD -> NFC
    text = text.translate(ZERO_WIDTH)            # ZWSP, ZWNJ, BOM, soft hyphen
    text = text.replace("\u00a0", " ")            # NBSP -> space
    text = re.sub(r"[ \t]+", " ", text)
    text = re.sub(r"\r\n?", "\n", text)           # CRLF/CR -> LF
    text = re.sub(r"\n{3,}", "\n\n", text)
    return text.strip().casefold()

def exact_key(text: str) -> str:
    return hashlib.sha256(canonical(text).encode("utf-8")).hexdigest()

NFKC rather than NFC is deliberate here and wrong elsewhere: the compatibility mapping folds the fi ligature, full-width Latin and superscript digits into their plain forms, which is what you want for a dedupe key and not what you want for text you will show to a user. Compute the key from a canonical form; store the original.

MinHash: estimating Jaccard cheaply

Near-duplicate detection starts by treating a document as a set of shingles — overlapping n-grams, typically five words. Two documents that share most of their five-word runs are near-duplicates, and the similarity measure is Jaccard: the size of the intersection over the size of the union.

Computing Jaccard exactly for every pair is quadratic and the sets are large. MinHash, due to Broder (1997), replaces each set with a short signature: apply k independent hash functions to every shingle and keep the minimum value under each. The probability that two sets produce the same minimum under a random hash is exactly their Jaccard similarity, so the fraction of matching positions in two k-length signatures is an unbiased estimate of it. With k = 128 the standard error is on the order of 1/√k ≈ 0.09; with k = 256 it is about 0.06. That is the only accuracy knob, and it costs linear time and memory.

LSH: the band/row arithmetic

A signature makes each comparison cheap but there are still n(n−1)/2 of them. Locality-sensitive hashing turns the search into a lookup. Split the k-position signature into b bands of r rows each (k = b × r), hash each band, and put the document id in a bucket per band. Two documents are candidates if they collide in any band.

The probability of that is worth writing down, because it is the whole design. For documents with true Jaccard s:

P(candidate) = 1 - (1 - s^r)^b

# s = 0.9, b = 16, r = 8  ->  1 - (1 - 0.430)^16 = 0.99997   (found)
# s = 0.5, b = 16, r = 8  ->  1 - (1 - 0.004)^16 = 0.0616    (skipped)
# threshold where the curve crosses 0.5:  s* ≈ (1/b)^(1/r)
#   (1/16)^(1/8) = 0.707

That S-curve is the point of the scheme: it is nearly a step function, so pairs above the threshold are almost always found and pairs below it almost never generate work. Choose the threshold you want first, then pick b and r with (1/b)^(1/r) near it. Raising r sharpens the curve and misses more borderline pairs; raising b lowers the threshold and costs more candidate comparisons.

The implementation

datasketch implements both pieces; the parameters above map onto its constructor arguments directly, and it will pick b and r for a threshold if you let it.

from datasketch import MinHash, MinHashLSH

K, THRESHOLD, NGRAM = 128, 0.8, 5

def shingles(text: str, n: int = NGRAM):
    words = canonical(text).split()
    for i in range(len(words) - n + 1):
        yield " ".join(words[i:i + n]).encode("utf-8")

def signature(text: str) -> MinHash:
    m = MinHash(num_perm=K)
    m.update_batch(list(shingles(text)))
    return m

def dedupe(docs: dict[str, str]) -> dict[str, str]:
    """docs: id -> text. Returns id -> canonical id it duplicates."""
    lsh = MinHashLSH(threshold=THRESHOLD, num_perm=K)
    sigs, duplicate_of = {}, {}
    for doc_id, text in docs.items():
        m = signature(text)
        for other in lsh.query(m):                  # candidates only
            if m.jaccard(sigs[other]) >= THRESHOLD: # verify exactly
                duplicate_of[doc_id] = duplicate_of.get(other, other)
                break
        else:
            lsh.insert(doc_id, m)                   # a new representative
            sigs[doc_id] = m
    return duplicate_of

Two details that decide whether this works. The for/else means a document only becomes a representative if it matched nothing — which keeps the cluster structure a forest rather than a tangle. And the explicit m.jaccard(...) check after the LSH query is not redundant: LSH returns candidates, and at any threshold below about 0.9 a meaningful share of them are false positives.

Memory: K 32-bit values per document is 512 bytes at K = 128, so ten million documents is around 5 GB of signatures plus the LSH buckets. Past that, shard by band into a key-value store or switch to SimHash — Charikar’s 64-bit variant, which Manku et al. (2007) describe using for web-scale near-duplicate detection with a Hamming-distance threshold — which trades resolution for a signature that fits in a machine word.

Which copy to keep

Detection is the easy half. Deciding which member of a duplicate cluster survives is a policy question and it should be an explicit function, not an accident of iteration order. Reasonable criteria, roughly in order: the longest extraction (a truncated copy is worse than a complete one), then the most authoritative source, then the earliest first_seen so that stable ids do not churn between runs.

Do not delete the losers. Keep them as rows pointing at the representative, because a user who searches for the URL of a suppressed copy still needs an answer, and because duplicates you removed at the document level can reappear at the chunk level and you will want to see the history when they do.

Set the threshold deliberately too, and set it per corpus rather than per taste. Around 0.9 catches only near-identical copies and is the safe default when suppressing a document has consequences. Around 0.7 starts catching genuinely different documents that share a large template — different contracts on the same form, different releases of the same report — and whether that is a duplicate depends entirely on what a user is looking for. The way to decide is to sample fifty pairs at each candidate threshold and read them; it takes an hour and it is the only method that answers the question for your data.

One last property to preserve: deduplication must be deterministic across runs, or it becomes a source of churn all by itself. The representative chosen for a cluster should be a pure function of the cluster’s members, not of the order in which documents were processed — otherwise a re-run with a slightly different iteration order suppresses a different member, every downstream chunk id changes, and you re-embed a corpus that did not change.