يتطلب هذا المقال مستوى: متوسط. يفترض إنك تعرف يعني إيه embedding ومتجه (vector)، وإن عندك فكرة بسيطة عن البحث الدلالي. مش لازم تكون شغّلت قاعدة بيانات متجهات قبل كده.
لو عندك مليون متجه وعايز تلاقي أقرب 10 لنص المستخدم، المقارنة بالكل بتاخد مئات المللي ثانية لكل استعلام. خوارزمية HNSW بتنزّلها لأقل من مللي ثانية مقابل دقة تقارب 97%. هنا هتفهم إزاي، وإمتى الحل ده مش مناسب لك.
خوارزمية HNSW: البحث التقريبي عن أقرب جار في ملايين المتجهات
المشكلة باختصار
كل بحث دلالي أو نظام RAG بيحوّل النص لمتجه أرقام (embedding). وقت السؤال، محتاج تلاقي أقرب المتجهات المخزّنة للمتجه بتاع السؤال. الطريقة المباشرة اسمها البحث الشامل (brute-force / flat): قارن السؤال بكل متجه واحد واحد.
ده بيشتغل تمام على 10 آلاف متجه. لكن على مليون متجه بأبعاد 768، كل استعلام بيتطلب مليون عملية حسابية تقيلة. اللي بيحصل فعلاً: زمن الاستجابة بيقفز لـ 300–400 مللي ثانية لكل سؤال على معالج واحد. لو عندك 200 مستخدم بيبحثوا في نفس اللحظة، السيرفر بيقع.
الفكرة الأساسية: زي سايق التوصيل
تخيّل سايق توصيل عايز يوصل لعنوان في مدينة كبيرة. مش هيمشي شارع شارع من أول المدينة. هو بيبدأ بالطريق السريع (الدائري)، يقرّب من المنطقة، ينزل على شارع رئيسي، وبعدها يدخل الشارع الصغير للعنوان بالظبط. كل طبقة أوسع بتقرّبه بسرعة، والطبقة الأصغر بتظبّط المكان.
HNSW بيعمل نفس الحكاية بالظبط. بدل ما يقارن بكل المتجهات، بيبني خريطة طرق من طبقات: الطبقة العليا فيها عدد قليل من العقد بقفزات طويلة (زي الطرق السريعة)، وكل ما تنزل طبقة بتزيد العقد وتقصر القفزات، لحد الطبقة صفر اللي فيها كل المتجهات.
التفسير العلمي
الاسم اختصار لـ Hierarchical Navigable Small World. مبني على فكرتين:
- Small World Graph: رسم بياني بتربط فيه كل عقدة بأقرب جيرانها، فأي عقدتين بينهم عدد قليل من القفزات (زي فكرة "ست درجات من الانفصال").
- الطبقات الاحتمالية (Skip List): كل متجه بيتحط في طبقة عشوائيًا باحتمال متناقص. القليل بس بيوصل للطبقات العليا، فتبقى متفرقة وقفزاتها طويلة.
البحث بيبدأ من نقطة دخول ثابتة في أعلى طبقة، ويعمل بحث جشع (greedy): كل خطوة بيروح للجار الأقرب للسؤال. لما يوصل لأقرب عقدة في الطبقة دي، بينزل طبقة تحت ويكرّر. النتيجة إن التعقيد بينزل من O(n) في البحث الشامل لـ O(log n) تقريبًا. يعني على مليون متجه، بدل مليون مقارنة بتعمل عشرات المقارنات بس.
مثال تنفيذي شغّال
ده كود Python بمكتبة hnswlib بيبني فهرس على مليون متجه ويعمل استعلام:
import hnswlib
import numpy as np
dim = 768 # أبعاد متجه الـ embedding
num = 1_000_000 # مليون متجه
data = np.random.rand(num, dim).astype('float32')
# بناء الفهرس
index = hnswlib.Index(space='cosine', dim=dim)
index.init_index(max_elements=num, ef_construction=200, M=16)
index.add_items(data, np.arange(num))
# الاستعلام
index.set_ef(50) # كل ما زاد ef زادت الدقة وقلّت السرعة
query = np.random.rand(1, dim).astype('float32')
labels, distances = index.knn_query(query, k=10)
print(labels) # أقرب 10 متجهات
الأرقام اللي بتطلع في الواقع على جهاز عادي: البحث الشامل ~350 مللي ثانية لكل استعلام، وHNSW بنفس البيانات ~1.2 مللي ثانية، بدقة recall@10 حوالي 0.97. يعني تسريع أكتر من 250 مرة مقابل خسارة 3% من النتائج المثالية.
البارامترات اللي بتتحكم في كل حاجة
- M: عدد الروابط لكل عقدة. أعلى = دقة أحسن وذاكرة أكتر وبناء أبطأ. القيمة الشائعة 16–32.
- ef_construction: جودة البناء. أعلى = فهرس أدق ووقت بناء أطول. 100–200 كفاية غالبًا.
- ef (وقت البحث): عدد المرشحين اللي بيفحصهم لكل استعلام. ده الزرار اللي بتلعب بيه لحظيًا: تزوّده تكسب دقة وتخسر سرعة.
الـ trade-offs الصريحة
الـ trade-off الأول: الدقة مقابل السرعة. رفع ef من 50 لـ 200 ممكن يرفع الـ recall لـ 0.99، بس بيضاعف زمن الاستعلام تقريبًا. الافتراض إن 97% دقة مقبولة عندك — لو محتاج نتائج مضبوطة 100% ده مش مكانك.
الـ trade-off التاني: الذاكرة. الرسم البياني بيضيف روابط فوق المتجهات نفسها. عند M=16 على مليون متجه، الروابط بتاكل حوالي 128 ميجابايت زيادة فوق حجم البيانات الأصلي — مقبول، لكن على 100 مليون متجه الرقم ده بيبقى مؤثر.
الـ trade-off التالت: التحديث. HNSW ممتاز للقراءة، لكن الحذف الكتير بيخرّب جودة الرسم مع الوقت. الافتراض إن بياناتك شبه ثابتة أو بتتعاد فهرستها دوريًا.
متى لا تستخدم هذه الطريقة
- بيانات صغيرة (أقل من 10–50 ألف متجه): البحث الشامل (flat) بيبقى سريع كفاية ومضبوط 100%. HNSW هنا تعقيد بلا فايدة.
- محتاج دقة كاملة مضمونة: إزالة التكرار أو المطابقة القانونية بتحتاج نتيجة مضبوطة، مش تقريبية.
- فلترة تقيلة بالميتاداتا: لو بتفلتر بشروط كتير قبل البحث، الـ HNSW ممكن يرجّع نتائج ناقصة إلا لو استخدمت آلية فلترة مدمجة (زي اللي في Qdrant).
- تحديث/حذف مستمر بمعدل عالي: فكّر في فهرس يدعم إعادة البناء أو بنية مختلفة.
الخطوة التالية
خُد الـ embeddings اللي عندك دلوقتي، وابنِ فهرس hnswlib بـ M=16 وef_construction=200. بعدين خُد 1000 استعلام عيّنة، وقِس الـ recall@10 بمقارنة نتايج HNSW بنتايج البحث الشامل. زوّد ef بالتدريج لحد ما الـ recall يعدّي 0.95، وسيبه عند أقل قيمة تحقق ده. كده تكون ظبطت أسرع بحث بأقل خسارة دقة.
المصادر
- الورقة الأصلية: Malkov, Y. A., & Yashunin, D. A. (2018). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, IEEE TPAMI — arxiv.org/abs/1603.09320
- مكتبة hnswlib الرسمية: github.com/nmslib/hnswlib
- توثيق FAISS عن فهارس HNSW: github.com/facebookresearch/faiss/wiki
- pgvector — فهرس HNSW داخل PostgreSQL: github.com/pgvector/pgvector
- توثيق Qdrant عن HNSW والفلترة: qdrant.tech/documentation/concepts/indexing