दस्तावेज़ों को स्कैन करने की तुलना में व्युत्क्रमित अनुक्रमणिका को क्यों पसंद किया जाता है?

प्रत्येक क्वेरी के लिए हर दस्तावेज़ को स्कैन करना बड़े पैमाने पर बहुत धीमा है। व्युत्क्रमित अनुक्रमणिका प्रणाली को सीधे उन दस्तावेज़ों के छोटे सेट पर जाने देती है जिनमें क्वेरी पद होते हैं, इसलिए क्वेरी का समय पूरे संग्रह के आकार के बजाय इसमें शामिल पोस्टिंग सूचियों पर निर्भर करता है।

क्या अनुक्रमणिका को संपीड़ित करने से खोज धीमी हो जाती है?

आमतौर पर इसका उल्टा होता है। एक छोटी अनुक्रमणिका डिस्क और मेमोरी ट्रैफ़िक को कम करती है, और आधुनिक पूर्णांक कोड बहुत तेज़ी से डीकंप्रेस होते हैं, इसलिए इनपुट/आउटपुट पर बचाया गया समय और बेहतर कैश व्यवहार आमतौर पर डिकोडिंग लागत से अधिक होता है, जिससे संपीड़ित अनुक्रमणिका छोटी और तेज़ दोनों होती हैं।

अनुक्रमणिका और क्वेरी प्रसंस्करण

अनुक्रमणिका और क्वेरी प्रसंस्करण में डेटा संरचनाएं और एल्गोरिदम शामिल हैं जो एक खोज प्रणाली को बड़े पाठ संग्रहों पर प्रश्नों का त्वरित उत्तर देने की अनुमति देते हैं, मुख्य रूप से व्युत्क्रमित अनुक्रमणिका (inverted index) के माध्यम से।

PaperMind से विषय खोजेंजल्द हीFind papers & topics

Tools & resources

स्लाइड डाउनलोड करें

Learn & explore

वीडियोजल्द ही

Definition

अनुक्रमणिका डेटा संरचनाओं का निर्माण है, मुख्य रूप से व्युत्क्रमित अनुक्रमणिका जो पदों को उन दस्तावेज़ों से मैप करती है जिनमें वे शामिल हैं, जो कुशल लुकअप (lookup) का समर्थन करते हैं, जबकि क्वेरी प्रसंस्करण एल्गोरिदम का एक सेट है जो इन संरचनाओं को पार करता है ताकि उन दस्तावेज़ों की गणना की जा सके जो किसी क्वेरी के लिए मेल खाते हैं या सबसे अच्छी रैंक पर हैं।

Scope

यह क्षेत्र बताता है कि पाठ संग्रहों को खोज योग्य संरचनाओं में कैसे बदला जाता है और उनके विरुद्ध प्रश्नों का मूल्यांकन कैसे किया जाता है: व्युत्क्रमित अनुक्रमणिका का निर्माण, इसके पीछे के टोकनाइजेशन (tokenization) और पद-शब्दावली (term-vocabulary) के निर्णय, स्थान बचाने और पहुंच को गति देने के लिए पोस्टिंग (postings) को संपीड़ित करना, रैंक किए गए पुनर्प्राप्ति (ranked retrieval) और प्रारंभिक समाप्ति (early termination) सहित प्रश्नों को कुशलतापूर्वक संसाधित करना, और वाइल्डकार्ड (wildcard), वर्तनी-सुधार (spelling-correction), और ध्वन्यात्मक मिलान (phonetic matching) जैसी सहिष्णु पुनर्प्राप्ति (tolerant retrieval) तकनीकें। यह तेज़ पुनर्प्राप्ति के सिस्टम इंजीनियरिंग को संबोधित करता है, जो रैंकिंग को परिभाषित करने वाले पुनर्प्राप्ति मॉडल और गुणवत्ता को मापने वाली मूल्यांकन विधियों से अलग है।

Sub-topics

Core questions

एक बड़े, बदलते संग्रह के लिए व्युत्क्रमित अनुक्रमणिका का निर्माण और अद्यतन कैसे किया जाता है?
क्वेरी मूल्यांकन को धीमा किए बिना पोस्टिंग सूचियों को कैसे संपीड़ित किया जा सकता है?
विशेष रूप से लाखों दस्तावेज़ों पर रैंक किए गए प्रश्नों का कुशलतापूर्वक मूल्यांकन कैसे किया जाता है?
एक प्रणाली हर दस्तावेज़ को स्कोर किए बिना अच्छे परिणाम कैसे प्राप्त कर सकती है?
एक प्रणाली गलत वर्तनी, वाइल्डकार्ड और अनुमानित मिलान को कैसे संभालती है?

Key concepts

व्युत्क्रमित अनुक्रमणिका
पोस्टिंग सूची
टोकनाइजेशन और पद शब्दावली
अनुक्रमणिका निर्माण (BSBI, SPIMI)
अनुक्रमणिका संपीड़न
एक-समय-में-दस्तावेज़ और एक-समय-में-पद मूल्यांकन
गतिशील छंटनी और प्रारंभिक समाप्ति
सहिष्णु पुनर्प्राप्ति

Key theories

मुख्य डेटा संरचना के रूप में व्युत्क्रमित अनुक्रमणिका: प्रत्येक पद को उन दस्तावेज़ों (और स्थितियों) की पोस्टिंग सूची में मैप करना जहाँ यह होता है, पुनर्प्राप्ति को केवल क्वेरी पदों वाले दस्तावेज़ों को छूने देता है, जिससे यह स्केलेबल पाठ खोज के लिए मूलभूत संरचना बन जाती है।
संपीड़न-दक्षता व्यापार-बंद: कॉम्पैक्ट पूर्णांक कोड के साथ दस्तावेज़-आईडी अंतराल और पद आवृत्तियों को एन्कोड करना अनुक्रमणिका को नाटकीय रूप से सिकोड़ता है और, इनपुट/आउटपुट को कम करके और कैश व्यवहार में सुधार करके, क्वेरी प्रसंस्करण को भी गति दे सकता है।
कुशल रैंक किए गए क्वेरी मूल्यांकन: एक-समय-में-दस्तावेज़ और एक-समय-में-पद रणनीतियाँ, गतिशील छंटनी और प्रारंभिक-समाप्ति तकनीकों के साथ मिलकर, प्रणालियों को पूरे संग्रह को पूरी तरह से स्कोर किए बिना शीर्ष-रैंक वाले परिणाम वापस करने की अनुमति देती हैं।

Clinical relevance

व्युत्क्रमित अनुक्रमणिका और कुशल क्वेरी प्रसंस्करण हर उत्पादन खोज प्रणाली का इंजन रूम हैं, वेब खोज इंजनों और ओपन-सोर्स खोज प्लेटफार्मों से लेकर उद्यम और डेटाबेस पूर्ण-पाठ खोज तक। उनकी दक्षता सीधे क्वेरी विलंबता (query latency), हार्डवेयर लागत और संग्रहों के पैमाने को निर्धारित करती है जिन्हें इंटरैक्टिव रूप से खोजा जा सकता है।

History

पाठ खोज के लिए सबसे शुरुआती सूचना प्रणालियों के बाद से व्युत्क्रमित फ़ाइलों का उपयोग किया गया है, लेकिन अनुक्रमणिका निर्माण, संपीड़न और कुशल मूल्यांकन का आधुनिक सिद्धांत 1990 के दशक में समेकित किया गया था, विशेष रूप से विटेन, मोफ़त और बेल के मैनेजिंग गीगाबाइट्स (Managing Gigabytes) कार्य द्वारा। ज़ोबेल और मोफ़त का 2006 का सर्वेक्षण वेब-स्केल खोज के रूप में व्युत्क्रमित-अनुक्रमणिका अनुसंधान के दो दशकों को संश्लेषित करता है जिसने दक्षता को सर्वोपरि बना दिया।

Key figures

Justin Zobel
Alistair Moffat
Ian H. Witten
W. Bruce Croft

Seminal works

zobel2006
wittenmgb1999
manning2008

Frequently asked questions

दस्तावेज़ों को स्कैन करने की तुलना में व्युत्क्रमित अनुक्रमणिका को क्यों पसंद किया जाता है?: प्रत्येक क्वेरी के लिए हर दस्तावेज़ को स्कैन करना बड़े पैमाने पर बहुत धीमा है। व्युत्क्रमित अनुक्रमणिका प्रणाली को सीधे उन दस्तावेज़ों के छोटे सेट पर जाने देती है जिनमें क्वेरी पद होते हैं, इसलिए क्वेरी का समय पूरे संग्रह के आकार के बजाय इसमें शामिल पोस्टिंग सूचियों पर निर्भर करता है।
क्या अनुक्रमणिका को संपीड़ित करने से खोज धीमी हो जाती है?: आमतौर पर इसका उल्टा होता है। एक छोटी अनुक्रमणिका डिस्क और मेमोरी ट्रैफ़िक को कम करती है, और आधुनिक पूर्णांक कोड बहुत तेज़ी से डीकंप्रेस होते हैं, इसलिए इनपुट/आउटपुट पर बचाया गया समय और बेहतर कैश व्यवहार आमतौर पर डिकोडिंग लागत से अधिक होता है, जिससे संपीड़ित अनुक्रमणिका छोटी और तेज़ दोनों होती हैं।