درخت تلفیقی

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

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

یک درخت ترکیبی اساساً یک B-tree با عوامل شاخه‌ای w1/5 (هر توان کوچک دیگری نیز ممکن است) است که باعث می‌شود ارتفاع درخت از (O(logw n باشد. برای این که به زمان اجرای مطلوب از لحاظ بروزرسانی و پاسخ گویی برسیم، درخت باید توانایی جستجوی یک گره با کلید w1/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 را b1 < b2 < ··· < br فرض کنیم آنگاه sketch کلیدهای xw-1···x1x0 یک عدد r بیتی به صورت می‌شود. با machine wordهای استاندارد که مانند آن‌ها در زبان C دیده می‌شود، مشکل است که sketch هر کلید را در (O(1 بیابیم. پس به جای آن بیت‌های sketch می‌توانند در محدوده اندازه حداکثر r4 تایی با استفاده از ضرب و And بیت به بیت فشرده شوند. نقش bitwise AND این است که همه بیت‌های غیر sketch در کلید را روشن سازد. عمل ضرب نیز بیت‌های sketch را shift می‌دهد تا محدوده کوچک‌تر گردد؛ بنابراین مثل یک sketch عالی، تخمین sketch تربیت کلیدها را حفظ می‌کند.

برای انجام یک عمل ضرب درست در زمان ثابت چند پیش پردازش مورد نیاز است. هر بیت sketch در مکان bi باید با عمل ضرب (در حالی که m = 2mi) به مکان bi + mi، shift پیدا کند.

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

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

3) br + mr) - (b1 - m1) ≤ r4) چون بیت‌های sketch در محدوده‌ای با حداکثر اندازه r4 بسته‌بندی می‌شوند.

تحلیل روی argument نشان می‌دهد که چگونه mi می‌تواند ساخته شود. فرض می‌کنیم که m1 = w − b1 و 1 < t ≤ r بوده و m1, m2... mt-1 قبلاً انتخاب شده‌اند. کوچکترین عدد mt را به نحوی برمی‌داریم که قواعد ۱ و ۲ به هم نخورد. اعمال قاعده اول موجب می‌شود که mt ≠ bi − bj + ml برای هر ۱ ≤ i, j ≤ r , 1 ≤ l ≤ t-1 برقرار باشد. همچنین mt از مقادیر کمتر از tr2 ≤ r3 باید دوری کند؛ بنابراین mt انتخابی در رابطه bt + mt) ≤ (bt-1 + mt-1) + r3) صدق می‌کند و قاعده سوم تضمین می‌گردد.

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

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

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

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

بیت‌ها الان شامل بلاک‌های متصل به یکدیگر حداکثر r4 < w4/5 بیتی هستند.

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

مقایسه موازی

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

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

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

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

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

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

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

Desketching

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

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

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

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

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

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

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

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

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

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

منابع
      This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.