Topic 4.3
Cleaning and De-duplicating
In one line
Cleaning removes control characters, stray whitespace and headers repeated on every page. De-duplication removes exact copies with a hash and near-copies by comparing sets of overlapping word groups (shingles) with Jaccard similarity.
Think of it like this
Before photocopying a stack of forms you take out the staples, flatten the creases and throw away the duplicates that someone filed twice. Cleaning is that tidying; de-duplicating is the second pile. Neither adds information, but both stop the copier (here, the index) from wasting effort and stop the same page being found five times.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Cleaning
- Removing text that carries no meaning: control characters, extra whitespace, repeated headers.
- Control character
- An invisible character with code 0 to 31 (except tab and newline), such as NUL or form feed.
- Hash
- A fixed-size number computed from a text. Equal texts always give equal hashes.
- FNV-1a
- A very small, fast 32-bit hash. Used here so every language prints the same value.
- Normalise
- Make superficial differences disappear: lower-case, collapse spaces.
- Shingle
- A window of k consecutive words taken from a text.
- Jaccard similarity
- Size of the overlap of two sets divided by the size of their union, from 0 to 1.
- Near-duplicate
- Two texts that are almost, but not exactly, the same.
Step by step
01Step 1: remove what cannot be read
Delete control characters but keep newlines so the line structure survives. The form-feed character that marks a page break in many extractions goes here.
import re
page = re.sub(r"[\x00-\x08\x0b-\x1f]", "", page) # keeps tab (09) and newline (0a)02Step 2: tidy each line
Collapse runs of spaces and tabs, trim the ends and drop empty lines. Shops open at 7 am<TAB>and close becomes Shops open at 7 am and close.
03Step 3: find repeated lines
Count, for each line, on how many pages it appears. A line on more than half of the pages is a running header or footer. Print what you removed and from how many pages, so a human can disagree.
04Step 4: hash the normalised text
Lower-case, keep only words, join with single spaces, then hash. Equal hash means an exact duplicate after normalisation. Keep a dictionary from hash to the first document that had it.
05Step 5: turn texts into shingle sets
Take every window of k words. For 3-word shingles a text of n words has n - 2 of them. Use sets so repeats count once.
06Step 6: compare with Jaccard and decide
overlap / union. The example shows the same pair at k = 1 (0.818) and k = 3 (0.652). Choose k and the threshold by looking at real pairs from your corpus.
Try it yourself
- 1
Change the threshold of repetition
In the first example, change
count * 2 > len(pages)tocount * 3 > len(pages) * 2(two thirds of the pages). Does the header still go? Now make one page lack the header and try again. - 2
Make two texts duplicates
In the second example, add a fifth document that is the
othertext with every word upper-case. Predict its hash line before running: new, or an exact duplicate ofother? - 3
Move the k
Change the shingle size from 3 to 2 and then 5 for the
rewordedpair. Write down the three Jaccard values. Which k separates the reworded pair from the unrelated one by the widest margin? - 4
Use the lab
In the lab, press Search and open the similarity grid. Which two passages are most alike? Is a threshold of 0.95 enough to keep the refund rule that changed from 2 to 3 hours? What would you keep instead?
Code & diagrams
Three tiny pages stand in for a real extraction. The report line is the point: always print what a cleaning rule removed.
Expected output
removed (repeated on 3 of 3 pages): Lumen Bikes Handbook - Confidential
characters before: 278
page 1: Shops open at 7 am and close at 9 pm.
page 2: A helmet is included free with every rental.
page 3: Bikes returned late are charged 2 dollars for every 15 minutes.
characters after: 144FNV-1a is written out by hand so the three languages agree. In production use a standard hash such as SHA-256 from your language's library.
Expected output
fnv1a("a") = e40c292c
original 33c77a38 new
reformatted 33c77a38 exact duplicate of original
reworded 96b3c071 new
other 8d2cd51c new
reworded vs original: words 0.818, 3-word shingles 0.652
other vs original: words 0.029, 3-word shingles 0.000Try: The question is the refund passage itself. Search and read the Cosine column: the copy that changes 2 hours to 3 hours scores almost 1, and a paraphrase scores lower but is still close. What would a de-duplication threshold on cosine do to the fact that the rule changed? Then try replacing 3 hours with 24 hours and search again.
Goals
- A copy with a different number still scores 0.95 or more
- A passage about a different topic stays under 0.70
Press Search. Then change one thing (a word in the question, a passage, the ranker) and compare the scores.
Break it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Treat every line as repeated
In the Python tab of the first example, change count * 2 > len(pages) to count >= 1. Run (the output is shortened here).
Break #2
Hash the raw text instead of the normalised text
In the Python tab of the second example, change fnv1a(" ".join(tokenize(text))) to fnv1a(text). Run.
Myth vs fact
Myth
De-duplicating is only about saving space.
Fact
The bigger gain is quality: duplicate hits crowd the prompt, and conflicting near-copies make the model pick a side. Space is the smaller benefit.
Myth
A high similarity means the texts say the same thing.
Fact
Two rules that differ by one number are 65 percent alike by shingles and about 99 percent by an embedding. Similarity measures form, not truth.
Myth
Remove repeated lines automatically and forget about it.
Fact
A repeated line may be an important warning. Report removals, sample them, and re-check when the source changes.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Comparing every pair is quadratic: a million chunks is half a trillion pairs. At scale use MinHash (a fixed-size summary of a shingle set whose agreement approximates Jaccard) with locality-sensitive hashing, which puts likely duplicates in the same bucket. The by-hand version here is exactly what those methods approximate.
- ▸
De-duplicate before embedding. Embedding calls cost money and time (Topic 4.8), and a chunk you drop at the hash stage is a call you never make.
- ▸
Pick which copy survives by rule, not by accident: newest version, most authoritative source, or the one with the most metadata. Log the dropped copy and its twin so a deletion can be explained and reversed.
Remember this
- 1
Why this exists. Raw text is full of things that carry no meaning: invisible control characters, runs of spaces and tabs, a line such as
Lumen Bikes Handbook - Confidentialat the top of every page,Page 7at the bottom. Left in, they repeat in thousands of chunks (Topic 4.1 explained the damage), and two copies of the same passage waste space in the index and in the prompt, where five identical hits push out useful ones (Topic 6.6). - 2
Cleaning, in the order the first example does it. First delete control characters (the invisible codes 0 to 31 except tab and newline, which includes the form-feed character many extractors put at page breaks, and also the carriage return of Windows line endings, which is harmless because the newline stays). Then, line by line, collapse runs of spaces and tabs to one space and trim the ends. Drop empty lines. Then find repeated lines: count on how many pages each line appears (once per page), and remove lines that appear on more than half of the pages. The header appears on 3 of 3 pages and goes. A pattern such as
Page 1,Page 2is not the same string on any two pages, so a small regular expression removes those by shape. - 3
Never clean away meaning. A repeated line can be real content (a warning that does appear on every page of a safety manual and matters). A rule that is safe on one corpus can damage another. Count what each rule removes, print a few removed examples, and read them before trusting the rule: the example prints exactly how many characters were removed (278 before, 144 after) for this reason.
- 4
Exact duplicates by hash. A hash function turns any text into a fixed-size number so that equal texts give equal numbers. Compare numbers instead of long texts. The example writes a tiny 32-bit hash, FNV-1a, by hand (start at 2166136261, then for each character XOR it in, which is a bit operation that mixes two numbers, and multiply by 16777619, keeping 32 bits), so every language prints the same value: the hash of the letter
aise40c292c. Real systems use a standard cryptographic hash such as SHA-256, which makes accidental collisions practically impossible, but the idea is identical. Hash the normalised text (lower-cased words) so that capital letters and extra spaces do not hide a copy: in the examplereformattedhas the same hash asoriginal. - 5
Near-duplicates by shingles and Jaccard. Many copies are not identical: one number changed, a sentence added, a different footer. A shingle is a window of
kconsecutive words; 3-word shingles ofA ride cancelled at leastarea ride cancelled,ride cancelled at,cancelled at least. Turn each text into its set of shingles. The Jaccard similarity of two sets is the size of the overlap divided by the size of the union: 1 means identical sets, 0 means nothing shared. Worked number: the original and the reworded text have 20 different words each, 18 of them shared, so the union is 22 and 18 / 22 = 0.818. With 3-word shingles each has 19, 15 are shared, the union is 23, and 15 / 23 = 0.652. Single words score higher than 3-word shingles because shingles are stricter: one changed word spoils every window that contains it, and they also notice word order. An unrelated passage scores 0.029 and 0.000. - 6
Where to set the threshold, and a warning. There is no universal value: pick one by looking at pairs just above and just below it. Also know what Jaccard cannot see. The reworded example changes
2 hoursto3 hours, which is a different rule, yet the texts are 65 percent similar. A real embedding is even more forgiving: in the lab below the 3-hours copy scores 0.99 and a paraphrase 0.85 against the original, so a cosine threshold of 0.95 would merge the changed rule into the old one. A de-duplicator that keeps one copy and drops the other has just chosen which rule is true. Prefer to keep the newest version (Topic 4.6's metadata) or to flag conflicts for a human, rather than silently picking the first.
Explain it without notes
Walk through cleaning a PDF extraction: which steps, in what order, and why print a removal report?
How does a hash find exact duplicates, and why normalise before hashing?
What are shingles and Jaccard similarity, and why are 3-word shingles stricter than single words?
Why is Jaccard similarity not enough to decide that two versions of a policy can be merged?
Practice
Write drop_repeated(pages, share) where pages is a list of lists of lines. It returns the pages without any line that appears on more than share of the pages (count a line once per page). Test it on three pages that all start with HEADER and print the result.
Write jaccard_words(a, b) that tokenises two texts into sets of lower-case words and returns the Jaccard similarity formatted with three decimals. Print it for "the monthly pass" and "the day pass".
Trade-offs
- ↔
A higher near-duplicate threshold: fewer wrongly merged documents, more near-copies stay. A lower one: smaller index, more risk of deleting a real difference.
- ↔
Larger shingles: stricter, fewer false matches, but a small edit in the middle of a sentence hides a real duplicate.
- ↔
Cryptographic hash versus FNV-1a: the cryptographic one is slower and safe from collisions in practice. FNV-1a is tiny and fine for teaching and small jobs, not for a billion items.
Done when you can
Done when you can clean a page and print a report of what was removed.
Done when you can detect exact duplicates with a normalised hash.
Done when you can compute shingles and Jaccard similarity by hand and say what each k means.
Done when you can explain why similarity must never be the only reason to delete a passage.