Simplex tree
टोपोलॉजिकल डेटा विश्लेषण में, एक सिम्प्लेक्स ट्री एक प्रकार का ट्राइ है जिसका उपयोग किसी भी सामान्य सरल परिसर को कुशलता से प्रस्तुत करने के लिए किया जाता है। अपने नोड्स के माध्यम से, यह डेटा संरचना विशेष रूप से सभी सरलताओं का स्पष्ट रूप से प्रतिनिधित्व करती है। इसकी लचीली संरचना निरंतर समरूपता की गणना के लिए उपयोगी कई बुनियादी कार्यों के कार्यान्वयन की अनुमति देती है। इस डेटा संरचना का आविष्कार जीन-डेनियल बोइसोनेट और क्लेमेंट मारिया ने 2014 में द सिम्प्लेक्स ट्रीः एन एफिशिएंट डेटा स्ट्रक्चर फॉर जनरल सिम्प्लिकल कॉम्प्लेक्स लेख में किया था। यह डेटा संरचना विरल सरल परिसरों पर कुशल संचालन प्रदान करती है। घने या अधिकतम सरलीकरण के लिए, कंकाल-अवरोधक प्रतिनिधित्व या टोपलेक्स मानचित्र प्रतिनिधित्व का उपयोग किया जाता है। परिभाषा टोपोलॉजिकल डेटा विश्लेषण में कई शोधकर्ता सिम्प्लेक्स ट्री को सरल परिसरों के लिए सबसे कॉम्पैक्ट सिम्प्लेक्स-आधारित डेटा संरचना मानते हैं, और एक डेटा संरचना जो उनके गणितीय गुणों के एकीकृत उपयोग के कारण सरल परिसरों की सहज ज्ञान युक्त समझ की अनुमति देती है। किसी भी सरल परिसर पर विचार करें कि वह बिंदु (0 आयाम), रेखा खंड (1 आयाम), त्रिभुज (2 आयाम) और उनके एन-आयामी समकक्षों से बना एक समूह है, जिन्हें एक स्थलवैज्ञानिक स्थान के भीतर एन-सिम्प्लेक्स कहा जाता है। सिम्प्लेक्स के गणितीय गुणों के अनुसार, कोई भी एन-सिम्प्लेक्स कई-सिम्प्लेक्स से बना होता है। इस प्रकार, रेखाएँ बिंदुओं, रेखाओं के त्रिकोणों, त्रिभुज के चतुष्कोणों से बनी होती हैं। ध्यान दें कि प्रत्येक उच्च स्तर एन-सिम्प्लेक्स के शीर्षों में 1 शीर्ष जोड़ता है। डेटा संरचना सिम्प्लेक्स-आधारित है, इसलिए, इसे सिम्प्लेक्स को परिभाषित करने वाले बिंदुओं द्वारा सभी सिम्प्लेक्स का विशिष्ट रूप से प्रतिनिधित्व करना चाहिए। इसे प्राप्त करने का एक सरल तरीका यह है कि प्रत्येक सिंप्लेक्स को उसके अंकों द्वारा क्रमबद्ध क्रम में परिभाषित किया जाए। मान लीजिए कि आयाम k का एक सरल परिसर, इसका शीर्ष समुच्चय, जहां शीर्षों को 1 से लेबल किया जाता है और तदनुसार क्रमबद्ध किया जाता है। अब, एक शब्दकोश आकार का निर्माण करें जिसमें सभी शीर्ष लेबल क्रम में हों। यह 0-आयामी सिम्प्लेक्स का प्रतिनिधित्व करता है। फिर, प्रारंभिक शब्दकोश में प्रत्येक प्रविष्टि के प्रारंभिक शब्दकोश के मार्ग के लिए, बाल शब्दकोश के रूप में सभी शीर्षों को जोड़ें जो वर्तमान शीर्षों के सेट से पूरी तरह से जुड़े हुए हैं, जिनमें से सभी पर उससे बड़ा लेबल है। के स्तरों पर इस चरण का प्रतिनिधित्व करें। स्पष्ट रूप से, पहले शब्दकोश को गहराई 0 के रूप में देखते हुए, इस डेटा संरचना में किसी भी शब्दकोश की गहराई पर कोई भी प्रविष्टि विशिष्ट रूप से एक-सिम्प्लेक्स का प्रतिनिधित्व करती है। पूर्णता के लिए, प्रारंभिक शब्दकोश के बिंदु को खाली सिम्प्लेक्स का प्रतिनिधित्व माना जाता है। संचालन की व्यावहारिकता के लिए, एक ही स्तर पर दोहराए जाने वाले लेबल एक साथ जुड़े होते हैं, जिससे एक लूप की गई लिंक सूची बनती है। अंत में, बाल शब्दकोशों में तेजी से पूर्वजों तक पहुँच के लिए उनके मूल शब्दकोश के लिए संकेत भी हैं। रचनात्मक परिभाषा मान लीजिए कि यह आयाम k का एक सरल कॉम्प्लेक्स है। हम सरल कॉम्प्लेक्स को पारस्परिक रूप से अनन्य सिम्प्लेक्स में विघटित करके शुरू करते हैं। इसे लालची तरीके से सरल परिसर से उच्चतम क्रम के सिम्प्लेक्स को बार-बार हटाकर तब तक प्राप्त किया जा सकता है जब तक कि सरल परिसर खाली न हो जाए। फिर हमें प्रत्येक शीर्ष को 1 से लेबल करने की आवश्यकता है और प्रत्येक सिंप्लेक्स को उसके संबंधित "शब्द" के साथ जोड़ना होगा, जो कि लेबल द्वारा उसके शीर्षों की क्रमबद्ध सूची है। लेबल को ऑर्डर करने से यह सुनिश्चित होता है कि सिम्प्लेक्स ट्री में कोई पुनरावृत्ति न हो, क्योंकि सिम्प्लेक्स का वर्णन करने का केवल एक ही तरीका है। हम एक शून्य मूल से शुरू करते हैं, जो शून्य सिंप्लेक्स का प्रतिनिधित्व करता है। फिर, हम सभी सिंप्लेक्स के माध्यम से और प्रत्येक सिंप्लेक्स शब्द के प्रत्येक लेबल के माध्यम से पुनरावृत्ति करते हैं। यदि लेबल वर्तमान मूल के लिए एक बच्चे के रूप में उपलब्ध है, तो उस बच्चे को सम्मिलन प्रक्रिया का अस्थायी मूल बनाएँ, अन्यथा, बच्चे के लिए एक नया नोड बनाएँ, इसे नया अस्थायी मूल बनाएँ, और बाकी शब्द के साथ जारी रखें। इस प्रक्रिया के दौरान, के शब्दकोशों को सभी लेबलों के साथ बनाए रखा जाता है और संबंधित लेबल के लिए नोड का पता डाला जाता है। यदि शब्दकोश में उस स्थान पर पहले से ही कोई पता है, तो पुराने नोड से नए नोड तक एक सूचक बनाया जाता है। एक बार प्रक्रिया समाप्त हो जाने के बाद प्रत्येक नोड के सभी बच्चों को एक शब्दकोश में दर्ज किया जाता है, और सभी संकेत लूप की गई लिंक सूची बनाने के लिए लूप होते हैं। हैश टेबल की तरह यहाँ शब्दकोशों की एक विस्तृत श्रृंखला लागू की जा सकती है, लेकिन कुछ संचालन प्रविष्टियों के एक क्रमबद्ध पारगमन की संभावना मानते हैं, जिससे लाल-काले पेड़ों का उपयोग करने के लिए अधिकांश कार्यान्वयन शब्दकोश हैं। जबकि सिंप्लेक्स ट्री सरल जटिल प्रतिनिधित्व के लिए सबसे अधिक स्थान कुशल डेटा संरचना नहीं हैं, विरल डेटा पर उनके संचालन को अत्याधुनिक माना जाता है। यहाँ, हम इस प्रतिनिधित्व के माध्यम से संभव विभिन्न उपयोगी संचालन की सीमाएँ देते हैं। इन कार्यों के कई कार्यान्वयन उपलब्ध हैं। हम सबसे पहले संकेतन का परिचय देते हैं। एक दिए गए सिम्प्लेक्स पर विचार करें, एक दिया गया नोड है जो अंतिम शीर्ष के अनुरूप है, उस नोड के लिए लेबल सहयोगी है, उस नोड की गहराई है, सरल परिसर का आयाम है, एक शब्दकोश में उपयोग करने के लिए संचालन की अधिकतम संख्या है (यदि शब्दकोश एक लाल-काला पेड़ है, तो जटिलता है)। कोफेस की संख्या पर विचार करें, और क्या सिंप्लेक्स ट्री के नोड्स की संख्या लेबल के साथ समाप्त होती है जिसकी गहराई उससे अधिक होती है। नोटिस करें। शब्द खोजें, डालें और हटाएं। एक पूरा सिंप्लेक्स डालें और हटा दें। निरंतर समरूपता की गणना, या अधिक शामिल तरीके से, बेट्टी संख्याओं की गणना, एक सिम्प्लेक्स ट्री का सबसे कुशलता से उपयोग करना एक खुली समस्या बनी हुई है, हालांकि, विरल सरल परिसरों पर इस कार्य के लिए वर्तमान एल्गोरिदम अत्याधुनिक प्रदर्शन प्राप्त करते हैं। सिंप्लेक्स पेड़ों की संरचना संकुचित सिंप्लेक्स के प्रारंभिक पतन की अनुमति देती है, हालांकि सामान्य मामले में इस ऑपरेशन की सीमा अज्ञात है। प्राथमिक पतन का एक उप-मामला किनारा-संकुचन है। किनारे का संकुचन प्राप्त किया जा सकता है। दिए गए सिम्प्लेक्स के कोफेस का पता लगाने में प्राप्त किया जा सकता है। दिए गए सिम्प्लेक्स के कोफैसेट्स का पता लगाने में प्राप्त किया जा सकता है। जहां तक निर्माण की बात है, जैसा कि रचनात्मक परिभाषा में देखा गया है, निर्माण सरल परिसर में सिम्प्लेक्स की संख्या और जटिलता के समानुपाती है। यह विशेष रूप से महंगा हो सकता है यदि सरल परिसर घना हो। हालांकि, फ्लैग कॉम्प्लेक्स, रिप्स कॉम्प्लेक्स और विटनेस कॉम्प्लेक्स सहित विशेष सरल कॉम्प्लेक्स के लिए कुछ अनुकूलन। अनुप्रयोग सिम्प्लेक्स ट्री विरल सरल परिसरों में कुशल होते हैं। इस उद्देश्य के लिए, उच्च-आयामी वास्तविक डेटा (अक्सर विरल) पर ध्यान केंद्रित करने वाले कई स्थायी समरूपता एल्गोरिदम इन एल्गोरिदम के भीतर सिम्प्लेक्स ट्री का उपयोग करते हैं। जबकि सिम्प्लेक्स ट्री घटना मैट्रिक्स के रूप में कुशल नहीं हैं, उनकी सिम्प्लेक्स-आधारित संरचना उन्हें निरंतर समरूपता एल्गोरिदम के भीतर सरल जटिल भंडारण के लिए उपयोगी कुशल होने की अनुमति देती है। संदर्भ वृक्ष (डेटा संरचना) सरल समुच्चय