library(readr)
library(dplyr)
library(tibble)
library(purrr)
library(stringr)
library(digest)
library(stringdist)
library(tidyr)
library(ggplot2)
workforce_sentences <- read_csv(
"data/workforce/workforce_sentences.csv",
na = character(),
col_types = cols(
sentence_id = col_character(),
document_id = col_character(),
source_line = col_character(),
text = col_character(),
reference_label = col_character(),
uncertainty = col_character(),
annotator_id = col_character(),
rationale = col_character(),
codebook_version = col_character(),
codebook_hash = col_character(),
derived = col_character(),
transformation = col_character()
)
)
source_text <- workforce_sentences |>
filter(sentence_id == "s006") |>
pull(text)
unrelated_text <- workforce_sentences |>
filter(sentence_id == "s004") |>
pull(text)
documents <- tibble(
doc_id = c("D01", "D02", "D03", "D04", "D05", "D06"),
source = c(
"Riverton sentence s006",
"Exact author copy",
"Formatting author copy",
"One-word author variant",
"Near distractor",
"Unrelated Riverton sentence s004"
),
text = c(
source_text,
source_text,
" THE employer pays for certification TRAINING. ",
"The employer covers certification training.",
"The employer pays for certification exam.",
unrelated_text
),
duplicate_family = c(
"certification-training",
"certification-training",
"certification-training",
"certification-training",
"certification-exam",
"spreadsheet-skills"
)
)Deduplicating documents
Find repeated records before they distort a collection
documents
deduplication
workforce research
Learn how exact, normalized, and near-duplicate checks behave on Riverton workforce documents.
A repeated record can make a collection appear larger than it is before training and evaluation. The coordinator must distinguish a duplicated training sentence from separate notices that contain the same sentence.
That choice affects later counts. Duplicate documents can inflate phrase and label frequencies. They can also place the same information in both training and evaluation splits.
This lesson works at the document level. A duplicate is a record that the analyst should not count separately for the research question.
Lesson 12 builds augmented examples with source_family_id. Those rows also need protection against overlap between splits. This page uses a smaller constructed set to show the distance calculation.
Note
Riverton is a teaching case. The documents and duplicate families below are fictional.
TipWhat you will learn
After this lesson, you should be able to:
- explain why duplicate documents change downstream counts.
- find exact duplicates with a SHA-256 hash.
- find formatting-only duplicates with a normalized hash.
- compare near duplicates with character trigram distance.
- choose a threshold based on the relative costs of its errors.
Build a small comparison set
The comparison starts with the sentence file. The code prepares tables, normalizes text, and calculates fingerprints and distances. It then compares pairs and plots thresholds.
A hash is a fixed-length fingerprint made from text. The same input gives the same hash. A different input should give a different hash. Hash comparison examines exact identity rather than similarity.
| Document | Source | Text |
|---|---|---|
| D01 | Riverton sentence s006 | The employer pays for certification training. |
| D02 | Exact author copy | The employer pays for certification training. |
| D03 | Formatting author copy | THE employer pays for certification TRAINING. |
| D04 | One-word author variant | The employer covers certification training. |
| D05 | Near distractor | The employer pays for certification exam. |
| D06 | Unrelated Riverton sentence s004 | Applicants need basic spreadsheet skills. |
The author wrote this six-row set to demonstrate a known failure mode. Four rows form one marked duplicate family. They contain the source sentence, an exact copy, a spacing-and-case copy, and a one-word paraphrase. The exam sentence changes the claim but retains much of the original wording. The spreadsheet sentence is unrelated.
Find exact duplicates
An exact duplicate has the same text byte for byte. The code hashes each text value with SHA-256. In the code, \(value) is R shorthand for “for each value, execute the small calculation that follows.”
documents <- documents |>
mutate(
exact_hash = map_chr(
text,
\(value) digest::digest(
value,
algo = "sha256",
serialize = FALSE
)
)
)
exact_groups <- documents |>
count(exact_hash, name = "documents") |>
filter(documents > 1L)
exact_duplicate_pairs <- sum(choose(exact_groups$documents, 2))| Document | Text | SHA-256 start |
|---|---|---|
| D01 | The employer pays for certification training. | 438036566b2c |
| D02 | The employer pays for certification training. | 438036566b2c |
| D03 | THE employer pays for certification TRAINING. | 067ebbd5c451 |
| D04 | The employer covers certification training. | a0a37ade34c8 |
| D05 | The employer pays for certification exam. | 5b0a3b98751f |
| D06 | Applicants need basic spreadsheet skills. | 3e2ee0c2b4dd |
Only the source and the exact copy match, giving one exact duplicate pair. The formatting copy receives a different fingerprint because capital letters and extra spaces are real characters.
Normalize before hashing
Normalization applies a recorded rule before text comparison. This rule converts text to lowercase and replaces consecutive whitespace with one space. It removes formatting differences but also removes capitalization and layout information.
documents <- documents |>
mutate(
normalized_text = str_squish(str_to_lower(text)),
normalized_hash = map_chr(
normalized_text,
\(value) digest::digest(
value,
algo = "sha256",
serialize = FALSE
)
)
)
normalized_groups <- documents |>
count(normalized_hash, name = "documents") |>
filter(documents > 1L)
normalized_duplicate_pairs <- sum(choose(normalized_groups$documents, 2))| Document | Normalized text | Normalized SHA-256 start |
|---|---|---|
| D01 | the employer pays for certification training. | 69adc10ac2fe |
| D02 | the employer pays for certification training. | 69adc10ac2fe |
| D03 | the employer pays for certification training. | 69adc10ac2fe |
| D04 | the employer covers certification training. | cfdd886532f0 |
| D05 | the employer pays for certification exam. | 4dbec4bc5178 |
| D06 | applicants need basic spreadsheet skills. | c2c27a31f3b6 |
The normalized hash joins three rows, which make three duplicate pairs. That is useful here, but risky for a flyer where line breaks or all-capital headings carry meaning.
Measure near duplicates
A near duplicate is similar enough to require a check even when its text is not identical. A character trigram contains three consecutive characters. The code extracts every overlapping trigram from each normalized string. It then removes ordering and duplicate trigrams to form a set.
Jaccard distance is the share of trigrams in the combined sets that do not appear in both. The distance is 0 for identical sets and 1 for sets with no shared trigrams. Without order, this measure describes differences in surface text rather than meaning.
comparison_pairs <- expand_grid(
left_doc = documents$doc_id,
right_doc = documents$doc_id
) |>
filter(left_doc < right_doc) |>
left_join(
documents |>
select(
left_doc = doc_id,
left_text = text,
left_norm = normalized_text,
left_family = duplicate_family
),
by = join_by(left_doc)
) |>
left_join(
documents |>
select(
right_doc = doc_id,
right_text = text,
right_norm = normalized_text,
right_family = duplicate_family
),
by = join_by(right_doc)
) |>
mutate(
manual_duplicate =
left_family == right_family &
left_family == "certification-training",
jaccard_distance = map2_dbl(
left_norm,
right_norm,
\(left, right) stringdist::stringdist(
left,
right,
method = "jaccard",
q = 3
)
)
)
calibration_pair <- tibble(
left_text = "Evening shifts require a valid forklift certification.",
right_text = "Evening shifts require a valid forklift certificate."
) |>
mutate(
jaccard_distance = stringdist::stringdist(
left_text,
right_text,
method = "jaccard",
q = 3
)
)
calibration_distance <- calibration_pair$jaccard_distance| Pair | Hand-marked duplicate | Jaccard distance |
|---|---|---|
| D01 / D02 | TRUE | 0.0000 |
| D01 / D03 | TRUE | 0.0000 |
| D01 / D04 | TRUE | 0.3200 |
| D01 / D05 | FALSE | 0.2917 |
| D01 / D06 | FALSE | 0.9877 |
| D02 / D03 | TRUE | 0.0000 |
| D02 / D04 | TRUE | 0.3200 |
| D02 / D05 | FALSE | 0.2917 |
| D02 / D06 | FALSE | 0.9877 |
| D03 / D04 | TRUE | 0.3200 |
| D03 / D05 | FALSE | 0.2917 |
| D03 / D06 | FALSE | 0.9877 |
| D04 / D05 | FALSE | 0.5455 |
| D04 / D06 | FALSE | 0.9873 |
| D05 / D06 | FALSE | 0.9870 |
| Left text | Right text | Jaccard distance |
|---|---|---|
| Evening shifts require a valid forklift certification. | Evening shifts require a valid forklift certificate. | 0.1132 |
The calibration strings explain the scale but are separate from the comparison set. Two sentences that differ only in certification versus certificate score 0.1132. In the constructed set, the exam distractor scores 0.2917 against the source. The meaning-preserving paraphrase scores 0.32.
The distractor replaces one short word, while the duplicate replaces a longer phrase. Surface overlap therefore ranks the changed meaning as more similar. Real collections can contain such pairs. This small set makes the mechanism visible.
Compare thresholds
A threshold is the maximum distance at which the pipeline joins two documents. The lesson does not fit the threshold. The team tries several values and counts correct and incorrect joins.
threshold_sweep <- tibble(
threshold = c(0, 0.2, 0.3, 0.35, 0.7, 0.99)
) |>
mutate(
caught_true = map_int(
threshold,
\(cutoff) sum(
comparison_pairs$manual_duplicate &
comparison_pairs$jaccard_distance <= cutoff
)
),
wrongly_joined = map_int(
threshold,
\(cutoff) sum(
!comparison_pairs$manual_duplicate &
comparison_pairs$jaccard_distance <= cutoff
)
)
)
perfect_threshold <- threshold_sweep |>
filter(caught_true == 6L, wrongly_joined == 0L)| Threshold | True duplicate pairs found | Distinct pairs wrongly joined |
|---|---|---|
| 0.00 | 3 | 0 |
| 0.20 | 3 | 0 |
| 0.30 | 3 | 3 |
| 0.35 | 6 | 3 |
| 0.70 | 6 | 4 |
| 0.99 | 6 | 9 |
Show the plotting code
source("R/lesson-figures.R")
sweep_lines <- threshold_sweep |>
tidyr::pivot_longer(
cols = c(caught_true, wrongly_joined),
names_to = "result",
values_to = "pairs"
) |>
mutate(
result = if_else(
result == "caught_true",
"true duplicate pairs caught",
"distinct pairs wrongly joined"
)
)
line_colours <- c(
"true duplicate pairs caught" = lesson_colours[["accent"]],
"distinct pairs wrongly joined" = lesson_colours[["contrast"]]
)
label_colours <- c(
"true duplicate pairs caught" = lesson_text_colours[["accent"]],
"distinct pairs wrongly joined" = lesson_text_colours[["contrast"]]
)
ggplot(sweep_lines, aes(x = threshold, y = pairs, colour = result)) +
geom_step(aes(linetype = result), linewidth = 0.9, direction = "hv") +
geom_point(size = 2.2) +
geom_text(
data = \(d) filter(d, threshold == max(threshold)),
aes(label = str_c(pairs, " ", result), colour = I(label_colours[result])),
hjust = 0,
nudge_x = 0.02,
family = lesson_font,
size = 10,
size.unit = "pt"
) +
scale_colour_manual(values = line_colours, guide = "none") +
scale_linetype_manual(
values = c(
"true duplicate pairs caught" = "solid",
"distinct pairs wrongly joined" = "22"
),
guide = "none"
) +
scale_x_continuous(
breaks = threshold_sweep$threshold,
guide = guide_axis(n.dodge = 2),
expand = expansion(mult = c(0.02, 0.55))
) +
scale_y_continuous(breaks = seq(0, 9, by = 3)) +
labs(
title = "No threshold finds every duplicate without joining distinct pairs",
subtitle = "Pairs joined at or below each evaluated Jaccard distance threshold",
x = "Jaccard distance threshold",
y = "Pairs"
) +
theme_lesson(grid = "y")
For this constructed set, 0.2917 is smaller than 0.32. The distractor is closer to the source than the paraphrase is. Because those two distances are ordered that way, no threshold on these pairs can match the paraphrase without also joining the distractor. The comparison shows how a threshold reduces one error at the cost of another in this set. It does not establish a general law of deduplication.
Deduplication at scale
The expand_grid() step builds all pairs, with \(O(N^2)\) computational scaling. This approach works for a small teaching set. On large datasets, all-pairs Jaccard calculations require too much time and memory.
Production systems avoid \(O(N^2)\) all-pairs comparisons through Locality Sensitive Hashing (LSH) and MinHash. These algorithms operate on shingles, overlapping sequences of text units. MinHash summarizes set similarity, while LSH groups likely near matches for comparison. Packages such as R’s textreuse and Python’s datasketch can group near duplicates across millions of documents without comparing every pair.
What to remember
- Duplicate documents can inflate counts and leak between training and evaluation.
- Exact hashes find only byte-for-byte duplicates.
- Normalized hashes find some formatting-only duplicates but remove formatting information.
- Character-trigram Jaccard distance measures surface overlap, not preserved meaning.
- Near-duplicate thresholds change the numbers of missed duplicates and wrongly joined records in this set.
- The right threshold depends on which error costs more for the project.
The system can remove exact duplicates automatically. A person must examine near matches before any training or evaluation split. These threshold results describe the constructed set rather than a universal setting for Riverton documents.