science

W-shingling

W-shingling is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand W-shingling rather than just read about it. In short: In natural language processing a w-shingling is a set of unique shingles (therefore n-grams) each of which is composed of contiguous subsequences of tokens within a document, which can then be used to ascertain the similarity between documents. The symbol w denotes the quantity of tokens in each shingle selected, or solved for.

Key takeaways

W-shingling belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect W-shingling to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of W-shingling from memory before moving on to harder problems.

Reference excerpt

In natural language processing a w-shingling is a set of unique shingles (therefore n-grams) each of which is composed of contiguous subsequences of tokens within a document, which can then be used to ascertain the similarity between documents. The symbol w denotes the quantity of tokens in each shingle selected, or solved for. The document, "a rose is a rose is a rose" can therefore be maximally tokenized as follows:

(a,rose,is,a,rose,is,a,rose) The set of all contiguous sequences of 4 tokens (Thus 4=n, thus 4-grams) is

{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) } Which can then be reduced, or maximally shingled in this particular instance to

{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }.

Resemblance For a given shingle size, the degree to which two documents A and B resemble each other can be expressed as the ratio of the magnitudes of their shinglings' intersection and union, or

r ( A , B ) = | S ( A ) ∩ S ( B ) | | S ( A ) ∪ S ( B ) | {\displaystyle r(A,B)={{|S(A)\cap S(B)|} \over {|S(A)\cup S(B)|}}}

where |A| is the size of set A. The resemblance is a number in the range [0,1], where 1 indicates that two documents are identical. This definition is identical with the Jaccard coefficient describing similarity and diversity of sample sets.

See also Bag-of-words model Jaccard index Concept mining k-mer MinHash n-gram Rabin fingerprint Rolling hash Vector space model

References

Broder; Glassman; Manasse; Zweig (1997). "Syntactic Clustering of the Web". SRC Technical Note #1997-015.{{cite web}}: CS1 maint: url-status (link) Manber (1993). "Finding Similar Files in a Large File System" (PDF). Does not yet use the term "shingling". Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (7 July 2008). "w-shingling". Introduction to Information Retrieval. Cambridge University Press. ISBN 978-1-139-47210-4.

Worked examples

Example 1 — a first encounter with W-shingling

Start with the simplest possible case. Write down what W-shingling claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to W-shingling before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about W-shingling ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of W-shingling

In research: W-shingling appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses W-shingling in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: W-shingling is common in secondary-school and first-year university syllabi. It links to neighbouring topics Natural language processing, so understanding it makes those chapters shorter.
In everyday life: Look for W-shingling outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study W-shingling in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what W-shingling means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain W-shingling out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is W-shingling in simple terms?

Why does W-shingling matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study W-shingling?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on W-shingling.