अंतर्निहित डेटा संरचना
कंप्यूटर विज्ञान में, अंतर्निहित डेटा संरचना या स्पेस-कुशल डेटा संरचना एक डेटा संरचना है जो मुख्य या आवश्यक डेटा के अतिरिक्त बहुत कम जानकारी संग्रहीत करती है: डेटा संरचना जिसके लिए कम ओवरहेड (कंप्यूटिंग) की आवश्यकता होती है। उन्हें अंतर्निहित कहा जाता है क्योंकि तत्वों की स्थिति तत्वों के बीच अर्थ और संबंध रखती है; यह तत्वों के बीच स्पष्ट संबंध देने के लिए पॉइंटर (कंप्यूटर विज्ञान) के उपयोग से इसकी तुलना की जाती है। कम ओवरहेड की परिभाषाएँ अलग-अलग होती हैं, किन्तु सामान्यतः बड़े O नोटेशन, O(1) ओवरहेड में इसका अर्थ निरंतर ओवरहेड होता है। एक कम प्रतिबंधात्मक परिभाषा एक संक्षिप्त डेटा संरचना है, जो अधिक ओवरहेड की अनुमति देती है।
परिभाषा
अंतर्निहित डेटा संरचना स्थिरांक वाली होती है O(1) स्पेस ओवरहेड (सूचना-सैद्धांतिक निचली सीमा के ऊपर)।
ऐतिहासिक रूप से, Munro & Suwanda (1980) ने अंतर्निहित डेटा संरचना (और पर कार्य करने वाले एल्गोरिदम) को ऐसी संरचना के रूप में परिभाषित किया है जिसमें संरचनात्मक जानकारी पॉइंटर्स में स्पष्ट होने के बजाय डेटा संग्रहीत करने के तरीके में अंतर्निहित होती है। वे परिभाषा में कुछ हद तक अस्पष्ट हैं, इसे सबसे सख्ती से एकल सरणी के रूप में परिभाषित करते हैं, जिसमें केवल आकार बरकरार रखा जाता है (ओवरहेड की एकल संख्या),[1] या अधिक शिथिल रूप से निरंतर ओवरहेड के साथ डेटा संरचना के रूप में (O(1)).[2] यह बाद वाली परिभाषा आज अधिक मानक है, और गैर-स्थिर किन्तु छोटी डेटा संरचना की अभी भी ढीली धारणा है o(n) ओवरहेड को आज संक्षिप्त डेटा संरचना के रूप में जाना जाता है, जैसा कि परिभाषित किया गया है Jacobson (1988); इसे अर्ध-अंतर्निहित के रूप में संदर्भित किया गया था Munro & Suwanda (1980).[3] स्थैतिक डेटा संरचना (केवल पढ़ने के लिए) और गतिशीलता (जिसे संशोधित किया जा सकता है) के बीच बुनियादी अंतर है। सरल अंतर्निहित डेटा संरचनाएं, जैसे कि क्रमबद्ध सूची को सरणी के रूप में प्रस्तुत करना, स्थिर डेटा संरचना के रूप में बहुत कुशल हो सकता है, किन्तु गतिशील डेटा संरचना के रूप में अक्षम, संशोधन संचालन (जैसे कि क्रमबद्ध सूची के मामले में सम्मिलन) के कारण अकुशल.
उदाहरण
अंतर्निहित डेटा संरचना का तुच्छ उदाहरण सरणी डेटा संरचना है, जो सूची (अमूर्त डेटा प्रकार) के लिए अंतर्निहित डेटा संरचना है, और केवल लंबाई के निरंतर ओवरहेड की आवश्यकता होती है; लिंक्ड सूची के विपरीत, जिसमें प्रत्येक डेटा तत्व के साथ सूचक जुड़ा होता है, जो स्पष्ट रूप से तत्व से दूसरे तक संबंध बताता है। इसी तरह, एक शून्य-समाप्त स्ट्रिंग स्ट्रिंग (कंप्यूटर विज्ञान) (वर्णों की सूची) के लिए अंतर्निहित डेटा संरचना है। इन्हें बहुत सरल माना जाता है क्योंकि ये स्थिर डेटा संरचनाएं (केवल पढ़ने के लिए) हैं, और केवल तत्वों पर पुनरावृत्ति के सरल संचालन को स्वीकार करते हैं।
इसी तरह सरल बहु-आयामी सरणी को उसके आयामों के साथ एकल 1-आयामी सरणी के रूप में प्रस्तुत करना है। उदाहरण के लिए, m × n सरणी को लंबाई m·n की एकल सूची के रूप में प्रस्तुत करना, संख्याओं m और n के साथ (प्रत्येक 1-आयामी उपसरणी के लिए पॉइंटर्स की 1-आयामी सरणी के बजाय)। तत्वों को ही प्रकार का होना जरूरी नहीं है, और डेटा की तालिका (जानकारी) (रिकॉर्ड (कंप्यूटर विज्ञान) की सूची) को प्रत्येक फ़ील्ड की लंबाई के साथ, फ्लैट (1-आयामी) सूची के रूप में दर्शाया जा सकता है। (कंप्यूटर विज्ञान), जब तक कि प्रत्येक फ़ील्ड का आकार समान हो (इसलिए प्रति फ़ील्ड ही आकार का उपयोग किया जा सकता है, प्रति रिकॉर्ड नहीं)।
कम तुच्छ उदाहरण क्रमबद्ध सरणी द्वारा क्रमबद्ध सूची का प्रतिनिधित्व कर रहा है, जो बाइनरी खोज द्वारा लघुगणकीय समय में खोज की अनुमति देता है। खोज वृक्ष के साथ तुलना करें, विशेष रूप से द्विआधारी खोज वृक्ष, जो लघुगणक-समय खोज की भी अनुमति देता है, किन्तु इसके लिए पॉइंटर्स की आवश्यकता होती है। क्रमबद्ध सरणी केवल स्थिर डेटा संरचना के रूप में ही कुशल है, क्योंकि सूची को संशोधित करना धीमा है - बाइनरी सर्च ट्री के विपरीत - किन्तु इसके लिए ट्री के ओवरहेड स्थान की आवश्यकता नहीं होती है।
अंतर्निहित डेटा संरचना का महत्वपूर्ण उदाहरण गहराई के बढ़ते क्रम में पूरा बाइनरी ट्री को सूची के रूप में प्रस्तुत करना है, जैसे रूट, पहला बायां बच्चा, पहला दायां बच्चा, पहले बाएं बच्चे का पहला बायां बच्चा, आदि। ऐसा पेड़ उल्लेखनीय रूप से होता है किसी दिए गए गहराई तक वंश चार्ट के लिए, और अंतर्निहित प्रतिनिधित्व को वंशावली (पूर्वज तालिका) के रूप में जाना जाता है।
इसे उत्तम बाइनरी ट्री (जहां अंतिम स्तर अधूरा हो सकता है) के लिए सामान्यीकृत किया जा सकता है, जो अंतर्निहित डेटा संरचना का सबसे प्रसिद्ध उदाहरण देता है, अर्थात् बाइनरी ढेर , जो प्राथमिकता कतार के लिए अंतर्निहित डेटा संरचना है। यह पहले के उदाहरणों की तुलना में अधिक परिष्कृत है क्योंकि यह एकाधिक संचालन की अनुमति देता है, और कुशल गतिशील डेटा संरचना है (यह डेटा के कुशल संशोधन की अनुमति देता है): न केवल 'शीर्ष', बल्कि 'सम्मिलित करें' और 'पॉप' भी।
अधिक परिष्कृत अंतर्निहित डेटा संरचनाओं में बीप (द्वि-अभिभावक ढेर) शामिल है।
इतिहास
सूचियों या मूल्यों की तालिकाओं के तुच्छ उदाहरण प्रागैतिहासिक काल के हैं, जबकि ऐतिहासिक रूप से गैर-तुच्छ अंतर्निहित डेटा संरचनाएं कम से कम अहनेंटाफेल की हैं, जिसे वंशावली में उपयोग के लिए 1590 में माइकल एइट्ज़िंगर द्वारा पेश किया गया था। औपचारिक कंप्यूटर विज्ञान में, पहली अंतर्निहित डेटा संरचना को सामान्यतः क्रमबद्ध सूची माना जाता है, जिसका उपयोग बाइनरी खोज के लिए किया जाता है, जिसे 1946 में जॉन मौचली द्वारा मूर स्कूल व्याख्यान में पेश किया गया था, जो किसी भी कंप्यूटर से संबंधित व्याख्यान का पहला सेट था। विषय।[4][5] बाइनरी हीप को पेश किया गया था Williams (1964) ढेर बनाएं और छांटें को लागू करने के लिए।[5]अंतर्निहित डेटा संरचना की धारणा को औपचारिक रूप दिया गया था Munro & Suwanda (1980), बीप का परिचय और विश्लेषण करने के भाग के रूप में।[5]
संदर्भ
- ↑ "Thus, only a simple array is needed for the data.", p. 236; "We will draw no formal distinction between a pointer and an integer (index) in the range . A data structure is then implicit, if the only such integer which need be retained is N itself.", p. 238
- ↑ "... one might prefer to permit a constant number of pointers to be retained and still designate the structure as implicit.", p. 238
- ↑ "We will also suggest two structures which might be described as “semi-implicit,” in that a variable, but o(N), number of pointers (indices) is kept.", p. 238
- ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".
- ↑ 5.0 5.1 5.2 Franceschini, Gianni; Munro, J. Ian (2006). अद्यतन और तेज़ खोज के अनुसार ओ(1) संशोधनों के साथ निहित शब्दकोश. Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms. Miami, FL, United States. pp. 404–413. doi:10.1145/1109557.1109603.
- Munro, J.Ian; Suwanda, Hendra (October 1980). "Implicit data structures for fast search and update". Journal of Computer and System Sciences. 21 (2): 236–250. doi:10.1016/0022-0000(80)90037-9.
- Jacobson, G. J (1988). Succinct static data structures (Ph.D.). Pittsburgh, PA: Carnegie Mellon University.
अग्रिम पठन
See publications of Hervé Brönnimann, J. Ian Munro, and Greg Frederickson.
