حذف اسناد تکراری در مقیاس بالا: از تطابق دقیق تا اسنادِ «تقریباً» مشابه

حذف داده‌های تکراری یا همون Deduplication تا وقتی که پای داده‌های واقعی وسط نیومده، خیلی ساده به نظر می‌رسه.

اگه فقط چند هزار تا متن کوتاه داشته باشید، تقریباً هر روشی جواب میده. اما وقتی صحبت از میلیون‌ها سند طولانی، زبان‌های مختلف، داده‌های کثیف و نیاز به پیدا کردن اسنادی میشه که «خیلی شبیه هم هستن» (ولی دقیقاً یکی نیستن)، بازی کلاً عوض میشه: از الگوریتم‌ها و ساختار داده بگیرید تا مدیریت حافظه و حتی تعریفی که از «شباهت» دارید، همگی تغییر می‌کنن.

توی این پست، می‌خوام قدم‌به‌قدم مسیر تکامل سیستم‌های حذف تکرار رو با افزایش مقیاس (Scale) بررسی کنیم:

• اول از متن‌های کوتاه و حذف موارد دقیقاً یکسان شروع می‌کنیم.
• بعد میریم سراغ مجموعه‌های بزرگ (بیشتر از ۱۰ میلیون سند طولانی) و چالش‌های مهندسی که اونجا ظاهر میشن.
• در نهایت هم با بحث Near-duplicate یا تشخیص اسناد «تقریباً مشابه» بحث رو می‌بندیم؛ یعنی پیدا کردن اسنادی که محتواشون یکیه ولی از نظر بایتی با هم فرق دارن. یه نگاهی هم به شباهت‌های معنایی میندازیم.

---

۱. حذف تکرارهای دقیق برای متن‌های کوتاه

بیاید با ساده‌ترین حالت شروع کنیم: اسناد کوتاه (مثل توییت، کامنت یا مقاله‌های کوتاه) و دیتاستی که راحت توی رم (RAM) جا میشه.

توی این سطح، حذف تکرار یعنی: اگه دو تا سند دقیقاً یکی هستن، فقط یکی رو نگه دار.

۱.۱. استفاده از هش (Hash-based)

دم‌دستی‌ترین راه، هش کردن کل متن هست:

import hashlib

def hash_text(text: str) -> str:
    return hashlib.sha256(text.encode("utf-8")).hexdigest()

seen = set()
unique_docs = []
for doc in documents:
    h = hash_text(doc)
    if h not in seen:
        seen.add(h)
        unique_docs.append(doc)

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

• هش کردن، متن با هر طولی رو به یک «اثر انگشت» با اندازه ثابت تبدیل می‌کنه.
• چک کردن وجود یک آیتم در set به طور میانگین از مرتبه O(1) هست.
• برای داده‌های کم، هزینه CPU و حافظه ناچیزه.

نکته مهم:

هش‌های رمزنگاری مثل SHA-256 برای این کار زیاده‌روی هستن. احتمال رخ دادن «تصادم» (Collision) هم از نظر تئوری هست، ولی در این ابعاد عملاً صفره.

۱.۲. نرمال‌سازی از خودِ هش مهم‌تره

یک اشتباه رایج تازه‌کارها، هش کردن متن خام هست. این دو تا عبارت از نظر معنایی یکی هستن، ولی از نظر بایتی فرق دارن:

1. "Hello world"
2. "hello world"

قبل از هش کردن، نرمال‌سازی حیاتیه:

import re

def normalize(text: str) -> str:
    text = text.lower()
    text = re.sub(r"\s+", " ", text) # حذف فاصله‌های اضافی
    return text.strip()

در مقیاس‌های کوچک، تصمیماتی که برای نرمال‌سازی می‌گیرید، معمولاً بیشتر از خودِ الگوریتم روی نتیجه تاثیر می‌ذاره.

---

۲. وقتی داده‌ها دیگه توی رم جا نمی‌شن

حالا بیاید مقیاس رو ببریم بالا. تصور کنید:

• ۱۰ میلیون سند داریم.
• میانگین طول هر کدوم: ۵ تا ۲۰ کیلوبایت.
• زبان‌های مختلف.
• ذخیره شده روی دیسک یا Object Storage.

اینجاست که با اون روش ساده set() بلافاصله کدمون کرش می‌کنه.

۲.۱. حذف تکرار به صورت جریانی (Streaming)

اولین تغییر ذهنی، رفتن به سمت Streaming هست. یعنی به جای بارگذاری همه چیز، اسناد رو یکی‌یکی (یا دسته‌ای) پردازش می‌کنیم و فقط «اثر انگشت‌ها» رو نگه می‌داریم.

def hash_text(text: str) -> bytes:
    return hashlib.md5(text.encode()).digest()

چرا MD5 به جای SHA-256؟

• هش کوچک‌تر (۱۶ بایت در مقابل ۳۲ بایت).
• سرعت بالاتر.
• هنوز هم برای حذف تکرار کاملاً جواب میده.

در ۱۰ میلیون سند: $16 \text{ bytes} \times 10M \approx 160 \text{ MB}$. این عدد لب مرزه، ولی هنوز قابل مدیریته.

۲.۲. استفاده از پایگاه داده‌های کلید-مقدار (Disk-backed)

اگه حافظه رم کم آوردید، نترسید؛ فقط ساختار داده رو عوض کنید. راه‌حل‌های رایج استفاده از LevelDB، LMDB یا Redis هست.

مثال با LMDB:

import lmdb
import hashlib

env = lmdb.open("dedup.lmdb", map_size=10**10)
with env.begin(write=True) as txn:
    for doc in documents:
        h = hashlib.md5(doc.encode()).digest()
        if not txn.get(h):
            txn.put(h, b"1")
            process(doc)

این الگو — چک کردن هش قبل از پردازش — توی پایپ‌لاین‌های بزرگ خیلی رایجه.

۲.۳. در مقیاس‌های عظیم، مرتب‌سازی (Sorting) برنده است

وقتی به صدها میلیون سند می‌رسیم، حتی دیتابیس‌های Key-Value هم هزینه‌بر میشن. یک ترفند کلاسیک اینه:

1. هش‌ها رو محاسبه کنید.
2. زوج‌های (hash, doc_id) رو روی دیسک بنویسید.
3. یک External Sort بر اساس هش انجام بدید.
4. موارد تکراری که حالا کنار هم قرار گرفتن رو حذف کنید.

توی سیستم‌های توزیع شده مثل Spark، این کار خیلی ساده انجام میشه:

rdd.map(lambda d: (hash(d), d)) \
   .reduceByKey(lambda a, b: a) \
   .values()

وقتی مقیاس خیلی بالا میره، الگوریتم‌هایی که روی کاغذ کندتر به نظر میان (مثل مرتب‌سازی کل داده)، در عمل به خاطر سازگاری با دیسک و موازی‌سازی، برنده‌ می‌شن.

---

۳. چرا حذف تکرارِ «دقیق» کافی نیست؟

تا اینجا فرض کردیم اسناد دقیقاً مثل هم هستن. اما توی دنیای واقعی، این اتفاق نادریه. مثلاً:

• خبرهایی که با ادیت‌های خیلی کوچک بازنشر میشن.
• اسناد حقوقی که فقط تاریخشون عوض شده.
• محتوای تولید شده توسط LLM که بازنویسی (Paraphrase) شده.

هش کردنِ بایتی اینجا کاملاً شکست می‌خوره. حالا وارد دنیای Near-duplicate detection میشیم.

---

۴. از سند به مجموعه: روش Shingling

ایده اصلی پشت تشخیص شباهت نزدیک اینه: به جای متن خام، ساختار رو مقایسه میکنیم.

۴.۱. کی-شینگل (k-shingles)

یک شینگل، دنباله‌ای متوالی از توکن‌هاست.

def shingles(tokens: List[str], k: int = 5):
    return [tuple(tokens[i:i+k]) for i in range(len(tokens) - k + 1)]

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

مثلاً با k=2:

• سند الف: ["داده کاوی", "کاوی جذاب", "جذاب است"]
• سند ب: ["داده کاوی", "کاوی عالی", "عالی است"]

حالا می‌تونیم از شباهت جاکارد (Jaccard Similarity) استفاده کنیم:

$J(A,B) = \frac{|A \cap B|}{|A \cup B|}$

اما یک مشکل بزرگ هست: مقایسه همه جفت‌ اسناد با هم از مرتبه $O(n^2)$ هست که برای میلیون‌ها سند عملاً غیرممکنه.

---

۵. الگوریتم MinHash: فشرده‌سازی شباهت

الگوریتم MinHash وقتی برای اولین بار درکش می‌کنید، شبیه جادو می‌مونه. به جای ذخیره همه شینگل‌ها، یک «امضای کوتاه» ذخیره می‌کنیم که شباهت جاکارد رو حفظ می‌کنه.

ایده اصلی:

• چندین تابع هش رو روی هر شینگل اعمال می‌کنیم.
• برای هر تابع هش، فقط کوچکترین مقدار (Minimum) رو نگه می‌داریم.
• احتمال اینکه دو سند مقدارِ مینیممِ یکسانی داشته باشن، دقیقاً برابر با شباهت جاکارد اون‌هاست.

هر چی تعداد توابع هش بیشتر باشه، دقت تخمین شباهت بالاتر میره. اما باز هم مشکل $O(n^2)$ پابرجاست. اینجا سؤالی پیش میاد: چطور بدون مقایسه همه با هم، جفت‌های مشابه رو پیدا کنیم؟ پاسخ: LSH.

---

۶. LSH

اگر MinHash به ما امضاهای فشرده میده، LSH به ما توانایی پیدا کردن کاندیداها رو میده.

ایده اینه:

1. امضاها رو به چند بخش (Band) تقسیم کن.
2. هر بخش رو هش کن.
3. فقط اسنادی رو با هم مقایسه کن که حداقل توی یک «سطل» (Bucket) مشترک افتادن.

LSH عمداً دقت رو فدای سرعت می‌کنه. توی سیستم‌های بزرگ، اینکه یک مورد تکراری رو اشتباهاً چک کنیم (False Positive) خیلی بهتر از اینه که یک تکرار واقعی رو کلاً از دست بدیم (False Negative).

---

۷. حذف تکرار با استفاده از Embedding (شباهت معنایی)

گاهی اوقات اصلاً ساختار کلمات براتون مهم نیست، بلکه معنا براتون مهمه. دو تا متن ممکنه با کلمات کاملاً متفاوت، یک حرف رو بزنن. اینجاست که Embedding وارد میشه.

یک مدل Embedding، سند رو به یک بردار عددی در فضای چندبعدی تبدیل می‌کنه. حالا به جای اینکه بپرسیم «آیا این دو متن کلمات مشترک دارن؟»، می‌پرسیم «آیا بردار این دو متن در فضا به هم نزدیک هستن؟»

نکته: استفاده از بردارها خیلی سنگینه (مثلاً ۳۰ گیگابایت رم برای ۱۰ میلیون سند). برای همین معمولاً از بردارها به عنوان مرحله اول استفاده نمی‌کنیم، بلکه به عنوان فیلتر نهایی روی کاندیداهایی که قبلاً با روش‌های ارزان‌تر پیدا شدن، استفاده می‌کنیم. میتونین این کار رو با الستیک سرچ خیلی خوب و سریع انجام بدین. برای آشنایی میتونین این پست رو بخونین.

---

۸. ابزار FAISS: جستجوی شباهت در مقیاس واقعی

برای جستجوی بین میلیون‌ها بردار، نمی‌تونیم تک‌تک اون‌ها رو با هم مقایسه کنیم. FAISS (کتابخانه فیس‌بوک) استاندارد این کاره. FAISS از تکنیک‌هایی مثل کوانتیزه‌سازی (Quantization) استفاده می‌کنه تا سرعت رو به‌شدت بالا ببره.

توی تنظیمات FAISS برای حذف تکرار، یادتون باشه که هیچ‌وقت به دنبال جستجوی دقیق (IndexFlat) نرید، چون خیلی کنده. همیشه از روش‌های تقریبی مثل IndexIVFFlat یا HNSW استفاده کنید.

---

سخن پایانی: شکار تکراری‌ها

حذف تکرار (Deduplication) یک الگوریتم واحد نیست؛ یک فرآیند پالایش تدریجی است:

1. ارزان شروع کنید: اول موارد دقیقاً یکسان رو با هش ساده حذف کنید.
2. هوشمندانه جلو برید: از MinHash و LSH برای پیدا کردن شباهت‌های ساختاری استفاده کنید.
3. فقط وقتی لازمه هزینه کنید: از Embedding و FAISS برای شباهت‌های معنایی پیچیده استفاده کنید.

خلاصه مطلب اینکه: سیستم‌های حذف تکرارِ خوب، فقط کدنویسی نشدن، بلکه مهندسی شدن. وقتی یک بار چنین سیستمی بسازید، دیگه هیچ‌وقت به دکمه «حذف تکراری‌ها» مثل قبل نگاه نمی‌کنید!