. متن داده‌شده را خلاصه کن

متن: ثابت تشابه ژاکار برای دو مجموعه a و b به صورت زیر تعریف می‌شود که یک عدد بین ۰ و ۱ است؛ وقتی دو مجموعه کاملا از هم جدا هستند مقدار ۰ و وقتی دو مجموعه برابر هستند مقدار ۱ را می‌پذیرد. در بقیه حالات به‌طور موکد بین ۰ و ۱ است. این ثابت یک نمایش رایج برای نشان دادن میزان تشابه بین دو مجموعه است: دو مجموعه بیشتر به هم شبیه هستند اگر ثابت ژاکار آن نزدیکتر به ۱ باشد، و به همین طریق وقتی ثابت ژاکار آن‌ها به ۰ نزدیکتر باشد، کمتر متشابه‌اند. فرض کنید h یک تابع درهم‌سازی باشد که اعضای a و b را به اعداد صحیح متمایز نسبت می‌دهد، و برای هر مجموعه s تعریف می‌کنیم hmin (s) که عضو x از s است با مقدار میانی h (x). بنابراین hmin (a) = hmin (b) دقیقا زمانی که مقدار درهم سازی میانی اجتماع a ∪ b داخل تلاقی a ∩ b قرار گیرد. از همین رو، به عبارتی دیگر، اگر r یک متغیر تصادفی باشد که وقتی hmin (a) = hmin (b) است برابر ۱ و در غیر این صورت ۰ باشد، آنگاه r یک برآوردگر بی‌غرض از j (a,b) است، با اینکه واریانس بالایی برای اینکه در نوع خود مفید باشد، دارد. هدف روش درهم‌سازی میانی برای کاهش واریانس، میانگین‌گیری از چندین متغیر است که به صورت یکسان تولید شده‌اند. ساده‌ترین نسخه از روش درهم‌سازی میانی از k تابع درهم‌سازی متفاوت استفاده می‌کند (که یک پارامتر عدد صحیح ثابت است) و نمایانگر هر مجموعه s با k مقدار از hmin (s) برای این k تابع است. برای تخمین زدن j (a,b) با استفاده از این نسخه این رویه، فرض کنید y تعداد توابع درهم‌سازی باشد به صورتی که hmin (a) = hmin (b)، از y / k به عنوان تخمین استفاده کنید. این تخمین حاصل میانگین k متغیر تصادفی است که بین ۰ - ۱ هستند، که هر کدام وقتی hmin (a) = hmin (b) است، برابر ۱ و در غیر اینصورت برابر ۰ هستند، و هرکدام از این‌ها یک ثابت مطلق ژاکار هستند. از این رو میانگین آن‌ها هم یک برآوردگر بی‌غرض است، و بر طبق کران‌های چرنوف استاندارد برای مجموع متغیرهای تصادفی ۰ - ۱ خطای مورد انتظار از o (۱ / √k) می‌باشد. از این رو، برای هر ε> ۰ ای یک ثابت k = o (۱ / ε ۲) وجود دارد به طوری که خطای مورد انتظار تخمین حداکثر برابر ε است. برای مثال، ۴۰۰ تابع در هم‌سازی ملزوم تخمین j (a,b) با خطای مورد انتظار کوچکتر یا مساوی ۰ ٫ ۰۵ است. این زیر مجموعه h (k) (s) به عنوان یک مشخصه برای مجموعه s است. از این رو …
خلاصه:
در علوم کامپیوتر ، درهم‌سازی میانی یک روش برای تخمین میزان مشابهت دو مجموعه به صورت سریع می‌باشد . این رویه توسط آندری برودر ابداع شد و ابتدا در موتور جستجو آلتاویستا برای پیدا کردن و حذف کردن صفحه‌های تکراری استفاده شد . همچنین در خیلی مسایل مربوط به دسته بندی کردن ، مانند دسته بندی مدارک و اسناد با توجه به تشابه بین مجموعه کلمات آنها ، استفاده شد .