Deduplication › Exact Deduplication

The simplest form of deduplication removes documents that are bit-for-bit identical. Given a document $d$, you compute a deterministic hash function $h(d)$ and store the hash in a lookup set. If you encounter the same hash again, you discard the duplicate and keep the original.

Exact deduplication works on two levels: the document level and the line or paragraph level.

At the document level, you compute a single hash for the entire document and check it against a set of previously seen hashes. For a document $d$ consisting of a sequence of bytes, we want a compact fingerprint that uniquely identifies its content. SHA-256 maps the document to a fixed-size bit string:

$$h(d) = \text{SHA256}(d) \in \{0,1\}^{256}$$

where:

• $d$: the document represented as a sequence of bytes
• $\text{SHA256}$: the SHA-256 cryptographic hash function
• $\{0,1\}^{256}$: the output space of 256-bit binary strings, giving $2^{256} \approx 10^{77}$ possible fingerprints

You maintain a global set $S$ of seen fingerprints. For each incoming document:

1. Compute $h(d)$
2. If $h(d) \in S$: discard $d$ as a duplicate
3. If $h(d) \notin S$: add $h(d)$ to $S$ and keep $d$

The collision probability for SHA-256 is negligibly small, approximately $2^{-128}$ for any two distinct documents in a corpus of practical size, so treating equal hashes as identical documents is safe in practice. MD5 has known theoretical collisions but produces false positives so rarely in practice that most deduplication pipelines use it for speed. The 128-bit MD5 output is half the size of SHA-256, which matters when your lookup set needs to hold fingerprints for billions of documents: a billion MD5 fingerprints require about 16 GB of memory for the fingerprint store alone, compared to 32 GB for SHA-256.

An implementation requirement is normalization before hashing. Raw documents from different sources may encode the same content with different whitespace, Unicode normalization forms (NFC vs NFD), or HTML entities. Two copies of the same article might differ only in whether smart quotes are used versus straight quotes, or whether newlines are \r\n versus \n. If you hash without normalizing, these formatting differences will cause you to keep both copies, defeating the purpose. This is a deceptively common failure mode: a team that believes their deduplication pipeline is working well may be keeping thousands of near-identical copies that differ only in invisible whitespace or encoding artifacts.

Standard normalizations applied before hashing include:

• Lowercasing the entire text
• Stripping leading and trailing whitespace from each line
• Collapsing multiple consecutive whitespace characters to a single space
• Unicode normalization to NFC (Canonical Decomposition followed by Canonical Composition)
• Stripping HTML entities

The choice of normalization is a policy decision. If you apply aggressive normalization (stripping all punctuation, collapsing to bare words), you will catch more variants of the same content but also risk merging documents that are materially distinct. Most production pipelines normalize conservatively, targeting only the kinds of formatting variation that arise from scraping rather than from content differences.

Document-level exact deduplication catches only perfect or near-perfect copies. It misses the common case where the same article appears with slightly different headlines, updated timestamps, or added comments. For that, you need fuzzy matching.

A subtler form of exact deduplication operates at the line level. Rather than hashing entire documents, you hash individual lines and track which line hashes appear frequently across the corpus. Lines that appear in more than some threshold fraction of documents are removed from all documents.

This catches repeated boilerplate that is not enough to trigger document-level matching. A cookie consent notice appears on millions of pages but constitutes only a few lines in each document. Removing those lines cleans the corpus without discarding the entire document.

The C4 dataset used line-level exact deduplication as one of its core cleaning steps, removing any three-sentence span that appeared more than once in the corpus. This removed approximately 70% of the raw text from Common Crawl before the dataset was released, an indication of just how much redundant boilerplate exists in raw web data. The magnitude of that reduction is striking: the majority of the raw Common Crawl content, by volume, is repeated content. The unique, high-value text is a minority of what you scrape.

Line-level deduplication requires a two-pass algorithm. In the first pass, you collect all line hashes and count their frequencies across the corpus. In the second pass, you revisit each document and remove any line whose frequency exceeds your threshold. This two-pass structure is necessary because you cannot know a line's global frequency until you have seen the entire corpus.

The trade-off is that aggressive line-level deduplication can break document coherence. If you remove every line that appears in more than 1% of documents, you might inadvertently remove common transition phrases, list formatting conventions, or formulaic sentence starters that appear frequently but carry legitimate semantic content in context. The resulting documents may have coherent paragraphs separated by visible gaps where lines were removed, which the model then learns to produce. This is a real problem that appeared in some early C4-trained models, which would occasionally produce text with strange rhythmic gaps corresponding to places where boilerplate lines had been excised.