البحث المتجهي دون مسح شامل: كيف تعمل خوارزميتا IVF وHNSW

عندما تحتوي قاعدة بيانات متجهية على ملايين التضمينات (embeddings)، يصبح البحث عن المتجهات المتشابهة بطريقة المسح الشامل مستحيلاً. تعالج خوارزميتان، هما IVF وHNSW، هذه المشكلة بالبحث التقريبي، فتجدان الجواب في أجزاء من الثانية بدل دقائق. وتتناول مقالة جديدة مفصلة على Habr النهجين معاً، بدءاً من الأساس الرياضي النظري وصولاً إلى التنفيذ بلغة Python.

لماذا لا ينجح البحث الدقيق

في الأبعاد المنخفضة (2D و3D) يمكن بناء فهارس مكانية، مثل أشجار k-d وأشجار R. تعتمد هذه الفهارس على الهندسة: إذا كان الاستعلام بعيداً عن جزء معيّن من الفضاء، يمكن استبعاد هذا الجزء من البحث دون خسارة أي نتائج.

لكن هذه الفكرة تنهار في الأبعاد العالية (768D لنموذج BERT و3072D لنموذج GPT-4 Turbo). تفقد المسافات طابعها المحلي، إذ تصبح جميع النقاط تقريباً على مسافة متقاربة جداً من بعضها. يُعرف هذا الأثر باسم «لعنة الأبعاد». وتفقد الفهارس التقليدية فاعليتها ولا تعود تقلّص فضاء البحث، فنعود إلى المسح الشامل، أي مقارنة الاستعلام بجميع الملايين من المتجهات في القاعدة.

IVF: التجميع في العناقيد يسعف البحث

تعالج IVF (Inverted File Index) المسألة عبر تجميع مسبق في عناقيد. تستخدم الخوارزمية k-means الكلاسيكية لتقسيم الفضاء إلى «سلال» أو عناقيد افتراضية. الفكرة بسيطة: إذا كانت المتجهات قريبة من بعضها في الفضاء فمن المفترض أن تقع في العنقود نفسه، وعند البحث يكفي فحص بضعة عناقيد ذات صلة بدل فحص القاعدة كلها.

تعمل العملية على مرحلتين. أثناء الفهرسة يُسنَد كل متجه في القاعدة إلى أقرب عنقود له (أي إلى مركزه). وأثناء البحث يعثر النظام أولاً على أقرب K عنقود للاستعلام عبر بحث سريع، ثم يبحث عن المطابقة الدقيقة داخل هذه العناقيد فقط. هذا يقلّص عدد المقارنات بشكل حاد، فبدل ملايين المقارنات يلزم إجراء بضعة آلاف فقط.

• المرحلة الأولى: تقسّم k-means الفضاء إلى مئات أو آلاف العناقيد
• المرحلة الثانية: يُفهرَس كل متجه في القاعدة ضمن عنقوده (يُحفظ معرّف المركز ID)
• عند البحث: نعثر على أقرب K عنقود، ثم نجري بحثاً كاملاً داخلها فقط

تتوسع IVF بشكل جيد إلى مليارات المتجهات، وتتطلب ذاكرة قليلة نسبياً. ويقدّم Habr تنفيذاً بلغة Python مع أمثلة برمجية محددة ومقاييس للأداء.

HNSW: رسم بياني هرمي للجوار

تعتمد HNSW (Hierarchical Navigable Small World) نهجاً مختلفاً تماماً، فهي تبني رسماً بيانياً للجوار بدل العناقيد. يصبح كل متجه عقدة في الرسم البياني، وتربط الحواف بين المتجهات المتجاورة (القريبة). يُبنى الرسم هرمياً: تضم المستويات السفلى الجوار المحلي الكثيف لكل متجه، وتضم المستويات العليا وصلات بعيدة متفرقة تتيح نزولاً عالمياً تقريبياً سريعاً.

أثناء البحث تبدأ الخوارزمية من نقطة دخول في المستوى الأعلى، وتنزل عبر الهرم، مختارة في كل خطوة الجيران الأقرب إلى الاستعلام المطلوب. وهذا يشبه التنقل في مدينة كبيرة: تبدأ بالطرق السريعة الرئيسية، ثم تنتقل إلى الشوارع المحلية حتى تصل إلى العنوان المطلوب.

«تعمل HNSW مثل نظام ملاحة في مدينة غير مألوفة: تبدأ بالطرق الرئيسية، ثم تنزل إلى الشوارع المحلية»، بحسب ما يشرحه مؤلفو المقالة على

Habr.

عملياً، تكون HNSW عادةً أسرع من IVF في البحث ذي زمن الاستجابة المنخفض، لكنها تتطلب ذاكرة أكبر لتخزين بنية الرسم البياني والروابط بين العقد.

ماذا يعني ذلك

تُستخدم الخوارزميتان في قواعد البيانات المتجهية الحديثة: Pinecone وWeaviate وQdrant وMilvus. وبالنسبة إلى تطبيقات LLM، مثل أنظمة RAG والبحث في المستندات والتوصيات الدلالية وروبوتات الدردشة الذكية، فإن اختيار خوارزمية البحث يؤثر مباشرة في سرعة الاستجابة وتجربة المستخدم.

يُفضَّل اختيار IVF لقواعد البيانات الضخمة ذات الذاكرة المحدودة، بينما تتفوق HNSW عندما يكون الحد الأدنى من زمن الاستجابة مطلباً أساسياً، وعند العمل مع مجموعات بيانات أكثر إحكاماً.