बक्से, या कॉम्पैक्ट डेटा संरचनाओं में बिल्लियाँ

यदि खोज ट्री पूरे RAM में विकसित हो गया है और सर्वर रूम में पड़ोसी रैक को रूट करने के लिए मुझे क्या करना चाहिए? उलटे संसाधन-भूखे सूचकांक के साथ क्या करना है? यदि उपयोगकर्ता "फोन मेमोरी फुल" प्राप्त करता है तो क्या मुझे एंड्रॉइड डेवलपमेंट से कनेक्ट करना चाहिए और एप्लिकेशन एक महत्वपूर्ण कंटेनर का केवल आधा लोड है?

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

इस बीच, हैबर पर एक नायक होगा जो एक पंक्ति में तीन बार फिर से बात कर सकता है
[Səksɪŋkt]?

कॉम्पैक्टनेस की दुनिया का दरवाजा

तो, एक डेटा संरचना को कॉम्पैक्ट माना जाता है (रसीला) अगर यह:

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

इसका मतलब यह है कि दोषरहित संपीड़न एल्गोरिदम का कॉम्पैक्ट डेटा संरचनाओं से कोई लेना-देना नहीं है। आखिरकार, वे प्रसंस्करण के लिए एक संपीड़ित स्थिति से डेटा को पुनर्स्थापित करना शामिल करते हैं।

परिचित, रेखांकन, हैश टेबल और अन्य चीजों के "मुख्यधारा" कार्यान्वयन भी अच्छे नहीं हैं। खोज के पेड़ में बाल तत्वों को कम से कम इंगित करें। वे सभ्य स्थान खाते हैं: $$$O (MN)$ जहाँ $$$एम$ - सूचक की लंबाई, और $$$एन$ - पेड़ में नोड्स की संख्या। लेकिन रसीला पेड़ कार्यान्वयन हमें स्पर्शोन्मुख व्यवहार में सुधार करने की अनुमति देता है $$$2 एन + ओ (एन)$ जो सैद्धांतिक निचली सीमा के करीब है $$$2N - 2 (लॉग एन)$ से लकड़ी के लिए $$$एन$ नोड्स। सूचक लंबाई के साथ $$$M = 8$ बाइट का मतलब है इससे आगे बढ़ना $$$O (8N)$ स्पर्शोन्मुखता के एक पूरी तरह से अलग क्रम में - बस $$$2N$ , उस पर विचार कर $$$ओ (एन)$ - के सापेक्ष नगण्य मूल्य $$$एन$ ।

कॉम्पैक्ट (succinct) डेटा संरचनाएं बिट वैक्टर, मल्टीसेट्स, प्लेनर ग्राफ और अन्य पसंदीदा शास्त्रीय संरचनाओं के लिए संकुचित प्रतिनिधित्व हैं। अक्सर वे स्थिर होते हैं, एक बार निर्मित होते हैं और उपयोग के दौरान बदलते नहीं हैं। अपवाद हैं - तत्वों को जोड़ने और हटाने के त्वरित संचालन के साथ रसीला-संरचनाएं।

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

एक कॉम्पैक्ट इंडेक्सेबल डिक्शनरी एक ही बिटमैप है, लेकिन दो ऑपरेशनों द्वारा पूरक है: रैंक और चयन। ये ऑपरेशन हाथी हैं जिन पर दुनिया भर की सरकारें टिकी हुई हैं। मोटे तौर पर, रैंक तत्वों की संख्या की एक संख्या है, और चयन एक तत्व के लिए एक खोज है:

• $$$रैंक_x (i)$ के बराबर बिट्स की संख्या देता है $$$x$ जिनके सूचकांक एक खंड पर स्थित हैं $$$[0; i]$ । क्योंकि $$$x$ - बिट का मान, तो यह विशेष रूप से 0 या 1 के बराबर हो सकता है।
• $$$select_x (j)$ रिटर्न इंडेक्स $$$ज$ के बराबर है $$$x$ । सामान्य ज्ञान कहता है कि कोई शून्य घटना नहीं है, केवल पहला है। इसलिये$$ $ इनलाइन $ j> 0 $ इनलाइन $ : गणना एक से की जाती है। इसके अलावा, $$$ज$ के बराबर शब्दकोश में बिट्स की कुल संख्या से अधिक नहीं हो सकती $$$x$ ।

मान लीजिए कि हमारे पास एक इंडेक्सेबल डिक्शनरी है जिसमें 7 बिट्स में से 4 सेट हैं। तो $$$रैंक 1$ और $$$select_1$ निम्नलिखित मान लेंगे:

एक अनुक्रमणिका शब्दकोश और इसके लिए गणना का एक उदाहरण $$$रैंक 1$ । $$$select_1$ ।

एक चौकस पाठक ध्यान देगा कि चयन रैंक का विलोम है। अगर $$$rank_1 (5) = 4$ तो $$$select_1 (4) = 5$ ।

किसी ने देखते ही देजा वु को दे दिया था $$$rank_1 (i)$ ? और सभी क्योंकि यह ऑपरेशन हेमिंग वजन को सामान्य करता है - अनुक्रम में गैर-शून्य वर्णों की संख्या। बाइनरी दृश्यों के लिए, हैमिंग के वजन को पॉपकाउंट (जनसंख्या गणना) भी कहा जाता है।

छूटे हुए बिट्स के लिए रैंक / चयन भी लागू होता है। यहाँ एक गणना उदाहरण है $$$रैंक_0$ और $$$select_0$ 0 के बराबर बिट्स के लिए:

इसके लिए एक कॉम्पैक्ट इंडेक्सेबल शब्दकोश और गणना का उदाहरण $$$रैंक_0$ । $$$select_0$ ।

एक पेड़ को बिटिकों में देखा

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

पेड़ों के कॉम्पैक्ट प्रतिनिधित्व के तीन तरीके सबसे लोकप्रिय हैं:

• BP (संतुलित कोष्ठक) - संतुलित कोष्ठक क्रम।
• डीएफयूडीएस (गहराई-पहली अनार्य डिग्री अनुक्रम) - गहराई खोज द्वारा क्रमबद्ध यूनिट-एनकोडेड नोड्स का एक क्रम।
• एलओयूडीएस (स्तर-ऑर्डर किए गए एकरी डिग्री सीक्वेंस) - स्तर द्वारा क्रमबद्ध इकाई-एनकोडेड नोड्स के अनुक्रम।

"एकल डिग्री वाले नोड" के लिए "एकात्मक डिग्री" के अनुवाद की संदिग्ध तार्किक श्रृंखला क्या है? तो ठीक है। इन नामों में यूनेरी डिग्री का मतलब है, ट्रेलर में एक शून्य के साथ, बच्चे के नोड्स की संख्या के अनुसार इकाइयों के अनुक्रम के साथ ट्री नोड्स को एन्कोड करना।

पेड़ों के प्रतिनिधित्व के ये तीन तरीके त्वरित संचालन की उपस्थिति से एकजुट होते हैं: एक माता-पिता को ढूंढें; पहला वंश खोजें; अंतिम वंश को खोजो; बाएँ और दाएँ आसन्न नोड्स का पता लगाएं। अन्य संचालन की मौलिक संभावना और प्रभावशीलता विधि से विधि में भिन्न होती है।

आइए हम LOUDS विधि पर ध्यान केन्द्रित करें । इसे समझने के बाद, अन्य दो से निपटना मुश्किल नहीं होगा। इसके अलावा, पिछले साल, LOUDS पेड़ों ने अपना 30 वां जन्मदिन मनाया! LOUDS पेड़ों के लिए अतिरिक्त उपयोगी संचालन में कार्यान्वित किया जाता है $$$O (1)$ : नोड के वंशजों की संख्या ज्ञात करें; अपने सभी वंशजों के बीच नोड के वंशज संख्या की गणना करें (पहला वंशज, दूसरा, $$$मैं$ वें, आदि); खोजने के लिए $$$मैं$ वें वंश। LOUDS का नुकसान सबट्री नोड्स की संख्या की गणना के लिए एक प्रभावी एल्गोरिदम की कमी है।

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

चेतावनी, उपसर्ग वृक्ष:

LOUDS विधि का उपयोग कर संपीड़न के लिए तैयार उपसर्ग पेड़।

बाइनरी फॉर्म में प्रस्तुति के लिए पेड़ तैयार करें:

1. पेड़ को नकली जड़ से जोड़ो। वह बहुत जल्द अपना किरदार निभाएंगे।
2. हम पेड़ के सभी नोड्स की संख्या, स्तर से स्तर, बाएं से दाएं, जैसे कि बीएफएस (चौड़ाई-पहली खोज) में करते हैं। नकली जड़ को नजरअंदाज किया जाता है, और असली को शून्य द्वारा अनुक्रमित किया जाता है।
3. नोड्स को एनकोड करें। ट्री नोड को प्रत्यक्ष वंशज, और शून्य के अनुरूप इकाइयों के अनुक्रम द्वारा एन्कोड किया गया है। यदि नोड में चार बच्चे हैं, तो यह 11110 के रूप में एन्कोडेड है, और यदि कोई नहीं है - 0. फर्जी रूट पहले एन्कोडेड है। इसका एकल वंशज है, इसलिए इसका कोड 10 है।

गिने हुए नोड्स के साथ एक उपसर्ग वृक्ष। नोड्स एन्कोडेड हैं।

स्तर-दर-स्तरीय ट्री ट्रैवर्सल की प्रक्रिया में, एक कॉम्पैक्ट इंडेक्सेबल डिक्शनरी बनाई जाती है - एन्कोडेड नोड्स से बिट्स का एक क्रम ऊपर से नीचे और बाएं से दाएं से चिपके हुए। हमारे पास 21-बिट अनुक्रम है। वैसे, इसे एलबीएस (LOUDS बिट स्ट्रिंग) कहा जाता है।

उपसर्ग वृक्ष के लिए कॉम्पैक्ट इंडेक्सेबल डिक्शनरी।

कॉम्पैक्ट LOUDS उपसर्ग पेड़ बनाया गया है। लकड़ी के लिए एलबीएस $$$एन$ नोड्स (नकली की गिनती नहीं है) लेता है $$$2N + 1$ बिट। सबसे दिलचस्प बात बनी हुई है - एक पेड़ को काटने के लिए सूत्र एक बिटमैप में बदल गए।

पहले बच्चे की खोज करें । एक नोड से संक्रमण $$$मैं$ इसकी पहली संतान नोड सूत्र के अनुसार की जाती है:

$$

$$FirstChild (i) = select_0 (i + 1) - i$$

$$$मैं$ - यह बैंगनी में चिपकाए गए पिछले प्लेट में नोड नंबर है।

अनुक्रमणिका 3 (अक्षर "a") के साथ नोड का पहला वंशज खोजें:

$$

$$फ़र्स्टहिल्ड (3) = चयन_0 (3 + 1) - 3 = चयन_0 (4) - 3 = 9 - 3 = 6$$

पहला बच्चा नोड इंडेक्स 6 में है, और यह अक्षर "k" है। हम पेड़ की जड़ के लिए सूत्र लागू करते हैं:

$$

$$FirstChild (0) = select_0 (0 + 1) - 0 = select_0 (1) = 1$$

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

किसी नोड के अंतिम वंशज की खोज करें $$$मैं$ दो चरणों में गुजरता है: नोड कोड में अंतिम इकाई के सूचकांक का निर्धारण - यह वह है जो इस बच्चे को नामित करता है और फिर बच्चे के सूचकांक को स्वयं निर्धारित करना:

$$

$$lastChildPos (i) = select_0 (i + 2) -1$$

नोड कोड में अंतिम इकाई का सूचकांक प्राप्त करने के बाद, यह सत्यापित करना आवश्यक है कि इस सूचकांक में बिट वास्तव में सेट है। यदि नहीं, तो निष्कर्ष खुद पता चलता है: यह एक वंशज है, वंशज के बिना, एक पत्ती। यदि बिट सेट है, तो आगे बढ़ें:

$$

$$lastChild (i) = rank_1 (lastChildPos (i) -1)$$

नोड 2 के अंतिम वंशज (अक्षर "k") का पता लगाएं।

$$

$$lastChildPos (2) = select_0 (2 + 2) -1 = select_0 (4) -1 = 9-1 = $$$

सूचकांक 8 पर बिट 1 है, इसलिए, नोड 2 एक पत्ती नहीं है, और हम इसके अंतिम बच्चे का सूचकांक पा सकते हैं:

$$

$$lastChild (i) = rank_1 (8-1) = 5$$

वंशजों की संख्या। वंशजों की संख्या निर्धारित करने का सबसे सरल तरीका नोड के अंतिम वंशज के सूचकांक से अपने पहले वंशज के सूचकांक को घटाना और 1 जोड़ना है:

$$

$$चिल्ड्रन (i) = लास्टहिल्ड (i) - फर्स्टहिल्ड (i) + 1$$

लेकिन मान लीजिए नोड $$$मैं$ एक पड़ोसी नोड है $$$i + 1$ के रूप में एक ही पेड़ के स्तर पर स्थित है $$$मैं$ । फिर वंशजों की संख्या $$$मैं$ नोड्स के पहले वंश के सूचकांकों के बीच अंतर के रूप में परिभाषित किया जा सकता है $$$i + 1$ और $$$मैं$ :

$$

$$चिल्ड्रन (i) = फ़र्स्टहिल्ड (i + 1) - फ़र्स्टहिल्ड (i)$$

नोड के वंशज भी क्रमिक रूप से गिने जाते हैं। अगर पहला वंशज $$$मैं$ क्या वह $$$ज$ फिर दूसरा - $$$j + 1$ और इसलिए इस स्तर पर एक नोड पड़ोसी के वंशज के लिए नीचे $$$i + 1$ (यदि कोई हो)।

सूचकांक 1 के साथ पत्ती "और" के वंशजों की संख्या शून्य है:

$$

$$बच्चे (1) = (चयन_0 (2 + 1) - 2) - (चयन_0 (1 + 1) - 1) = 3 - 3 = 0$$

अभिभावक एक नोड खोजते हैं $$$मैं$ सूत्र द्वारा आयोजित:

$$

$$माता-पिता (i) = रैंक_0 (चयन 1 (i + 1) - 1) -1$$

हम इसका उपयोग नोड 6 के माता-पिता ("k" अक्षर) की खोज के लिए करेंगे:

$$

$$माता-पिता (6) = रैंक_0 (चयन 1 (7) - 1) -1 = रैंक_0 (9) -1 = 3$$

यह नोड 3 है, अक्षर "ए"।

बच्चे और माता-पिता के सूचकांकों के लिए सूत्रों के ज्ञान के साथ, पूरे पेड़ के चारों ओर जाना मुश्किल नहीं है। मुख्य बात यह है कि रूट और पत्तियों के लिए सीमा की स्थिति के प्रसंस्करण के बारे में भूलना नहीं है।

बीपी और डीएफयूडीएस तरीकों के बारे में कोप्पेक की एक जोड़ी। दोनों विधियों में स्थानिक स्पर्शोन्मुखता है - $$$2 एन + ओ (एन)$ लकड़ी के लिए बिट $$$एन$ नोड्स, और दोनों कोष्ठक खोलने और बंद करने के रूप में एक पेड़ के नोड के प्रतिनिधित्व में समान हैं।

बीपी (संतुलित कोष्ठक) एक पेड़ को कोष्ठक के अनुक्रम में परिवर्तित करता है, प्रत्येक नोड के लिए एक जोड़ी। ऐसा करने के लिए, पेड़ गहराई में जाता है; प्रत्येक नोड का दो बार दौरा किया जाता है। पहली यात्रा में, उद्घाटन ब्रैकेट रिकॉर्ड किया जाता है, दूसरी यात्रा में - समापन ब्रैकेट। उनके बीच बच्चों के कोष्ठक हैं।

बिटमैप के रूप में कोष्ठक के अनुक्रम का प्रतिनिधित्व करना सुविधाजनक है, जहां 1 प्रारंभिक ब्रैकेट है और 0 क्लोजिंग ब्रैकेट है। बीपी के साथ काम करने के सभी फॉर्मूले त्वरित खोज के लिए तेज किए गए हैं। LOUDS के विपरीत, बीपी आपको जल्दी से एक सबट्री के आकार की गणना करने और दो नोड्स के निकटतम सामान्य पूर्वज का निर्धारण करने की अनुमति देता है। लेकिन पाते हैं $$$मैं$ एलयूडीएस की तुलना में यह वंश अधिक जटिल है।

DFUDS (गहराई-पहली संयुक्त डिग्री अनुक्रम) BP और LOUDS दोनों के लिए समान है। बीपी के साथ, यह एक ट्री वॉक को गहराई से और इसके ब्रैकेट प्रतिनिधित्व को जोड़ती है। और ब्रैकेट्स का सिद्धांत LOUDS में नोड्स को एन्कोड करने के सिद्धांत के समान है। पेड़ पर चढ़ने से पहले, हम पहले से एक कोष्ठक क्रम में एक कोष्ठक जोड़ते हैं। फिर, जब नोड्स को ट्रैवर्स किया जाता है, तो हम वंश की संख्या के अनुसार खुले कोष्ठक लिखते हैं, साथ ही एक को बंद करते हैं। यह पता चला है कि DFUDS में वंश के भंडारण की स्थानीयता BP की तुलना में अधिक है। सबट्री के आकार और निकटतम सामान्य पूर्वज की खोज के लिए गणना की जाती है $$$O (1)$ । लेकिन सबट्री की ऊंचाई का निर्धारण और माता-पिता को खोजने पर $$$ज$ स्तर - DFUDS के लिए भारी संचालन।

स्पष्टता के लिए, हम एक उदाहरण के रूप में मिनी-ट्री का उपयोग करते हुए LOUDS, BP और DFUDS विधियों की तुलना करते हैं।

पेड़ के नोड्स को नारंगी में गिना जाता है जैसे कि चौड़ाई में (LOUDS के लिए), नीला - जब गहराई में चल रहा हो (BP और DFUDS के लिए)।

LOUDS, BP, और DFUDS वृक्ष के दृश्य।

अंग्रेजी-भाषा के कार्यों में सूत्रों के अंतर को देखें तो आश्चर्यचकित न हों। गणितज्ञों में, एक से शुरू होने वाले अनुक्रमण के प्रेमी हैं। और कुछ डेवलपर्स शब्द रैंक और रेंज व्यंजन पर विचार करते हैं, इसलिए वे रैंक को आधा समय बनाते हैं। $$$[0; i)$ । रैंक / चयन की समरूपता बनाए रखने की आवश्यकता के कारण, वे गणना करते हैं $$$चयन (i)$ कैसे $$$चयन (i + 1)$ । लेकिन इस फॉर्म में कुछ फॉर्मूले छोटे दिखते हैं।

विरल सरणी: हिलाओ, लेकिन मिश्रण मत करो

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

अक्सर इस तरह के सरणियों को लवक्राफ्टियन शैली में साइक्लोपियन किया जाता है, एक भोली कार्यान्वयन के साथ वे राम में फिट नहीं होते हैं, लगभग खाली रहते हैं। स्मृति और गति की आवश्यकताओं के आधार पर, स्पार्स सरणियां बहुत अधिक कॉम्पैक्ट हैश तालिकाओं, आसन्न सूचियों, बाइनरी पेड़ों ... या रसीले में बदल जाती हैं।

मान लीजिए कि हमारे पास तारों का एक विरल सरणी है। इसके लिए एक कॉम्पैक्ट इंडेक्सेबल शब्दकोश संलग्न करें। यह क्या देगा?

एक बिटमैप के साथ विरल सरणी।

अब, मूल सरणी तक सीधे पहुंच के बिना, यह जांचना आसान है कि क्या कोई तत्व ब्याज के सूचकांक में मौजूद है या नहीं। सभी अपूर्ण तत्वों को बाहर निकालने से मूल सरणी को सिकोड़ने से कुछ नहीं रोकता है:

खाली तत्वों के बिना एक सरणी।

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

$$

$$j = rank_1 (i) -1$$

आइए देखें कि 8 वें तत्व के साथ चीजें कैसी हैं: $$$बिटमैप [bit] = ०$ । तो, मूल सरणी में ऐसा कोई तत्व नहीं है। तत्व 7 के बारे में क्या? $$$बिटमैप [bit] = १$ । इसका मूल्य प्राप्त करें: $$$रैंक_1 (7) - 1 = 3-1 = 2$ । इंडेक्स 2 में "गो" है।

स्रोत सरणी में सूचकांक की गणना। सरणी में निश्चित रूप से आपको तत्वों द्वारा खोज करने की आवश्यकता होगी! यदि डेटा सॉर्ट नहीं किया जाता है, तो खोज को कम कर दिया जाता है $$$O (N)$ जहाँ $$$एन$ - गैर-खाली तत्वों की संख्या। मिली हुई वस्तु के लिए $$$ज$ इसके सूचकांक प्राप्त करने की आवश्यकता हो सकती है $$$मैं$ मानो सरणी सिकुड़ी नहीं थी। ऐसा करने के लिए, चयन का उपयोग करें, रैंक का व्युत्क्रम:

$$

$$i = select_1 (j + 1)$$

उदाहरण के लिए, "C ++" लाइन ढूंढें। एक कॉम्पैक्ट सरणी में, यह इंडेक्स 0. पर स्थित है और मूल सरणी में इसका इंडेक्स है $$$select_1 (0 + 1) = 3$ ।

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

भंडारण के लिए निश्चित रूप से $$$2 ^ {30}$ वर्णित विधि उपयुक्त नहीं है। इसकी प्रयोज्यता समाप्त होती है जहां सूचकांक के विकास के साथ समस्याएं शुरू होती हैं। लेकिन निश्चित रूप से, सरणियों और इसकी विविधताओं को संपीड़ित करने की इस पद्धति का अपना आला है। एक दैनिक उदाहरण बिटटोरेंट प्रोटोकॉल का कार्यान्वयन है। बिटमैप में डाउनलोड किए गए फ़ाइल खंडों के बारे में जानकारी होती है, और सहकर्मी अपने खंडों के सूचकांकों का आदान-प्रदान करते हैं। एक स्थान का उदाहरण खंडित डेटा ट्रांसमिशन विकल्प है जिसका उपयोग रोवर्स, वॉयर्स और न्यू होराइजन्स स्टेशन द्वारा किया जाता है, जो ट्रांस-नेप्च्यून खुले स्थानों की जुताई करता है।

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

वास्तव में, इन कार्यों को अत्यंत कुशलता से लागू किया जा सकता है: रैंक - के लिए $$$O (1)$ ; का चयन करें - के लिए $$$O (लॉग (लॉग एन))$ , जो लगभग स्थिर है। और हां, यह कुछ ट्रिक्स के बिना नहीं है। और चूंकि जटिल साजिश के साथ किसी भी काम में थोड़ी समझ होनी चाहिए, मैं यहां रुकूंगा।

रोचक तथ्य

सूचना सिद्धांत के संदर्भ में कब्जे वाले संसाधनों की सैद्धांतिक निम्न सीमा क्या है? मान लीजिए कि एक डेटा संरचना बहुत सारे स्टोर करती है $$$एन$ तत्वों। टकराव के बिना उन्हें पहचानने के लिए, आपको कई बिट्स की आवश्यकता होती है, इससे कम नहीं $$$X = log_2N$ । $$$X$ और हार्टले फार्मूले द्वारा निर्धारित बहुत कम सीमा है। कुछ विशेष मामलों में, संग्रहीत डेटा की प्रकृति के बारे में जानकारी होने पर, संरचना को और भी अधिक कुशलता से संकुचित किया जा सकता है।

क्या रसीला स्ट्रिंग एक डेटा संरचना है? इसमें सम्‍मिलित है $$$एन$ वर्ण और एक अशक्त ASCII वर्ण के साथ समाप्त होता है। तो यह लेता है $$$एन + 1$ स्थानों, और इसलिए ... वह रसीला है, और अधिक विशेष रूप से, निहित है! जो हमें अगले प्रश्न की ओर ले जाता है।

क्या सभी रसीली संरचनाएं समान रूप से कॉम्पैक्ट हैं? सक्सेस रिसर्च क्षेत्र तीन प्रकार की कॉम्पैक्ट संरचनाओं को परिभाषित करता है जो स्थानिक जटिलता में भिन्न होती हैं:

• कॉम्पैक्ट - $$$O (N)$ । से रैखिक जटिलता $$$एन$ — . «» . . , : . , . , 0 , . $$$O(2N)$ ( 2 , ) select .
• succinct — $$$N + o(N)$ । — , succinct data structures . : (Pascal string), . $$$N + log(N)$ ।
• implicit — $$$N + O(1)$ । , . : (heap) . $$$N + 1$ ।

? , , . succinct- . , -, FM-, RMQ (range minimum queries), LCP (longest common prefix), , succinct'. -.

, , . और इतना ही नहीं। , , X, .

succinct — , «- ». Succinct — . , , succinct. , . (IME) Google, . MAPS.ME succinct- .

, . ., 97 % -: . 3 %.

आगे क्या है?

, succinct:

• rank/select Bitmagic Library.
• , succinct. .
• MIT, succinct.
• , 18 .
• , succinct.
• RRR — .

, :

• सी ++ में रसीला डेटा संरचनाएं पुस्तकालय परियोजना।
• C ++ में बिटमैजिक प्रोजेक्ट।
• पाइथन में एलियास-फ़ानो के रसीद कार्यान्वयन के साथ पैकेज।
• रस्ट में कुछ रसीली संरचनाओं का कार्यान्वयन।