Project 14

Find Near-Duplicate Documents

Represent documents with exact overlapping token groups, compare every bounded pair, and retain the source evidence behind each candidate.

  • 9 milestones
  • Optional
  • Browser workspace

Project question: Can you represent documents by exact overlapping token groups, compare every eligible pair with a supplied set-overlap rule, and keep enough source evidence to inspect every flagged pair?

What makes this a project

A near-duplicate flag is a report about one visible lexical rule. In this project you will select exact text tokens, preserve both selected-token and full-token positions, build overlapping tuple groups, compare every eligible document pair with exact Jaccard arithmetic, and attach source evidence to the ordered flagged view. You will also inspect how group size and a rational threshold change eligibility and selection on the supplied corpus.

This is not a semantic similarity system and not an automatic deletion policy. A flagged pair is evidence that two documents met the stated group-overlap rule. It does not establish that they have the same meaning or that one should be removed.

You will produce:

  • checked corpus, tokenizer, document, and configuration identities;
  • selected token records with both coordinate systems and excluded-kind counts;
  • exact overlapping groups, unique group sets, and complete occurrences;
  • exhaustive unordered pair metrics, eligibility reasons, and rational threshold decisions;
  • ordered flagged pairs, complete shared-group evidence, and bounded excerpts;
  • group-size and threshold sensitivity records with exact additions/removals;
  • saved figures from exact plot data, read-back, and separate replay; and
  • an evidence-limited near-duplicate review card.

What you should know first

The project follows the Python path through Chapter 13. You should be able to validate ordered records and stable IDs, build overlapping sequence windows, use tuples and sets, generate each unordered pair once, calculate a supplied ratio, sort under exact ties, join source positions, save structured artifacts, and replay a deterministic analysis. TEXT-02 is useful but optional. The project restates its token and group rules; do not invent a normalization or similarity convention.

Supplied inputs

Use the accepted TEXT-02 corpus, tokenizer identity, document manifest, and complete token records, or a version-matched fallback. Also use plans/near_duplicate_config.json, tiny documents covering exact copies, edits, reordered passages, repeated groups, unrelated text, case and punctuation changes, non-ASCII text, underscores, and short documents, plus expected selected tokens, groups, pair metrics, evidence, excerpts, and sensitivity rows.

The primary configuration has a positive group size and exact rational threshold. Its small ordered audit grid is for sensitivity inspection only. Thresholds use non-boolean integer numerator and positive denominator with 0 <= numerator <= denominator; duplicate settings are rejected and the primary setting appears once in the grid.

The project workspace

project/
  README.md
  data/                              # supplied, read only
  plans/near_duplicate_config.json   # supplied starting config
  src/config.py                      # reader implementation
  src/documents.py                   # reader implementation
  src/groups.py                      # reader implementation
  src/pairs.py                       # reader implementation
  src/evidence.py                    # reader implementation
  src/sensitivity.py                 # reader implementation
  src/report.py                      # reader implementation
  src/main.py                        # reader implementation
  output/                            # generated artifacts
  tests/public_cases.py              # supplied, read only

Keep one continuous workspace through every milestone. Token selection, group construction, occurrence retention, pair generation, exact similarity, threshold decisions, evidence rendering, and sensitivity inspection should remain independently inspectable.

Project milestones

Work through these in order. Each milestone produces evidence used by the next one, while project completion remains separate from lesson progress.

  1. 1Verify corpus, tokenizer, documents, and configuration

    Check source identities, complete token positions, primary and audit settings, rational thresholds, evidence limits, document order, and short-document fixtures.

  2. 2Select exact text tokens and preserve source positions

    Retain selected-token and complete-token coordinates, exact spelling, source identity, and excluded-token counts without crossing documents.

  3. 3Build unique groups and complete occurrences

    Construct every overlapping exact tuple, keep all occurrence coordinates, and classify documents that cannot form a group.

  4. 4Hand-check eligibility and exact similarity

    Work through intersection, union, exact fractions, threshold cross-products, equality boundaries, and excluded short-document pairs.

  5. 5Compare every eligible document pair exactly once

    Generate every manifest-ordered unordered pair, retain eligible and excluded rows, calculate exact metrics, and prove complete pair accounting.

  6. 6Select flagged pairs and attach source evidence

    Apply exact ordering, join every shared group and occurrence, and render bounded excerpts without deleting the complete saved evidence.

  7. 7Inspect bounded group-size and threshold sensitivity

    Rebuild each accepted setting and separate eligibility changes from threshold-only additions and removals without choosing a best parameter.

  8. 8Save, reload, visualize, and replay the analysis

    Persist exact token, group, pair, evidence, sensitivity, plot, identity, and manifest artifacts; read them back; and reproduce them separately.

  9. 9Write and audit the near-duplicate review card

    State token and group rules, short-document policy, exact threshold, pair scope, evidence limits, sensitivity, replay, and limits on interpretation.

Required evidence

Save versioned configuration and corpus/tokenizer identity; selected_tokens.jsonl and excluded-token summaries; document_groups.jsonl and group_occurrences.jsonl with both coordinate systems; all_pair_metrics.csv with eligible and excluded pairs, exact numerators and denominators, threshold products, decisions, and pair order; flagged_pairs.jsonl, shared_group_evidence.jsonl, and review_excerpts.jsonl; sensitivity_summary.csv and exact pair additions/removals per audit setting; eligibility, similarity, flagged-pair, and sensitivity figures with exact plot_data.json; near_duplicate_manifest.json, read-back checks, a separate replay agreement or first-mismatch record; and project-root report.md.

Limits

This project does not teach semantic similarity, embeddings, hashes as group identity, MinHash, locality-sensitive hashing, probabilistic estimates, approximate candidate generation, clustering, transitive duplicate groups, automatic keep-or-delete decisions, labelled accuracy evaluation, threshold learning, HTML-boilerplate removal, web crawling, cross-split leakage policy, copyright or provenance decisions, production-scale all-pairs comparison, distributed processing, or performance benchmarking. It does not claim that a flagged pair is meaningfully or legally equivalent, accurate, scalable, or the best result under a learned parameter.

Review

The final review asks whether token and source identities remain compatible, excluded tokens stay accounted for, groups never cross document boundaries, unique sets conserve repeated occurrences, every unordered pair appears once, exact fractions decide thresholds, excluded pairs retain reasons, evidence limits affect display only, sensitivity separates eligibility from selection, replay is separate, and the card stays within lexical evidence.