W-shingling

W-shingling

A w-shingling is a set of unique "shingles"—contiguous subsequences of tokens in a document—that can be used to gauge the similarity of two documents. The w denotes the number of tokens in each shingle in the set.

The document, "a rose is a rose is a rose" can be tokenized as follows:

:(a,rose,is,a,rose,is,a,rose)

The set of all contiguous sequences of 4 tokens (N-grams, here: 4-grams) is

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

By removing duplicate elements from this set, a 4-shingling is obtained:

:{ (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)={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

*Concept Mining offers an alternative method for document similarity calculation with more computational complexity, but where the measure more closely models a human's perception of document similarity.

References

*(Manber 1993) "Finding Similar Files in a Large File System". Does not yet use the term "shingling". Available [http://webglimpse.net/pubs/TR93-33.pdf as PDF]
*(Broder, Glassman, Manasse, and Zweig 1997) "Syntactic Clustering of the Web". SRC Technical Note #1997-015. Available [http://gatekeeper.research.compaq.com/pub/DEC/SRC/technical-notes/SRC-1997-015-html/ as HTML]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Shingling — Shin gling, n. 1. The act of covering with shingles; shingles, collectively; a covering made of shingles. [1913 Webster] 2. (Metal) The process of expelling scori[ae] and other impurities by hammering and squeezing, in the production of wrought… …   The Collaborative International Dictionary of English

  • Shingling hammer — Shingling Shin gling, n. 1. The act of covering with shingles; shingles, collectively; a covering made of shingles. [1913 Webster] 2. (Metal) The process of expelling scori[ae] and other impurities by hammering and squeezing, in the production of …   The Collaborative International Dictionary of English

  • Shingling mill — Shingling Shin gling, n. 1. The act of covering with shingles; shingles, collectively; a covering made of shingles. [1913 Webster] 2. (Metal) The process of expelling scori[ae] and other impurities by hammering and squeezing, in the production of …   The Collaborative International Dictionary of English

  • Shingling — was a stage in the production of bar iron or steel, in the finery and puddling processes. As with many ironmaking terms, this is derived from the French cinglage The product of the finery was a bloom or loop (French loup ); that of the puddling… …   Wikipedia

  • Shingling — Shingle Shin gle, v. t. [imp. & p. p. {Shingled}; p. pr. & vb. n. {Shingling}.] 1. To cover with shingles; as, to shingle a roof. [1913 Webster] They shingle their houses with it. Evelyn. [1913 Webster] 2. To cut, as hair, so that the ends are… …   The Collaborative International Dictionary of English

  • shingling — noun 1. (geology) sediment in which flat pebbles are uniformly tilted in the same direction • Topics: ↑geology • Hypernyms: ↑rock, ↑stone 2. the laying on of shingles shingling is a craft very different from carpentry …   Useful english dictionary

  • shingling — /shing gling/, n. Geol. a sedimentary structure in which flat pebbles are uniformly tilted in the same direction. Also called imbrication. [1695 1705, for literal sense; SHINGLE1 + ING1] * * * …   Universalium

  • shingling — shin·gle || ʃɪŋgl n. thin piece of wood stone or other material laid in overlapping rows on a roof or wall; small smooth stones on beaches and shores; short hairstyle for women; small signboard (especially one placed at the entrance to a… …   English contemporary dictionary

  • shingling-mill — n. Furnace, forge …   New dictionary of synonyms

  • shingling — shin·gling …   English syllables

  • shingling hatchet — noun : a hatchet usually with a notch in the blade for extracting nails and a hammerhead opposite the cutting edge …   Useful english dictionary

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”