Near-duplicate detection

Documents. Choose Example for a generated set of short news-like sentences in which a share are edited copies of earlier ones (300 to 20,000 documents), Paste for one document per line (or blank-line separated), CSV to pick the text column of a CSV file, or Files to drop text, Markdown or HTML files (each file is one document; HTML tags are stripped).

Shingles and MinHash. A document becomes a set of shingles — character k-grams (k = 5 is a good start for short text, 9 or so for web pages) or word k-grams — after optional lower-casing, punctuation removal and white-space collapsing. Each shingle is hashed once (MurmurHash3), then by k hash functions h_i(x) = (a_i·x + b_i) mod (2³¹ − 1) with seeded a_i and b_i; the signature keeps each function’s minimum. Two signatures agree at a position with probability equal to the Jaccard similarity of the sets, so the share of agreeing positions estimates it with standard error √(J(1 − J)/k). The Hash functions tab lists the first sixteen (a_i, b_i) and, for any document, which shingle wins each of the first few positions.

LSH banding. The signature is cut into b bands of r rows; two documents become a candidate pair if any band matches exactly. The chance of that is 1 − (1 − s^r)^b, an S-curve that is steepest near (1/b)^1/r. The chart draws it for your b and r, shades the false-positive area (under the curve, left of your threshold t) and the false-negative area (above it, right of t), and — once the exact pairs are known — plots the measured share of pairs that became candidates in each 0.05 band of similarity. With pick b and r for me on, the tuner chooses the b × r ≤ k that minimises the weighted sum of the two areas; slide the weights toward FN to miss fewer pairs (at the cost of more candidates to check). The table under the chart lists the best eight choices.

Results. The tiles show the candidates, the true pairs (exact J ≥ t), the candidates' recall and precision, and the precision and recall after the usual second step — keeping only candidates whose MinHash estimate reaches t. The ground truth comes from comparing every pair exactly when there are up to 2,500 documents, and from an exact similarity join (PPJoin: prefix, length and positional filtering, then verification) above that, so even 10,000 documents get exact numbers without 50 million comparisons.

Settings are kept in this browser, and Share puts them (not your documents) in a link.

MinHash with banding is the tool for "similar enough": it can find pairs at J = 0.5 with a tunable trade-off. SimHash fingerprints are 8 bytes and very cheap to search at small distances, which suits "almost identical" (the original use was crawled web pages at distance 3), but a pair at Jaccard 0.5 is typically 15–20 bits apart, where the table method needs too many tables. The Compare tab makes that visible on your own data.

Clusters are transitive: a chain of small edits can join documents whose ends are not similar. If that matters, check pairs within a cluster against its first document.

The tests (tests/tools/near-duplicates.test.js) check the hash functions against BigInt arithmetic, the MinHash estimate’s mean and spread over 200 seeds against J and √(J(1 − J)/k), the banding rate against the S-curve, the similarity join against brute force, and the SimHash table search against all-pairs Hamming. With Python’s datasketch 2.0: the tuner chooses the same (b, r) as its MinHashLSH for seven threshold/weight cases, and on a 600-document corpus its MinHash and this page’s had the same error against exact Jaccard (RMSE 0.034 and 0.036, theory 0.034) and their LSH indexes both found every pair at J ≥ 0.5. The signatures themselves differ from datasketch’s (it hashes with SHA-1 and a 61-bit prime), so compare estimates, not values.

Any current browser. Large corpora are processed in a Web Worker; if workers are unavailable the work runs on the page and it may pause while it does.

Your documents never leave the browser: they are processed in this tab, nothing is uploaded, and nothing is loaded from other sites. Pasted text and CSV are kept in this browser’s local storage so they are there next time; share links carry only the settings.