संक्षिप्त डेटा संरचना

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

माना कि $Z$ कुछ डेटा को स्टोर करने के लिए आवश्यक बिट्स की सूचना-सैद्धांतिक इष्टतम संख्या है। इस डेटा का एक प्रतिनिधित्व कहा जाता है:

• निहित डेटा संरचना यदि यह लेता है $Z+O(1)$ अन्तराल के बिट्स,
• यदि लगे तो संक्षिप्त करें $Z+o(Z)$ अन्तराल के बिट्स, और
• कॉम्पैक्ट अगर यह लेता है $O(Z)$ अन्तराल के बिट्स।

उदाहरण के लिए, एक डेटा संरचना जो उपयोग करती है $2Z$ भंडारण के बिट्स कॉम्पैक्ट हैं, $Z+{\sqrt {Z}}$ बिट संक्षिप्त है, $Z+\lg Z$ बिट भी संक्षिप्त है, और $Z+3$ बिट्स निहित है।

इस प्रकार अंतर्निहित संरचनाएं सामान्यतः इनपुट डेटा के कुछ क्रमपरिवर्तन का उपयोग करके जानकारी संग्रहीत करने के लिए कम हो जाती हैं; इसका सबसे प्रसिद्ध उदाहरण हीप (डेटा संरचना) है।

संक्षिप्त शब्दकोश

सक्सेस इंडेक्सेबल डिक्शनरी, जिसे रैंक/सिलेक्ट डिक्शनरी भी कहा जाता है, बाइनरी ट्री सहित कई सक्सेसफुल रिप्रेजेंटेशन तकनीकों का आधार बनता है, $k$-एरी ट्री और मल्टीसेट,साथ ही प्रत्यय ट्री और प्रत्यय सरणीमूल समस्या एक सबसेट को स्टोर करना है $S$ एक अंतराल का $U=[0\dots n)=\{0,1,\dots ,n-1\}$, सामान्यतः एक बिट सरणी के रूप में दर्शाया जाता है $B[0\dots n)$ कहाँ $B[i]=1$ आईएफएफ $i\in S.$ एक इंडेक्सेबल डिक्शनरी (क्वेरी, और डायनामिक केस में इंसर्शन/डिलीशन) के साथ-साथ निम्नलिखित ऑपरेशंस पर सामान्य तरीकों का समर्थन करता है:

• $\mathbf {rank} _{q}(x)=|\{k\in [0\dots x]:B[k]=q\}|$
• $\mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}$

के लिए $q\in \{0,1\}$.

दूसरे शब्दों में, $\mathbf {rank} _{q}(x)$ के बराबर तत्वों की संख्या देता है $q$ स्थिति तक $x$ जबकि $\mathbf {select} _{q}(x)$ की स्थिति लौटाता है $x$-वीं घटना $q$ है।

एक साधारण प्रतिनिधित्व हैजो उपयोग करता है $n+o(n)$ भंडारण स्थान के बिट्स (मूल बिट सरणी और a $o(n)$ सहायक संरचना) और रैंक का समर्थन करता है और निरंतर समय में चयन करता है। यह रेंज न्यूनतम क्वेरी रेंज-मिनिमम क्वेरीज; सीमित आकार की उप-समस्या पर रुकने से पहले निरंतर संख्या में पुनरावर्तन होते हैं। बिट सरणी $B$ आकार के बड़े ब्लॉकों में बांटा गया है $l=\lg ^{2}n$ बिट्स और आकार के छोटे ब्लॉक $s=\lg n/2$ बिट्स प्रत्येक बड़े ब्लॉक के लिए, उसके पहले बिट का रैंक एक अलग तालिका में संग्रहीत किया जाता है $R_{l}[0\dots n/l)$; प्रत्येक ऐसी प्रविष्टि लेता है $\lg n$ कुल के लिए बिट्स $(n/l)\lg n=n/\lg n$ भंडारण के बिट्स एक बड़े ब्लॉक के भीतर, दूसरी निर्देशिका $R_{s}[0\dots l/s)$ प्रत्येक के रैंक को स्टोर करता है $l/s=2\lg n$ इसमें छोटे ब्लॉक होते हैं। यहाँ अंतर यह है कि इसकी केवल आवश्यकता है $\lg l=\lg \lg ^{2}n=2\lg \lg n$ प्रत्येक प्रविष्टि के लिए बिट्स, क्योंकि बड़े ब्लॉक वाले पहले बिट के रैंक से केवल अंतर को संग्रहीत करने की आवश्यकता होती है। इस प्रकार, यह तालिका कुल $(n/s)\lg l=4n\lg \lg n/\lg n$ बिट्स लेती है। एक लुकअप टेबल $R_{p}$ तब उपयोग किया जा सकता है जो हर संभव रैंक क्वेरी के उत्तर को लंबाई के एक बिट स्ट्रिंग पर संग्रहीत करता है $s$ के लिए $i\in [0,s)$; इस आवश्यकता है $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ भंडारण स्थान के बिट्स इस प्रकार, चूंकि इनमें से प्रत्येक सहायक तालिका लेती है $o(n)$ अन्तराल, यह डेटा संरचना रैंक प्रश्नों का समर्थन करती है $O(1)$ समय और $n+o(n)$ अन्तराल के बिट्स एक स्थिर समय एल्गोरिथम गणना करता है,

एक प्रश्न का उत्तर देने के लिए $\mathbf {rank} _{1}(x)$ निरंतर समय में, एक स्थिर समय एल्गोरिथम गणना करता है:

• $\mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor ]+R_{s}[\lfloor x/s\rfloor ]+R_{p}[x\lfloor x/s\rfloor ,x{\text{ mod }}s]$

व्यवहार में, लुकअप तालिका $R_{p}$ बिटवाइज़ ऑपरेशंस और छोटी तालिकाओं द्वारा प्रतिस्थापित किया जा सकता है जिनका उपयोग छोटे ब्लॉकों में सेट बिट्स की संख्या का पता लगाने के लिए किया जा सकता है। यह अक्सर फायदेमंद होता है, क्योंकि संक्षिप्त डेटा संरचनाएं बड़े डेटा सेट में अपना उपयोग ढूंढती हैं, इस मामले में कैश की कमी बहुत अधिक हो जाती है और लुकअप टेबल को करीबी सीपीयू कैश से बेदखल करने की संभावना अधिक हो जाती है।रैंक के लिए उपयोग की जाने वाली समान सहायक संरचना पर बाइनरी खोज करके चुनिंदा प्रश्नों का आसानी से समर्थन किया जा सकता है; हालाँकि, यह लेता है $O(\lg n)$ सबसे खराब स्थिति में समय। एक अधिक जटिल संरचना का उपयोग करना $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ निरंतर समय में चयन का समर्थन करने के लिए अतिरिक्त संग्रहण के बिट्स का उपयोग किया जा सकता है।व्यवहार में, इनमें से कई समाधानों में छिपे हुए स्थिरांक हैं $O(\cdot )$ संकेतन जो किसी भी स्पर्शोन्मुख लाभ के स्पष्ट होने से पहले हावी हो जाता है; व्यापक शब्द संचालन और शब्द-संरेखित ब्लॉक का उपयोग करने वाले कार्यान्वयन अक्सर अभ्यास में बेहतर प्रदर्शन करते हैं।

एंट्रॉपी-संपीड़ित शब्दकोश

$n+o(n)$ h> अन्तराल दृष्टिकोण को ध्यान में रखते हुए सुधार किया जा सकता है $\textstyle {\binom {n}{m}}$ अलग $m$-उपसमुच्चय $[n)$ (या लंबाई के बाइनरी तार $n$ साथ बिल्कुल $m$ 1), और इस प्रकार $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ एक सूचना सिद्धांत है जो स्टोर करने के लिए आवश्यक बिट्स की संख्या पर कम है $B$. एक संक्षिप्त (स्थैतिक) शब्दकोश है जो इस सीमा को प्राप्त करता है, अर्थात् उपयोग करना ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ अन्तराल।इस संरचना को रैंक का समर्थन करने और प्रश्नों का चयन करने और लेने के लिए बढ़ाया जा सकता है ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ अन्तराल।इस संरचना में सही रैंक प्रश्न हालांकि सेट में निहित तत्वों तक सीमित हैं, जो न्यूनतम पूर्ण हैशिंग फ़ंक्शन के काम करने के अनुरूप है। डिक्शनरी के स्टोरेज स्पेस को कम करके इस बाउंड को स्पेस/टाइम ट्रेडऑफ़ में कम किया जा सकता है, डेटा संरचना किसी कंप्यूटर सिस्टम में डेटा को स्टोर तथा व्यवस्थित करने का एक तरीका होता है। जिससे कि हम डेटा का आसानी से इस्तेमाल कर सकें, अर्थात डेटा को इस प्रकार स्टोर तथा व्यवस्थित किया जाता है कि उसको बाद में किसी भी समय आसानी से एक्सेस किया जा सकें।

उदाहरण

एक अशक्त-समाप्त स्ट्रिंग (सी स्ट्रिंग) Z + 1 स्थान लेती है, और इस प्रकार निहित है। मनमाना लंबाई (पास्कल स्ट्रिंग) के साथ एक स्ट्रिंग Z + लॉग (Z) स्थान लेती है, और इस प्रकार संक्षिप्त होती है। यदि अधिकतम लंबाई है - जो व्यवहार में मामला है, चूंकि 2³² = 4 GiB डेटा एक बहुत लंबी स्ट्रिंग है, और 2⁶⁴ = 16 EiB डेटा व्यवहार में किसी भी स्ट्रिंग से बड़ा है - फिर लंबाई के साथ एक स्ट्रिंग भी निहित है, Z + k स्पेस लेते हुए, जहाँ k अधिकतम लंबाई का प्रतिनिधित्व करने के लिए डेटा की संख्या है (जैसे, 64 बिट्स)।

जब चर-लंबाई वाली वस्तुओं (जैसे तार) के अनुक्रम को एन्कोड करने की आवश्यकता होती है, तो विभिन्न संभावनाएँ होती हैं। एक सीधा तरीका प्रत्येक रिकॉर्ड में एक लंबाई और एक आइटम को स्टोर करना है - फिर इन्हें एक के बाद एक रखा जा सकता है। यह प्रभावशाली अगले की अनुमति देता है, लेकिन kth आइटम नहीं ढूंढता है। एक विकल्प यह है कि वस्तुओं को एक सीमांकक के साथ क्रम में रखा जाए (उदाहरण के लिए, अशक्त-समाप्त स्ट्रिंग) यह एक लंबाई के बजाय एक सीमांकक का उपयोग करता है, और काफी धीमा है, क्योंकि पूरे अनुक्रम को सीमांकक के लिए स्कैन किया जाना चाहिए। ये दोनों अन्तराल-प्रभावशाली हैं। एक वैकल्पिक दृष्टिकोण आउट-ऑफ़-बैंड अलगाव है: वस्तुओं को बिना किसी सीमांकक के एक के बाद एक रखा जा सकता है। आइटम सीमाओं को इस क्रम में लंबाई, या बेहतर, ऑफ़सेट के अनुक्रम के रूप में संग्रहीत किया जा सकता है। वैकल्पिक रूप से, एक अलग बाइनरी स्ट्रिंग जिसमें आइटम शुरू होने वाले स्थान पर 1s होता है, और 0s हर जगह इसके साथ एन्कोड किया जाता है। इस स्ट्रिंग को देखते हुए, $select$ फ़ंक्शन जल्दी से यह निर्धारित कर सकता है कि प्रत्येक आइटम कहाँ से शुरू होता है, इसकी अनुक्रमणिका दी गई है। यह कॉम्पैक्ट है लेकिन संक्षिप्त नहीं है, क्योंकि यह 2Z स्थान लेता है, जो O(Z) है।

एक अन्य उदाहरण एक बाइनरी ट्री का प्रतिनिधित्व है: एक मनमाना बाइनरी ट्री ऑन $n$ नोड्स में प्रदर्शित किया जा सकता है $2n+o(n)$ बिट्स किसी भी नोड पर विभिन्न प्रकार के संचालन का समर्थन करते हुए, जिसमें इसके माता-पिता, इसके बाएं और दाएं बच्चे को ढूंढना और इसके सबट्री के आकार को वापस करना शामिल है, प्रत्येक निरंतर समय में। विभिन्न बाइनरी ट्रीों की संख्या $n$ नोड्स है ${\tbinom {2n}{n}}$$/(n+1)$. बड़े के लिए $n$, इस बारे में है $4^{n}$; इस प्रकार हमें कम से कम चाहिए $\log _{2}(4^{n})=2n$ इसे एनकोड करने के लिए बिट्स। एक संक्षिप्त बाइनरी ट्री इसलिए केवल कब्जा करेगा $2$ बिट्स प्रति नोड।

यह भी देखें

• मिनिमल परफेक्ट हैश फंक्शन
• जीरो-नॉलेज_प्रूफ जीरो-नॉलेज प्रूफ प्रोटोकॉल ज्ञान के संक्षिप्त गैर-संवादात्मक तर्क