مستوى المقال: محترف. يفترض إنك تعرف الـ embeddings والبحث الدلالي، وعايز تفهم إزاي قاعدة البيانات الشعاعية بتلاقي أقرب جار في ملايين المتجهات في أقل من مللي ثانية.
بحث المتجهات في الملايين: HNSW وأقرب جار
لو البحث الدلالي عندك بياخد 200 مللي ثانية على مليون متجه والـ CPU مش مشغول، المشكلة مش في السيرفر. المشكلة إنك بتقارن كل متجه بكل متجه في كل استعلام. الحل اسمه HNSW، وبينزّل الزمن ده لأقل من مللي ثانية بدقة قريبة من 99%.
المشكلة باختصار
خزّنت مليون مقال كـ embeddings، كل واحد متجه بطول 768 رقم. المستخدم بيبعت سؤال، بتحوّله لمتجه، وعايز أقرب 10 متجهات ليه. الطريقة المباشرة: احسب المسافة بين متجه السؤال وكل المليون. ده اسمه البحث الشامل (brute-force) وتعقيده O(n·d): مليون متجه × 768 بُعد = حوالي 768 مليون عملية ضرب وجمع لكل استعلام. على نواة واحدة ده بيتراوح بين 80 و150 مللي ثانية. اضربها في 500 مستخدم في الثانية، وهتحتاج أسطولًا من الخوادم لمهمة المفروض تخلص في لمح البصر.
الفكرة قبل العلم: البحث في ملعب
تخيّل إنك عايز تلاقي صاحبك في ملعب فيه 80 ألف متفرج. الطريقة الغبية إنك تبص في وش كل واحد لحد ما تلاقيه. الطريقة الذكية: تسأل حد "صاحبي في القطاع الشمالي" فتقفز للقطاع ده، وبعدين "في الصف العلوي" فتقرّب أكتر، وبعدين تمشي بين الكراسي القريبة بس. كل خطوة بتقصّ مساحة البحث لجزء صغير. انت بتضحّي بضمانة إنك أكيد هتلاقيه بأقصر مسار، مقابل إنك توصل أسرع بمراحل. ده بالظبط اللي بيعمله HNSW.
HNSW علميًا: رسم بياني متعدد الطبقات
اسمه الكامل Hierarchical Navigable Small World. هو رسم بياني (graph) كل عقدة فيه متجه، والحواف بتربط كل متجه بجيرانه الأقرب. الحيلة إنه متعدد الطبقات: الطبقة القاعدية (Layer 0) فيها كل المتجهات وكثيفة الروابط. كل طبقة أعلى فيها عينة أقل بكثير، بس بحواف أطول تقفز مسافات كبيرة في الفضاء.
البحث بيبدأ من نقطة دخول ثابتة في أعلى طبقة، وبيمشي ناحية العقدة الأقرب لمتجه السؤال باستخدام القفزات الطويلة. أول ما يعجز عن التقريب أكتر في الطبقة دي، بينزل طبقة تحت ويكرّر. النتيجة إن عدد العُقد اللي بيزورها بيتناسب مع لوغاريتم عدد المتجهات، مش مع العدد نفسه. يعني الفرق بين مليون خطوة و20 خطوة تقريبًا.
الكود: قِس الفرق بنفسك
مكتبة hnswlib بتنفّذ الخوارزمية دي بكفاءة. الكود ده يبني فهرسًا على 500 ألف متجه ويقارن زمن HNSW بالبحث الشامل:
import hnswlib, numpy as np, time
dim, n = 768, 500_000
data = np.random.rand(n, dim).astype(np.float32)
q = np.random.rand(dim).astype(np.float32)
# 1) البحث الشامل: أساس المقارنة
t = time.perf_counter()
dists = np.linalg.norm(data - q, axis=1)
brute_top = set(np.argsort(dists)[:10])
print(f"brute-force: {(time.perf_counter()-t)*1000:.1f} ms")
# 2) بناء فهرس HNSW مرة واحدة
index = hnswlib.Index(space='l2', dim=dim)
index.init_index(max_elements=n, ef_construction=200, M=16)
index.add_items(data) # يُبنى مرة، ثم يُعاد استخدامه
index.set_ef(100) # ef_search: يتحكم في الدقة مقابل السرعة
# 3) الاستعلام
t = time.perf_counter()
labels, _ = index.knn_query(q, k=10)
print(f"HNSW: {(time.perf_counter()-t)*1000:.3f} ms")
recall = len(brute_top & set(labels[0])) / 10
print(f"recall@10: {recall:.2f}")