फ्यूज़न ट्री

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

फ्रेडमैन और विलार्ड के मूल 1990 पेपर के उपरांत से कई प्रगति हुई है। 1999 में यह दर्शाया गया कि गणना के एक प्रारूप के तहत फ़्यूज़न ट्री को कैसे कार्यान्वित किया जाए जिसमें एल्गोरिदम के सभी अंतर्निहित संचालन AC⁰ से संबंधित हों, सर्किट जटिलता का एक प्रारूप जो जोड़ और बिटवाइज़ बूलियन संचालन की अनुमति देता है परंतु मूल फ़्यूज़न ट्री एल्गोरिदम में उपयोग किए जाने वाले गुणन संचालन की अनुमति नहीं देता है। हैश तालिकाओं का उपयोग करके फ़्यूज़न ट्री का एक गतिशील संस्करण 1996 में प्रस्तावित किया गया था जो मूल संरचना के O(log_w n) रनटाइम के अपेक्षानुसार समानता रखता था। घातीय ट्री का उपयोग करने वाला एक और गतिशील संस्करण 2007 में प्रस्तावित किया गया था जो प्रत्येक आपरेशन के लिए O(log_w n + log log n) के खराब तरह का रनटाइम प्रदान करता है। अंतिम रूप में, दर्शाया गया कि गतिशील फ्यूजन ट्री संज्ञानात्मक ढंग से प्रत्येक आपरेशन को O(log_w n)न्यूनतम समय में कर सकता है।

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

यह कैसे कार्य करता है

फ्यूजन ट्री मूल रूप से w^1/5 शाखा कारक वाली b-ट्री होती है, जिससे इसकी ऊचाई O(log_w n) होती है। अद्यतन और पूछताछ के लिए वांछित रनटाइम प्राप्त करने के लिए, फ्यूजन ट्री को एक बार में w^1/5 कुंजीयों को खोजने की क्षमता होनी चाहिए। इसका कारण है कि कुंजीयों को "रेखाचित्रों" करके ऐसे संपीड़ित किया जाता है कि एक मशीन सभी शब्द में समायोजित हो सकें, जिससे पुनर्मिलन संघों को समानांतर में करने में सक्षमता होती है। इसलिए, रेखाचित्रोंिंग, समानांतर तुलना और सबसे महत्वपूर्ण बिट सूचक स्थानक के आधार पर की जाने वाली गणनाओं का एक श्रृंखला, उचित समाधान तक पहुंचने में सहायता करती है।

रेखाचित्र

रेखाचित्र वह विधि होती है जिसके द्वारा प्रत्येक w-बिट कुंजी एक नोड पर युक्त k कुंजियाँ केवल k − 1 बिट्स में संपीड़ित होती हैं।. प्रत्येक कुंजी x को w ऊंचाई के पूर्ण बाइनरी ट्री में एक पथ के रूप में सोचा जा सकता है जो x जड़ से प्रारंभ होकर पत्ती पर समाप्त होता है। यह पथ सामान्यतः इस प्रकार प्रसंस्करण किया जा सकता है कि, सभी बिट स्कैन किए जाने तक, iवें बिट 0 है तो वाम बच्चे की खोज की जाएगी, और iवें बिट 1 है तो दायीं बच्चे की खोज की जाएगी। दो पथों को पृथक करने के लिए, उनके शाखा बिंदु को देखना पर्याप्त है।क्योंकि अधिकतम k कुंजियाँ होती हैं, इसलिए k-1 से अधिक शाखा बिंदु नहीं होंगे, जिसका अर्थ है कि किसी कुंजी की पहचान करने के लिए k-1 बिट्स से अधिक की आवश्यकता नहीं है। और इसलिए, किसी भी रेखाचित्रों में k-1 बिट्स से अधिक नहीं होगा।

रेखाचित्रों फलन का एक महत्वपूर्ण गुण यह है कि यह कुंजियों के क्रम को संरक्षित करता है। वह है, sketch(x) < sketch(y) किन्हीं दो कुंजियों के लिए x < y. तो, चाबियों की पूरी श्रृंखला के लिए, रेखाचित्रों(x₀)<sketch(x₁)<...<sketch(x_k-1) क्योंकि यदि बाइनरी ट्री जैसे पथ का अनुसरण किया जाता है तो नोड्स को इस तरह से ऑर्डर किया जाएगा कि x₀<x₁<...<x_k-1.

रेखाचित्रों फलन की एक महत्वपूर्ण गुणधर्म है कि यह कुंजीयों का क्रमबद्धता को संरक्षित रखता है। अर्थात, किसी भी दो कुंजीयों x < y के लिए sketch(x) < sketch(y) होगा। इसलिए, पूरे कुंजी दायरे के लिए, sketch(x0) < sketch(x1) < ... < sketch(xk-1) होगा, क्योंकि यदि बाइनरी ट्री के समान पथ का पालन किया जाता है, तो नोड ऐसी व्यवस्था में क्रमबद्ध x0 < x1 < ... < xk-1 होंगे।

रेखाचित्रों का अनुमान लगाना

यदि रेखाचित्रों बिटों की स्थानों को b1 < b2 < ··· < br माना जाता है, तो कुंजी xw-1···x1x0 का रेखाचित्रों r-बिट पूर्णांक होता है।

$x_{b_{r}}x_{b_{r-1}}\cdots x_{b_{1}}$.

केवल सी प्रोग्रामिंग भाषा के जैसे मानक शब्द आपरेशन का उपयोग करके, एक कुंजी का पूर्ण रेखाचित्रों सीधे समय में निर्धारित करना कठिन होता है। इसके अतिरिक्त, रेखाचित्रों बिट्स को बिटवाइज़ AND और गुणाकार का उपयोग करके, अधिकतम r⁴ आकार के रेंज में पैक किया जा सकता है, जिसे अनुमानित रेखाचित्रों कहा जाता है, जिसमें सभी महत्वपूर्ण बिट होते हैं परंतु इसके साथ कुछ अतिरिक्त खराब बिट भी होते हैं जो एक पूर्वानुमानित पैटर्न में विस्तृत होते हैं। बिटवाइज़ AND आपरेशन गैर-रेखाचित्रों बिट्स को कुंजी से हटाने के लिए मास्क के रूप में कार्य करता है, जबकि गुणाकार रेखाचित्रों बिट्स को एक छोटी सीमा में स्थानांतरित करता है। "पूर्ण" रेखाचित्रों की तरह, अनुमानित रेखाचित्रों भी कुंजीयों का क्रमबद्धता संरक्षित करता है और इसका अर्थ है कि sketch(x0) < sketch(x1) < ... < sketch(xk-1) होता है।

सही गुणन स्थिरांक निर्धारित करने के लिए कुछ पूर्वप्रक्रिया की आवश्यकता होती है। जहा स्थान b_i में प्रत्येक रेखाचित्रों बिट में b_i + m_i m = से गुणा करके $\textstyle \sum _{i=1}^{r}$ 2^{m_i. स्थानांतरित हो जायेंगे वहा अनुमानित रेखाचित्रों को कार्यान्वित करने के लिए, निम्नलिखित तीन गुण होने चाहिए:}

1. b_i + m_j सभी जोड़ियों (i, j) के लिए पृथक-पृथक होते हैं। इससे यह सुनिश्चित हो जाएगा कि रेखाचित्रों बिट्स गुणन द्वारा दूषित नहीं होता हैं।
2. b_i + m_i i का सख्ती से बढ़ता हुआ फलन है। अर्थात्, रेखाचित्रों बिट्स का क्रम x'.m में भी संरक्षित रहता है।
3. (b_r + m_r) - (b₁ + m₁) ≤ r⁴. अर्थात्, रेखाचित्रों बिट्स को अधिकतम r⁴ आकार की श्रेणी में पैक किया जाता है, जहां r ≤ O(w^1/5).होता हैं।

एक आगमनात्मक तर्क दिखाता है कि कैसे m_i निर्माण किया जा सकता है. m₁ = w − b₁. मान लीजिए कि 1 < t ≤ r और वह m₁, m₂... m_t-1 पहले ही चुना जा चुका है. पुनः सबसे छोटा पूर्णांक m_t चुनें इस प्रकार कि दोनों गुण (1) और (2) संतुष्ट हैं। संपत्ति (1) के लिए m_t ≠ b_i − b_j + m_l सभी 1 ≤ i, j ≤ r और 1 ≤ l ≤ t-1 के लिए आवश्यक है । इस प्रकार, tr² ≤ r³ से न्यूनतम हैं मूल्य जो m_t बचना चाहिए. क्योंकी m_t न्यूनतम (b_t + m_t) ≤ (b_t-1 + m_t-1) + r³. होना चाहिए, इसका तात्पर्य विशेषता (3) से है।

इस प्रकार अनुमानित रेखाचित्र की गणना इस प्रकार की जाती है:

1. रेखाचित्रों बिट्स को छोड़कर बाकी सभी को x और$\sum _{i=0}^{r-1}2^{b_{i}}$ के मध्य बिटवाइज़ से मास्क करना चाहिए .।
2. ऊपर की गणना के अनुसार कुंजी को पूर्व निर्धारित स्थिरांक m से गुणा करें। इस ऑपरेशन के लिए वास्तव में दो मशीनी शब्दों की आवश्यकता होती है, परंतु यह अभी भी निरंतर समय में किया जा सकता है।
3. स्थानांतरित रेखाचित्रों बिट्स को छोड़कर सभी को मास्क करें। ये अब अधिकतम r⁴<w^4/5 बिट्स.के सन्निहित ब्लॉक में समाहित होते हैं।

समानांतर तुलना

रेखाचित्रोंिंग द्वारा प्राप्त की जाने वाली संक्षिप्ति का उद्देश्य है कि सभी कुंजीयों को एक w-बिट शब्द में संग्रहीत किया जा सके। नोड के रेखाचित्रों को बिट स्ट्रिंग कहा जाता है।

1sketch(x₁)1sketch(x₂)...1sketch(x_k)

यहाँ, सभी रेखाचित्रों शब्दों को एक स्ट्रिंग में जोड़ा जाता है जिसमें प्रत्येक शब्द के पहले एक सेट बिट प्रविष्ट किया जाता है। हम मान सकते हैं कि रेखाचित्रों फलन बिल्कुल b ≤ r⁴ बिट्स का उपयोग करती है। तब प्रत्येक ब्लॉक में 1 + b ≤ w^4/5 बिट्स का उपयोग होता है, और क्योंकि k ≤ w^1/5 होता है, नोड रेखाचित्रों में कुल बिट्स की संख्या w से अधिकतम होती है।

एक संक्षिप्त नोटेशनल एक तरफ: एक बिट स्ट्रिंग एस और गैर-नकारात्मक पूर्णांक m के लिए, चलो s^m स्ट्रिंग s के स्वयं के साथ m बार संयोजन को दर्शाता है। यदि t एक बिट स्ट्रिंग st भी है, तो t से s के संयोजन को दर्शाता है।

नोड रेखाचित्रों द्वारा कुंजीयों की खोज योग्य बिट य के लिए संभव बनाता है।मान लीजिए z = (0y)^k लें, जिसे स्थानिक समय में गणित (y को निर्धारित मान ( (0^b1)^k) से गुणा करें) करके बनाया जा सकता है, क्योंकी यह नोड रेखाचित्रों की तरह लंबा हो और नोड रेखाचित्रों में प्रत्येक शब्द क्वेरी इंटीजर y के साथ एक कार्य में तुलना की जा सके, जो शब्द-स्तर समानांतरिज़म का प्रदर्शन करता है। यदि y 5 बिट लंबा होता है, तो यह 000001....000001 से गुणा करके sketch(y)^k मिलेगा। sketch(x_i) और 0y के मध्य अंतर के परिणामस्वरूप प्रत्येक ब्लॉक के प्रमुख बिट को 1 होना चाहिए, जब केवल sketch(y) ≤ sketch(x_i) होता है। इस प्रकार, हम निम्नतम सूचकांक i की गणना कर सकते हैं जिसके लिएsketch(x_i) ≥ y रहता है, इस प्रकार हैं:

1. नोड रेखाचित्रों से z न्यनतम करें।
2. अंतर और स्थिरांक (10^b)^k के मध्य बिटवाइज़ AND लें। इससे प्रत्येक ब्लॉक के प्रमुख बिट को छोड़कर सभी बिट्स हट जाएगें।
3. क्वेरी रेखाचित्रों से छोटे रेखाचित्रों वाले तत्वों से क्वेरी रेखाचित्रों से बड़े तत्वों में संक्रमण के सटीक सूचकांक की पहचान करने के लिए, परिणाम का सबसे महत्वपूर्ण बिट ढूंढें।
4. इस तथ्य का उपयोग करके रेखाचित्रों की रैंक i की गणना करें कि i-वें ब्लॉक के अग्रणी बिट में सूचकांक i(b+1) होता है।

डेरेखाचित्रोंिंग

एक मनमानी क्वेरी q के लिए, समानांतर तुलना सूचकांक i की गणना इस प्रकार करती है

sketch(x_i-1) ≤ sketch(q) ≤ sketch(x_i)

दुर्भाग्य से, यह q का ठीक पूर्वपद या उत्तरकर्ता नहीं देता है, क्योंकि सभी मानों के रेखाचित्रों के स्थान की स्थिति q के रेखाचित्रों के स्थान के समान नहीं हो सकती है। सत्य यह है कि सभी कुंजीयों के मध्य से या तो x_i-1 या x_i q के साथ सबसे लंबा सामान्य प्राथमिकता है। यह इसलिए है क्योंकि किसी भी कुंजी y के साथ जिसका q के साथ अधिक सामान्य प्राथमिकता होगी, उसमे भी q के साथ अधिक रेखाचित्रों बिट्स साझा होंगे, और इस प्रकार sketchy) , sketch(q) ,sketch(x_j) से निकटता में होगा।

दो w-बिट पूर्णांक a और b के मध्य लंबाई सबसे लंबे सामान्य उपसर्ग की गणना निरंतर समय में a और b के मध्य बिटवाइज XOR के सबसे महत्वपूर्ण बिट को ढूंढकर की जा सकती है। इसके उपरांत इसका उपयोग सबसे लंबे सामान्य उपसर्ग को छोड़कर सभी को छिपाने के लिए किया जा सकता है।

ध्यान दें कि p केवल q को कुंजीयों के सेट से पृथक करने की स्थान की सटीकता निर्धारित करता है। यदि q का अगला बिट 0 है, तो q का उत्तरकर्ता p1 उपट्री में समाहित है, और यदि q का अगला बिट 1 है, तो q का पूर्वपद p0 उपट्री में समाहित होता है। इससे q के सटीक स्थान की निर्धारण के लिए निम्नलिखित एल्गोरिदम सुझाए गए हैं:

1. ऐसमानांतर तुलना का उपयोग करके sketch(x_i-1) ≤ sketch(q) ≤ sketch(x_i).के रूप में सूचकांक i की गणना करते हैं।
2. q और इनमें से किसी भी एक (x_i-1 या x_i) की सबसे लंबी सामान्य प्राथमिकता p की गणना करते हैं ।
3. l-1 को सबसे लंबी सामान्य प्राथमिकता p की लंबाई मानें।
   1. यदि q का l-वां बिट 0 है, तो मान लीजिए e = p10^w-l. है समानांतर तुलना का उपयोग करके sketch(e) के उत्तरकर्ता की करे। यह q का वास्तविक पूर्ववर्ती है।
   2. यदि q का l-वाँ बिट 1 है, तो मान लीजिए e = p01^w-l है.समानांतर तुलना का उपयोग करके sketch(e) के पूर्ववर्ती की खोज करे। यह q का वास्तविक उत्तरकर्ता है।
4. एक बार जब q का पूर्वपद या उत्तरकर्ता मिल जाए, तो कुंजीयों के सेट में q का सटीक स्थान निर्धारित हो जाता है।

फ्यूजन हैशिंग

.

फ्यूजन ट्रीज का हैश तालिकाओं के एक अनुप्रयोग को विल्लार्ड द्वारा दिया गया था, जो एक डेटा संरचना का वर्णन करते हैं जो हैश चेनिंग के साथ एक बाह्य स्तर हैश तालिका को जोड़ती है। हैश चेनिंग में, एक स्थिर भार संकेतक के साथ एक हैश तालिका में, एक चेन का औसत आकार स्थिर होता है, परंतु इसके अलावा उच्च संभावना के साथ सभी चेनों का आकार O(log n / log log n), होता है, यहाँ n हैश किए गए आइटमों की संख्या है। यह चेन का आकार इतना छोटा होता है कि एक फ्यूजन ट्री इसके अंदर खोज और अद्यतन को स्थायी समय में संभाल सकती है। इस प्रकार, डेटा संरचना में सभी कार्यों का समय संभावनानुसार स्थिर होता है। और अधिक सटीकता से कहें तो, इस डेटा संरचना के साथ, प्रत्येक इंवर्स अर्ध-बहुपद समय संभावना p(n) = exp((log n)^O(1)) के लिए, एक स्थिरC ऐसा होता है जिससे यह संभावना होती है कि किसी भी कार्य का समय C से अधिक होने की संभावना n पर न्यूनतम से न्यूनतम p(n) होती है।

संगणनात्मक प्रारूप और आवश्यक धारणाएँ

फ्यूजन ट्री एल्गोरिदम के लिए कंप्यूटेशनल प्रारूप एक वर्ड आरएएम है जिसमें एक विशेष निर्देश सेट होता है, जिसमें अंकगणितीय निर्देश - जोड़, घटाव, गुणाकार निर्देश (सभी मॉड्यूलो 2^w में किए जाते हैं) और बूलियन निर्देश - बिटवाइज़ AND, NOT आदि सम्मिलित हैं। इसमें डबल-प्रेसिजन गुणाकार निर्देश भी सम्मिलित है। यह प्रमाणित किया गया हैअंतिम निर्देश को हटाने से O(n log n) से तीव्रता से क्रमबद्ध करना असंभव होता है, जब तक इसे लगभग 2^w शब्दों के मेमोरी स्थान का उपयोग करने की अनुमति नहीं है , या इसके स्थान पर अन्य निर्देशों को सम्मिलित किया जाता हैं।

बाहरी संबंध

• MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003)
• MIT CS 6.897: Advanced Data Structures: Lecture 5, More fusion trees; self-organizing data structures, move-to-front, static optimality, Prof. Erik Demaine (Spring 2003)
• MIT CS 6.851: Advanced Data Structures: Lecture 13, Fusion Tree notes, Prof. Erik Demaine (Spring 2007)
• MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof. Erik Demaine (Spring 2012)