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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی انفجاری
کلاس الگوریتم مرتب‌سازی
ساختمان داده‌ها آرایه، درخت پیشوندی، درخت جستجوی دودویی
عملکرد بدترین حالت

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

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

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

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

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

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

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

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

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

جستجو[ویرایش]

جستجو در یک درخت پیشوندی انفجاری از دو گام مجزای زیر[۴] تشکیل شده است. ورودی این عملیات یک رشته حرفی و خروجی اشاره‌گری به یک رکورد یا در صورت جستجوی ناموفق اشاره‌گری به نال است.

- گام اول:

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

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

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

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

- گام دوم:

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

مثال[ویرایش]

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

a simple burst trie

درج[ویرایش]

با فرض اینکه قصد داریم یک رشته حرفی را در درخت پیشوندی انفجاری درج کنیم، دو گام باید پیموده شود:

- گام اول:

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

- گام دوم:

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

حذف[ویرایش]

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

انفجار[ویرایش]

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

- گام اول:

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

- گام دوم:

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

الف) حرف اول آن رشته () برداشته می‌شود، و

ب) این رکورد به ظرفی که پوینتر گره b به آن اشاره می‌کند، اضافه می‌شود. در صورتی که رکورد یک رشته خالی بود، زیر اشاره‌گر تهی افزوده می‌شود.

- گام سوم:

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

جستارهای وابسته[ویرایش]

پانویس[ویرایش]

منابع[ویرایش]