Is a shingle the same as an n-gram?

It is a contiguous token sequence of a chosen length, so it is closely related to an n-gram. Shingling emphasizes representing and comparing documents through such sequences.

Does 100% set similarity prove identical documents?

No. Different sequences can sometimes have the same shingle set, especially when order beyond the window and repeated counts are lost.

Can it detect paraphrases?

It may detect retained wording, but substantial rephrasing can remove overlap. Semantic similarity requires additional methods.

AI Glossary / Natural language and speech / Intermediate

W-shingling

Definition

W-shingling represents a document using overlapping sequences of w consecutive tokens, called shingles. Comparing the resulting collections helps detect shared wording and near-duplicate text. The parameter w specifies the length of each sequence.

What it means

For word tokens and w = 3, each shingle contains three adjacent words. Moving one word forward produces the next shingle, so the windows overlap. Character tokens or other defined units can also be used.

A common representation keeps only unique shingles. Other formulations preserve repetition through a multiset or occurrence labels. The choice matters because a set records presence, while a frequency-aware representation can distinguish repeated passages.

Shingling captures local wording and order, not meaning in general. Two paraphrases may express the same idea with few matching shingles. Conversely, documents can share substantial boilerplate while differing on an important number or condition. A similarity score should therefore be interpreted according to the chosen representation and purpose.

How it works

First choose tokenization and any normalization, such as case handling. Slide a window of width w over the token sequence. A document containing n tokens has n − w + 1 window occurrences when n is at least w, before duplicate shingles are removed.

For sets, Jaccard similarity divides the number of shared shingles by the number in their union. Directional containment instead compares the shared shingles with the set size of a specified document. These answer different questions.

Broder's original work connects these comparisons to compact sampling methods. Hashing and sketching can make large-scale comparison practical, but a sketch is an approximation to a defined set comparison. It is not an independent semantic judgment.

Three practical examples

A search team identifies pages with nearly identical article text despite different surrounding site layouts.
A document manager groups repeated versions of a policy for review before deciding which records to retain.
A corpus builder checks whether long passages are repeated across training and evaluation collections.

Think of it this way

Think of comparing books by the short strips of consecutive words printed on overlapping index cards. Shared cards reveal shared local wording even when the entire books differ.

The analogy has limits: a collection of cards loses some global arrangement, and a set loses repeated copies. Matching cards also cannot tell whether the books make the same argument or whether copying was authorized.

Worked example

Computing a two-word shingle comparison

Use the invented texts A = “blue boats cross calm water” and B = “blue boats cross deep water”. Treat spaces as word boundaries and set w = 2.

A has four shingles: blue boats, boats cross, cross calm, calm water. B also has four: blue boats, boats cross, cross deep, deep water.

The intersection contains two shingles. The union contains six, so Jaccard similarity is 2 / 6 = 1/3, approximately 33.3%. The containment of A's shingle set in B is 2 / 4 = 50%; the reverse happens to match because the sets have equal size.

One changed middle word disrupted two overlapping shingles. Now compare A with C = “blue boats cross”. C has two shingles, both present in A. Containment of C in A is 100%, while Jaccard similarity is 2 / 4 = 50%.

This illustrates why a short passage can be fully contained in a longer document without the documents being highly similar under every measure.

Illustrative case study

A fictional training publisher collects course handouts from several departments. Many contain the same introductory page followed by different exercises.

The team uses shingle comparisons to identify candidate groups, then reviews where the overlap occurs. It separates shared introductions from genuinely duplicated lessons and preserves exercises that contain distinct material. It also records the tokenization and shingle length so later comparisons remain interpretable.

The publisher does not delete a document solely because its similarity score crosses a threshold. It examines version dates, ownership and the substance of the differences. This case illustrates a review workflow, not a measured duplicate-detection result or a judgment about copyright.

Common misconceptions and mistakes

Confusing shingle occurrences with unique shingles. Repetition changes the former count without necessarily changing the latter.
Treating similarity and directional containment as interchangeable.
Assuming a high score proves identical meaning or misconduct.
Comparing documents processed with inconsistent tokenization or normalization.
Believing that increasing w always helps. Longer windows are more specific but more sensitive to small changes.
Forgetting a convention for documents shorter than w, which may produce empty collections.

Business use

W-shingling is useful for discovering redundant content and managing near-duplicates. It can also support data-quality checks before training or evaluating language systems, where repeated material may distort results.

Choose w and preprocessing rules according to document length and the kind of variation that matters. Evaluate short texts separately from long documents. Common navigation menus, footers and disclaimers can dominate overlap unless handled appropriately.

Use candidate detection to reduce review effort, then inspect consequential decisions. If hashing or sampled signatures are used, account for approximation and collision handling. Document the threshold and the measure being applied. A 90% containment statement about a small passage is not the same as 90% resemblance between two complete documents.

Check your understanding

A seven-token document is processed with w = 3. How many window occurrences are produced, and must that equal the number of unique shingles?

Answer: Seven minus three plus one gives five occurrences. The unique count can be smaller if a three-token sequence repeats.

Related terms

N-gram
Tokenization
Jaccard similarity
document resemblance
containment
MinHash
near-duplicate detection
locality-sensitive hashing

Learn next

Read Jaccard similarity and MinHash. Compare the same short texts with one-word and two-word shingles, explaining which ordering information each retains. Then distinguish full-document resemblance from containment of a shorter passage.

Sources

Andrei Z. Broder, On the Resemblance and Containment of Documents (1997), primary paper available at: https://skeptric.com/resources/broder97resemblance.pdf. The paper distinguishes repeated and unique shingle representations and defines resemblance and containment. The boat-text calculations and publisher story are original illustrations.

Previous: Vuong's closeness test Next: W-test