موضوع مقاله: آبشاره‌سازی جزءبه‌جزء | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # آبشاره‌سازی جزءبه‌جزء | مقدمه: اولین جستجو، بنا به حالت عادی یک جستجوی دودویی، در زمانی لگاریتمی انجام می‌شود، اما جستجوهای بعدی سریعتر خواهند بود. | ## بخش 1: آبشاره‌سازی جزءبه‌جزء | این روش، برگرفته از دو ایده بود: یکی ایدهٔ آبشاره‌سازی که از الگوریتم "جستجوی دامنه‌ای داده در داده ساختارهاً از لوکر (۱۹۷۸) و ویلارد (۱۹۷۸) برگرفته شده‌بود. بعد از آن افراد دیگری شکل‌های پیچیده تری از روش آبشاره‌سازی جزءبه‌جزء ارائه کردند. در این الگوریتم‌ها، داده ساختار، وقتی دنباله‌ای از عملیات حذف و درج روی آن انجام شود و داده‌ها تغییر کنند، همچنان معتبر است و امکان جستجوی سریع در آن وجود دارد. در فناوری اطلاعات، اصطلاحاً به ترتیب دادن یک سلسله فعالیت‌های پیوسته در پردازش داده‌ها که در آن انجام هر مرحله وابسته به وقوع مرحلهٔ قبل است آبشاره‌سازی می‌گویند. مثال به عنوان یک مثال ساده از آبشاره‌سازی جزءبه‌جزء، این مسئله را در نظر بگیرید: تعداد k لیست مرتب شده از اعداد حقیقی به ما داده شده‌است. می‌خواهیم این لیست‌ها را طوری پردازش کنیم که بتوانیم جستجوهای دودویی را به دنبال مقدار خواسته شدهٔ q در هر یک از این k لیست انجام دهیم. برای مثال، به ازای n = ۴ و k = ۱۷: L1 = ۲٫۴، ۶٫۴، ۶٫۵، ۸٫۰، ۹٫۳ L2 = ۲٫۳، ۲٫۵، ۲٫۶ L3 = ۱٫۳، ۴٫۴، ۶٫۲، ۶٫۶ L4 = ۱٫۱، ۳٫۵، ۴٫۶، ۷٫۹، ۸٫۱ ساده‌ترین راه حل برای این مسئلهٔ جستجو، ذخیره کردن هر لیست به طور جداگانه (در یک آرایه) است. ما می‌توانیم k لیست را در یک لیست بزرگ L با هم ادغام کنیم و به ازای هر مورد x از لیست L، نتایج جستجوهای x در لیست‌های کوچکتر Li را قرار دهیم. یک المان از لیست ادغام شده را با x[a, b, c, d] نشان می‌دهیم، که x یک مقدار، و a, b, c, d مکان‌های مقادیر عنصر بعدی x، در هر یک از لیست‌های ورودی است (فرض بر این است که نخستین مکان را با ۰ نشان می‌دهیم). با توجه به مرتب بودن لیست‌های ورودی، منظور از عنصر بعدی، عنصر بلافاصله بزرگ‌تر یا حد اقل مساوی با x است. (اگر چنین عنصری وجود نداشت، مکان بعد از آخرین خانهٔ لیست را، قرار داد می‌کنیم) در این صورت خواهیم داشت: L = ۱٫۱[۰٬۰٬۰٬۰], ۱٫۳[۰٬۰٬۰٬۱], ۲٫۳[۰٬۰٬۱٬۱], ۲٫۴[۰٬۱٬۱٬۱], ۲٫۵[۱٬۱٬۱٬۱], ۲٫۶[۱٬۲٬۱٬۱], ۳٫۵[۱٬۳٬۱٬۱], ۴٫۴[۱٬۳٬۱٬۲], ۴٫۶[۱٬۳٬۲٬۲], ۶٫۲[۱٬۳٬۲٬۳], ۶٫۴[۱٬۳٬۳٬۳], ۶٫۵[۲٬۳٬۳٬۳], ۶٫۶[۳٬۳٬۳٬۳], ۷٫۹[۳٬۳٬۴٬۳], ۸٫۰[۳٬۳٬۴٬۴], ۸٫۱[۴٬۳٬۴٬۴], ۹٫۳[۴٬۳٬۴٬۵] با این راه حل ادغامی یک پرس و جو در زمان (O(log n + k انجام می‌شود. با توجه به اینکه مکان هایx در هر لیست‌های ورودی، در لیست L عنصر x ذخیره شده‌اند، نتایج پس از جستجو به‌دست می‌آیند. لیست نهایی در این دنباله Mk است که برابر است با Lk، و هر لیست قبلی از ادغام Li با هر یک از به ازای هر عنصر x در این لیست ادغامی، ما دو عدد ذخیره می‌کنیم: مکانی که از جستجوی x در Li به دست می‌آید، و مکانی که از جستجوی x در Mi+۱ به‌دست می‌آید. با دقت بیشتر، جستجوی دودویی برای q در M۲ مقدار ۷٫۹[۳، ۵] در موقعیت ۵ یا مقدار۶٫۲[۳، ۳] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با ۶٫۲ و مشاهده اینکه کوچکتر است، ما می‌یابیم که نتیجه درست در M۲ , ۶٫۲[۳، ۳] است. اولین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که جستجو برای qدر L۲ باید L۲[۳] را برگرداند. به طور دقیق تر، جستجوی دودویی برای q در M۳ مقدار۶٫۲[۲، ۳] در موقعیت ۳ یا مقدار ۴٫۴[۱، ۲] یک مکان جلوتر را برمی‌گرداند. «۲» در۶٫۲[۲٬۳] به ما می‌گوید که جستجو برای qدر L۳ باید L۳[۲]=۶٫۲ را برگرداند و «۳» در ۶٫۲[۲٬۳] به ما می‌گوید که نتیجه جستجو برای q در M۴ برابر با M۴[۳] = ۷٫۹[۳٬۰] یا M۴[۲] = ۴٫۶[۲٬۰] است. با مقایسه q با ۴٫۶ نشان می‌دهد که نتیجه صحیح ۷٫۹[۳٬۰] است و نتیجه جستجو برای q در L۴ برابر L۴[۳] = ۷٫۹. است پس ما q را در هر یک از چهار لیست پیدا کردیم به‌وسیلهٔ جستجوی دوتایی در تک لیست M۱ همراه با یک مقایسه در هر لیست متواتر. به‌طور کلی تر برای هر ساختار داده از این نوع ما یک پرس و جو را به‌وسیلهٔ انجام یک جستجوی دودویی q در M۱ انجام می‌دهیم و با استفاده از مقدار نتیجه شده موقعیتq در L۱ را تعیین می‌کنیم. | ## بخش 2: آبشاره‌سازی جزءبه‌جزء | در مثال ما، لیست‌های آبشاره‌سازی جزءبه‌جزء شده، در مجموع ۲۵ عنصر دارند که مقداری کمتر از دو برابر ورودی اصلی است. که به سادگی اثبات می‌شود سایز داده ساختار حد اکثر ۲n است: (Σ|Mi| = Σ|Li|(۱ + ½ + ¼ +…) ≤ ۲n = O(n مسئلهٔ کلی به طور کلی، آبشاره‌سازی جزءبه‌جزء با گراف کاتالوگ آغاز می‌شود. گراف کاتالوگ گرافی جهت دار است که هر رأس آن با یک لیست مرتب شده برچسب گذاری شده‌است. هر پرس و جو در این داده ساختار، شامل یک مسیر از این گراف و یک مقدار q است و به ازای این دو، داده ساختار باید مشخص کند q در هر یک از لیست‌های مرتب شده‌ای که در رئوس مسیر داده شده قرار دارند، چندمین عنصر است. با استفاده از روش پویا (داینامیک)، امکان این وجود دارد که پاسخ رئوس بعدی یک مسیر را بر اساس نتایج جستجو در رئوس قبلی مسیر به دست آید. در این گراف به ازای مقدار ثابت d حداکثر تعداد یال‌های ورودی از هر رأس d و حد اقل تعداد یال‌های ورودی به هر رأس نیز d است. لیست‌های مربوط به هر رأس را، بر اساس همسایه‌های منتهی به یال‌های خروجی رأس، گسترش می‌دهیم. هر مورد، در هر لیست گسترش یافته، محل قرار گرفتن آن مورد را در لیست‌های گسترش نایافته‌ای که در همان رأس و در رأس‌های همسایهٔ منتهی به یال‌های خروجی، ذخیره شده‌اند، ذخیره می‌کند. به عنوان یک مثال ساده از این توضیحات، d=۱، و ما هر لیست را با ½ از همسایه‌هایش گسترش داده‌ایم: یک پرسش در این داده ساختار، شامل یک جستجوی دودویی عادی در لیست گسترش یافتهٔ مربوط به رأس اول از مسیر مورد پرس و جو، و علاوه بر آن، تعدادی جستجوی ساده‌تر، در هر یک از رئوس بعدی مسیر است. اگرکسر ۱/r از همسایه‌های یک رأس در گسترش دادن لیست آن استفاده شود، در آن صورت نتیجهٔ هر پرسش بعدی حداکثر در r مرحله، از روی مکان‌هایی که در پرسش‌های قبلی، در رئوس قبلی مسیر ذخیره شده‌است، به‌دست خواهد آمد و حتی ممکن است در زمانی ثابت و کوتاه، بدون انجام یک جستجوی دودویی کامل یافته شود. آبشاره‌سازی جزءبه‌جزء پویا در آبشاره‌سازی جزءبه‌جزء به صورت پویا، لیستی که در هر گره از گراف کاتالوگ ذخیره شده‌است، می‌تواند به صورت پویا تغییر کند. به عبارتی اجزای این لیست می‌توانند به روز شوند و یک عضو در آن درج شود یا از آن حذف گردد. یکی از مشکلاتی که در این زمینه وجود دارد این است که هنگام اضافه شدن یک عضو به یک گره یا حذف شدن عضوی از آن، تغییراتی در لیست مربوط به آن گره ایجاد می‌شود. از طرفی تغییر در یک لیست منجر به وجود آمدن تغییرات در سایر لیست‌ها در سایر گره‌ها نیز می‌گردد. برای حل این مشکل، به جای استفاده از یک آرایهٔ مرتب شده برای هر گره، از یک درخت دودویی جستجو استفاده می‌شود. با استفاده از درخت دودویی جستجو، امکان به روز رسانی سایر گره‌ها هنگام تغییر یک گره، با تعداد عملیاتی محدود فراهم می‌شود و همچنین توانایی جستجوی دودویی پابرجا باقی خواهد ماند. همان‌طور که پیش‌تر گفته شد، هر گره از گراف کاتالوگ، تعدادی از اعضای لیست همسایهٔ خود را نیز نگه‌داری می‌کند. به عبارتی در لیست یک گره، اعضایی که در مکان d از لیست همسایه قرار دارند نیز وجود دارد. در برخی شرایط با توجه به مقدار d و همچنین اعضای یک لیست، این امکان وجود دارد که با هر به روز رسانی و تغییر در یک لیست، لیست‌های همسایه نیز تغییر کنند. با استفاده از این روش، می‌توان اطمینان حاصل کرد که تعداد داده‌هایی که انتخاب می‌شوند، کمتر از کل داده‌های لیست تقسیم بر d است و همچنین این اعداد در مکان‌های ثابتی از لیست قرار دارند. این موضوع باعث می‌شود که انتقال تغییرات هنگام درج یا حذف برای یک لیست از یک گره، تعداد عملیاتی کمتر از یک تقسیم بر d نیاز داشته باشد. | ## بخش 3: آبشاره‌سازی جزءبه‌جزء | یعنی یک تغییر در یک گره، به طور میانگین حداکثر یک تقسیم بر d تغییر برای به روز رسانی سایر گره‌ها نیاز دارد. با این روش، توزیع داده‌ها در میان گره‌ها به گونه‌ای خواهد بود که میانگین تعداد عملیاتی که برای به روز رسانی درخت‌های جستجوی دودویی صورت می‌گیرد، عددی ثابت است. همان‌طور که پیش‌تر گفته شد، هر عضو از لیست موجود در یک گره، دو اندیس را نگه می‌دارد. یکی اندیس مربوط به جستجوی خودش در همان لیست و یکی اندیس مربوط به جستجوی آن عضو در لیست همسایه. نگه‌داری این اندیس‌ها به صورت پویا هزینه‌بر است، چراکه با تغییر یک عضو، تعداد اندیس‌هایی که در تمام لیست‌ها باید تغییر کند، عدد بسیار بزرگی خواهد بود. برای همین، در این مدل، داده ساختارهای دیگری برای ذخیره شدن در هر گره، در نظر گرفته می‌شود که به شرح زیر می‌باشند: یک نگاشت از اجزای لیست مربوط به یک گره، به اعداد صحیح کوچک؛ بنابراین برای بررسی ترتیب قرار گیری عناصر یک لیست، کافیست این اعداد صحیح نسبت داده شده به آن‌ها را با هم مقایسه کرد و با انجام عملیات بر عکس این نگاشت می‌توان از اعداد صحیح به اجزای اصلی لیست، دست یافت. روشی که Dietz در سال ۱۹۸۲ به آن دست یافت، راهکاری می‌دهد تا این نگاشت به صورت کارایی ذخیره شود؛ بنابراین هر گره، این نگاشت را ذخیره می‌کند و تنها با داشتن همین نگاشت می‌توان از اعضای لیست به لیستی از اعداد صحیح کوچک‌تر و برعکس دست یافت. با استفاده از این داده ساختار، می‌توان در میان اعداد صحیح نسبت داده شده به اعضای لیست، که طبق نگاشت گفته شده حاصل می‌شوند، به جستجوی عدد مورد نظر پرداخت. برای هر گره همسایه در گراف کاتالوگ، یک داده ساختار جستجوگر اعداد صحیح مشابه برای زیر مجموعه‌ای از اعداد به دست آمده از آن گره در نظر گرفته می‌شود. به وسیلهٔ این داده ساختار و نگاشت اعضای لیست به اعداد صحیح، به صورت مؤثر می‌توان هر عضو x لیست آن گره را در تعداد مراحل ثابت پیدا کرد. این داده ساختارها باعث می‌شوند که آبشاره‌سازی پویا در مرتبهٔ زمانی (O(log n برای هر درج و حذف عمل کند. کاربردها یکی از کاربردهایی که آبشاره‌سازی جزءبه‌جزء دارد، در داده ساختارهای جستجوی محدوده Range search که در هندسهٔ محاسباتی مورد استفاده قرار می‌گیرد، می‌باشد. آبشاره‌سازی جزءبه‌جزء به این مسئله کمک می‌کند تا عملیات جستجو برای شیب‌های مربوط به هر لایه در حافظهٔ مرتبهٔ (O(n و زمان (O(log n + h صورت گیرد که در آن h اندازهٔ زیرمجموعه‌هایی از نقاط است که مورد سؤال قرار می‌گیرد. با توجه به این مثال، کاربرد آبشاره‌سازی جزءبه‌جزء شامل تعدادی جستجوی دودویی در یک سری خطی از لیست‌ها (سری‌های تودرتو از لایه‌های محدب) می‌باشد؛ بنابراین گراف کاتالوگ در این حالت، فقط یک مسیر ساده خواهد بود. ناحیهٔ یکنواخت، بخشی از صفحه شامل تعدادی چندضلعی است که هر خط هرکدام از چندضلعی‌ها را در حداکثر دو نقطه قطع کند. سپس یک جستجوی دودویی بر روی این مسیرها باید زد تا مسیری را که در پایین‌ترین سطح قرار دارد و همچنین بالاتر از نقطهٔ مورد جستجو واقع شده‌است پیدا کرد. این موضوع که یک نقطه بالای یک مسیر قرار دارد یا پایین آن، با جستجوی دودویی قابل بررسی است. به عبارتی باید جستجویی بر روی مختصهٔ اول از هرکدام از نقاط مسیر داشت تا مقایسه کرد که نقطهٔ مورد بررسی زیر مسیر قرار دارد یا بالای آن؛ بنابراین برای جستجوهای دودویی که صورت می‌گیرد، می‌توان از آبشاره‌سازی جزءبه‌جزء استفاده کرد و سرعت را افزایش داد. با استفاده از این روش، مرتبهٔ زمانی انجام جستجو (O(log n خواهد بود و فضای (O(n از حافظه درگیر خواهد شد. در این حالت، گراف کاتالوگ یک گراف درخت خواهد بود که ترتیب‌های ممکن را برای جستجوی دودویی خارجی را می‌نمایاند. | ## جمع‌بندی | Gao et al نیز از آن به عنوان مدلی برای توزیع و بازیابی داده در حسگرهای شبکه‌ای استفاده کرده‌است.