> bwt | تحويل | ضغط <
// Burrows-Wheeler Transform - تحويل نص قابل للعكس لتحسين الضغط
>> المزايا
قابل للعكس بالكامل
تحويل بلا فقدان يمكن عكسه واسترجاع النص الأصلي بدقة.
تجميع الأحرف
يجمع الأحرف المتشابهة معاً ليجعل الناتج أسهل في الضغط بواسطة خوارزميات لاحقة.
نواة bzip2
جزء أساسي من عائلة خوارزميات الضغط المبنية على bzip2.
>> معلومات تقنية
كيف يعمل BWT
تحويل بوروز ويلر ينشئ جميع الدورانات الدورية لسلسلة الإدخال، ثم يرتبها ترتيباً معجمياً ويأخذ العمود الأخير من المصفوفة المرتبة مع مؤشر السطر الأصلي. هذا يكوّن كتل من أحرف متشابهة، ما يجعل البيانات الناتجة قابلة للضغط بشكل ممتاز باستخدام RLE أو Move-to-Front أو مرمّزات أخرى.
مثال BWT
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
لماذا نستخدم BWT
- يحسن قابلية البيانات للضغط
- قابل للعكس بالكامل دون فقدان
- يجمع السياقات المتشابهة في كتل
- أساس خوارزمية الضغط bzip2
- تمهيد فعّال قبل خطوات الضغط الأخرى
>> أسئلة شائعة
ما هو تحويل بوروز ويلر؟
تحويل بوروز ويلر (BWT) خوارزمية قابلة للعكس تعيد ترتيب سلسلة من الأحرف لتوليد سلاسل تحتوي على كتل من الرموز المتكررة. طُرحت عام 1994 من قبل مايكل بوروز وديفيد ويلر وتستخدم كخطوة تمهيدية في برامج ضغط مثل bzip2 لتحسين نسبة الضغط.
لماذا يحسن BWT الضغط؟
يقوم BWT بتجميع الأحرف التي تظهر في سياقات متشابهة بحيث تظهر العديد من تكرارات الحرف نفسه متجاورة في الخرج. هذه الكتل تضغط بكفاءة باستخدام ترميز طول التشغيل أو Move-to-Front أو مرمّزات إنتروبية مثل هوفمان.
ما هي علامة EOF؟
علامة EOF (نهاية الملف)، وغالباً ما تكون الرمز '$' أو حرفاً فريداً آخر، تضمن أن كل الدورانات مميزة وتساعد على تحديد موضع السلسلة الأصلية. من دونها قد لا تكون لبعض السلاسل تمثيلات فريدة. عند عكس التحويل تتم إزالة علامة EOF.
هل BWT خوارزمية ضغط كاملة بحد ذاتها؟
لا. BWT ليست ضاغطاً مستقلاً، بل تحويل يجعل البيانات أكثر قابلية للضغط. عادةً ما تُستخدم مع Move-to-Front و RLE وترميز هوفمان في مخططات مثل bzip2.