फ्यूज़न ट्री

संगणक विज्ञान में, फ्यूजन ट्री एक प्रकार की ट्री डेटा संरचना है जो एक विस्तृत यूनिवर्स पर w-बिट पूर्णांकों पर एक सहयोगी संख्या को लागू करती है, जहां प्रत्येक इनपुट पूर्णांक का आकार 2w से न्यूनतम होता है और अवांछित होता है. n की-मान तथा-मान जोड़ी के संग्रह पर आपरेशन करने पर, यह O(n) अंतरिक्ष का उपयोग करती है और खोजों को O(log_w n) समय में पूरा करती है, जो पारंपरिक आपस्तित्व वाले स्व-संतुलन द्विआधारी खोज वृक्ष से असंतुलित होता है, और w के बड़े मानों के लिए वैन m्डे बोस ट्री से भी बेहतर होता है. यह तेज़ी इसलिए प्राप्त करता है क्योंकि इसमें मशीन शब्द पर कुछ स्थायी समय आपरेशन का उपयोग किया जा सकता है. फ्यूजन ट्री की खोज में 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₀)<स्केच(x₁)<...<स्केच(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}}$.

केवल मानक शब्द संचालन, जैसे कि , के साथ, निरंतर समय में किसी कुंजी के सही स्केच की सीधे गणना करना मुश्किल है। इसके अतिरिक्त, स्केच बिट्स को अधिकतम r आकार की श्रेणी में पैक किया जा सकता है, बिटवाइज़ AND और गुणन का उपयोग करते हुए, अनुमानित स्केच कहा जाता है, जिसमें सभी महत्वपूर्ण बिट्स होते हैं परंतु कुछ अतिरिक्त बेकार बिट्स भी एक पूर्वानुमानित पैटर्न में विस्तृत होते हैं। बिटवाइज़ AND ऑपरेशन इन सभी गैर-स्केच बिट्स को कुंजी से हटाने के लिए एक मास्क के रूप में कार्य करता है, जबकि गुणन स्केच बिट्स को एक छोटी सीमा में स्थानांतरित करता है। पूर्ण स्केच की तरह, अनुमानित स्केच भी कुंजियों के क्रम को सुरक्षित रखता है और इसका मतलब है कि स्केच(x₀)<स्केच(x₁)<...<स्केच(x_k-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³मूल्य जो म_t बचना चाहिए. चूंकि m_t न्यूनतम होना चुना गया है, (b_t + m_t) ≤ (b_t-1 + m_t-1) + r³. इसका तात्पर्य संपत्ति (3) से है।

एक आनुवंशिक तर्क दिखाता है कि कैसे m_i का निर्माण किया जा सकता है। तो m1 = w − b1 चुनें। मान लीजिए कि 1 < t ≤ r है और m1, m2... mt-1 पहले से ही चुन लिए गए हैं। पुनः ऐसा सबसे छोटा पूर्णांक mt चुनें, जिसके लिए प्रोपर्टी (1) और (2) दोनों संतुष्ट होती हैं। प्रोपर्टी (1) यह मांगती है कि mt ≠ bi − bj + ml हर 1 ≤ i, j ≤ r और 1 ≤ l ≤ t-1 के लिए। इसलिए, mt को एक कम से कम r3 मानों को बचना चाहिए। क्योंकि mt को न्यूनतम चुना गया है, (bt + mt) ≤ (bt-1 + mt-1) + r3 होता है। इससे प्रोपर्टी (2) प्राप्त होती है।

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

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

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

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

1sketch(एक्स₁)1sketch(एक्स₂)...1sketch(एक्स_k)

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

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

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

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

डेस्केचिंग

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

sketch(एक्स_i-1) ≤ sketch(क्यू) ≤ sketch(एक्स_i)

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

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

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

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

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

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

न्यूनतम्प्यूटेशनल मॉडल और आवश्यक धारणाएँ

फ़्यूज़न ट्री एल्गोरिदम के लिए न्यूनतम्प्यूटेशनल मॉडल एक शब्द राम है जिसमें एक विशिष्ट निर्देश सेट होता है, जिसमें अंकगणितीय निर्देश शामिल होते हैं - जोड़, घटाव और गुणा (सभी निष्पादित) सापेक्ष 2^w) और बूलियन ऑपरेशन - बिटवाइज और, नहीं आदि। एक डबल-सटीक गुणन निर्देश भी शामिल है। यह दर्शाया गया है उपरांत वाले निर्देश को हटाने से तेजी से सॉर्ट करना असंभव हो जाता है 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)