يتطلب هذا المقال مستوى: متوسط. يفترض إنك تعرف يعني إيه 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 متجهات