🎮 قصة "سلم وحيّة"
تخيل إنك بتلعب "سلم وحيّة" مع أصحابك.. 🎲
في الطريقة العادية (Basic Merge)، إنت بتمشي المربعات واحد ورا الثاني (1، 2، 3...). هاض بطيء جداً.
لكن.. شو بصير أول ما توقف عند "السلم"؟ 🪜
فجأة، بتعمل "قفزة" خرافية من المربع 10 للمربع 50 بلمحة بصر! هاض "السلم" هو بالظبط الـ Skip
Pointer. هو اختصار ذكي بيخليك تتعدى "مربعات" (بيانات) مش محتاجها.
✨ باختصار: الـ Skip Lists هي الداتا وهي راكبة "سلالم" عشان تهرب من بطء المشي العادي!
⏪ Recall: Basic Merge
Walk through the two postings simultaneously, in time linear in the total number
of postings entries.
تخيلوا معنا القائمتين (Brutus و Caesar):
🦶 حبة حبة.. كيف العملية بتم؟
1️⃣ بنبدأ بالمؤشر عند أول رقم في Brutus وهو (2) وأول رقم في Caesar وهو (1).
2️⃣ الـ (1) أصغر، فبنحرك مؤشر Caesar للرقم اللي بعده وهو (2).
3️⃣ صرنا عند (2) و (2) والنتيجة: MATCH! بنسجل الرقم 2 عنا وبنحرك الاثنين للرقم اللي بعده.
4️⃣ الآن إحنا عند (4) و (3) والـ (3) أصغر، فبنحرك Caesar للرقم (8).
5️⃣ صرنا عند (4) و (8) والـ (4) أصغر، فبنحرك Brutus للرقم (8).
6️⃣ صرنا عند (8) و (8) والنتيجة: MATCH! بنسجل الرقم 8 وبنحرك الاثنين.
⏳ إيش المشكلة؟
العملية هاي بتأخذ وقت O(m+n)، يعني لو القائمة فيها مليون عنصر، بدك تمشي مليون خطوة "حبة حبة"
عشان توصل للآخر!
❓ هل بنقدر نعمل إشي أسرع؟ الجواب: نعم، وهاض هو دور الـ Skip Lists.
⏭️ Augmenting Index with Skips
هنا نجاوب على الأسئلة الثلاثة المهمة (ليش، كيف، وين):
Why? To skip postings that will not figure in the search results.
🤔 ليش؟
ببساطة، عشان "نقفز" فوق الأرقام اللي مش رح تدخل في النتيجة (Intersection). إذا إحنا عند رقم
صغير وبندور على رقم كبير موجود في القائمة الثانية، الـ Skip بيخلينا نتعدى كل الأرقام "اللي
بالنص" اللي أصغر منه، وهيك بنقلل عدد العمليات وبنسرع البحث.
How? (at indexing time)
🛠️ كيف؟
هاض الإجراء بتم في وقت الفهرسة (Indexing Time). وإحنا بنبني الـ Index وبنكتب الـ
Postings Lists، بنضيف مؤشر إضافي (Pointer) بياخدنا لمكان أبعد في القائمة. يعني التجهيز بتم
مسبقاً مش وإحنا بنبحث.
Where do we place skip pointers?
📍 وين بنحطهم؟
في قاعدة بنمشي عليها عشان نوازن بين "سرعة البحث" وبين "حجم التخزين": بنحط قفزة كل
√L
(حيث L هو طول القائمة).
يعني لو القائمة فيها 100 عنصر، بنحط قفزة كل 10 نودات. هيك بنحصل على أفضل أداء للبحث بدون ما
نكبر حجم الملف بشكل كبير.
💻 Algorithm: Intersection with Skips
هاد هو الكود البرمجي (Pseudo-code) الرسمي لعملية الدمج باستخدام الـ Skip Pointers. ركز في
التفاصيل لأنها بتوضح كيف الـ "قفز" بصير بالظبط:
INTERSECTWITHSKIPS(p1, p2)
1. answer ← ⟨ ⟩
2. while p1 ≠ NIL and p2 ≠ NIL
3. do if docID(p1) = docID(p2)
4. then ADD(answer, docID(p1))
5. p1 ← next(p1)
6. p2 ← next(p2)
7. else if docID(p1) < docID(p2)
8. then if hasSkip(p1) and (docID(skip(p1)) ≤ docID(p2))
9. then while hasSkip(p1)
and (docID(skip(p1)) ≤ docID(p2))
10. do p1 ←
skip(p1)
11. else p1 ← next(p1)
12. else if hasSkip(p2) and (docID(skip(p2)) ≤ docID(p1))
13. then while hasSkip(p2) and (docID(skip(p2)) ≤ docID(p1))
14. do p2 ← skip(p2)
15. else p2 ← next(p2)
16. return answer
💡 شرح الكود "حبة حبة":
الأسطر 4-6: إذا لقينا الرقمين متساويين، هاد يعني إنه رقم الملف (DocID) موجود في الكلمتين، بنضيفه
للنتيجة وبنحرك القائمتين.
الأسطر 8-10 (السرّ هون): إذا كان الرقم في القائمة الأولى أصغر، بدل ما نحرك خطوة غبية لـ (Next)،
بنعمل فحص ذكي:
- هل الـ Skip Pointer لـ p1 رح يوديني لمكان لسه أصغر من أو يساوي p2؟
- إذا "نعم"، ليش أمشي خطوة خطوة؟ بضل أقفز (while) لحد ما أوصل لأبعد نقطة ممكنة قبل ما أتعدى p2.
الأسطر 12-15: نفس المنطق بنطبقه على القائمة الثانية إذا كان p2 هو الأصغر.
✅ النتيجة: بنخلص البحث بسرعة صاروخية لأننا ما مرينا على كل عنصر بالنص!
🔎 Query Processing Example
Visualizing
the Skip: Moving from 11 directly to 31
Suppose we've stepped through the lists until we process 8 on each list. We match
it and advance.
تخيلوا إننا مشينا في القوائم ووصلنا لعند الرقم 8 ولقيناه مشترك في الكلمتين (Match).
الآن بدنا نكمل ونشوف شو الرقم اللي بعده.
We then have 41 and 11 on the lower. 11 is smaller.
الآن، المؤشر في القائمة العلوية واقف عند 41، وفي القائمة السفلية واقف عند 11.
بما إن الـ 11 أصغر، لازم نحرك مؤشر القائمة السفلية عشان ندور على الـ 41.
But the skip successor of 11 on the lower list is 31, so we can skip ahead past
the intervening postings.
هون بيجي دور ذكاء البحث:
1️⃣ السيستم بيشوف إنه الـ 11 عندها Skip Pointer بيوصلنا للـ 31.
2️⃣ بيسأل سؤال ذهبي لنفسه: هل الـ 31 لسه أصغر من أو يساوي الـ 41 اللي فوق؟ الجواب نعم.
3️⃣ 🚀 قفزة! بننتقل من 11 إلى 31 مباشرة، وبنتعدى (Skip) كل الأرقام اللي كانت بالنص (17، 21،
28) بلمحة بصر.
✅ هيك وفرنا مجهود كبير كان رح يضيع في مقارنات ما لها داعي!
⚖️ Where do we place skips?
وصلنا لسؤال المليون: وين لازم نحط القفزات؟ هل نحط كثير ولا قليل؟ السلايد هاض بيشرح لنا الموازنة
(Trade-off) الدقيقة اللي بتحدد أداء النظام.
Trade-off
Visualization: Frequent vs. Rare Skips
More skips → shorter skip spans ⇒ more likely to skip. But lots of
comparisons to skip pointers.
🔝 السيناريو الأول: قفزات كثيرة (مسافات قصيرة)
- الميزة: بصير "احتمال" إننا نلاقي فرصة للقفز كبيرة جداً، لأن المسافات قصيرة.
- العيب: السيستم رح يضيع وقت وهو بيعمل "مقارنات" (Comparisons) كثير مع الـ Skip Pointers
نفسها. يعني بدل ما نوفر وقت، بنضيعه في "التفتيش" عن القفزات.
Fewer skips → few pointer comparison, but then long skip spans ⇒ few
successful skips.
🔻 السيناريو الثاني: قفزات قليلة (مسافات طويلة)
- الميزة: ما بنعمل مقارنات كثير مع الـ Pointers، فـ "تكلفة" الفحص قليلة.
- العيب: القفزات بتصير "نادرة". غالباً القفزة رح توديك لمكان أبعد بكثير من اللي بتدور عليه،
فبضطر السيستم يرفض القفزة ويمشي عادي (Linear Scan). هيك ما بنكون استفدنا من الـ Skip أصلاً!
🏆 الحل المثالي | The Golden Rule
أفضل موازنة هي وضع قفزة كل √L نود.
هيك بنضمن أسرع وقت بحث ممكن مع أقل استهلاك للمساحة والمقارنات!
⚙️ اعتبارات تقنية إضافية
Simple heuristic: for postings of length L, use √L evenly-spaced skip
pointers
التوزيع المتساوي: في أبسط حالتها، الخوارزمية بتقسم القائمة لمسافات متساوية بناءً على جذر
الطول. يعني لو عندك 100 عنصر، بنحط قفزة كل 10.
This ignores the distribution of query terms.
مشكلة التوزيع: الطريقة هاي "غبية" شوي لأنها بتفترض إن كل الكلمات بنبحث عنها بنفس الطريقة،
بينما الحقيقة إن فيه كلمات عليها ضغط بحث أكتر ولازم تقسيم القفزات فيها يكون أذكى.
Easy if the index is relatively static; harder if L keeps changing because of
updates.
تحدي التحديثات: الموضوع سهل لما يكون الـ Index ثابت وما بيتغير (Static). لكن لو الـ Index
بيتحدث باستمرار وبنزيد عليه ملفات جديدة، طول القائمة L رح يضل يتغير، وهون بصير إعادة حساب
أماكن القفزات عملية "صعبة" وبتحتاج مجهود إضافي.
💪 Exercise: Apply the Algorithm
وصلنا لأهم جزء! هاض التمرين من السلايدات وبدنا نحله مع بعض عشان نتأكد إننا فاهمين كيف الـ Skip
Pointers بتشتغل فعلياً.
Exercise: Find
the intersection of Brutus and Caesar using skips.
🎯 الحل خطوة بخطوة:
1️⃣ البداية ومطابقة (2):
بنمشي خطوة بخطوة في الأول، وبنلاحظ إن الرقم 2 موجود في القائمتين. هاض أول Match!
2️⃣ مطابقة (8):
بنمشي خطوة بخطوة في الأول، وبرضه بنلاحظ إن الرقم 8 موجود في القائمتين. هاض ثانٍٍ
Match!
3️⃣ اللحظة الحاسمة (القفزة):
- الآن إحنا عند 41 (فوق) و 11 (تحت). الرقم 11 أصغر، فبدنا نحرك القائمة اللي تحت.
- بنفحص الـ Skip Pointer تبع الـ 11 وبنلاقيه بيودينا للـ 31.
- هل الـ 31 ≤ 41؟ نعم أكيد!
- 🚀 Skip! بنقفز فوراً للـ 31 وبنتجاوز الأعداد (17، 21، 28).
4️⃣ النتيجة النهائية:
الأرقام المشتركة اللي لقيناها هي: {2, 8}. والـ 31 ما لقينا إلها مثيل فوق فبنوقف لأننا وصلنا
لآخر القوائم.
🚀 تحدي تم اجتيازه!
إنت الآن فاهم كيف السيستم بيوفر وقت
"الملايين" من عمليات البحث!