زیر رشته دبلیو

در پردازش زبان طبیعی، یک زیررشته دبلیو، مجموعه‌ای از زیررشته‌های منحصربه‌فرد (بنابراین ان-گرم) است که هر کدام‌شان، متشکل از زیردنباله‌های مجاور از توکن‌ها درون یک سند هستند که سپس می‌توان از آنها برای تعیین شباهت بین اسناد استفاده نمود. نماد w، نشان‌گر تعداد توکن‌ها در هر زیررشته منتخب می‌باشد.

بنابراین، سند "یک رز، یک رز است یک رز است" را میتوان حداکثر به صورت زیر، توکنسازی نمود:

(یک، رُز، است، یک، رُز، است، یک، رُز)

مجموعه همه دنباله‌های مجاور از 4 توکن (بنابراین 4 = n، بنابراین 4 گرم) عبارت است از

{(یک، رُز، است، یک)، (رُز، است، یک، رُز)، (است، یک، رُز، است)، (یک، رُز، است، یک)، (رُز، است، یک، رُز)}

که سپس می‌توان آن را کاهش داد، یا تا حد ممکن، به نمونه خاص زیر از زیررشته‌ها تبدیل نمود:

{(یک، رُز، است، یک)، (رُز، است، یک، رُز)، (است، یک، رُز، است) }

شباهت

برای اندازه معین زیررشته، میزان شباهت دو سند A و B با یکدیگر را می‌توان به صورت نسبت اندازه‌های اشتراک و اجتماع زیررشته‌ها بیان کرد، یا

𝑟(𝐴. 𝐵) = | 𝑆(𝐴) ∩ 𝑆(𝐵)| \| S(A) ∪ S(B)|1

که |A|، اندازه مجموعه A است. شباهت، عددی در محدوده [0،1] می‌باشد که 1، نشانگر یکسان‌بودن دو سند هستند. این تعریف، با ضریب ژاکار (Jaccard) که تشابه و تنوع مجموعه‌های نمونه را توصیف می‌کند، یکسان است.

همچنین

مدل کیسه کلمات

مفهوم‌کاوی

کی-مر (k-mer)

مینی‌هش

ان-گرم

اثر انگشت رابین

هش رولینگ

مدل فضای برداری

منابع

1. Broder; Glassman; Manasse; Zweig (1997)."Syntactic Clustering of the Web".SRC Technical Note#1997-015.
2. Manber(1993)."Finding Similar Files in a Large File System"(PDF).Does not yet use the term "shingling".
3. 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