درخت تلفیقی

درخت تلفیقی نوعی داده ساختار درخت گونه است که یک آرایه ارتباطی را روی اعداد صحیح w بیتی پیاده‌سازی می‌کند. این درخت از فضایی به مقدار (O(n استفاده کرده و جستجو را در زمان (O(log_w n انجام می‌دهد که به‌طور تقریبی از درخت سنتی – به نام درخت دودویی جستجوی خود تعادلی- سریع تر بوده و در واقع از درخت وان آمده باوس (van Emde Boas tree) در حالتی که w بزرگ است، بهتر می‌باشد. این نوع درخت سرعت خود را با بهره‌گیری از عملیات مخصوصی که در زمان ثابت انجام می‌شود، به دست می‌آورد که این عملیات می‌تواند توسط کلمه (در معنای رایانه‌ای) انجام شود. درخت‌های تلفیقی در سال ۱۹۹۰ توسط مایکل فردمن(Michael Fredman) و دان ویلارد(Dan Willard) اختراع شد. از زمان انتشار نسخه اصلی مقاله فردمن و ویلارد، چندین پیشرفت انجام شده‌است. در سال ۱۹۹۹ نشان داده شد که چگونه می‌توان درخت‌های تلفیقی را تحت مدل AC0 پیاده‌سازی کرد، به گونه‌ای که ضرب دیگر زمان ثابتی را به خود اختصاص ندهد. یک نسخه پویایی از درخت‌های تلفیقی با استفاده از جداول درهم سازی در سال ۱۹۹۶ پیشنهاد شد که با زمان اجرای مورد انتظار(O(log_w n مطابقت داشت. یک نسخه پویای دیگر با استفاده از درخت نمایی در سال ۲۰۰۷ پیشنهاد شد که در بدترین حالت به زمان اجرای (O(log_w n + log log u برای هر عملیات رسید. در این معادله u اندازه بزرگترین کلید است. این مسئله هم چنان باز است تا جایی که درخت تلفیقی با احتمال بالایی به (O(log_w n در هر عملیات برسد.

چگونه عمل می‌کند؟

یک درخت ترکیبی اساساً یک B-tree با عوامل شاخه‌ای w^1/5 (هر توان کوچک دیگری نیز ممکن است) است که باعث می‌شود ارتفاع درخت از (O(log_w n باشد. برای این که به زمان اجرای مطلوب از لحاظ بروزرسانی و پاسخ گویی برسیم، درخت باید توانایی جستجوی یک گره با کلید w^1/5 به بالا را در زمان ثابت (O(n داشته باشد. این خواسته ما با روش فشرده سازی "sketching" برآورده می‌شود. در این روش کلیدها به صورتی در می‌آید که در یک machine word جای گیرد. در واقع این روش اجازه می‌دهد که مقایسه‌ها به صورت موازی انجام گیرد. در ادامه این مقاله اجرا در یک static Fusion Tree که پاسخ گویی مطلوب را پشتیبانی می‌کند، توصیف می‌کنیم.

Sketching

Sketching تابعی است که طبق آن هر کلید w بیتی منسوب به یک node شامل k تا کلید است که در k-1 بیت فشرده شده‌است. هر کلید x می‌تواند این‌طور در نظر گرفته شود که یک مسیر کامل در یک درخت دودویی با ارتفاع w، از ریشه تا برگِ مطابق با x است. جهت تمایز دو مسیر کافی است به سر شاخه‌ها نگاه کنیم (محل انشعاب بین دو شاخه، یعنی محل اولین بیتی که دو کلید متفاوت می‌شوند). بدیهی است که k تا مسیر در کنار هم k-1 نقطه انشعاب دارند؛ بنابراین حداکثر k-1 بیت نیاز است تا بتوانیم بین هر جفت از k تا کلید تمایز قائل شویم.

Visualization of the sketch function.

خاصیت مهم تابع sketch این است که ترتیب کلیدها را حفظ می‌کند؛ بنابراین اگر x < y آنگاه (sketch(x) < sketch(y

تخمین sketch

اگر موقعیت بیت‌های sketch را b₁ < b₂ < ··· < b_r فرض کنیم آنگاه sketch کلیدهای x_w-1···x₁x₀ یک عدد r بیتی به صورت $x_{b_{r}}x_{b_{r-1}}\cdots x_{b_{1}}$ می‌شود. با machine wordهای استاندارد که مانند آن‌ها در زبان C دیده می‌شود، مشکل است که sketch هر کلید را در (O(1 بیابیم. پس به جای آن بیت‌های sketch می‌توانند در محدوده اندازه حداکثر r⁴ تایی با استفاده از ضرب و And بیت به بیت فشرده شوند. نقش bitwise AND این است که همه بیت‌های غیر sketch در کلید را روشن سازد. عمل ضرب نیز بیت‌های sketch را shift می‌دهد تا محدوده کوچک‌تر گردد؛ بنابراین مثل یک sketch عالی، تخمین sketch تربیت کلیدها را حفظ می‌کند.

برای انجام یک عمل ضرب درست در زمان ثابت چند پیش پردازش مورد نیاز است. هر بیت sketch در مکان b_i باید با عمل ضرب (در حالی که m = $\textstyle \sum _{i=1}^{r}$ 2^m_i) به مکان b_i + m_i، shift پیدا کند.

برای کارایی تخمین sketch لازم است سه قاعده زیر رعایت گردد:

1. b_i + m_j باید برای هر جفت (i, j) متفاوت باشد. این قانون به ما اطمینان می‌دهد که عمل ضرب، بیت‌های sketch را خراب نکرده و معتبر می‌مانند.
2. b_i + m_j لزوماً تابعی صعودی بر حسب i است. (به دلیل نگهداری ترتیب بیت‌های sketch)

3) b_r + m_r) - (b₁ - m₁) ≤ r⁴) چون بیت‌های sketch در محدوده‌ای با حداکثر اندازه r⁴ بسته‌بندی می‌شوند.

تحلیل روی argument نشان می‌دهد که چگونه m_i می‌تواند ساخته شود. فرض می‌کنیم که m₁ = w − b₁ و 1 < t ≤ r بوده و m₁, m₂... m_t-1 قبلاً انتخاب شده‌اند. کوچکترین عدد m_t را به نحوی برمی‌داریم که قواعد ۱ و ۲ به هم نخورد. اعمال قاعده اول موجب می‌شود که m_t ≠ b_i − b_j + m_l برای هر ۱ ≤ i, j ≤ r , 1 ≤ l ≤ t-1 برقرار باشد. همچنین m_t از مقادیر کمتر از tr² ≤ r³ باید دوری کند؛ بنابراین m_t انتخابی در رابطه b_t + m_t) ≤ (b_t-1 + m_t-1) + r³) صدق می‌کند و قاعده سوم تضمین می‌گردد.

محاسبه تخمین sketch در مراحل زیر انجام خواهد شد:

۱) بررسی و نمایش همه، که در اینجا بیت‌های sketch با یک bitwise AND همراه خواهند بود.

۲) ضرب کلید با توجه به ثابت m از قبل تعیین شده. این عمل در حقیقت دو machine word نیاز دارد اما باز هم می‌تواند در زمان ثابت (O(1 انجام گیرد.

۳) نمایش همگانی دیگر که این بار بیت‌های sketch به صورت shift داده شده، نشان داده خواهند شد.

بیت‌ها الان شامل بلاک‌های متصل به یکدیگر حداکثر r⁴ < w^4/5 بیتی هستند.

در ادامه مقاله sketch به‌کار گرفته می‌شود تا منظور از تخمین sketch را دریابیم.

مقایسه موازی

هدف فشرده سازی که از طریق Sketching به دست می‌آید این است که به تمام کلیدها اجازه دهیم در یک کلمه w بیتی ذخیره شوند. در گره Sketch یک گره، رشته بیتی قرار دارد: (1sketch(x₁)1sketch(x₂)...1sketch(x_k

می‌توانیم فرض کنیم که تابع sketch دقیقاً از b بیت b ≤ r⁴، سپس هر بلوک از 1 + b ≤ w^4/5 استفاده می‌کند و از آن جایی که k ≤ w^1/5 کل تعداد بیت‌ها در گره sketch حداکثر w است. یک اشارهٔ مختصر: برای یک رشته بیتی s و عدد صحیح غیر منفی m, s^m الحاق m مرتبه s را باخودش نشان می‌دهد. اگر t هم یک رشته بیتی باشد، st الحاق t به s را نشان می‌دهد.

گره sketch جستجوی کلیدها برای هر عدد صحیح b بیتی را امکان‌پذیر می‌سازد. z = (0y)^k قرار می‌دهیم که می‌تواند در زمان ثابتی محاسبه شود (ضرب y در ثابت 0^b1)^k)). توجه کنید که 1sketch(x_i) - 0y همواره مثبت است، ولی اگر sketch(x_i) ≥ y پیشرو خود را حفظ می‌کند؛ بنابراین می‌توانیم کوچکترین شاخص i را به طوری که sketch(x_i) ≥ y باشد به صورت زیر محاسبه کنیم:

1)Z را از گره sketch کم کنید.

۲)بیت‌های مقدار حاصل و ثابت 10^b)^k) را به صورت منطقی و بیت به بیت با هم and کن. این کار همه بیت‌ها به جز بیت پیشرو هر بلوک را پاک می‌کند.

۳)پر ارزش‌ترین بیت نتیجه را پیدا کنید.

4) i را با استفاده از این حقیقت که بیت پیشرو i امین بلوک شاخصی برابر(i(b+1 دارد محاسبه کنید.

Desketching

برای یک صف دلخواه q، مقایسه موازی شاخص i را به نحوی محاسبه می‌کند که (sketch(x_i-1) ≤ sketch(q) ≤ sketch(x_i

متأسفانه، تابع sketch خارج از مجموعه کلیدها به صورت کلی نمی‌تواند مرتبه زمانی اش را نگه دارد؛ بنابراین لزوماً این حالتی نیست که x_i-1 ≤ q ≤ x_i. آنچه که درست است این است که در میان تمام کلیدها، یا x_i-1 یا x_i بزرگ‌ترین پسوند مشترک را با q دارد. این به خاطر این است که هر کلید y با یک پسوند مشترک طولانی‌تر با q تعداد sketch بیت‌های مشترک بیشتری با q داردو بنابراین (sketch(y از هر (sketch(x_j ای به (sketch(q نزدیک تر است.

طول بزرگترین پسوند مشترک بین دو عدد صحیح w بیتی a و b می‌تواند با پیدا کردن پرارزش‌ترین بیت xor منطقی بیت به بیت بین a و b در زمان ثابت محاسبه شود. این کار سپس می‌تواند برای پوشاندن تمام پسوندها به جز بزرگ‌ترین پسوند مشترک، به کار رود.

توجه کنید که p دقیقاً جایی را که q از مجموعه کلیدها جدا می‌شود را مشخص می‌کند. اگر بیت بعدی q، ۰ باشد، successor (کوچک‌ترین عدد بزرگ‌تر از q) در زیر درخت p1 قرار دارد و اگر بیت بعدی q، ۱ باشد، آن گاه predecessor (بزرگ‌ترین عدد کوچک‌تر از q) در زیردرخت p0 قرار دارد. این حالت الگوریتم زیر را پیشنهاد می‌کند:

۱. از مقایسه موازی برای پیدا کردن شاخص i استفاده کنید، به طوری که(sketch(x_i-1) ≤ sketch(q) ≤ sketch(x_i

۲. بزرگترین پسوند مشترک p از q و نیز xi-1 یا x_i را محاسبه کنید (از هر جفت، آنچه طولانی‌تر است را بگیرید)

3.l-۱ را طول بزرگترین پسوند مشترک p بگیرید

۳٫۱. اگر l امین بیت q، ۰ است، e = p10^w-l قرار دهید. از مقایسه موازی برای جستجوی successor برای (sketch(e استفاده کنید. این در واقع predecessor برای q است.

۳٫۲. اگر l امین بیت q، ۱ است، e = p10^w-l قرار دهید. از مقایسه موازی برای جستجوی predecessor برای (sketch(e استفاده کنید. این در واقع successor برای q است.

۴. زمانی که یا predecessor یا successor برای q پیدا شد، محل دقیق q بین مجموعه کلیدها مشخص شده‌است.

منابع

• http://en.wikipedia.org/wiki/Fusion_tree
• 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)