فاصل الانفجار

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
الموسوعة الحرة

تُعدّ خوارزمية Burstsort ومشتقاتها خوارزميات فعّالة من حيث استخدام الذاكرة المؤقتة لفرز السلاسل النصية . وهي عبارة عن مشتقات من خوارزمية الفرز الجذري التقليدية، ولكنها أسرع في التعامل مع مجموعات البيانات الكبيرة من السلاسل النصية الشائعة، وقد نُشرت لأول مرة في عام 2003، مع نشر بعض الإصدارات المحسّنة في السنوات اللاحقة. [ 1 ]

تستخدم خوارزميات فرز Burstsort شجرة بحث (Trie) لتخزين بادئات السلاسل النصية، مع مصفوفات قابلة للتوسع من المؤشرات كعقد طرفية تحتوي على لواحق فريدة ومرتبة (تُسمى " الدلاء "). تقوم بعض المتغيرات بنسخ ذيول السلاسل النصية إلى الدلاء. عندما يتجاوز حجم الدلاء حدًا معينًا، يتم "تقسيمها" إلى أشجار بحث، ومن هنا جاء اسم الفرز. يستخدم متغير أحدث فهرس دلو مع دلاء فرعية أصغر لتقليل استهلاك الذاكرة. تعتمد معظم التطبيقات على فرز سريع متعدد المفاتيح، وهو امتداد لفرز سريع ثلاثي الاتجاهات، لفرز محتويات الدلاء. من خلال تقسيم المدخلات إلى دلاء ذات بادئات مشتركة، يمكن إجراء الفرز بطريقة فعالة من حيث استخدام الذاكرة المؤقتة.

طُرحت خوارزمية Burstsort كخوارزمية فرز مشابهة لخوارزمية MSD radix sort ، [ 1 ] ولكنها أسرع منها بفضل مراعاتها للتخزين المؤقت وتخزين الأسس ذات الصلة بالقرب من بعضها البعض نظرًا لخصائص بنية الشجرة. تستغل هذه الخوارزمية خصائص السلاسل النصية الشائعة في العالم الحقيقي. وعلى الرغم من أنها تُقارب خوارزمية radix sort من حيث التعقيد الزمني O ( wn ) ( حيث w طول الكلمة و n عدد السلاسل النصية المراد فرزها)، إلا أنها، بفضل توزيع الذاكرة الأفضل، تميل إلى أن تكون أسرع بمرتين عند التعامل مع مجموعات البيانات الكبيرة من السلاسل النصية. وقد وُصفت بأنها "أسرع خوارزمية معروفة لفرز مجموعات كبيرة من السلاسل النصية". [ 2 ]

مراجع

  • خوارزمية مشتقة من فرز الاندفاع (C-burstsort)، أسرع من فرز الاندفاع: سينها، رانجان؛ زوبيل، جاستن؛ رينغ، ديفيد (يناير 2006). "فرز السلاسل بكفاءة عالية باستخدام النسخ" (ملف PDF) . مجلة الخوارزميات التجريبية . 11 (1.2): 1.2. CiteSeerX 10.1.1.85.3498 . doi : 10.1145/1187436.1187439 . S2CID 3184411. مؤرشفة من الأصل (ملف PDF) بتاريخ 1 أكتوبر 2007. تم الاطلاع عليها بتاريخ 31 مايو 2007 .  
  • نوع البيانات المستخدم في خوارزمية فرز السلاسل المتتابعة: هاينز، ستيفن؛ زوبل، جاستن؛ ويليامز، هيو إي. (أبريل 2002). "أشجار السلاسل المتتابعة: بنية بيانات سريعة وفعالة لمفاتيح السلاسل النصية" (ملف PDF) . معاملات ACM لأنظمة المعلومات . 20 (2): 192-223 . CiteSeerX 10.1.1.18.3499 . doi : 10.1145/506309.506312 . S2CID 14122377. مؤرشف من الأصل (ملف PDF) بتاريخ 5 ديسمبر 2013. تم الاطلاع عليه بتاريخ 25 سبتمبر 2007 .  
  • سينها، رانجان؛ زوبيل، جاستن (2003). "فرز فعال لمجموعات كبيرة من السلاسل النصية باستخدام شجرة البحث" (ملف PDF) . وقائع المؤتمر الأسترالي السادس والعشرين لعلوم الحاسوب . المجلد  16. الجمعية الأسترالية للحاسوب. الصفحات 11-18 . CiteSeerX 10.1.1.12.2757 . ISBN   978-0-909-92594-9أُرشف من النسخة الأصلية (PDF) بتاريخ 8 فبراير 2012. تم الاطلاع عليه بتاريخ 25 سبتمبر 2007 .
  • سينها، رانجان؛ ويرث، أنتوني (مارس 2010). "هندسة فرز السلاسل المتتابعة: نحو فرز سريع للسلاسل في مكانها" (ملف PDF) . مجلة ACM للخوارزميات التجريبية . 15 (2.5): 1-24 . doi : 10.1145/1671970.1671978 . S2CID 16410080 .