w-shingling

I naturligt språkbehandling är en w -shingling en uppsättning unika bältros (därför n-gram ) som var och en består av sammanhängande undersekvenser av tokens i ett dokument , som sedan kan användas för att fastställa likheten mellan dokument . Symbolen w anger mängden tokens i varje shingel vald eller löst för.

Dokumentet, "en ros är en ros är en ros" kan därför maximalt symboliseras enligt följande:

(en,ros,är,en,ros,är,en,ros)

Uppsättningen av alla sammanhängande sekvenser av 4 tokens (alltså 4= n , alltså 4- gram ) är

{ (en,ros,är,en), (ros,är,en,ros), (är,en,ros,är), (en,ros,är,en), (ros,är,en,ros) } Som sedan kan reduceras eller maximalt shinglas i just detta fall till { (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }.

Likhet

För en given bältrosstorlek kan graden i vilken två dokument A och B liknar varandra uttryckas som förhållandet mellan storleken på deras bältros skärning och förening , eller

$r(A,B)={{|S(A)\cap S(B)|} \över {|S(A)\cup S(B)|}}$

där |A| är storleken på uppsättning A. Likheten är en siffra i intervallet [0,1], där 1 indikerar att två dokument är identiska. Denna definition är identisk med Jaccard-koefficienten som beskriver likhet och mångfald av provuppsättningar.

Se även

• Bag-of-words modell
• Koncept gruvdrift
• k -mer
• MinHash
• N-gram
• Rabin fingeravtryck
• Rullande hash
• Vektor utrymme modell

• Broder; Glassman; Manasse; Zweig (1997). "Syntaktisk klustring av webben" . SRC Technical Note #1997-015 .
• Manber (1993). "Hitta liknande filer i ett stort filsystem" (PDF) . Använder ännu inte termen "shingling".
•   Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (7 juli 2008). "w-shingling" . Introduktion till informationssökning . Cambridge University Press. ISBN 978-1-139-47210-4 .