Retrieval Data Structure
कंप्यूटर विज्ञान में, एक पुनर्प्राप्ति डेटा संरचना, जिसे स्थिर कार्य के रूप में भी जाना जाता है, एक अंतरिक्ष-कुशल शब्दकोश जैसा डेटा प्रकार है जो (कुंजी, मूल्य) जोड़े के संग्रह से बना होता है जो निम्नलिखित कार्यों की अनुमति देता हैः (कुंजी, मूल्य) जोड़े के संग्रह से निर्माण दी गई कुंजी या किसी भी चीज़ से जुड़े मूल्य को पुनर्प्राप्त करें यदि कुंजी संग्रह में निहित नहीं है तो कुंजी (वैकल्पिक) से जुड़े मूल्य को अपडेट करें उन्हें एक ब्रह्मांड के लिए एक कार्य और कुंजी के सेट के रूप में भी सोचा जा सकता है जहां पुनर्प्राप्ति को किसी भी मूल्य और अन्यथा से एक मनमाने मूल्य के लिए वापस करना पड़ता है। स्थैतिक कार्यों के विपरीत, ए. एम. क्यू.-फ़िल्टर (संभावित) सदस्यता प्रश्नों का समर्थन करते हैं और शब्दकोश अतिरिक्त रूप से कुंजी को सूचीबद्ध करने या किसी कुंजी से जुड़े मूल्य को देखने और यदि कुंजी शामिल नहीं है तो किसी अन्य प्रतीक को वापस करने जैसे कार्यों की अनुमति देते हैं। जैसा कि संचालन से प्राप्त किया जा सकता है, इस डेटा संरचना को कुंजी को संग्रहीत करने की आवश्यकता नहीं है और वास्तव में प्रमुख मूल्य जोड़े की एक सरल सूची के लिए आवश्यक जगह से कम जगह का उपयोग कर सकता है। यह उन स्थितियों में इसे आकर्षक बनाता है जहां संबंधित डेटा छोटा है (जैसे। कुछ बिट्स) कुंजियों की तुलना में क्योंकि हम कुंजियों द्वारा उपयोग की जाने वाली जगह को कम करके बहुत कुछ बचा सकते हैं। एक सरल उदाहरण देने के लिए मान लीजिए कि वीडियो गेम के नाम एक बूलियन के साथ दिए गए हैं जो दर्शाते हैं कि क्या खेल में एक कुत्ता है जिसे पालतू बनाया जा सकता है। इस डेटाबेस से निर्मित एक स्थिर कार्य मूल समूह में निहित सभी नामों के लिए संबंधित ध्वज को पुनः प्रस्तुत कर सकता है और अन्य नामों के लिए एक मनमाना कार्य कर सकता है। इस स्थिर फलन का आकार एक छोटे के लिए केवल बिट्स बनाया जा सकता है जो स्पष्ट रूप से किसी भी जोड़ी आधारित प्रतिनिधित्व की तुलना में बहुत कम है। उदाहरण एक स्थिर फलन का एक तुच्छ उदाहरण कुंजी और मूल्यों की एक क्रमबद्ध सूची है जो उपरोक्त सभी कार्यों और कई अन्य कार्यों को लागू करती है। हालांकि, एक सूची में पुनर्प्राप्ति धीमी है और हम कई अनावश्यक कार्यों को लागू करते हैं जिन्हें अनुकूलन की अनुमति देने के लिए हटाया जा सकता है। इसके अलावा, हमें कबाड़ वापस करने की भी अनुमति है यदि पूछताछ की गई कुंजी शामिल नहीं है जिसका हमने बिल्कुल भी उपयोग नहीं किया है। एक स्थिर कार्य बनाने के लिए एक और सरल उदाहरण एक पूर्ण हैश कार्य का उपयोग करना हैः हमारी कुंजियों के लिए पी. एच. एफ. बनाने के बाद, संबंधित मूल्यों को कुंजी के लिए सही स्थिति में संग्रहीत करें। जैसा कि देखा जा सकता है, यह दृष्टिकोण संबद्ध मूल्यों को अद्यतन करने की भी अनुमति देता है, कुंजी स्थिर होनी चाहिए। शुद्धता सही हैश फ़ंक्शन की शुद्धता से आती है। न्यूनतम पूर्ण हैश फ़ंक्शन का उपयोग करने से एक बड़ा स्थान सुधार होता है यदि संबंधित मान अपेक्षाकृत छोटे होते हैं। एक्स. ओ. आर.-पुनर्प्राप्ति हैश्ड फ़िल्टरों को उनके प्रश्नों द्वारा ओ. आर., ए. एन. डी. और एक्स. ओ. आर.-फ़िल्टरों में वर्गीकृत किया जा सकता है। उदाहरण के लिए, ब्लूम फ़िल्टर एक ए. एन. डी.-फ़िल्टर है क्योंकि यह सदस्यता प्रश्न के लिए सही लौटता है यदि सभी जांच किए गए स्थान मेल खाते हैं। एक्सओआर फिल्टर केवल स्थिर पुनर्प्राप्ति के लिए काम करते हैं और उन्हें कुशलता से जगह बनाने के लिए सबसे आशाजनक हैं। वे एक रैखिक प्रणाली को हल करके बनाए जाते हैं जो यह सुनिश्चित करता है कि प्रत्येक कुंजी के लिए एक क्वेरी सही हो। निर्माण एक हैश फ़ंक्शन को देखते हुए जो प्रत्येक कुंजी को लंबाई के बिटवेक्टर के लिए मैप करता है जहां सभी रैखिक रूप से स्वतंत्र हैं, रैखिक समीकरणों की निम्नलिखित प्रणाली का एक समाधान हैः इसलिए, स्थिर फ़ंक्शन द्वारा दिया जाता है और और स्थान उपयोग पर हावी होता है जिसके लिए मोटे तौर पर बिट प्रति कुंजी है, हैश फ़ंक्शन को छोटा माना जाता है। के लिए एक पुनर्प्राप्ति को सभी सेट बिट्स के लिए पंक्तियों के बिटवाइज XOR के रूप में व्यक्त किया जा सकता है। इसके अलावा, तेज़ प्रश्नों के लिए विरल आवश्यकता होती है, इस प्रकार इस विधि के लिए जिन समस्याओं को हल करने की आवश्यकता है, वे हैं एक उपयुक्त हैश फ़ंक्शन खोजना और फिर भी रैखिक समीकरणों की प्रणाली को कुशलता से हल करने में सक्षम होना। रिबन पुनर्प्राप्ति एक विरल यादृच्छिक मैट्रिक्स का उपयोग करके पुनर्प्राप्ति कैश को अक्षम बनाता है क्योंकि वे यादृच्छिक गैर-स्थानीय पैटर्न में अधिकांश तक पहुँचते हैं। प्रत्येक को चौड़ाई का एक लगातार "रिबन" देकर रिबन पुनर्प्राप्ति में सुधार होता है जिसमें बिट्स को यादृच्छिक रूप से सेट किया जाता है। मैट्रिक्स के गुणों का उपयोग करके अपेक्षित समय में गणना की जा सकती हैः रिबन हल करने का काम पहले पंक्तियों को उनकी प्रारंभिक स्थिति (जैसे. गिनती प्रकार)। फिर, एक आरईएम फॉर्म का निर्माण वर्तमान पंक्ति के नीचे की पंक्तियों पर पंक्ति संचालन करके किया जा सकता है, इस पंक्ति की पहली 1-प्रविष्टि के नीचे सभी स्तंभों में सभी 1-प्रविष्टियों को हटा दिया जाता है। पंक्ति संचालन रिबन के बाहर कोई मूल्य उत्पन्न नहीं करते हैं और बहुत सस्ते होते हैं क्योंकि उन्हें केवल बिट्स के एक्सओआर की आवश्यकता होती है जिसे रैम पर समय पर किया जा सकता है। यह दिखाया जा सकता है कि पंक्ति संचालन की अपेक्षित मात्रा है। अंत में, समाधान पीठ प्रतिस्थापन द्वारा प्राप्त किया जाता है। अनुप्रयोग अनुमानित सदस्यता एक अनुमानित सदस्यता डेटा संरचना के निर्माण के लिए एक फिंगरप्रिंटिंग फ़ंक्शन का उपयोग करते हैं। फिर हमारी कुंजियों के क्षेत्र तक सीमित एक स्थिर कार्य बनाएँ। किसी तत्व की सदस्यता की जाँच के साथ मूल्यांकन किया जाता है और यदि लौटाया गया मूल्य बराबर है तो सही लौटाया जाता है। यदि, सही मान देता है और हम सही लौटाते हैं। अन्यथा, एक यादृच्छिक मान देता है और हम गलत उत्तर दे सकते हैं। हैश की लंबाई गलत सकारात्मक दर को नियंत्रित करने की अनुमति देती है। इस डेटा संरचना का प्रदर्शन बिल्कुल अंतर्निहित स्थिर कार्य का प्रदर्शन है। सही हैश कार्य एक पुनर्प्राप्ति डेटा संरचना का उपयोग एक सही हैश कार्य के निर्माण के लिए किया जा सकता हैः पहले हैश कार्य और आकार 1 की बाल्टियों के साथ एक कोयल हैश तालिका में कुंजी डालें। फिर, प्रत्येक कुंजी भंडार के लिए हैश फ़ंक्शन का सूचकांक जो एक-बिट पुनर्प्राप्ति डेटा संरचना में हैश तालिका में एक कुंजी के सम्मिलन की ओर ले जाता है। सही हैश फ़ंक्शन द्वारा दिया जाता है। संदर्भ सार डेटा प्रकार सहयोगी सरणी