جدول المحتويات:
تعريف - ماذا يعني تحويل الجحور ويلر (BWT)؟
يُعد تحويل Burrows-Wheeler (BWT) خوارزمية تأخذ كتل من البيانات ، مثل السلاسل ، وتعيد ترتيبها في مجموعات أحرف متشابهة. بعد التحويل ، تحتوي كتلة الإخراج على نفس عناصر البيانات الدقيقة قبل أن تبدأ ، ولكنها تختلف في الترتيب. تميل طبيعة الخوارزمية إلى وضع أحرف متشابهة بجانب بعضها البعض ، مما يجعل ضغط البيانات الناتجة أسهل. وبالتالي يتم استخدامه في العديد من خوارزميات الضغط.
تيكوبيديا تشرح تحول الجحور (BWT)
تعد خوارزمية تحويل Burrows-Wheeler خوارزمية جديدة نسبيًا تم اختراعها عام 1994 من قِبل Michael Burrows و David Wheeler واستنادا إلى تحول غير منشور اكتشفه Wheeler في عام 1983 ، والذي نشر في ورقته "خوارزمية ضغط البيانات المفقودة بلا خسارة."
في معظمها الأساسي ، تأخذ BWT مجموعة من البيانات مثل سلسلة ، وتضيف حرفًا EOF ، ثم تقوم بترتيب جميع دورات هذه السلسلة في ترتيب معجمي. يوضح الكود الكاذب أو الخطوات التالية الخوارزمية:
- قم بإنشاء جدول يحتوي على صفوف تمثل جميع التدويرات الممكنة بزيادة واحدة في السلسلة.
- فرز جميع الصفوف أبجديا.
- إخراج العمود الأخير من الجدول.
على سبيل المثال: كلمة "banana" ؛ إضافة حرف EOF يحولها إلى "banana $" ثم نطبق الخوارزمية:
1. قم بإنشاء جدول به صفوف تمثل جميع الدورات الممكنة:
الموز $
آنيانا $ ب
نانا $ با
آنا $ الحظر
غ $ البنا
و$ البنان
$ الموز
2. فرز الصفوف أبجديًا / معجميًا وفقًا للعمود الأول:
$ الموز
و$ البنان
آنا $ الحظر
آنيانا $ ب
الموز $
نانا $ با
غ $ البنا
3.Return العمود الأخير كإخراج BWT: annb $ aa
من السهل ضغط السلسلة الناتجة لأن الحروف المتكررة يتم تجميعها بجانب بعضها البعض. ولكن يجب أن تكون هناك بيانات إضافية مخزنة مع البيانات المحولة بحيث يمكن إجراء تحول عكسي. على الرغم من أن البيانات المحولة الناتجة أكبر من شكلها الأصلي ، إلا أن خاصية قابليتها للضغط تزداد بعدة أضعاف ، مما يجعلها أساسًا "مجانية" لتحسين كفاءة أساليب الضغط.
