Succinct data structure
कंप्यूटर विज्ञान में, एक संक्षिप्त डेटा संरचना एक डेटा संरचना है जो सूचना-सैद्धांतिक निचली सीमा के "करीब" स्थान का उपयोग करती है, लेकिन (अन्य संपीड़ित अभ्यावेदनों के विपरीत) अभी भी कुशल प्रश्न संचालन के लिए अनुमति देती है। अवधारणा को मूल रूप से जैकबसन द्वारा बिट वैक्टर, (बिना लेबल वाले) पेड़ों और समतल ग्राफ को कूटबद्ध करने के लिए पेश किया गया था। सामान्य हानिरहित डेटा संपीड़न एल्गोरिदम के विपरीत, संक्षिप्त डेटा संरचनाएं उन्हें पहले विघटित किए बिना, उन्हें अपने स्थान पर उपयोग करने की क्षमता बनाए रखती हैं। एक संबंधित धारणा एक संपीड़ित डेटा संरचना की है, जहाँ तक संग्रहीत या एन्कोडेड डेटा का आकार उसी तरह डेटा की विशिष्ट सामग्री पर निर्भर करता है। मान लीजिए कि यह कुछ डेटा को संग्रहीत करने के लिए आवश्यक बिट्स की सूचना-सैद्धांतिक इष्टतम संख्या है। इस डेटा के एक प्रतिनिधित्व को कहा जाता हैः निहित यदि यह थोड़ी सी जगह लेता है, संक्षिप्त यदि यह थोड़ी सी जगह लेता है, और कॉम्पैक्ट यदि यह थोड़ी सी जगह लेता है। उदाहरण के लिए, एक डेटा संरचना जो भंडारण के बिट्स का उपयोग करती है, वह कॉम्पैक्ट होती है, बिट्स संक्षिप्त होते हैं, बिट्स भी संक्षिप्त होते हैं, और बिट्स अंतर्निहित होते हैं। इस प्रकार अंतर्निहित संरचनाओं को आमतौर पर इनपुट डेटा के कुछ क्रमपरिवर्तन का उपयोग करके जानकारी संग्रहीत करने के लिए कम कर दिया जाता है; इसका सबसे प्रसिद्ध उदाहरण ढेर है। विशिष्ट अनुक्रमण योग्य शब्दकोश, जिन्हें श्रेणी/चुनिंदा शब्दकोश भी कहा जाता है, कई संक्षिप्त प्रतिनिधित्व तकनीकों का आधार बनाते हैं, जिनमें द्विआधारी पेड़,-एरी पेड़ और मल्टीसेट के साथ-साथ प्रत्यय पेड़ और सरणी शामिल हैं। मूल समस्या ब्रह्मांड के एक उपसमुच्चय को संग्रहीत करना है, जिसे आमतौर पर एक बिट सरणी के रूप में दर्शाया जाता है जहां एक अनुक्रमित शब्दकोश शब्दकोशों पर सामान्य तरीकों (प्रश्न, और गतिशील मामले में सम्मिलन/विलोपन) के साथ-साथ निम्नलिखित कार्यों का समर्थन करता हैः के लिए। दूसरे शब्दों में, स्थिति के बराबर तत्वों की संख्या लौटाता है जबकि-th घटना की स्थिति लौटाता है। एक सरल प्रतिनिधित्व है जो भंडारण स्थान (मूल बिट सरणी और एक सहायक संरचना) के बिट्स का उपयोग करता है और स्थिर समय में रैंक और चयन का समर्थन करता है। यह सीमा-न्यूनतम प्रश्नों के लिए समान विचार का उपयोग करता है; सीमित आकार की उप-समस्या पर रुकने से पहले पुनरावृत्तियों की एक निरंतर संख्या होती है। बिट सरणी को आकार बिट्स के बड़े ब्लॉकों और आकार बिट्स के छोटे ब्लॉकों में विभाजित किया जाता है। प्रत्येक बड़े ब्लॉक के लिए, इसके पहले बिट की श्रेणी को एक अलग तालिका में संग्रहीत किया जाता है; ऐसी प्रत्येक प्रविष्टि भंडारण के कुल बिट्स के लिए बिट्स लेती है। एक बड़े ब्लॉक के भीतर, एक अन्य निर्देशिका प्रत्येक छोटे ब्लॉक की श्रेणी को संग्रहीत करती है। यहाँ अंतर यह है कि इसे प्रत्येक प्रविष्टि के लिए केवल बिट्स की आवश्यकता होती है, क्योंकि केवल बड़े ब्लॉक वाले पहले बिट की श्रेणी से अंतर को संग्रहीत करने की आवश्यकता होती है। इस प्रकार, यह तालिका कुल बिट्स लेती है। एक खोज तालिका का उपयोग तब किया जा सकता है जो प्रत्येक संभावित श्रेणी प्रश्न के उत्तर को लंबाई की एक छोटी सी स्ट्रिंग पर संग्रहीत करता है; इसके लिए भंडारण स्थान के बिट्स की आवश्यकता होती है। इस प्रकार, चूंकि इन सहायक तालिकाओं में से प्रत्येक स्थान लेती है, इसलिए यह डेटा संरचना समय और स्थान के टुकड़ों में श्रेणी प्रश्नों का समर्थन करती है। स्थिर समय में किसी प्रश्न का उत्तर देने के लिए, एक स्थिर समय एल्गोरिथ्म गणना करता हैः व्यवहार में, खोज तालिका को बिटवाइज संचालन और छोटी तालिकाओं द्वारा प्रतिस्थापित किया जा सकता है जिनका उपयोग छोटे ब्लॉकों में सेट किए गए बिट्स की संख्या का पता लगाने के लिए किया जा सकता है। यह अक्सर फायदेमंद होता है, क्योंकि संक्षिप्त डेटा संरचनाएं बड़े डेटा सेटों में अपने उपयोग पाते हैं, इस मामले में कैश चूक बहुत अधिक बार हो जाती है और करीब सीपीयू कैश से लुकअप टेबल के बेदखल होने की संभावना अधिक हो जाती है। चयनित प्रश्नों को रैंक के लिए उपयोग की जाने वाली उसी सहायक संरचना पर द्विआधारी खोज करके आसानी से समर्थित किया जा सकता है; हालाँकि, सबसे खराब स्थिति में इसमें समय लगता है। अतिरिक्त भंडारण के टुकड़ों का उपयोग करके एक अधिक जटिल संरचना का उपयोग निरंतर समय में चयन का समर्थन करने के लिए किया जा सकता है। व्यवहार में, इनमें से कई समाधानों में संकेतन में छिपे हुए स्थिरांक होते हैं जो किसी भी एसिम्प्टोटिक लाभ के स्पष्ट होने से पहले हावी होते हैं; व्यापक शब्द संचालन और शब्द-संरेखित ब्लॉकों का उपयोग करके कार्यान्वयन अक्सर व्यवहार में बेहतर प्रदर्शन करते हैं। एन्ट्रापी-संपीड़ित समाधान यह ध्यान में रखते हुए अंतरिक्ष दृष्टिकोण में सुधार किया जा सकता है कि (या ठीक 1 के साथ लंबाई के द्विआधारी तार) के अलग-अलग उपसमुच्चय हैं, और इस प्रकार भंडारण के लिए आवश्यक बिट्स की संख्या पर एक सूचना सैद्धांतिक निचली सीमा है। एक संक्षिप्त (स्थिर) शब्दकोश है जो इस सीमा को प्राप्त करता है, अर्थात् स्थान का उपयोग करते हुए। इस संरचना को रैंक का समर्थन करने और प्रश्नों का चयन करने के लिए बढ़ाया जा सकता है और इसमें जगह लगती है। इस संरचना में सही श्रेणी प्रश्न हालांकि सेट में निहित तत्वों तक सीमित हैं, जो न्यूनतम सही हैशिंग कार्य कैसे काम करते हैं, इसके अनुरूप है। इस सीमा को शब्दकोश के भंडारण स्थान को कम करके समय लेने वाले प्रश्नों के साथ एक स्थान/समय विनिमय तक कम किया जा सकता है। एक अनुक्रमित शब्दकोश का निर्माण करना भी संभव है जो श्रेणी का समर्थन करता है (लेकिन चयन नहीं करता है) जो बिट से कम का उपयोग करता है। इस तरह के शब्दकोश को मोनोटोन मिनिमल परफेक्ट हैश फंक्शन कहा जाता है, और इसे कम से कम बिट्स का उपयोग करके लागू किया जा सकता है। एक संक्षिप्त हैश तालिका, जिसे एक संक्षिप्त क्रमहीन शब्दकोश के रूप में भी जाना जाता है, एक डेटा संरचना है जो अंतरिक्ष बिट्स का उपयोग करके ब्रह्मांड से कुंजी संग्रहीत करती है, और निरंतर अपेक्षित समय में सदस्यता प्रश्नों का समर्थन करती है। यदि एक संक्षिप्त हैश तालिका भी निरंतर अपेक्षित समय में सम्मिलन और विलोपन का समर्थन करती है, तो इसे गतिशील के रूप में संदर्भित किया जाता है, और अन्यथा इसे स्थिर के रूप में संदर्भित किया जाता है। पहला गतिशील संक्षिप्त हैश टेबल 2003 में रमन और राव के कारण था। जहाँ, उनका समाधान स्पेस बिट्स का उपयोग करता है। इसके बाद, यह दिखाया गया कि लॉगरिदम्स की किसी भी स्थिर संख्या के लिए इस स्थान सीमा को बिट्स में सुधार किया जा सकता है। बाद वाला समाधान उच्च संभावना के साथ सबसे खराब स्थिति में स्थिर समय में सभी संचालन का समर्थन करता है। पहली स्थिर संक्षिप्त हैश तालिका 1999 में पाघ के कारण थी। ऐसे मामले में जहां, उनका समाधान स्पेस बिट्स का उपयोग करता है, और सबसे खराब-स्थिति स्थिर-समय प्रश्नों का समर्थन करता है। इस सीमा को बाद में बिट्स और फिर बिट्स में सुधार किया गया। जबकि पहले दो समाधान सबसे खराब-स्थिति निरंतर-समय प्रश्नों का समर्थन करते हैं, अंतिम एक निरंतर अपेक्षित-समय प्रश्नों का समर्थन करता है। अंतिम समाधान के लिए आकार की एक खोज तालिका तक पहुंच की भी आवश्यकता होती है, लेकिन यह खोज तालिका संग्रहीत किए जा रहे तत्वों के समूह से स्वतंत्र है। अन्य उदाहरण एक मनमाना लंबाई (पास्कल स्ट्रिंग) के साथ एक स्ट्रिंग Z + लॉग (Z) स्थान लेती है, और इस प्रकार संक्षिप्त है। यदि अधिकतम लंबाई है-जो व्यवहार में मामला है, क्योंकि 232 = 4 गीगाबाइट डेटा एक बहुत लंबी स्ट्रिंग है, और 264 = 16 ई. आई. बी डेटा व्यवहार में किसी भी स्ट्रिंग से बड़ा है-तो लंबाई वाली एक स्ट्रिंग भी निहित है, जो जेड + के स्थान लेती है, जहां के अधिकतम लंबाई (जैसे, 64 बिट) का प्रतिनिधित्व करने के लिए डेटा की संख्या है। जब चर-लंबाई वाली वस्तुओं (जैसे स्ट्रिंग्स) के अनुक्रम को कूटबद्ध करने की आवश्यकता होती है, तो विभिन्न संभावनाएं होती हैं। एक सीधा तरीका प्रत्येक रिकॉर्ड में एक लंबाई और एक वस्तु को संग्रहीत करना है-इन्हें फिर एक के बाद एक रखा जा सकता है। यह कुशल अगले की अनुमति देता है, लेकिन kth आइटम नहीं ढूंढता है। एक विकल्प यह है कि वस्तुओं को एक परिसीमक (जैसे, शून्य-समाप्त स्ट्रिंग) के साथ क्रम में रखा जाए। यह लंबाई के बजाय परिसीमन का उपयोग करता है, और काफी धीमा है, क्योंकि परिसीमन के लिए पूरे अनुक्रम को स्कैन किया जाना चाहिए। ये दोनों ही स्थान-कुशल हैं। एक वैकल्पिक दृष्टिकोण आउट-ऑफ-बैंड पृथक्करण हैः वस्तुओं को बिना किसी परिसीमक के एक के बाद एक रखा जा सकता है। आइटम सीमा को तब लंबाई के अनुक्रम के रूप में संग्रहीत किया जा सकता है, या बेहतर, इस अनुक्रम में ऑफसेट किया जा सकता है। वैकल्पिक रूप से, एक अलग द्विआधारी स्ट्रिंग जिसमें उन स्थितियों में 1s होता है जहां एक वस्तु शुरू होती है, और हर जगह 0s को इसके साथ कूटबद्ध किया जाता है। इस स्ट्रिंग को देखते हुए, फ़ंक्शन जल्दी से निर्धारित कर सकता है कि प्रत्येक वस्तु कहाँ से शुरू होती है, इसकी अनुक्रमणिका को देखते हुए। यह कॉम्पैक्ट है लेकिन संक्षिप्त नहीं है, क्योंकि यह 2Z स्थान लेता है, जो कि O (Z) है। एक अन्य उदाहरण द्विआधारी वृक्ष का प्रतिनिधित्व हैः नोड्स पर एक मनमाना द्विआधारी वृक्ष को किसी भी नोड पर विभिन्न प्रकार के संचालन का समर्थन करते हुए बिट्स में दर्शाया जा सकता है, जिसमें इसके माता-पिता, इसके बाएं और दाएं बच्चे को ढूंढना और इसके उप-वृक्ष के आकार को वापस करना शामिल है, प्रत्येक स्थिर समय में। नोड्स पर विभिन्न द्विआधारी पेड़ों की संख्या है। बड़े के लिए, यह लगभग है; इस प्रकार हमें इसे कूटबद्ध करने के लिए कम से कम बिट्स की आवश्यकता है। इसलिए एक संक्षिप्त द्विआधारी वृक्ष प्रति नोड केवल बिट्स पर कब्जा करेगा। मिनिमल परफ़ेक्ट हैश फंक्शन सुसिंक्ट नॉन-इंटरेक्टिव आर्ग्यूमेंट्स ऑफ़ नॉलेज रेफेरेंस भी देखें।