مرتب‌سازی انفجاری

مرتب‌سازی انفجاری (به انگلیسی: Burstsort) و گونه‌هایش الگوریتم‌های کارآمد در ذخیره‌گاه برای مرتب ساختن رشته‌ها هستند و از مرتب‌سازی سریع برای مجموعه بزرگی از داده‌ها سریع‌تر عمل می‌کنند. این الگوریتم نخستین بار در سال ۲۰۰۳ منتشر شد.

مرتب‌سازی انفجاری

رده	الگوریتم مرتب‌سازی
ساختمان داده	آرایه، درخت پیشوندی، درخت جستجوی دودویی
کارایی بدترین حالت	$O(n\log n)$

الگوریتم مرتب‌سازی انفجاری برای ذخیره کردن رشته‌ها از داده‌ساختار درخت پیشوندی انفجاری استفاده می‌کند.

درخت پیشوندی انفجاری

داده ساختاری است که جهت ذخیره رشته‌ها مورد استفاده قرار می‌گیرد. این داده ساختار از سه مؤلفه اصلی تشکیل شده‌است:

• رکوردها (به انگلیسی: Records)

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

• ظرف‌ها (به انگلیسی: Containers)

ظرف‌ها مجموعه کوچکی از رکوردها هستند که به صورت یک داده ساختار ساده مانند لیست یا درخت دودویی جستجو نگهداری می‌شوند. در یک ظرف به عمق $k$، رشته‌ها دارای طول حداقل $k$ هستند که $k$ حرف ابتدایی آن‌ها یکسانند. هر ظرف دارای یک سرآیند است که جهت ذخیره‌سازی آمار مورد استفاده قرار گرفته در عملیات انفجار مورد استفاده قرار می‌گیرند.

• درخت پیشوندی دسترسی (به انگلیسی: Access Trie)

یک درخت پیشوندی است که برگ‌های آن ظرف هستند. هر گره از یک آرایه $p$ به طول $|A|$ از اشاره‌گرها که به یک گره دیگر یا یک ظرف اشاره می‌کنند، تشکیل شده‌است.

عملیاتی که درخت پیشوندی انفجاری پشتیبانی می‌کند عبارتند از:

جستجو

جستجو در یک درخت پیشوندی انفجاری از دو گام مجزای زیر تشکیل شده‌است. ورودی این عملیات یک رشته $n$ حرفی $c_{1}...c_{n}$ و خروجی اشاره‌گری به یک رکورد یا در صورت جستجوی ناموفق اشاره‌گری به نال است.

- گام اول:

درخت پیشوندی دسترسی با توجه به حروف ابتدایی رشته مورد جستجو قرار گرفته طی می‌شود. شیء فعلی در مرحله اول برابر با ریشه درخت پیشوندی دسترسی و ارتفاع فعلی هم برابر با یک است. تا زمانی که شیء فعلی یکی از گره‌های درخت پیشوندی دسترسی است و ارتفاع $i$ کمتر از $n$ است:

الف) شیء فعلی را برابر با گره یا ظرف اشاره شده توسط $c_{i}$ امین عنصر آرایه $p$ قرار داده می‌شود،

ب) $i$ یکی زیاد می‌شود.

اگر شیء فعلی گره درخت پیشوندی با ارتفاع $i=n+1$ بود، شیء فعلی برابر با شیء اشاره شده توسط اشاره‌گر تهی (که برای سادگی می‌تواند یک ظرف حاوی صفر یا یک رکورد در نظر گرفته‌شود) قرار داده می‌شود. در غیر اینصورت، اگر شیء فعلی نال بود این رشته در درخت پیشوندی انفجاری وجود ندارد و جستجو خاتمه می‌یابد.

- گام دوم:

شیء فعلی یک ظرف معتبر است. اگر $i<=n$، از حروف باقی مانده $c_{i}...c_{n}$ جهت جستجو در ظرف استفاده می‌شود که در صورت پیدا شدن رکورد مربوطه، آن رکورد و در غیر اینصورت نال برگردانده می‌شود؛ وگرنه شیء فعلی برابر با یک ظرف حاوی صفر یا یک رکورد است که توسط یک اشاره‌گر تهی در دسترس قرار گرفته‌است. در انتها چون تمامی رشته در پیمایش درخت پیشوندی مورد استفاده قرار گرفته‌است، این اشاره‌گر برگردانده می‌شود.

مثال

برای مثال، جهت جستجوی عبارت "came" در درخت پیشوندی شکل زیر، ابتدا اشاره‌گر را از خانه 'C' گره ریشه تا گره بعدی درخت پیشوندی دنبال می‌کنیم. سپس از خانه 'A' به چپ‌ترین ظرف آن می‌رویم و در آنجا به دنبال زیررشته "me" می‌گردیم. ظرف‌های ما به شکل داده ساختار درخت دودویی جستجو هستند؛ بنابراین در این مرحله از الگوریتم جستجوی یک رشته در یک درخت دودویی جستجو استفاده می‌کنیم.

a simple burst trie

درج

با فرض اینکه قصد داریم یک رشته $n$ حرفی $c_{1}...c_{n}$ را در درخت پیشوندی انفجاری درج کنیم، دو گام باید پیموده شود:

- گام اول:

ابتدا باید ظرفی (با ارتفاع $k$) که رکورد باید در آن درج شود را پیدا کنیم. اگر $k=n+1$ بود، ظرف مورد نظر زیر اشاره‌گر تهی قرار گرفته‌است.

- گام دوم:

در غیر اینصورت اگر $k<=n$ بود، از الگوریتم معمول درج در داده ساختار ظرفمان (که برای مثال می‌تواند درخت دودویی جستجو باشد) جهت درج رکورد مربوطه استفاده می‌کنیم. این کار را با استفاده از حروف $c_{k+1}...c_{n}$ رشته انجام می‌دهیم.

حذف

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

انفجار

به فرایند جایگزینی یک ظرف در عمق $k$ با یک گره از درخت پیشوندی و مجموعه‌ای از ظرف‌های جدید در عمق $k+1$ (که تمامی رکوردهای موجود در ظرف اصلی بین آن‌ها نگهداری می‌شود) انفجار گفته می‌شود. یک استراتژی موفق انفجار باید سریع پیدا شدن رشته‌های معمول بدون جستجوی اضافه در ظرف‌ها را تضمین کند. مدیریت مناسب ظرف‌ها می‌تواند در کاهش هزینه جستجو مؤثر واقع شود. باید توجه داشت که ظرف‌هایی که به ندرت در دسترس قرار می‌گیرند نباید منفجر شوند، زیرا ظرف‌ها باید در قیاس با گره‌ها از فضای موجود بهره بیشتری ببرند. انفجار با پیمودن سه گام زیر انجام می‌شود:

- گام اول:

یک گره جدید در درخت پیشوندی دسترسی با نام $b$ ایجاد می‌شود و تمام اشاره‌گرهای آن به یک ظرف خالی اشاره می‌کنند.

- گام دوم:

برای هر رکورد $r$ در ظرف اصلی،

الف) حرف اول آن رشته ($c_{k+1}$) برداشته می‌شود، و

ب) این رکورد به ظرفی که پوینتر $c_{k+1}$ گره b به آن اشاره می‌کند، اضافه می‌شود. در صورتی که رکورد یک رشته خالی بود، زیر اشاره‌گر تهی $b$ افزوده می‌شود.

- گام سوم:

ظرف اصلی دور انداخته می‌شود.

جستارهای وابسته

• درخت پیشوندی
• درخت جستجوی دودویی

پانویس

• مشارکت‌کنندگان ویکی‌پدیا. «Burstsort». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۴ اسفند ۱۳۹۲.

منابع

• https://en.wikipedia.org/wiki/Burstsort
• Heinz Steen,"Burst Tries: A Fast Burst Tries: A Fast, Efficient Data Structure for String Keys", RMIT University, PT:2۲ آوریل ۲۰۱۰
• The data type used in burstsort: Heinz, Steffen; Zobel, Justin; Williams, Hugh E. (April 2002). "Burst Tries: A Fast, Efficient Data Structure for String Keys" (PDF). ACM Transactions on Information Systems. 20 (2): 192–223. CiteSeerX 10.1.1.18.3499. doi:10.1145/506309.506312. Archived from the original (PDF) on 5 December 2013. Retrieved 31 May 2017.