इंडेक्स संपीड़न
इंडेक्स संपीड़न एक व्युत्क्रमित इंडेक्स की पोस्टिंग सूचियों को सघन रूप से एन्कोड करता है ताकि एक खोज प्रणाली कम डेटा संग्रहीत करे और प्रश्नों का तेजी से उत्तर दे।
Definition
इंडेक्स संपीड़न एक व्युत्क्रमित इंडेक्स के डिक्शनरी और पोस्टिंग पर पूर्णांक- और स्ट्रिंग-कोडिंग विधियों का अनुप्रयोग है ताकि इसके भंडारण पदचिह्न को कम किया जा सके जबकि क्वेरी प्रसंस्करण के दौरान पोस्टिंग को तेजी से डिकोड करने योग्य रखा जा सके।
Scope
यह विषय व्युत्क्रमित इंडेक्स को संपीड़ित करने की तकनीकों को शामिल करता है, विशेष रूप से दस्तावेज़-पहचानकर्ता अंतरालों और चर-लंबाई और शब्द-संरेखित पूर्णांक कोड के साथ पद आवृत्तियों के एन्कोडिंग को। यह डिक्शनरी संपीड़न, गैप (डेल्टा) एन्कोडिंग, यूनरी, गामा और गोलोम्ब जैसे क्लासिक कोड, वेरिएबल-बाइट और PForDelta जैसी बाइट-संरेखित और ब्लॉक-आधारित योजनाओं, और संपीड़न अनुपात तथा डिकोडिंग गति के बीच के व्यापार-बंद पर चर्चा करता है। इसमें इंडेक्स के निर्माण और उसे उपभोग करने वाली क्वेरी-मूल्यांकन रणनीति को शामिल नहीं किया गया है।
Core questions
- दस्तावेज़ पहचानकर्ताओं के बीच के अंतरालों को एन्कोड करने से पोस्टिंग प्रभावी ढंग से संपीड़ित क्यों होती है?
- किन पूर्णांक कोडों का उपयोग किया जाता है, और वे संपीड़न अनुपात को डिकोडिंग गति के मुकाबले कैसे व्यापार करते हैं?
- पद डिक्शनरी को स्वयं कैसे संपीड़ित किया जाता है?
- संपीड़ित पोस्टिंग को क्वेरी विलंबता को कम रखने के लिए पर्याप्त तेजी से कैसे डिकोड किया जा सकता है?
- संपीड़न कैश व्यवहार और इनपुट/आउटपुट लागत के साथ कैसे इंटरैक्ट करता है?
Key concepts
- गैप (डेल्टा) एन्कोडिंग
- वेरिएबल-बाइट एन्कोडिंग
- गामा और गोलोम्ब-राइस कोड
- PForDelta और ब्लॉक-आधारित कोड
- डिक्शनरी संपीड़न
- संपीड़न अनुपात
- डिकोडिंग थ्रूपुट
- SIMD / वेक्टरयुक्त डिकोडिंग
Key theories
- पोस्टिंग का गैप एन्कोडिंग
- क्योंकि पोस्टिंग सूची में दस्तावेज़ पहचानकर्ता बढ़ते क्रम में होते हैं, लगातार पहचानकर्ताओं के बीच के अंतर (गैप) को संग्रहीत करने से छोटी संख्याएँ प्राप्त होती हैं जो अच्छी तरह से संपीड़ित होती हैं, खासकर घनी पोस्टिंग वाले बार-बार आने वाले पदों के लिए।
- संपीड़न-गति व्यापार-बंद
- गामा और गोलोम्ब जैसे बिट-संरेखित कोड संपीड़न को अधिकतम करते हैं लेकिन धीरे-धीरे डिकोड होते हैं, जबकि वेरिएबल-बाइट और PForDelta जैसे बाइट-संरेखित और ब्लॉक-आधारित कोड बहुत तेज, वेक्टरयुक्त डिकोडिंग के लिए कुछ अनुपात का त्याग करते हैं, जो अक्सर समग्र क्वेरी प्रदर्शन में जीत हासिल करता है।
Clinical relevance
बड़े पैमाने पर खोज संचालन के लिए संपीड़न आवश्यक है: यह इंडेक्स को छोटा करता है ताकि वे मेमोरी या छोटे भंडारण में फिट हो सकें, इनपुट/आउटपुट को कम करता है और कैश लोकैलिटी में सुधार करता है, और इस प्रकार क्वेरी विलंबता और हार्डवेयर लागत दोनों को कम करता है। उत्पादन खोज इंजन और ओपन-सोर्स खोज लाइब्रेरी सभी संपीड़ित पोस्टिंग पर निर्भर करते हैं।
History
पाठ इंडेक्स की सघन कोडिंग व्युत्क्रमित फ़ाइलों के साथ विकसित हुई, जिसमें 1990 के दशक के मैनेजिंग गीगाबाइट्स कार्य में क्लासिक बिट-संरेखित कोड (यूनरी, गामा, गोलोम्ब) को व्यवस्थित किया गया। जैसे-जैसे वेब-स्केल खोज में तेजी से डिकोडिंग की मांग बढ़ी, वेरिएबल-बाइट और PForDelta जैसी बाइट-संरेखित और ब्लॉक-आधारित योजनाएं, और बाद में प्रति सेकंड अरबों पूर्णांकों को संसाधित करने में सक्षम वेक्टरयुक्त डिकोडर, गति की ओर जोर देने लगे।
Key figures
- Alistair Moffat
- Ian H. Witten
- Daniel Lemire
- Justin Zobel
Related topics
Seminal works
- wittenmgb1999
- lemire2015
- manning2008
Frequently asked questions
- एक संपीड़ित इंडेक्स एक असंपीड़ित इंडेक्स से तेज कैसे हो सकता है?
- संपीड़न डिस्क या मेमोरी से पढ़े जाने वाले डेटा की मात्रा को कम करता है, जो अक्सर बाधा होती है। आधुनिक पूर्णांक कोड बहुत तेजी से डिकोड होते हैं, अक्सर वेक्टर निर्देशों का उपयोग करते हुए, इसलिए इनपुट/आउटपुट पर बचाया गया समय और बेहतर कैश व्यवहार डिकोडिंग कार्य के लिए पर्याप्त से अधिक क्षतिपूर्ति करता है।
- कच्चे दस्तावेज़ पहचानकर्ताओं के बजाय गैप क्यों संग्रहीत करें?
- एक पोस्टिंग सूची में दस्तावेज़ पहचानकर्ता क्रमबद्ध और बढ़ते क्रम में होते हैं, इसलिए लगातार वाले थोड़े अंतर से भिन्न होते हैं। बड़े निरपेक्ष पहचानकर्ताओं के बजाय उन छोटे गैप को संग्रहीत करने से ऐसे मान उत्पन्न होते हैं जिन्हें सघन कोड बहुत कम बिट्स में दर्शा सकते हैं।