फ्यूज़न ट्री: Difference between revisions

Revision as of 10:34, 6 July 2023

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

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

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

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

फ्यूजन ट्री मूल रूप से $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. स्थानांतरित हो जायेंगे वहा अनुमानित रेखाचित्रों को कार्यान्वित करने के लिए, निम्नलिखित तीन गुण होने चाहिए:}

b_i + m_j सभी जोड़ियों (i, j) के लिए पृथक-पृथक होते हैं। इससे यह सुनिश्चित हो जाएगा कि रेखाचित्रों बिट्स गुणन द्वारा दूषित नहीं हैं।
b_i + m_i i का सख्ती से बढ़ता हुआ फलन है। अर्थात्, रेखाचित्रों बिट्स का क्रम x'.m में भी संरक्षित रहता है।
(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) से है।

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

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

नोड रेखाचित्रों से z कम करें।
अंतर और स्थिरांक (10^b)^k के मध्य बिटवाइज़ AND लें। इससे प्रत्येक ब्लॉक के प्रमुख बिट को छोड़कर सभी बिट्स हट जाएगें।
क्वेरी रेखाचित्रों से छोटे रेखाचित्रों वाले तत्वों से क्वेरी रेखाचित्रों से बड़े तत्वों में संक्रमण के सटीक सूचकांक की पहचान करने के लिए, परिणाम का सबसे महत्वपूर्ण बिट ढूंढें।
इस तथ्य का उपयोग करके रेखाचित्रों की रैंक 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 के सटीक स्थान की निर्धारण के लिए निम्नलिखित एल्गोरिदम सुझाए गए हैं:

ऐसमानांतर तुलना का उपयोग करके sketch(x_i-1) ≤ sketch(q) ≤ sketch(x_i).के रूप में सूचकांक i की गणना करते हैं।
q और इनमें से किसी भी एक (x_i-1 या x_i) की सबसे लंबी सामान्य प्राथमिकता p की गणना करते हैं ।
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 का वास्तविक उत्तरकर्ता है।
एक बार जब q का पूर्वपद या उत्तरकर्ता मिल जाए, तो कुंजीयों के सेट में q का सटीक स्थान निर्धारित हो जाता है।

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

.

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

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

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

संदर्भ

↑ Fredman, M. L.; Willard, D. E. (1990), "BLASTING Through the Information Theoretic Barrier with FUSION TREES", Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC '90), New York, NY, USA: ACM, pp. 1–7, doi:10.1145/100216.100217, ISBN 0-89791-361-2, S2CID 16367160.
↑ ^2.0 ^2.1 Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), "Fusion trees can be implemented with $AC 0$ instructions only", Theoretical Computer Science, 215 (1–2): 337–344, doi:10.1016/S0304-3975(98)00172-8, MR 1678804.
↑ Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous", Fourth Annual European Symposium on Algorithms (ESA '96), Barcelona, Spain, September 25–27, 1996, Lecture Notes in Computer Science, vol. 1136, Berlin: Springer-Verlag, pp. 121–137, doi:10.1007/3-540-61680-2_51, MR 1469229.
↑ Andersson, Arne; Thorup, Mikkel (2007), "Dynamic ordered sets with exponential search trees", Journal of the ACM, 54 (3): A13, arXiv:cs/0210006, doi:10.1145/1236457.1236460, MR 2314255, S2CID 8175703.
↑ Patrascu, Mihai; Thorup, Mikkel (2014). "इष्टतम रैंक, चयन और पूर्ववर्ती खोज के साथ गतिशील पूर्णांक सेट". 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014: 166-175. doi:10.1109/FOCS.2014.26.
↑ Willard, Dan E. (2000), "Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree", SIAM Journal on Computing, 29 (3): 1030–1049, doi:10.1137/S0097539797322425, MR 1740562.
↑ Ben-Amram, Amir M.; Galil, Zvi (1997), "When Can We Sort in o(n log n) Time?", Journal of Computer and System Sciences, 54 (2): 345–370, doi:10.1006/jcss.1997.1474.

बाहरी संबंध

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)

[1] Fredman, M. L.; Willard, D. E. (1990), "BLASTING Through the Information Theoretic Barrier with FUSION TREES", Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC '90), New York, NY, USA: ACM, pp. 1–7, doi:10.1145/100216.100217, ISBN 0-89791-361-2, S2CID 16367160.

[AMT1999-2] 2.0 ^2.1 Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), "Fusion trees can be implemented with $AC 0$ instructions only", Theoretical Computer Science, 215 (1–2): 337–344, doi:10.1016/S0304-3975(98)00172-8, MR 1678804.

[3] Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous", Fourth Annual European Symposium on Algorithms (ESA '96), Barcelona, Spain, September 25–27, 1996, Lecture Notes in Computer Science, vol. 1136, Berlin: Springer-Verlag, pp. 121–137, doi:10.1007/3-540-61680-2_51, MR 1469229.

[4] Andersson, Arne; Thorup, Mikkel (2007), "Dynamic ordered sets with exponential search trees", Journal of the ACM, 54 (3): A13, arXiv:cs/0210006, doi:10.1145/1236457.1236460, MR 2314255, S2CID 8175703.

[5] Patrascu, Mihai; Thorup, Mikkel (2014). "इष्टतम रैंक, चयन और पूर्ववर्ती खोज के साथ गतिशील पूर्णांक सेट". 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014: 166-175. doi:10.1109/FOCS.2014.26.

[6] Willard, Dan E. (2000), "Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree", SIAM Journal on Computing, 29 (3): 1030–1049, doi:10.1137/S0097539797322425, MR 1740562.

[7] Ben-Amram, Amir M.; Galil, Zvi (1997), "When Can We Sort in o(n log n) Time?", Journal of Computer and System Sciences, 54 (2): 345–370, doi:10.1006/jcss.1997.1474.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
-[[कंप्यूटर विज्ञान|संगणक विज्ञान]] में, '''फ्यूजन ट्री''' एक प्रकार की ट्री डेटा संरचना है जो एक विस्तृत यूनिवर्स पर w-बिट पूर्णांकों पर एक सहयोगी संख्या को लागू करती है, जहां प्रत्येक इनपुट पूर्णांक का आकार 2w से न्यूनतम होता है और अवांछित होता है. n की-मान तथा-मान जोड़ी के संग्रह पर आपरेशन करने पर, यह {{math|''O''(''n'')}}  अंतरिक्ष का उपयोग करती है और खोजों को {{math|''O''(log<sub>''w''</sub> ''n'')}} समय में पूरा करती है, जो पारंपरिक आपस्तित्व वाले [[स्व-संतुलन द्विआधारी खोज वृक्ष]]  से असंतुलित होता है, और {{mvar|w}} के बड़े मानों के लिए  [[वैन एम्डे बोस कदम|वैन m्डे बोस]] ट्री से भी बेहतर होता है. यह तेज़ी इसलिए प्राप्त करता है क्योंकि इसमें [[मशीन शब्द]] पर कुछ स्थायी समय आपरेशन का उपयोग किया जा सकता है. फ्यूजन ट्री की खोज में {{math|''O''(log<sub>''w''</sub> ''n'')}} समय के कारण, यह 1990 में [[माइकल फ्रेडमैन]] और [[डैन विलार्ड]] द्वारा आविष्कृत की गई थी।<ref>{{citation
+[[कंप्यूटर विज्ञान|संगणक विज्ञान]] में, '''फ्यूजन ट्री''' एक प्रकार की ट्री डेटा संरचना है जो एक विस्तृत यूनिवर्स पर w-बिट पूर्णांकों पर एक सहयोगी संख्या को लागू करती है, जहां प्रत्येक इनपुट पूर्णांक का आकार 2w से न्यूनतम होता है और अवांछित होता है. n की-मान तथा-मान जोड़ी के संग्रह पर आपरेशन करने पर, यह {{math|''O''(''n'')}}  अंतरिक्ष का उपयोग करती है और खोजों को {{math|''O''(log<sub>''w''</sub> ''n'')}} समय में पूरा करती है, जो पारंपरिक आपस्तित्व वाले [[स्व-संतुलन द्विआधारी खोज वृक्ष]]  से असंतुलित होता है, और {{mvar|w}} के बड़े मानों के लिए  [[वैन एम्डे बोस कदम|वैन m्डे बोस]] ट्री से भी बेहतर होता है. यह तीव्रता इसलिए प्राप्त करता है क्योंकि इसमें [[मशीन शब्द]] पर कुछ स्थायी समय आपरेशन का उपयोग किया जा सकता है. फ्यूजन ट्री की खोज में {{math|''O''(log<sub>''w''</sub> ''n'')}} समय के कारण, यह 1990 में [[माइकल फ्रेडमैन]] और [[डैन विलार्ड]] द्वारा आविष्कृत की गई थी।<ref>{{citation
   | last1 = Fredman | first1 = M. L. | author1-link = Michael Fredman
   | last2 = Willard | first2 = D. E. | author2-link = Dan Willard
@@ Line 26: / Line 26: @@
   | volume = 215
   | year = 1999| doi-access = free
-  }}.</ref> 1999 में यह दर्शाया गया कि गणना के एक मॉडल के तहत फ़्यूज़न पेड़ों को कैसे कार्यान्वित किया जाए जिसमें एल्गोरिदम के सभी अंतर्निहित संचालन AC<sup>0</sup> से संबंधित हों, [[सर्किट जटिलता]] का एक मॉडल जो जोड़ और बिटवाइज़ बूलियन संचालन की अनुमति देता है परंतु मूल फ़्यूज़न ट्री एल्गोरिदम में उपयोग किए जाने वाले गुणन संचालन की अनुमति नहीं देता है। हैश तालिकाओं का उपयोग करके फ़्यूज़न पेड़ों का एक गतिशील संस्करण 1996 में प्रस्तावित किया गया था<ref>{{citation
+  }}.</ref> 1999 में यह दर्शाया गया कि गणना के एक प्रारूप के तहत फ़्यूज़न पेड़ों को कैसे कार्यान्वित किया जाए जिसमें एल्गोरिदम के सभी अंतर्निहित संचालन AC<sup>0</sup> से संबंधित हों, [[सर्किट जटिलता]] का एक प्रारूप जो जोड़ और बिटवाइज़ बूलियन संचालन की अनुमति देता है परंतु मूल फ़्यूज़न ट्री एल्गोरिदम में उपयोग किए जाने वाले गुणन संचालन की अनुमति नहीं देता है। हैश तालिकाओं का उपयोग करके फ़्यूज़न पेड़ों का एक गतिशील संस्करण 1996 में प्रस्तावित किया गया था<ref>{{citation
   | last = Raman | first = Rajeev
   | contribution = Priority queues: small, monotone and trans-dichotomous
@@ Line 52: / Line 52: @@
 == यह कैसे कार्य करता है ==
-फ्यूजन ट्री मूल रूप से {{math|''w''<sup>1/5</sup>}} शाखा कारक वाली [[बी-वृक्ष|b-वृक्ष]] होती है, जिससे इसकी ऊचाई {{math|''O''(log<sub>''w''</sub> ''n'')}} होती है। अद्यतन और पूछताछ के लिए वांछित रनटाइम प्राप्त करने के लिए, फ्यूजन ट्री को एक बार में {{math|''w''<sup>1/5</sup>}} कुंजीयों को खोजने की क्षमता होनी चाहिए। इसका कारण है कि कुंजीयों को "स्केच" करके ऐसा संपीड़ित किया जाता है कि सभी एक मशीन शब्द में समायोजित हो सकें, जिससे पुनर्मिलन संघों को पैरालेल में करने में सक्षमता होती है। इसलिए, स्केचिंग, पैरालेल तुलना और सबसे महत्वपूर्ण बिट सूचक स्थानक के आधार पर की जाने वाली गणनाओं का एक श्रृंखला, उचित समाधान तक पहुंचने में सहायता करती है।
+फ्यूजन ट्री मूल रूप से {{math|''w''<sup>1/5</sup>}} शाखा कारक वाली [[बी-वृक्ष|b-वृक्ष]] होती है, जिससे इसकी ऊचाई {{math|''O''(log<sub>''w''</sub> ''n'')}} होती है। अद्यतन और पूछताछ के लिए वांछित रनटाइम प्राप्त करने के लिए, फ्यूजन ट्री को एक बार में {{math|''w''<sup>1/5</sup>}} कुंजीयों को खोजने की क्षमता होनी चाहिए। इसका कारण है कि कुंजीयों को "रेखाचित्रों" करके ऐसा संपीड़ित किया जाता है कि सभी एक मशीन शब्द में समायोजित हो सकें, जिससे पुनर्मिलन संघों को समानांतर में करने में सक्षमता होती है। इसलिए, रेखाचित्रोंिंग, समानांतर तुलना और सबसे महत्वपूर्ण बिट सूचक स्थानक के आधार पर की जाने वाली गणनाओं का एक श्रृंखला, उचित समाधान तक पहुंचने में सहायता करती है।
-===स्केचिंग===
+===रेखाचित्र===
-स्केचिंग वह विधि है जिसके द्वारा प्रत्येक {{mvar|w}}-बिट कुंजी एक नोड पर युक्त {{mvar|k}} कुंजियाँ केवल {{math|''k'' &minus; 1}} बिट्स में संपीड़ित होती हैं।. प्रत्येक कुंजी {{mvar|x}} को {{mvar|w}} ऊंचाई के पूर्ण बाइनरी ट्री में एक पथ के रूप में सोचा जा सकता है जो {{mvar|x}} जड़ से प्रारंभ होकर पत्ती पर समाप्त होता है। यह पथ सामान्यतः इस प्रकार प्रसंस्करण किया जा सकता है कि, सभी बिट स्कैन किए जाने तक, iवें बिट 0 है तो वाम बच्चे की खोज की जाएगी, और iवें बिट 1 है तो दायीं बच्चे की खोज की जाएगी। दो पथों को पृथक करने के लिए, उनके शाखा बिंदु को देखना पर्याप्त है।क्योंकि अधिकतम k कुंजियाँ होती हैं, इसलिए k-1 से अधिक शाखा बिंदु नहीं होंगे, जिसका अर्थ है कि किसी कुंजी की पहचान करने के लिए k-1 बिट्स से अधिक की आवश्यकता नहीं है। और इसलिए, किसी भी स्केच में k-1 बिट्स से अधिक नहीं होगा।
+रेखाचित्र वह विधि है जिसके द्वारा प्रत्येक {{mvar|w}}-बिट कुंजी एक नोड पर युक्त {{mvar|k}} कुंजियाँ केवल {{math|''k'' &minus; 1}} बिट्स में संपीड़ित होती हैं।. प्रत्येक कुंजी {{mvar|x}} को {{mvar|w}} ऊंचाई के पूर्ण बाइनरी ट्री में एक पथ के रूप में सोचा जा सकता है जो {{mvar|x}} जड़ से प्रारंभ होकर पत्ती पर समाप्त होता है। यह पथ सामान्यतः इस प्रकार प्रसंस्करण किया जा सकता है कि, सभी बिट स्कैन किए जाने तक, iवें बिट 0 है तो वाम बच्चे की खोज की जाएगी, और iवें बिट 1 है तो दायीं बच्चे की खोज की जाएगी। दो पथों को पृथक करने के लिए, उनके शाखा बिंदु को देखना पर्याप्त है।क्योंकि अधिकतम k कुंजियाँ होती हैं, इसलिए k-1 से अधिक शाखा बिंदु नहीं होंगे, जिसका अर्थ है कि किसी कुंजी की पहचान करने के लिए k-1 बिट्स से अधिक की आवश्यकता नहीं है। और इसलिए, किसी भी रेखाचित्रों में k-1 बिट्स से अधिक नहीं होगा।
-[[File:FusionTreeSketch.gif|center|स्केच फ़ंक्शन का विज़ुअलाइज़ेशन।]]स्केच फ़ंक्शन का एक महत्वपूर्ण गुण यह है कि यह कुंजियों के क्रम को संरक्षित करता है। वह है, {{math|sketch(''x'') < sketch(''y'')}} किन्हीं दो कुंजियों के लिए {{math|''x'' < ''y''}}. तो, चाबियों की पूरी श्रृंखला के लिए, स्केच(x<sub>0</sub>)<स्केच(x<sub>1</sub>)<...<स्केच(x<sub>k-1</sub>) क्योंकि यदि बाइनरी ट्री जैसे पथ का अनुसरण किया जाता है तो नोड्स को इस तरह से ऑर्डर किया जाएगा कि x<sub>0</sub><x<sub>1</sub><...<x<sub>k-1</sub>.
+[[File:FusionTreeSketch.gif|center|रेखाचित्रों फ़ंक्शन का विज़ुअलाइज़ेशन।]]रेखाचित्रों फ़ंक्शन का एक महत्वपूर्ण गुण यह है कि यह कुंजियों के क्रम को संरक्षित करता है। वह है, {{math|sketch(''x'') < sketch(''y'')}} किन्हीं दो कुंजियों के लिए {{math|''x'' < ''y''}}. तो, चाबियों की पूरी श्रृंखला के लिए, रेखाचित्रों(x<sub>0</sub>)<sketch(x<sub>1</sub>)<...<sketch(x<sub>k-1</sub>) क्योंकि यदि बाइनरी ट्री जैसे पथ का अनुसरण किया जाता है तो नोड्स को इस तरह से ऑर्डर किया जाएगा कि x<sub>0</sub><x<sub>1</sub><...<x<sub>k-1</sub>.
-स्केच फ़ंक्शन की एक महत्वपूर्ण गुणधर्म है कि यह कुंजीयों का क्रमबद्धता को संरक्षित रखता है। अर्थात, किसी भी दो कुंजीयों x < y के लिए sketch(x) < sketch(y) होगा। इसलिए, पूरे कुंजी दायरे के लिए, sketch(x0) < sketch(x1) < ... < sketch(xk-1) होगा, क्योंकि यदि बाइनरी ट्री के समान पथ का पालन किया जाता है, तो नोड ऐसी व्यवस्था में क्रमबद्ध x0 < x1 < ... < xk-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-बिट पूर्णांक होता है।
+यदि रेखाचित्रों बिटों की स्थानों को b1 < b2 < ··· < br माना जाता है, तो कुंजी xw-1···x1x0 का रेखाचित्रों r-बिट पूर्णांक होता है।
 <math>x_{b_r}x_{b_{r-1}}\cdots x_{b_1}</math>.
-केवल मानक शब्द संचालन, जैसे कि , के साथ, निरंतर समय में किसी कुंजी के सही स्केच की सीधे गणना करना मुश्किल है। इसके अतिरिक्त, स्केच बिट्स को अधिकतम r आकार की श्रेणी में पैक किया जा सकता है, बिटवाइज़ AND और गुणन का उपयोग करते हुए, अनुमानित स्केच कहा जाता है, जिसमें सभी महत्वपूर्ण बिट्स होते हैं परंतु कुछ अतिरिक्त बेकार बिट्स भी एक पूर्वानुमानित पैटर्न में विस्तृत होते हैं। बिटवाइज़ AND ऑपरेशन इन सभी गैर-स्केच बिट्स को कुंजी से हटाने के लिए एक मास्क के रूप में कार्य करता है, जबकि गुणन स्केच बिट्स को एक छोटी सीमा में स्थानांतरित करता है। पूर्ण स्केच की तरह, अनुमानित स्केच भी कुंजियों के क्रम को सुरक्षित रखता है और इसका मतलब है कि स्केच(x<sub>0</sub>)<स्केच(x<sub>1</sub>)<...<स्केच(x<sub>k-1</sub>).
+केवल [[सी प्रोग्रामिंग भाषा]] के जैसे मानक शब्द आपरेशन का उपयोग करके, एक कुंजी का पूर्ण रेखाचित्रों सीधे समय में निर्धारित करना कठिन होता है। इसके अतिरिक्त, रेखाचित्रों बिट्स को बिटवाइज़ AND और गुणाकार का उपयोग करके, अधिकतम r<sup>4</sup> आकार के रेंज में पैक किया जा सकता है, जिसे अनुमानित रेखाचित्रों कहा जाता है, जिसमें सभी महत्वपूर्ण बिट होते हैं परंतु इसके साथ कुछ अतिरिक्त बेकार बिट भी होते हैं जो एक पूर्वानुमानित पैटर्न में विस्तृत होते हैं। बिटवाइज़ AND आपरेशन गैर-रेखाचित्रों बिट्स को कुंजी से हटाने के लिए मास्क के रूप में कार्य करता है, जबकि गुणाकार रेखाचित्रों बिट्स को एक छोटी सीमा में स्थानांतरित करता है। "पूर्ण" रेखाचित्रों की तरह, अनुमानित रेखाचित्रों भी कुंजीयों का क्रमबद्धता संरक्षित करता है और इसका अर्थ है कि sketch(x0) < sketch(x1) < ... < sketch(xk-1) होता है।
-केवल [[सी प्रोग्रामिंग भाषा]] के जैसे मानक शब्द आपरेशन का उपयोग करके, एक कुंजी का पूर्ण स्केच सीधे समय में निर्धारित करना कठिन होता है। इसके अतिरिक्त, स्केच बिट्स को बिटवाइज़ AND और गुणाकार का उपयोग करके, अधिकतम r<sup>4</sup> आकार के रेंज में पैक किया जा सकता है, जिसे अनुमानित स्केच कहा जाता है, जिसमें सभी महत्वपूर्ण बिट होते हैं परंतु इसके साथ कुछ अतिरिक्त बेकार बिट भी होते हैं जो एक पूर्वानुमानित पैटर्न में विस्तृत होते हैं। बिटवाइज़ AND आपरेशन गैर-स्केच बिट्स को कुंजी से हटाने के लिए मास्क के रूप में कार्य करता है, जबकि गुणाकार स्केच बिट्स को एक छोटी सीमा में स्थानांतरित करता है। "पूर्ण" स्केच की तरह, अनुमानित स्केच भी कुंजीयों का क्रमबद्धता संरक्षित करता है और इसका अर्थ है कि sketch(x0) < sketch(x1) < ... < sketch(xk-1) होता है।
+सही गुणन स्थिरांक निर्धारित करने के लिए कुछ पूर्वप्रक्रिया की आवश्यकता होती है। जहा स्थान b<sub>''i''</sub> में प्रत्येक रेखाचित्रों बिट में b<sub>''i''</sub> + m<sub>''i''</sub> m = से गुणा करके <math>\textstyle\sum_{i=1}^r</math> 2<sup>m<sub>''i.''</sub>  स्थानांतरित  हो जायेंगे वहा अनुमानित रेखाचित्रों को कार्यान्वित करने के लिए, निम्नलिखित तीन गुण होने चाहिए:
-सही गुणन स्थिरांक निर्धारित करने के लिए कुछ पूर्वप्रक्रिया की आवश्यकता होती है। जहा स्थान b<sub>''i''</sub> में प्रत्येक स्केच बिट में b<sub>''i''</sub> + m<sub>''i''</sub> m = से गुणा करके <math>\textstyle\sum_{i=1}^r</math> 2<sup>m<sub>''i.''</sub>  स्थानांतरित  हो जायेंगे वहा अनुमानित स्केच को कार्यान्वित करने के लिए, निम्नलिखित तीन गुण होने चाहिए:
+# b<sub>''i''</sub> + m<sub>''j''</sub> सभी जोड़ियों (i, j) के लिए पृथक-पृथक होते हैं। इससे यह सुनिश्चित हो जाएगा कि रेखाचित्रों बिट्स गुणन द्वारा दूषित नहीं हैं।
+# b<sub>''i''</sub> + m<sub>''i''</sub> i का सख्ती से बढ़ता हुआ फलन है। अर्थात्, रेखाचित्रों बिट्स का क्रम x'.m में भी संरक्षित रहता है।
-# b<sub>''i''</sub> + m<sub>''j''</sub> सभी जोड़ियों (i, j) के लिए पृथक-पृथक होते हैं। इससे यह सुनिश्चित हो जाएगा कि स्केच बिट्स गुणन द्वारा दूषित नहीं हैं।
+# (b<sub>''r''</sub> + m<sub>''r''</sub>) - (b<sub>1</sub> + m<sub>1</sub>) ≤ r<sup>4</sup>. अर्थात्, रेखाचित्रों बिट्स को अधिकतम r<sup>4</sup> आकार की श्रेणी में पैक किया जाता है, जहां r ≤ O(w<sup>1/5</sup>).होता हैं।
-# b<sub>''i''</sub> + m<sub>''i''</sub> i का सख्ती से बढ़ता हुआ फलन है। अर्थात्, स्केच बिट्स का क्रम x'.m में भी संरक्षित रहता है।
-# (b<sub>''r''</sub> + m<sub>''r''</sub>) - (b<sub>1</sub> + m<sub>1</sub>) ≤ r<sup>4</sup>. अर्थात्, स्केच बिट्स को अधिकतम r<sup>4</sup> आकार की श्रेणी में पैक किया जाता है, जहां r ≤ O(w<sup>1/5</sup>).होता हैं।
 एक आगमनात्मक तर्क दिखाता है कि कैसे m<sub>''i''</sub> निर्माण किया जा सकता है. m<sub>1</sub> = w − b<sub>1</sub>. मान लीजिए कि 1 < t ≤ r और वह m<sub>1</sub>, m<sub>2</sub>... m<sub>''t-1''</sub> पहले ही चुना जा चुका है. पुनः सबसे छोटा पूर्णांक m<sub>''t''</sub> चुनें इस प्रकार कि दोनों गुण (1) और (2) संतुष्ट हैं। संपत्ति (1) के लिए  m<sub>''t''</sub> ≠ b<sub>''i''</sub> − b<sub>''j''</sub> + m<sub>''l''</sub> सभी 1 ≤ i, j ≤ r और 1 ≤ l ≤ t-1 के लिए आवश्यक है । इस प्रकार, tr<sup>2</sup> ≤ r<sup>3</sup> से न्यूनतम हैं मूल्य जो m<sub>''t''</sub> बचना चाहिए. क्योंकी m<sub>''t''</sub> न्यूनतम (b<sub>''t''</sub> + m<sub>''t''</sub>) ≤ (b<sub>''t''-1</sub> + m<sub>''t''-1</sub>) + r<sup>3</sup>. होना चाहिए,  इसका तात्पर्य विशेषता (3) से है।
 इस प्रकार अनुमानित रेखाचित्र की गणना इस प्रकार की जाती है:
-# स्केच बिट्स को छोड़कर बाकी सभी को x और<math>\sum_{i=0}^{r-1} 2^{b_i}</math> के मध्य बिटवाइज़ से मास्क करें .
+# रेखाचित्रों बिट्स को छोड़कर बाकी सभी को x और<math>\sum_{i=0}^{r-1} 2^{b_i}</math> के मध्य बिटवाइज़ से मास्क करें .
 # ऊपर की गणना के अनुसार कुंजी को पूर्व निर्धारित स्थिरांक m से गुणा करें। इस ऑपरेशन के लिए वास्तव में दो मशीनी शब्दों की आवश्यकता होती है, परंतु यह अभी भी निरंतर समय में किया जा सकता है।
-# स्थानांतरित स्केच बिट्स को छोड़कर सभी को मास्क करें। ये अब अधिकतम r<sup>4</sup><w<sup>4/5</sup> बिट्स.के सन्निहित ब्लॉक में समाहित होते हैं
+# स्थानांतरित रेखाचित्रों बिट्स को छोड़कर सभी को मास्क करें। ये अब अधिकतम r<sup>4</sup><w<sup>4/5</sup> बिट्स.के सन्निहित ब्लॉक में समाहित होते हैं
 ===समानांतर तुलना===
-स्केचिंग द्वारा प्राप्त संपीड़न का उद्देश्य सभी कुंजियों को एक डब्ल्यू-बिट शब्द में संग्रहीत करने की अनुमति देना है। किसी नोड का नोड स्केच बिट स्ट्रिंग होने दें
+रेखाचित्रोंिंग द्वारा प्राप्त की जाने वाली संक्षिप्ति का उद्देश्य है कि सभी कुंजीयों को एक w-बिट शब्द में संग्रहीत किया जा सके। नोड के रेखाचित्रों को बिट स्ट्रिंग कहा जाता है।
-:1<code>sketch</code>(एक्स<sub>1</sub>)1<code>sketch</code>(एक्स<sub>2</sub>)...1<code>sketch</code>(एक्स<sub>''k''</sub>)
+:1<code>sketch</code>(x<sub>1</sub>)1<code>sketch</code>(x<sub>2</sub>)...1<code>sketch</code>(x<sub>''k''</sub>)
-यहां, सभी स्केच शब्दों को उनमें से प्रत्येक के लिए एक सेट बिट जोड़कर एक स्ट्रिंग में एक साथ जोड़ा गया है। हम मान सकते हैं कि स्केच फ़ंक्शन बिल्कुल b ≤ r का उपयोग करता है<sup>4</sup>बिट्स. पुनः प्रत्येक ब्लॉक 1 + b ≤ w का उपयोग करता है<sup>4/5</sup>बिट्स, और चूँकि k ≤ w<sup>1/5</sup>, नोड स्केच में बिट्स की कुल संख्या अधिकतम w है।
+यहाँ, सभी रेखाचित्रों शब्दों को एक स्ट्रिंग में जोड़ा जाता है जिसमें प्रत्येक शब्द के पहले एक सेट बिट प्रविष्ट किया जाता है। हम मान सकते हैं कि रेखाचित्रों फ़ंक्शन बिल्कुल b ≤ r<sup>4</sup> बिट्स का उपयोग करती है। तब प्रत्येक ब्लॉक में 1 + b ≤ w<sup>4/5</sup> बिट्स का उपयोग होता है, और क्योंकि k ≤ w<sup>1/5</sup> होता है, नोड रेखाचित्रों में कुल बिट्स की संख्या w से अधिकतम होती है।
-एक संक्षिप्त नोटेशनल एक तरफ: एक बिट स्ट्रिंग एस और गैर-नकारात्मक पूर्णांक m के लिए, चलो एस<sup>m</sup>s के स्वयं के साथ m बार संयोजन को दर्शाता है। यदि t एक बिट स्ट्रिंग st भी है, तो t से s के संयोजन को दर्शाता है।
+एक संक्षिप्त नोटेशनल एक तरफ: एक बिट स्ट्रिंग एस और गैर-नकारात्मक पूर्णांक m के लिए, चलो s<sup>m</sup> स्ट्रिंग s के स्वयं के साथ m बार संयोजन को दर्शाता है। यदि t एक बिट स्ट्रिंग st भी है, तो t से s के संयोजन को दर्शाता है।
-नोड स्केच किसी भी b-बिट पूर्णांक y के लिए कुंजी खोजना संभव बनाता है। मान लीजिए z = (0y)<sup>k</sup>, जिसकी गणना स्थिर समय में की जा सकती है (y को स्थिरांक (0) से गुणा करें)।<sup>ख</sup>1)<sup>k</sup>), इसे नोड स्केच जितना लंबा बनाने के लिए, ताकि नोड स्केच में प्रत्येक शब्द की तुलना एक ऑपरेशन में क्वेरी पूर्णांक y के साथ की जा सके, जो शब्द-स्तरीय समानता का प्रदर्शन करता है। यदि y 5 बिट लंबा होता, तो स्केच(y) प्राप्त करने के लिए इसे 000001....000001 से गुणा किया जाता।<sup>क</sup>. स्केच(x) के bच का अंतर<sub>i</sub>) और 0y के परिणामस्वरूप प्रत्येक ब्लॉक के लिए अग्रणी बिट 1 होता है, यदि और केवल यदि स्केच(y) <math>\leq
+नोड रेखाचित्रों द्वारा कुंजीयों की खोज योग्य बिट य के लिए संभव बनाता है।मान लीजिए z = (0y)<sup>k</sup> लें, जिसे स्थानिक समय में गणित (y को निर्धारित मान ( (0<sup>''b''</sup>1)<sup>''k''</sup>) से गुणा करें) करके बनाया जा सकता है, क्योंकी यह नोड रेखाचित्रों की तरह लंबा हो और नोड रेखाचित्रों में प्रत्येक शब्द क्वेरी इंटीजर y के साथ एक कार्य में तुलना की जा सके, जो शब्द-स्तर समानांतरिज़म का प्रदर्शन करता है। यदि y 5 बिट लंबा होता है, तो यह 000001....000001 से गुणा करके sketch(y)<sup>k</sup> मिलेगा। sketch(x<sub>i</sub>) और 0y के मध्य अंतर के परिणामस्वरूप प्रत्येक ब्लॉक के प्रमुख बिट को 1 होना चाहिए, केवल जब sketch(y) ≤ sketch(x<sub>i</sub>) होता है। इस प्रकार, हम निम्नतम सूचकांक i की गणना कर सकते हैं जिसके लिए<code>sketch</code>(x<sub>''i''</sub>) ≥ y  रहता है, इस प्रकार:
-</math> स्केच(x<sub>i</sub>). इस प्रकार हम सबसे छोटे सूचकांक i की गणना कर सकते हैं <code>sketch</code>(एक्स<sub>''i''</sub>) ≥ y इस प्रकार है:
-# नोड स्केच से z घटाएँ।
+# नोड रेखाचित्रों से z कम करें।
-# अंतर और स्थिरांक का बिटवाइज़ AND लें (10<sup>ख</sup>)<sup>क</sup>. यह प्रत्येक ब्लॉक के अग्रणी बिट को छोड़कर बाकी सब साफ़ कर देता है।
+# अंतर और स्थिरांक  (10<sup>''b''</sup>)<sup>''k''</sup> के मध्य बिटवाइज़ AND लें। इससे प्रत्येक ब्लॉक के प्रमुख बिट को छोड़कर सभी बिट्स हट जाएगें।
-# क्वेरी स्केच से छोटे स्केच वाले तत्वों से क्वेरी स्केच से बड़े तत्वों में संक्रमण के सटीक सूचकांक की पहचान करने के लिए, परिणाम का [[सबसे महत्वपूर्ण बिट]] ढूंढें।
+# क्वेरी रेखाचित्रों से छोटे रेखाचित्रों वाले तत्वों से क्वेरी रेखाचित्रों से बड़े तत्वों में संक्रमण के सटीक सूचकांक की पहचान करने के लिए, परिणाम का [[सबसे महत्वपूर्ण बिट]] ढूंढें।
-# इस तथ्य का उपयोग करके स्केच की रैंक i की गणना करें कि i-वें ब्लॉक के अग्रणी बिट में इंडेक्स i(b+1) है।
+# इस तथ्य का उपयोग करके रेखाचित्रों की रैंक i की गणना करें कि i-वें ब्लॉक के अग्रणी बिट में सूचकांक i(b+1) होता है।
-===डेस्केचिंग===
+===डेरेखाचित्रोंिंग===
 एक मनमानी क्वेरी q के लिए, समानांतर तुलना सूचकांक i की गणना इस प्रकार करती है
-:<code>sketch</code>(एक्स<sub>''i''-1</sub>) ≤ <code>sketch</code>(क्यू) ≤ <code>sketch</code>(एक्स<sub>''i''</sub>)
+:<code>sketch</code>(x<sub>''i''-1</sub>) ≤ <code>sketch</code>(q) ≤ <code>sketch</code>(x<sub>''i''</sub>)
-दुर्भाग्य से, यह q का सटीक पूर्ववर्ती या उत्तराधिकारी नहीं देता है, क्योंकि सभी मानों के रेखाचित्रों के bच q के रेखाचित्र का स्थान सभी वास्तविक मानों में q के स्थान के समान नहीं हो सकता है। जो सच है वह यह है कि, सभी कुंजियों में से, या तो x<sub>''i''-1</sub> या एक्स<sub>''i''</sub> q के साथ सबसे लंबा सामान्य उपसर्ग है। ऐसा इसलिए है क्योंकि q के साथ लंबे सामान्य उपसर्ग वाली किसी भी कुंजी y में q के साथ समान रूप से अधिक स्केच बिट्स होंगे, और इस प्रकार <code>sketch</code>(y) के करीब होगा <code>sketch</code>(क्यू) किसी से भी ज्यादा <code>sketch</code>(एक्स<sub>''j''</sub>).
+दुर्भाग्य से, यह q का ठीक पूर्वपद या उत्तरकर्ता नहीं देता है, क्योंकि सभी मानों के रेखाचित्रों के स्थान की स्थिति q के रेखाचित्रों के स्थान के समान नहीं हो सकती है। सत्य यह है कि सभी कुंजीयों के मध्य से या तो x<sub>i-1</sub> या x<sub>i</sub> q के साथ सबसे लंबा सामान्य प्राथमिकता है। यह इसलिए है क्योंकि किसी भी कुंजी y के साथ जिसका q के साथ अधिक सामान्य प्राथमिकता होगी, उसमे भी q के साथ अधिक रेखाचित्रों बिट्स साझा होंगे, और इस प्रकार <code>sketch</code>y) , <code>sketch</code>(q) ,<code>sketch</code>(x<sub>''j''</sub>) से निकटता में होगा।
-दो डब्ल्यू-बिट पूर्णांक ए और b के bच लंबाई सबसे लंबे सामान्य उपसर्ग की गणना निरंतर समय में ए और b के bच बिटवाइज एक्सओr के सबसे महत्वपूर्ण बिट को ढूंढकर की जा सकती है। इसके उपरांत इसका उपयोग सबसे लंबे सामान्य उपसर्ग को छोड़कर सभी को छिपाने के लिए किया जा सकता है।
+दो w-बिट पूर्णांक a और b के मध्य लंबाई सबसे लंबे सामान्य उपसर्ग की गणना निरंतर समय में a और b के मध्य बिटवाइज XOR के सबसे महत्वपूर्ण बिट को ढूंढकर की जा सकती है। इसके उपरांत इसका उपयोग सबसे लंबे सामान्य उपसर्ग को छोड़कर सभी को छिपाने के लिए किया जा सकता है।
-ध्यान दें कि p सटीक रूप से पहचानता है कि कुंजियों के सेट से q शाखाएँ कहाँ निकलती हैं। यदि q का अगला बिट 0 है, तो q का उत्तराधिकारी p1 सबट्री में समाहित है, और यदि q का अगला बिट 1 है, तो q का पूर्ववर्ती p0 सबट्री में समाहित है। यह q का सटीक स्थान निर्धारित करने के लिए निम्नलिखित एल्गोरिदम का सुझाव देता है:
+ध्यान दें कि p केवल q को कुंजीयों के सेट से पृथक करने की स्थान की सटीकता निर्धारित करता है। यदि q का अगला बिट 0 है, तो q का उत्तरकर्ता p1 उपवृक्ष में समाहित है, और यदि q का अगला बिट 1 है, तो q का पूर्वपद p0 उपवृक्ष में समाहित होता है। इससे q के सटीक स्थान की निर्धारण के लिए निम्नलिखित एल्गोरिदम सुझाए गए हैं:
-# ऐसे सूचकांक को खोजने के लिए समानांतर तुलना का उपयोग करें <code>sketch</code>(एक्स<sub>''i''-1</sub>) ≤ <code>sketch</code>(क्यू) ≤ <code>sketch</code>(एक्स<sub>''i''</sub>).
+# ऐसमानांतर तुलना का उपयोग करके <code>sketch</code>(x<sub>''i''-1</sub>) ≤ <code>sketch</code>(q) ≤ <code>sketch</code>(x<sub>''i''</sub>).के रूप में सूचकांक i की गणना करते हैं।
-# q और x दोनों में से सबसे लंबे सामान्य उपसर्ग p की गणना करें<sub>''i''-1</sub> या एक्स<sub>''i''</sub> (दोनों में से अधिक समय लेते हुए)।
+# q और इनमें से किसी भी एक (x<sub>i-1</sub> या x<sub>i</sub>) की सबसे लंबी सामान्य प्राथमिकता p की गणना करते हैं ।
-# मान लीजिए l-1 सबसे लंबे सामान्य उपसर्ग p की लंबाई है।
+# l-1 को सबसे लंबी सामान्य प्राथमिकता p की लंबाई मानें।
-## यदि q का l-वां बिट 0 है, तो मान लीजिए e = p10 है<sup>w-l</sup>. के उत्तराधिकारी की खोज के लिए समानांतर तुलना का उपयोग करें <code>sketch</code>(इ)। यह q का वास्तविक पूर्ववर्ती है।
+## यदि q का l-वां बिट 0 है, तो मान लीजिए e = p10<sup>w-l</sup>. है समानांतर तुलना का उपयोग करके <code>sketch</code>(e) के उत्तरकर्ता की करे। यह q का वास्तविक पूर्ववर्ती है।
-## यदि q का l-वाँ बिट 1 है, तो मान लीजिए e = p01 है<sup>w-l</sup>. के पूर्ववर्ती की खोज के लिए समानांतर तुलना का उपयोग करें <code>sketch</code>(इ)। यह q का वास्तविक उत्तराधिकारी है।
+## यदि q का l-वाँ बिट 1 है, तो मान लीजिए e = p01<sup>w-l</sup> है.समानांतर तुलना का उपयोग करके <code>sketch</code>(e) के पूर्ववर्ती की खोज करे। यह q का वास्तविक उत्तरकर्ता है।
-# एक बार जब q का पूर्ववर्ती या उत्तराधिकारी मिल जाता है, तो कुंजियों के सेट के bच q की सटीक स्थिति निर्धारित की जाती है।
+# एक बार जब q का पूर्वपद या उत्तरकर्ता मिल जाए, तो कुंजीयों के सेट में q का सटीक स्थान निर्धारित हो जाता है।
 ==फ्यूजन हैशिंग==
-[[हैश तालिका]]ओं के लिए फ़्यूज़न ट्री का एक अनुप्रयोग विलार्ड द्वारा दिया गया था, जो हैशिंग के लिए एक डेटा संरचना का वर्णन करता है जिसमें हैश चेनिंग के साथ एक बाहरी स्तर की हैश तालिका को प्रत्येक हैश श्रृंखला का प्रतिनिधित्व करने वाले फ़्यूज़न ट्री के साथ जोड़ा जाता है।
+.
-हैश चेनिंग में, एक स्थिर लोड फैक्टर वाली हैश तालिका में, एक चेन का औसत आकार स्थिर होता है, परंतु इसके अतिरिक्त उच्च संभावना के साथ सभी चेन का आकार होता है {{math|''O''(log ''n'' / log log ''n'')}}, कहाँ {{mvar|n}} हैश की गई वस्तुओं की संख्या है।
-इस श्रृंखला का आकार इतना छोटा है कि एक फ़्यूज़न ट्री प्रति ऑपरेशन निरंतर समय में इसके भीतर खोज और अपडेट को संभाल सकता है। इसलिए, डेटा संरचना में सभी परिचालनों का समय उच्च संभावना के साथ स्थिर है।
+फ्यूजन ट्रीज का [[हैश तालिका]]ओं  के एक अनुप्रयोग को विल्लार्ड द्वारा दिया गया था, जो एक डेटा संरचना का वर्णन करते हैं जो हैश चेनिंग के साथ एक बाह्य स्तर हैश तालिका को जोड़ती है। हैश चेनिंग में, एक स्थिर भार संकेतक के साथ एक हैश तालिका में, एक चेन का औसत आकार स्थिर होता है, परंतु इसके अलावा उच्च संभावना के साथ सभी चेनों का आकार {{math|''O''(log ''n'' / log log ''n'')}}, होता है, यहाँ n हैश किए गए आइटमों की संख्या है। यह चेन का आकार इतना छोटा होता है कि एक फ्यूजन ट्री इसके अंदर खोज और अद्यतन को स्थायी समय में संभाल सकती है। इस प्रकार, डेटा संरचना में सभी कार्यों का समय संभावनानुसार स्थिर होता है। और अधिक सटीकता से कहें तो, इस डेटा संरचना के साथ, प्रत्येक इंवर्स [[अर्ध-बहुपद समय]]  संभावना {{math|1=''p''(''n'') = exp((log ''n'')<sup>''O''(1)</sup>)}} के लिए, एक स्थिर{{mvar|C}} ऐसा होता है जिससे यह संभावना होती है कि किसी भी कार्य का समय {{mvar|C}} से अधिक होने की संभावना n पर कम से कम {{math|''p''(''n'')}} होती है।<ref>{{citation
-अधिक सटीक रूप से, इस डेटा संरचना के साथ, प्रत्येक व्युत्क्रम-[[अर्ध-बहुपद समय]] संभावना के लिए {{math|1=''p''(''n'') = exp((log ''n'')<sup>''O''(1)</sup>)}}, एक स्थिरांक है {{mvar|C}} जैसे कि संभावना है कि एक ऑपरेशन मौजूद है जो समय से अधिक है {{mvar|C}} अधिकतम है {{math|''p''(''n'')}}.<ref>{{citation
   | last = Willard | first = Dan E. | authorlink = Dan Willard
   | doi = 10.1137/S0097539797322425
@@ Line 130: / Line 126: @@
   | volume = 29
   | year = 2000}}.</ref>
+==संगणनात्मक प्रारूप और आवश्यक धारणाएँ==
+फ्यूजन ट्री एल्गोरिदम के लिए कंप्यूटेशनल प्रारूप एक वर्ड आरएएम है जिसमें एक विशेष निर्देश सेट होता है, जिसमें अंकगणितीय निर्देश - जोड़, घटाव, गुणाकार निर्देश (सभी मॉड्यूलो {{math|2<sup>''w''</sup>}} में किए जाते हैं) और बूलियन निर्देश - बिटवाइज़ AND, NOT आदि सम्मिलित हैं। इसमें डबल-प्रेसिजन गुणाकार निर्देश भी सम्मिलित है। यह प्रमाणित किया गया है<ref>{{citation
-==न्यूनतम्प्यूटेशनल मॉडल और आवश्यक धारणाएँ==
-फ़्यूज़न ट्री एल्गोरिदम के लिए न्यूनतम्प्यूटेशनल मॉडल एक [[शब्द राम]] है जिसमें एक विशिष्ट निर्देश सेट होता है, जिसमें अंकगणितीय निर्देश शामिल होते हैं - जोड़, घटाव और गुणा (सभी निष्पादित)
-सापेक्ष {{math|2<sup>''w''</sup>}}) और बूलियन ऑपरेशन - बिटवाइज और, नहीं आदि। एक डबल-सटीक गुणन निर्देश भी शामिल है। यह दर्शाया गया है<ref>{{citation
   | last1 = Ben-Amram| first1 = Amir M.
   | last2 = Galil | first2 = Zvi| author2-link = Zvi Galil
@@ Line 144: / Line 137: @@
   | volume = 54
   | year = 1997| doi-access = free
-  }}.</ref> उपरांत वाले निर्देश को हटाने से तेजी से सॉर्ट करना असंभव हो जाता है {{math|''O''(''n'' log ''n'')}}, जब तक कि इसे लगभग मेमोरी स्पेस का उपयोग करने की अनुमति न हो {{math|2<sup>''w''</sup>}} शब्द (फ़्यूज़न ट्रीज़ द्वारा उपयोग किए गए रैखिक स्थान के विपरीत), या इसके अतिरिक्त अन्य निर्देश शामिल करें{{R|AMT1999}}.
+  }}.</ref>अंतिम निर्देश को हटाने से {{math|''O''(''n'' log ''n'')}} से तीव्रता से क्रमबद्ध करना असंभव होता है, जब तक इसे लगभग {{math|2<sup>''w''</sup>}} शब्दों के मेमोरी स्थान का उपयोग करने की अनुमति नहीं है , या इसके स्थान पर अन्य निर्देशों को सम्मिलित किया जाता हैं।{{R|AMT1999}}
 == संदर्भ ==

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

Anonymous

Search

फ्यूज़न ट्री: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:34, 6 July 2023

Contents

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

रेखाचित्र

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

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

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

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

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

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

फ्यूज़न ट्री: Difference between revisions

Revision as of 10:34, 6 July 2023

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

रेखाचित्र

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

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

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

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

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

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories