مرتب‌سازی انفجاری
مرتب‌سازی انفجاری و گونه‌هایش الگوریتم‌های کارآمد در ذخیره‌گاه برای مرتب ساختن رشته‌ها هستند و از مرتب‌سازی سریع برای مجموعه بزرگی از داده‌ها سریع‌تر عمل می‌کنند. این الگوریتم نخستین بار در سال ۲۰۰۳ منتشر شد.
الگوریتم مرتب‌سازی انفجاری برای ذخیره کردن رشته‌ها از داده‌ساختار درخت پیشوندی انفجاری استفاده می‌کند.
داده ساختاری است که جهت ذخیره رشته‌ها مورد استفاده قرار می‌گیرد. این داده ساختار از سه مؤلفه اصلی تشکیل شده‌است: حاوی اطلاعاتی هستند که برنامه استفاده‌کننده از درخت پیشوندی انفجاری به آن احتیاج دارد؛ مانند محل قرار گرفتن رشته‌ها و همچنین اشاره‌گری جهت نگهداری ظرف‌هایی که آن رکورد را نگهداری می‌کنند. ظرف‌ها مجموعه کوچکی از رکوردها هستند که به صورت یک داده ساختار ساده مانند لیست یا درخت دودویی جستجو نگهداری می‌شوند. در یک ظرف به عمق formula_1، رشته‌ها دارای طول حداقل formula_1 هستند که formula_1 حرف ابتدایی آن‌ها یکسانند. هر ظرف دارای یک سرآیند است که جهت ذخیره‌سازی آمار مورد استفاده قرار گرفته در عملیات انفجار مورد استفاده قرار می‌گیرند. یک درخت پیشوندی است که برگ‌های آن ظرف هستند. هر گره از یک آرایه formula_4 به طول formula_5 از اشاره‌گرها که به یک گره دیگر یا یک ظرف اشاره می‌کنند، تشکیل شده‌است.
عملیاتی که درخت پیشوندی انفجاری پشتیبانی می‌کند عبارتند از:
جستجو در یک درخت پیشوندی انفجاری از دو گام مجزای زیر تشکیل شده‌است. ورودی این عملیات یک رشته formula_6 حرفی formula_7 و خروجی اشاره‌گری به یک رکورد یا در صورت جستجوی ناموفق اشاره‌گری به نال است.
- گام اول:
درخت پیشوندی دسترسی با توجه به حروف ابتدایی رشته مورد جستجو قرار گرفته طی می‌شود. شیء فعلی در مرحله اول برابر با ریشه درخت پیشوندی دسترسی و ارتفاع فعلی هم برابر با یک است. تا زمانی که شیء فعلی یکی از گره‌های درخت پیشوندی دسترسی است و ارتفاع formula_8 کمتر از formula_6 است:
الف) شیء فعلی را برابر با گره یا ظرف اشاره شده توسط formula_10 امین عنصر آرایه formula_4 قرار داده می‌شود،
ب) formula_8 یکی زیاد می‌شود.
اگر شیء فعلی گره درخت پیشوندی با ارتفاع formula_13 بود، شیء فعلی برابر با شیء اشاره شده توسط اشاره‌گر تهی (که برای سادگی می‌تواند یک ظرف حاوی صفر یا یک رکورد در نظر گرفته‌شود) قرار داده می‌شود. در غیر اینصورت، اگر شیء فعلی نال بود این رشته در درخت پیشوندی انفجاری وجود ندارد و جستجو خاتمه می‌یابد.
- گام دوم:
شیء فعلی یک ظرف معتبر است. اگر formula_14، از حروف باقی مانده formula_15 جهت جستجو در ظرف استفاده می‌شود که در صورت پیدا شدن رکورد مربوطه، آن رکورد و در غیر اینصورت نال برگردانده می‌شود؛ وگرنه شیء فعلی برابر با یک ظرف حاوی صفر یا یک رکورد است که توسط یک اشاره‌گر تهی در دسترس قرار گرفته‌است. در انتها چون تمامی رشته در پیمایش درخت پیشوندی مورد استفاده قرار گرفته‌است، این اشاره‌گر برگردانده می‌شود.
برای مثال، جهت جستجوی عبارت "came" در درخت پیشوندی شکل زیر، ابتدا اشاره‌گر را از خانه 'C' گره ریشه تا گره بعدی درخت پیشوندی دنبال می‌کنیم. سپس از خانه 'A' به چپ‌ترین ظرف آن می‌رویم و در آنجا به دنبال زیررشته "me" می‌گردیم. ظرف‌های ما به شکل داده ساختار درخت دودویی جستجو هستند؛ بنابراین در این مرحله از الگوریتم جستجوی یک رشته در یک درخت دودویی جستجو استفاده می‌کنیم.
با فرض اینکه قصد داریم یک رشته formula_6 حرفی formula_7 را در درخت پیشوندی انفجاری درج کنیم، دو گام باید پیموده شود:
- گام اول:
ابتدا باید ظرفی (با ارتفاع formula_1) که رکورد باید در آن درج شود را پیدا کنیم. اگر formula_19 بود، ظرف مورد نظر زیر اشاره‌گر تهی قرار گرفته‌است.
- گام دوم:
در غیر اینصورت اگر formula_20 بود، از الگوریتم معمول درج در داده ساختار ظرفمان (که برای مثال می‌تواند درخت دودویی جستجو باشد) جهت درج رکورد مربوطه استفاده می‌کنیم. این کار را با استفاده از حروف formula_21 رشته انجام می‌دهیم.
عملیات حذف در این داده ساختار کمی پیچیده‌تر از سایر عملیات است. برای حذف یک رکورد، ابتدا باید آن را جستجو کنیم، بیابیم و با استفاده از روش معمول حذف در داده ساختار ظرفمان آن را از ظرف حذف کنیم. اگر حذف باعث خالی شدن یک ظرف شود، گره‌ای که پدر آن ظرف است باید به‌روزرسانی شود. در صورتی که گره هیچ بچه‌ای نداشته باشد، از درخت پیشوندی انفجاری حذف می‌شود و این عملیات می‌تواند به‌طور بازگشتی تا ریشه ادامه پیدا کند.
به فرایند جایگزینی یک ظرف در عمق formula_1 با یک گره از درخت پیشوندی و مجموعه‌ای از ظرف‌های جدید در عمق formula_23 (که تمامی رکوردهای موجود در ظرف اصلی بین آن‌ها نگهداری می‌شود) انفجار گفته می‌شود. یک استراتژی موفق انفجار باید سریع پیدا شدن رشته‌های معمول بدون جستجوی اضافه در ظرف‌ها را تضمین کند. مدیریت مناسب ظرف‌ها می‌تواند در کاهش هزینه جستجو مؤثر واقع شود. باید توجه داشت که ظرف‌هایی که به ندرت در دسترس قرار می‌گیرند نباید منفجر شوند، زیرا ظرف‌ها باید در قیاس با گره‌ها از فضای موجود بهره بیشتری ببرند. انفجار با پیمودن سه گام زیر انجام می‌شود:
- گام اول:
یک گره جدید در درخت پیشوندی دسترسی با نام formula_24 ایجاد می‌شود و تمام اشاره‌گرهای آن به یک ظرف خالی اشاره می‌کنند.
- گام دوم:
برای هر رکورد formula_25 در ظرف اصلی،
الف) حرف اول آن رشته (formula_26) برداشته می‌شود، و
ب) این رکورد به ظرفی که پوینتر formula_26 گره b به آن اشاره می‌کند، اضافه می‌شود. در صورتی که رکورد یک رشته خالی بود، زیر اشاره‌گر تهی formula_24 افزوده می‌شود.
- گام سوم:
ظرف اصلی دور انداخته می‌شود.