آبشاره‌سازی جزءبه‌جزء

در علوم رایانه، آبشاره‌سازی جزءبه‌جزء (Fractional cascading) روشی است که با آن می‌توان، دنبال‌های از جستجوهای دودویی را انجام داد و یک مقدار مشخص را از میان دنباله‌ای از ساختار داده‌های مرتبط به هم، با سرعت بالایی جستجوی دودویی کرد.

اولین جستجو، بنا به حالت عادی یک جستجوی دودویی، در زمانی لگاریتمی انجام می‌شود، اما جستجوهای بعدی سریعتر خواهند بود. روش آبشاره‌سازی جزءبه‌جزء نخستین بار در سال ۱۹۸۶ توسط Chazelle Guibas , طی دو مقاله م(Chazelle & Guibas 1986a(Chazelle & Guibas ۱۹۸۶ ارائه شد. این روش، برگرفته از دو ایده بود: یکی ایدهٔ آبشاره‌سازی که از الگوریتم "جستجوی دامنه‌ای داده در داده ساختارهاً از لوکر (۱۹۷۸) و ویلارد (۱۹۷۸) برگرفته شده‌بود. دیگری ایده نمونه برداری جزء به جزء از (Chazelle (۱۹۸۳. بعد از آن افراد دیگری شکل‌های پیچیده تری از روش آبشاره‌سازی جزءبه‌جزء ارائه کردند. در این الگوریتم‌ها، داده ساختار، وقتی دنباله‌ای از عملیات حذف و درج روی آن انجام شود و داده‌ها تغییر کنند، همچنان معتبر است و امکان جستجوی سریع در آن وجود دارد.

در فناوری اطلاعات، اصطلاحاً به ترتیب دادن یک سلسله فعالیت‌های پیوسته در پردازش داده‌ها که در آن انجام هر مرحله وابسته به وقوع مرحلهٔ قبل است آبشاره‌سازی می‌گویند.

مثال

به عنوان یک مثال ساده از آبشاره‌سازی جزءبه‌جزء، این مسئله را در نظر بگیرید: تعداد k لیست مرتب شده از اعداد حقیقی به ما داده شده‌است. مجموع تعداد اعضای این لیست‌ها روی هم n است. یعنی اگر هر لیست را با Li نشان دهیم، Σ|Li|=n. می‌خواهیم این لیست‌ها را طوری پردازش کنیم که بتوانیم جستجوهای دودویی را به دنبال مقدار خواسته شدهٔ q در هر یک از این k لیست انجام دهیم. برای مثال، به ازای n = ۴ و k = ۱۷:

L1 = ۲٫۴، ۶٫۴، ۶٫۵، ۸٫۰، ۹٫۳

L2 = ۲٫۳، ۲٫۵، ۲٫۶

L3 = ۱٫۳، ۴٫۴، ۶٫۲، ۶٫۶

L4 = ۱٫۱، ۳٫۵، ۴٫۶، ۷٫۹، ۸٫۱

ساده‌ترین راه حل برای این مسئلهٔ جستجو، ذخیره کردن هر لیست به طور جداگانه (در یک آرایه) است. در این صورت به حافظهٔ اضافی از مرتبهٔ n نیاز داریم. جستجو را در هر یک از این k لیست به طور جداگانه انجام می‌دهیم. بدترین حالت زمانی رخ می‌دهد که تعداد اعضای لیست‌ها برابر و به میزان n/k باشد. در این صورت زمان یک جستجو، در هر لیست از مرتبهٔ (log(n/k و در نتیجه زمان کلی یک جستجو از مرتبهٔ (klog(n/k خواهد بود.

راه حل دوم جستجوهای سریع تری را ممکن می‌کند اما فضای بیشتری از حافظه می‌گیرد. ما می‌توانیم k لیست را در یک لیست بزرگ L با هم ادغام کنیم و به ازای هر مورد x از لیست L، نتایج جستجوهای x در لیست‌های کوچکتر Li را قرار دهیم. یک المان از لیست ادغام شده را با x[a, b, c, d] نشان می‌دهیم، که x یک مقدار، و a, b, c, d مکان‌های مقادیر عنصر بعدی x، در هر یک از لیست‌های ورودی است (فرض بر این است که نخستین مکان را با ۰ نشان می‌دهیم). با توجه به مرتب بودن لیست‌های ورودی، منظور از عنصر بعدی، عنصر بلافاصله بزرگ‌تر یا حد اقل مساوی با x است. (اگر چنین عنصری وجود نداشت، مکان بعد از آخرین خانهٔ لیست را، قرار داد می‌کنیم) در این صورت خواهیم داشت:

L = ۱٫۱[۰٬۰٬۰٬۰], ۱٫۳[۰٬۰٬۰٬۱], ۲٫۳[۰٬۰٬۱٬۱], ۲٫۴[۰٬۱٬۱٬۱], ۲٫۵[۱٬۱٬۱٬۱], ۲٫۶[۱٬۲٬۱٬۱], ۳٫۵[۱٬۳٬۱٬۱], ۴٫۴[۱٬۳٬۱٬۲], ۴٫۶[۱٬۳٬۲٬۲], ۶٫۲[۱٬۳٬۲٬۳], ۶٫۴[۱٬۳٬۳٬۳], ۶٫۵[۲٬۳٬۳٬۳], ۶٫۶[۳٬۳٬۳٬۳], ۷٫۹[۳٬۳٬۴٬۳], ۸٫۰[۳٬۳٬۴٬۴], ۸٫۱[۴٬۳٬۴٬۴], ۹٫۳[۴٬۳٬۴٬۵]

با این راه حل ادغامی یک پرس و جو در زمان (O(log n + k انجام می‌شود. زمان Log n برای جستجوی q در لیست n تایی L، و k برای گزارش کردن نتایج صرف می‌شود. با توجه به اینکه مکان هایx در هر لیست‌های ورودی، در لیست L عنصر x ذخیره شده‌اند، نتایج پس از جستجو بدست می‌آیند.

این مدل، چنین مسئله‌های جستجویی را با صرف زمان (O(log n + kو حافظهٔ (O(n حل می‌کند. راه حل آبشاره‌سازی جزءبه‌جزء ذخیره کردن دنباله‌های جدیدی از لیست‌های Mi است. لیست نهایی در این دنباله Mk است که برابر است با Lk، و هر لیست قبلی از ادغام Li با هر یک از به ازای هر عنصر x در این لیست ادغامی، ما دو عدد ذخیره می‌کنیم: مکانی که از جستجوی x در Li به دست می‌آید، و مکانی که از جستجوی x در Mi+۱ بدست می‌آید. به ازای داده‌های بالا، چنین عملی، این لیست‌ها را به ما می‌دهد:

M1 = ۲٫۴[۰، ۱], ۲٫۵[۱، ۱], ۳٫۵[۱، ۳], ۶٫۴[۱، ۵], ۶٫۵[۲، ۵], ۷٫۹[۳، ۵], ۸[۳، ۶], ۹٫۳[۴، ۶]

M2 = ۲٫۳[۰، ۱], ۲٫۵[۱، ۱], ۲٫۶[۲، ۱], ۳٫۵[۳، ۱], ۶٫۲[۳، ۳], ۷٫۹[۳، ۵]

M3 = ۱٫۳[۰، ۱], ۳٫۵[۱، ۱], ۴٫۴[۱، ۲], ۶٫۲[۲، ۳], ۶٫۶[۳، ۳], ۷٫۹[۴، ۳]

M4 = ۱٫۱[۰، ۰], ۳٫۵[۱، ۰], ۴٫۶[۲، ۰], ۷٫۹[۳، ۰], ۸٫۱[۴، ۰]

فرض کنید می‌خواهیم یک پرس و جو برای q=۵ انجام دهیم. ابتدا یک جستجوی دودویی به دنبال qدر M۱انجام می‌دهیم و مقدار ۶٫۴[۱٬۵]. را پیدا می‌کنیم. عدد «۱» در ۶٫۴[۱٬۵]. به ما می‌گوید که جستجوی q در L۱ باید L۱[۱] = ۶٫۴ را برگرداند. عدد ۵ نیز می‌گوید تخمین موقعیت q در M۲ مکان ۵ است. با دقت بیشتر، جستجوی دودویی برای q در M۲ مقدار ۷٫۹[۳، ۵] در موقعیت ۵ یا مقدار۶٫۲[۳، ۳] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با ۶٫۲ و مشاهده اینکه کوچکتر است، ما می‌یابیم که نتیجه درست در M۲ , ۶٫۲[۳، ۳] است. اولین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که جستجو برای qدر L۲ باید L۲[۳] را برگرداند. یک مقدار پرچم به معنی آن است که q از انتهای لیست L۲ گذشته‌است. دومین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که تخمین موقعیت qدر M۳ موقعیت ۳ است. به طور دقیق تر، جستجوی دودویی برای q در M۳ مقدار۶٫۲[۲، ۳] در موقعیت ۳ یا مقدار ۴٫۴[۱، ۲] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با مقدار کمتر ۶٫۲. به ما نشان می‌دهد که نتیجه درست در M۳ ،۶٫۲[۲٬۳] است. «۲» در۶٫۲[۲٬۳] به ما می‌گوید که جستجو برای qدر L۳ باید L۳[۲]=۶٫۲ را برگرداند و «۳» در ۶٫۲[۲٬۳] به ما می‌گوید که نتیجه جستجو برای q در M۴ برابر با M۴[۳] = ۷٫۹[۳٬۰] یا M۴[۲] = ۴٫۶[۲٬۰] است. با مقایسه q با ۴٫۶ نشان می‌دهد که نتیجه صحیح ۷٫۹[۳٬۰] است و نتیجه جستجو برای q در L۴ برابر L۴[۳] = ۷٫۹. است پس ما q را در هر یک از چهار لیست پیدا کردیم بوسیله جستجوی دوتایی در تک لیست M۱ همراه با یک مقایسه در هر لیست متواتر. به‌طور کلی تر برای هر ساختار داده از این نوع ما یک پرس و جو را بوسیله انجام یک جستجوی دودویی q در M۱ انجام می‌دهیم و با استفاده از مقدار نتیجه شده موقعیتq در L۱ را تعیین می‌کنیم.

در مثال ما، لیست‌های آبشاره‌سازی جزءبه‌جزء شده، در مجموع ۲۵ عنصر دارند که مقداری کمتر از دو برابر ورودی اصلی است. به طور کلی سایز Mi در این داده ساختار حداکثر به این اندازه‌است:
Lj| + ½| Li + ۱ | + ¼ | Li + ۲ | + … + ۱/ ۲j | Mi + j | +….

که به سادگی اثبات می‌شود سایز داده ساختار حد اکثر ۲n است:

(Σ|Mi| = Σ|Li|(۱ + ½ + ¼ +…) ≤ ۲n = O(n

مسئلهٔ کلی

به طور کلی، آبشاره‌سازی جزءبه‌جزء با گراف کاتالوگ آغاز می‌شود. گراف کاتالوگ گرافی جهت دار است که هر رأس آن با یک لیست مرتب شده برچسب گذاری شده‌است. هر پرس و جو در این داده ساختار، شامل یک مسیر از این گراف و یک مقدار q است و به ازای این دو، داده ساختار باید مشخص کند q در هر یک از لیست‌های مرتب شده‌ای که در رئوس مسیر داده شده قرار دارند، چندمین عنصر است. به عنوان یک مثال ساده، گراف کاتالوگ مسیری است با چهار رأس. با استفاده از روش پویا (داینامیک)، امکان این وجود دارد که پاسخ رئوس بعدی یک مسیر را بر اساس نتایج جستجو در رئوس قبلی مسیر به دست آید.

می‌خواهیم به پرسش‌هایی از این دست، در گرافی پاسخ دهیم. در این گراف به ازای مقدار ثابت d حداکثر تعداد یال‌های ورودی از هر رأس d و حد اقل تعداد یال‌های ورودی به هر رأس نیز d است. لیست‌های مربوط به هر رأس را، بر اساس همسایه‌های منتهی به یال‌های خروجی رأس، گسترش می‌دهیم. این کسر باید طوری انتخاب شود که کوچکتر از ۱/d باشد. به طوری که مقدار مجموع لیست‌های گسترش یافته نسبت به سایز ورودی خطی باشد. هر مورد، در هر لیست گسترش یافته، محل قرار گرفتن آن مورد را در لیست‌های گسترش نایافته‌ای که در همان رأس و در رأس‌های همسایهٔ منتهی به یال‌های خروجی، ذخیره شده‌اند، ذخیره می‌کند. به عنوان یک مثال ساده از این توضیحات، d=۱، و ما هر لیست را با ½ از همسایه‌هایش گسترش داده‌ایم:

یک پرسش در این داده ساختار، شامل یک جستجوی دودویی عادی در لیست گسترش یافتهٔ مربوط به رأس اول از مسیر مورد پرس و جو، و علاوه بر آن، تعدادی جستجوی ساده‌تر، در هر یک از رئوس بعدی مسیر است. اگرکسر ۱/r از همسایه‌های یک رأس در گسترش دادن لیست آن استفاده شود، در آن صورت نتیجهٔ هر پرسش بعدی حداکثر در r مرحله، از روی مکان‌هایی که در پرسش‌های قبلی، در رئوس قبلی مسیر ذخیره شده‌است، بدست خواهد آمد و حتی ممکن است در زمانی ثابت و کوتاه، بدون انجام یک جستجوی دودویی کامل یافته شود.

آبشاره‌سازی جزءبه‌جزء پویا

در آبشاره‌سازی جزءبه‌جزء به صورت پویا، لیستی که در هر گره از گراف کاتالوگ ذخیره شده‌است، می‌تواند به صورت پویا تغییر کند. به عبارتی اجزای این لیست می‌توانند به روز شوند و یک عضو در آن درج شود یا از آن حذف گردد. ایجاد این تغییرات باعث به وجود آمدن مشکلاتی در ساختاربندی داده‌ها می‌شود.

یکی از مشکلاتی که در این زمینه وجود دارد این است که هنگام اضافه شدن یک عضو به یک گره یا حذف شدن عضوی از آن، تغییراتی در لیست مربوط به آن گره ایجاد می‌شود. از طرفی تغییر در یک لیست منجر به وجود آمدن تغییرات در سایر لیست‌ها در سایر گره‌ها نیز می‌گردد. برای حل این مشکل، به جای استفاده از یک آرایهٔ مرتب شده برای هر گره، از یک درخت دودویی جستجو استفاده می‌شود. با این کار دو هدف برآورده خواهد شد. با استفاده از درخت دودویی جستجو، امکان به روز رسانی سایر گره‌ها هنگام تغییر یک گره، با تعداد عملیاتی محدود فراهم می‌شود و همچنین توانایی جستجوی دودویی پابرجا باقی خواهد ماند.

همان‌طور که پیش‌تر گفته شد، هر گره از گراف کاتالوگ، تعدادی از اعضای لیست همسایهٔ خود را نیز نگه‌داری می‌کند. به عبارتی در لیست یک گره، اعضایی که در مکان d از لیست همسایه قرار دارند نیز وجود دارد. در برخی شرایط با توجه به مقدار d و همچنین اعضای یک لیست، این امکان وجود دارد که با هر به روز رسانی و تغییر در یک لیست، لیست‌های همسایه نیز تغییر کنند. برای حل این مشکل از روشی شبیه به روش ساخت داده ساختار B tree استفاده می‌شود. با استفاده از این روش، می‌توان اطمینان حاصل کرد که تعداد داده‌هایی که انتخاب می‌شوند، کمتر از کل داده‌های لیست تقسیم بر d است و همچنین این اعداد در مکان‌های ثابتی از لیست قرار دارند. این موضوع باعث می‌شود که انتقال تغییرات هنگام درج یا حذف برای یک لیست از یک گره، تعداد عملیاتی کمتر از یک تقسیم بر d نیاز داشته باشد. یعنی یک تغییر در یک گره، به طور میانگین حداکثر یک تقسیم بر d تغییر برای به روز رسانی سایر گره‌ها نیاز دارد. با این روش، توزیع داده‌ها در میان گره‌ها به گونه‌ای خواهد بود که میانگین تعداد عملیاتی که برای به روز رسانی درخت‌های جستجوی دودویی صورت می‌گیرد، عددی ثابت است.

مسئلهٔ اصلی در مبحث پویا کردن آبشاره‌سازی جزءبه‌جزء، نگه‌داری اندیس‌ها می‌باشد. همان‌طور که پیش‌تر گفته شد، هر عضو از لیست موجود در یک گره، دو اندیس را نگه می‌دارد. یکی اندیس مربوط به جستجوی خودش در همان لیست و یکی اندیس مربوط به جستجوی آن عضو در لیست همسایه. نگه‌داری این اندیس‌ها به صورت پویا هزینه‌بر است، چراکه با تغییر یک عضو، تعداد اندیس‌هایی که در تمام لیست‌ها باید تغییر کند، عدد بسیار بزرگی خواهد بود. برای همین، در این مدل، داده ساختارهای دیگری برای ذخیره شدن در هر گره، در نظر گرفته می‌شود که به شرح زیر می‌باشند:

• یک نگاشت از اجزای لیست مربوط به یک گره، به اعداد صحیح کوچک؛ بنابراین برای بررسی ترتیب قرار گیری عناصر یک لیست، کافیست این اعداد صحیح نسبت داده شده به آن‌ها را با هم مقایسه کرد و با انجام عملیات بر عکس این نگاشت می‌توان از اعداد صحیح به اجزای اصلی لیست، دست یافت. روشی که Dietz در سال ۱۹۸۲ به آن دست یافت، راهکاری می‌دهد تا این نگاشت به صورت کارایی ذخیره شود؛ بنابراین هر گره، این نگاشت را ذخیره می‌کند و تنها با داشتن همین نگاشت می‌توان از اعضای لیست به لیستی از اعداد صحیح کوچک‌تر و برعکس دست یافت.
• داده ساختاری برای جستجوی اعداد صحیح (داده ساختاری مانند van Emde Boas tree). با استفاده از این داده ساختار، می‌توان در میان اعداد صحیح نسبت داده شده به اعضای لیست، که طبق نگاشت گفته شده حاصل می‌شوند، به جستجوی عدد مورد نظر پرداخت.
• برای هر گره همسایه در گراف کاتالوگ، یک داده ساختار جستجوگر اعداد صحیح مشابه برای زیر مجموعه‌ای از اعداد به دست آمده از آن گره در نظر گرفته می‌شود. به وسیلهٔ این داده ساختار و نگاشت اعضای لیست به اعداد صحیح، به صورت مؤثر می‌توان هر عضو x لیست آن گره را در تعداد مراحل ثابت پیدا کرد.

این داده ساختارها باعث می‌شوند که آبشاره‌سازی پویا در مرتبهٔ زمانی (O(log n برای هر درج و حذف عمل کند. همچنین یک زنجیره از k عمل جستجوی دودویی که در یک مسیر به طول k در گراف کاتالوگ صورت می‌گیرد، در مرتبهٔ زمانی (O(log n + k log log n انجام پذیرد.

کاربردها

یکی از کاربردهایی که آبشاره‌سازی جزءبه‌جزء دارد، در داده ساختارهای جستجوی محدوده ^{Range search} که در هندسهٔ محاسباتی مورد استفاده قرار می‌گیرد، می‌باشد. به طور مثال، در مسئلهٔ half-plane range reporting باید تعداد n نقطهٔ ثابت را تقسیم‌بندی کرد. یکی از ساختارهایی که در این زمینه مورد استفاده قرار می‌گیرد، لایه‌های محدب ^{convex layers} می‌باشد. آبشاره‌سازی جزءبه‌جزء به این مسئله کمک می‌کند تا عملیات جستجو برای شیب‌های مربوط به هر لایه در حافظهٔ مرتبهٔ (O(n و زمان (O(log n + h صورت گیرد که در آن h اندازهٔ زیرمجموعه‌هایی از نقاط است که مورد سؤال قرار می‌گیرد. با استفاده از الگوریتم Chazelle داده ساختاری که از مرتبهٔ زمانی (O(n log n ساخته می‌شود، این مسئله حل می‌شود. با توجه به این مثال، کاربرد آبشاره‌سازی جزءبه‌جزء شامل تعدادی جستجوی دودویی در یک سری خطی از لیست‌ها (سری‌های تودرتو از لایه‌های محدب) می‌باشد؛ بنابراین گراف کاتالوگ در این حالت، فقط یک مسیر ساده خواهد بود.

یکی دیگر از کاربردهای آبشاره‌سازی جزءبه‌جزء در داده ساختارهای هندسی در رابطه با مکان‌یابی نقاط در نواحی یکنواخت ^{monotone subdividions} می‌باشد. ناحیهٔ یکنواخت، بخشی از صفحه شامل تعدادی چندضلعی است که هر خط هرکدام از چندضلعی‌ها را در حداکثر دو نقطه قطع کند. Edelsbrunne, Guibas و Stolfi در سال ۱۹۸۶ نشان دادند که برای حل این مسئله، کافیست دسته‌ای از مسیرهای به شکل چندضلعی را یافت که از چپ تا راست ناحیهٔ مورد نظر کشیده شده‌اند. سپس یک جستجوی دودویی بر روی این مسیرها باید زد تا مسیری را که در پایین‌ترین سطح قرار دارد و همچنین بالاتر از نقطهٔ مورد جستجو واقع شده‌است پیدا کرد. این موضوع که یک نقطه بالای یک مسیر قرار دارد یا پایین آن، با جستجوی دودویی قابل بررسی است. به عبارتی باید جستجویی بر روی مختصهٔ اول از هرکدام از نقاط مسیر داشت تا مقایسه کرد که نقطهٔ مورد بررسی زیر مسیر قرار دارد یا بالای آن؛ بنابراین برای جستجوهای دودویی که صورت می‌گیرد، می‌توان از آبشاره‌سازی جزءبه‌جزء استفاده کرد و سرعت را افزایش داد. با استفاده از این روش، مرتبهٔ زمانی انجام جستجو (O(log n خواهد بود و فضای (O(n از حافظه درگیر خواهد شد. در این حالت، گراف کاتالوگ یک گراف درخت خواهد بود که ترتیب‌های ممکن را برای جستجوی دودویی خارجی را می‌نمایاند.

کاربرد آبشاره‌سازی جزءبه‌جزء تنها در محدودهٔ هندسهٔ محاسباتی نیست. Lakshamn و Stiliadis و همچنین Buddhikot, Suri و Waldvogel از این مدل برای طراحی داده ساختارهایی در حوزهٔ فیلتر کردن بسته‌های ارتباطی در مسیریاب‌های ^Routers اینترنتی استفاده کرده‌اند. Gao et al نیز از آن به عنوان مدلی برای توزیع و بازیابی داده در حسگرهای شبکه‌ای استفاده کرده‌است.

منابع

http://en.wikipedia.org/wiki/Fractional_cascading