تشخیص محتوای تکراری در مقیاس بزرگ: از Hash تا MinHash

کجا به Deduplication نیاز داریم؟

قبل از اینکه وارد مکانیزم‌های فنی بشیم، بهتره بفهمیم مشکل داده تکراری دقیقاً کجا ظاهر می‌شه و چه هزینه‌ای تحمیل می‌کنه.

شبکه‌های اجتماعی و پلتفرم‌های محتوا

یوتیوب، اینستاگرام و پلتفرم‌های مشابه روزانه با میلیون‌ها آپلود محتوا مواجهن. بخش قابل توجهی از این محتوا کپی، ری‌آپلود یا نسخه‌های کمی ویرایش‌شده از محتوای موجودن. بدون Deduplication، سیستم‌های توصیه‌گر به‌جای محتوای جدید، تکراری پیش‌نهاد می‌دن.

پلتفرم‌های E-commerce

در مارکت‌پلیس‌هایی مثل آمازون یا دیجی‌کالا، یک محصول ممکنه توسط صدها فروشنده مختلف با عناوین، توضیحات و تصاویر متفاوت لیست بشه. Deduplication محصولات باعث می‌شه کاربر یک صفحه محصول یکپارچه ببینه، قیمت‌ها مقایسه بشن و تجربه خرید بهتری داشته باشه. این مسئله رو Product Matching یا Entity Resolution می‌نامن.

سیستم‌های خبری و News Aggregator

در پلتفرم‌هایی که از منابع خبری متعدد تغذیه می‌کنن، یک خبر ممکنه با کمی تغییر در صدها سایت بازنشر بشه. بدون تشخیص شباهت متنی، کاربر ده بار یک خبر رو می‌بینه در حالی که محتوای جدیدی وجود نداره.

سیستم‌های CRM و مدیریت مشتری

وقتی یک مشتری از کانال‌های مختلف (وب‌سایت، اپلیکیشن، تماس تلفنی) وارد سیستم می‌شه یا اطلاعاتش با حروف بزرگ/کوچک یا اشتباه تایپی ثبت می‌شه، پروفایل‌های تکراری ایجاد می‌شن. این مشکل مستقیماً روی کمپین‌های بازاریابی، Customer Journey و گزارش‌های تحلیلی تأثیر می‌ذاره.

مخرج مشترک همه این موارد:

وقتی حجم داده آن‌قدر زیاد می‌شه که مقایسه مستقیم رکورد به رکورد از نظر محاسباتی ممکن نیست، به الگوریتم‌هایی نیاز داریم که بتونن شباهت رو به‌صورت تقریبی و در مقیاس تشخیص بدن. اینجاست که MinHash و LSH وارد می‌شن.

داده تکراری چیست؟

به طور کلی دو نوع داده تکراری داریم:

۱. تکرار کامل (Exact Duplicate)
در این حالت دو محتوا دقیقاً یکسان هستند.
مثال:

سند A:
سلام دنیا

سند B:
سلام دنیا

در این سناریو استفاده از Hashهای معمولی کاملاً کافی است.

۲. تکرار تقریبی (Near Duplicate)
در این حالت محتواها دقیقاً یکسان نیستند اما از نظر ساختار بسیار شبیه‌اند.
مثال:

سند A:
نسخه جدید Kubernetes منتشر شد.

سند B:
Kubernetes نسخه جدید خود را منتشر کرد.

برای انسان این دو جمله تقریباً یک مفهوم دارند اما Hashهای معمولی آن‌ها را کاملاً متفاوت در نظر می‌گیرند.

شباهت Jaccard؛ پایه‌ای‌ترین معیار اندازه‌گیری تشابه:

قبل از هر چیز باید یک سوال ساده رو جواب بدیم: «دو سند چقدر به هم شبیه‌اند؟»
یکی از بنیادی‌ترین و در عین حال کاربردی‌ترین معیارها برای این سوال، Jaccard Similarity است.

فرمول آن ساده است:

چجوری دو متن رو در جاکارد تشابه سنجی کنیم؟

متن را به مجموعه تبدیل کنیم:
برای اینکه بتوانیم Jaccard را روی متن اعمال کنیم، ابتدا باید متن را به یک مجموعه تبدیل کنیم. رایج‌ترین روش Shingling (یا k-gram) است: متن را به تکه‌های k کاراکتری یا k کلمه‌ای متداخل تقسیم می‌کنیم.

مشکل اصلی: مقیاس

Jaccard به‌عنوان یک مفهوم ریاضی کامل است، اما در دنیای واقعی یک مشکل اساسی دارد:
اگر n سند داشته باشید، تعداد مقایسه‌های لازم برابر است با:

و اما MinHash

MinHash یک الگوریتم probabilistic است که به‌جای محاسبه دقیق Jaccard، آن را با دقت قابل تنظیم تخمین می‌زند — و این کار را در زمان و حافظه‌ای بسیار کمتر انجام می‌دهد.

بینش اصلی:
قضیه‌ای که MinHash روی آن بنا شده این است:

اگر یک تابع hash تصادفی و یکنواخت داشته باشیم که عناصر مجموعه را permute کند، احتمال اینکه minimum مقدار hash روی مجموعه A و B یکسان باشد، دقیقاً برابر Jaccard آن‌هاست.

ساختن Signature

ما برای تشابه سنجی متون نیاز داریم تا یک Signature تولید کنیم و آن نماینده متن ما در فرایند تشابه سنجی Signature Vector شامل یک ارایه از چندین هش است که جولوتر در باره طول اون صحبت میکنیم.

import hashlib
def minhash_signature(shingles: set, num_hashes: int = 128) -> list[int]:
    signature = []
    for seed in range(num_hashes):
        min_val = float('inf')
        for shingle in shingles:
            h = int(hashlib.md5(f"{seed}:{shingle}".encode()).hexdigest(), 16)
            min_val = min(min_val, h)
        signature.append(min_val)
    return signature

حالا به‌جای مقایسه دو مجموعه کامل از shingle، فقط دو vector از k عدد صحیح را با هم مقایسه می‌کنیم:

def estimate_jaccard(sig_a: list[int], sig_b: list[int]) -> float:
    matches = sum(a == b for a, b in zip(sig_a, sig_b))
    return matches / len(sig_a)

فلسفه MinHash:
ایده اصلی ساده است: اگر دو مجموعه زیاد با هم اشتراک داشته باشند، وقتی همه عناصرشان را hash کنیم و کوچک‌ترین مقدار را بگیریم، احتمال بالایی وجود دارد که آن کوچک‌ترین مقدار در هر دو مجموعه یکسان باشد.
چرا کوچک‌ترین؟ چون minimum یک نقطه مرجع ثابت است — از هر مجموعه‌ای فقط یک عدد نمایندگی می‌کند و قابل مقایسه است.
یک بار hash کافی نیست چون واریانس بالاست. پس همین کار را با seed های مختلف تکرار می‌کنیم — هر seed یک ترتیب متفاوت از hash ها تولید می‌کند و هر بار یک minimum متفاوت می‌گیریم. نتیجه یک Signature Vector است؛ آرایه‌ای از minimum ها که نماینده کل سند است.
هرچه دو Signature بیشتر در موضع‌های یکسان مقدار برابر داشته باشند، دو سند بیشتر به هم شبیه‌اند.

چقدر دقیق است؟

خطای تخمین با فرمول زیر کنترل می‌شود:
دقت MinHash مستقیماً به تعداد Hashهای استفاده‌شده در Signature بستگی دارد

LSH در MinHash؛ حذف مقایسه‌های غیرضروری

تا اینجا دیدیم که MinHash می‌تواند شباهت Jaccard بین دو سند را با دقت مناسبی تخمین بزند. اما یک مشکل هنوز باقی است، حتی با Signature های کوچک، هنوز باید همه جفت‌ها را با هم مقایسه کنیم. مشکل O(n^2) حل نشده.
Locality Sensitive Hashing تکنیکی است که این مشکل آخر را حل می‌کند. ایده اصلی آن است:

به‌جای مقایسه همه جفت‌ها، فقط جفت‌هایی را مقایسه کن که احتمال شباهت بالایی دارند.

ایده اصلی LSH

هدف LSH این است که اسناد مشابه با احتمال بالا در یک Bucket مشترک قرار بگیرند و اسناد غیرمشابه در Bucketهای متفاوت قرار بگیرند.
به جای اینکه یک سند جدید را با کل دیتاست مقایسه کنیم، تنها اسنادی بررسی می‌شوند که در Bucketهای مشابه قرار گرفته‌اند.
به این ترتیب تعداد مقایسه‌ها از میلیاردها مقایسه به چند ده یا چند صد مقایسه کاهش پیدا می‌کند.

Banding در MinHash

رایج‌ترین روش استفاده از LSH در کنار MinHash، تکنیکی به نام Banding است.
فرض کنید برای هر سند یک Signature با ۱۲۸ مقدار ساخته‌ایم:

[12, 45, 78, 91, ..., 456]

این Signature را به چند بخش (Band) تقسیم می‌کنیم.
برای مثال:

• 32 Band

• هر Band شامل 4 مقدار

Band 1: [12,45,78,91] 
Band 2: [15,22,67,31] 
Band 3: [44,81,10,77]

سپس برای هر Band یک Hash جداگانه تولید می‌شود.
اگر دو سند حداقل در یکی از Bandها Hash یکسانی داشته باشند، به عنوان Candidate مشابه در نظر گرفته می‌شوند.

Inverted Index؛ رویکرد دیگری برای یافتن کاندیداها

MinHash و LSH تنها راه حذف مقایسه‌های O(n2)O(n^2) O(n2) نیستند. Inverted Index — همان ساختار داده‌ای که موتورهای جستجو روی آن بنا شده‌اند — می‌تواند همین نقش را ایفا کند، اما با منطق متفاوتی.

ساختار Inverted Index چیست؟
یک Inverted Index نگاشتی است از token به لیست اسناد حاوی آن token:

"یادگیری ماشین"  → [doc_3, doc_7, doc_41, doc_190]
"شبکه عصبی"      → [doc_7, doc_55, doc_190, doc_312]
"پردازش زبان"    → [doc_41, doc_88, doc_190]

برعکس ایندکس معمولی که از سند به توکن می‌رود، اینجا از توکن به سند می‌رویم.

چطور برای Deduplication استفاده می‌شود؟
منطق آن ساده است:

دو سند فقط در صورتی می‌توانند شبیه هم باشند که حداقل یک توکن مشترک داشته باشند.

مهم‌ترین بخشی که اکثراً نادیده گرفته می‌شود: نرمال‌سازی

تمام الگوریتم‌هایی که تا اینجا بررسی کردیم — Jaccard، MinHash، LSH، Inverted Index — یک فرض ضمنی دارند:

داده‌ای که وارد می‌شود تمیز و یکدست است.

دو متن زیر را در نظر بگیرید:

"یادگیری ماشین در پایتون"
"یادگیری  ماشین در پایتون "

از نظر انسانی کاملاً یکسانند. اما اگر بدون نرمال‌سازی وارد pipeline شوند، shingle های مختلفی تولید می‌کنند، Signature متفاوتی می‌گیرند و سیستم آن‌ها را متفاوت تشخیص می‌دهد.

جمع‌بندی

Deduplication در مقیاس بزرگ یک مسئله چندلایه است. هیچ الگوریتمی به‌تنهایی کافی نیست و موفقیت سیستم به ترکیب درست چند چیز بستگی دارد: نرمال‌سازی محکم، انتخاب رویکرد متناسب با مقیاس، و تنظیم دقیق پارامترها بر اساس داده واقعی.
اگر یک چیز از این مقاله یادتان بماند، این باشد: قبل از اینکه وقت بگذارید روی تنظیم MinHash و LSH، مطمئن شوید pipeline نرمال‌سازی شما مطابق با داده های شما باشد. بیشترین باگ‌های سیستم‌های Deduplication از همین‌جا می‌آیند، نه از انتخاب اشتباه الگوریتم