ضغط الفهارس
يُشفّر ضغط الفهارس قوائم النشر الخاصة بالفهرس المقلوب بشكل مضغوط بحيث يخزّن نظام البحث بيانات أقل ويجيب على الاستفسارات بشكل أسرع.
Definition
ضغط الفهارس هو تطبيق طرق تشفير الأعداد الصحيحة والسلاسل على القاموس وقوائم النشر الخاصة بالفهرس المقلوب لتقليل مساحة التخزين المطلوبة مع الحفاظ على إمكانية فك تشفير قوائم النشر بسرعة أثناء معالجة الاستعلامات.
Scope
يغطي هذا الموضوع تقنيات ضغط الفهارس المقلوبة، خاصة تشفير الفجوات في معرّفات المستندات وتكرارات المصطلحات باستخدام رموز الأعداد الصحيحة متغيرة الطول والمحاذية للكلمات. ويتناول ضغط القواميس، وتشفير الفجوات (دلتا)، والرموز الكلاسيكية مثل الرموز الأحادية (unary)، وغاما (gamma)، وجولومب-رايس (Golomb-Rice)، والمخططات المحاذية للبايت والقائمة على الكتل مثل البايت المتغير (variable-byte) وPForDelta، والمفاضلة بين نسبة الضغط وسرعة فك التشفير. ويستثني بناء الفهرس نفسه واستراتيجية تقييم الاستعلام التي تستهلكه.
Core questions
- لماذا يضغط تشفير الفجوات بين معرّفات المستندات قوائم النشر بفعالية؟
- ما هي رموز الأعداد الصحيحة المستخدمة، وكيف توازن بين نسبة الضغط وسرعة فك التشفير؟
- كيف يتم ضغط قاموس المصطلحات نفسه؟
- كيف يمكن فك تشفير قوائم النشر المضغوطة بالسرعة الكافية للحفاظ على زمن استجابة منخفض للاستعلامات؟
- كيف يتفاعل الضغط مع سلوك الذاكرة المخبأة وتكلفة الإدخال/الإخراج؟
Key concepts
- تشفير الفجوات (دلتا)
- تشفير البايت المتغير
- رموز غاما وجولومب-رايس
- PForDelta والرموز القائمة على الكتل
- ضغط القواميس
- نسبة الضغط
- إنتاجية فك التشفير
- فك التشفير المتجه / SIMD
Key theories
- تشفير الفجوات في قوائم النشر
- نظرًا لأن معرّفات المستندات في قائمة النشر تتزايد، فإن تخزين الفروق (الفجوات) بين المعرّفات المتتالية ينتج أرقامًا صغيرة تضغط جيدًا، خاصة للمصطلحات المتكررة ذات قوائم النشر الكثيفة.
- المفاضلة بين الضغط والسرعة
- تعمل الرموز المحاذية للبت مثل غاما وجولومب على زيادة الضغط إلى أقصى حد ولكنها تفك التشفير ببطء، بينما تضحي الرموز المحاذية للبايت والقائمة على الكتل مثل البايت المتغير وPForDelta ببعض النسبة مقابل فك تشفير أسرع بكثير وقابل للتوجيه (vectorizable)، مما غالبًا ما يحقق أداءً أفضل للاستعلامات بشكل عام.
Clinical relevance
الضغط ضروري لتشغيل البحث على نطاق واسع: فهو يقلص الفهارس لتناسب الذاكرة أو مساحة تخزين أصغر، ويقلل من عمليات الإدخال/الإخراج ويحسن من موقعية الذاكرة المخبأة (cache locality)، وبالتالي يقلل من زمن استجابة الاستعلام وتكلفة الأجهزة. تعتمد جميع محركات البحث الإنتاجية ومكتبات البحث مفتوحة المصدر على قوائم النشر المضغوطة.
History
تطور التشفير المدمج لفهارس النصوص جنبًا إلى جنب مع الملفات المقلوبة، حيث تم تنظيم الرموز الكلاسيكية المحاذية للبت (unary, gamma, Golomb) في عمل "إدارة الجيجابايت" (Managing Gigabytes) في التسعينيات. ومع تطلب البحث على نطاق الويب فك تشفير أسرع باستمرار، حولت المخططات المحاذية للبايت والقائمة على الكتل مثل البايت المتغير (variable-byte) وPForDelta، ولاحقًا أجهزة فك التشفير المتجهة (vectorized decoders) القادرة على معالجة مليارات الأعداد الصحيحة في الثانية، التركيز نحو السرعة.
Key figures
- Alistair Moffat
- Ian H. Witten
- Daniel Lemire
- Justin Zobel
Related topics
Seminal works
- wittenmgb1999
- lemire2015
- manning2008
Frequently asked questions
- كيف يمكن أن يكون الفهرس المضغوط أسرع من الفهرس غير المضغوط؟
- يقلل الضغط من كمية البيانات المقروءة من القرص أو الذاكرة، والتي غالبًا ما تكون هي عنق الزجاجة. تقوم رموز الأعداد الصحيحة الحديثة بفك التشفير بسرعة كبيرة، وغالبًا ما تستخدم تعليمات المتجهات، لذا فإن الوقت الذي يتم توفيره في الإدخال/الإخراج وسلوك الذاكرة المخبأة الأفضل يعوضان أكثر من عمل فك التشفير.
- لماذا يتم تخزين الفجوات بدلاً من معرّفات المستندات الخام؟
- معرّفات المستندات في قائمة النشر تكون مرتبة ومتزايدة، لذا تختلف المتتالية منها بمقادير صغيرة. تخزين هذه الفجوات الصغيرة بدلاً من المعرّفات المطلقة الكبيرة ينتج قيمًا يمكن للرموز المدمجة تمثيلها بعدد قليل جدًا من البتات.