bzip2

bzip2 هو تنسيق ملفات وبرنامج لضغط الملفات . يستخدم البرنامج خوارزمية Burrows-Wheeler لضغط وفك ضغط ملف واحد باستخدام تنسيق ملفات bzip2 . libbzip2 هي مكتبة برمجية لضغط البيانات بدون فقدان، يستخدمها برنامج bzip2.

برنامج bzip2 ليس برنامجًا لضغط الملفات ، وبالتالي يعتمد على أدوات خارجية منفصلة مثل تلك tarالمستخدمة في مهام مثل التعامل مع ملفات متعددة، وأدوات أخرى للتشفير وتقسيم الأرشيف.

تم إصدار برنامج bzip2 لأول مرة عام 1996 (وكان يُسمى في الأصل bzip ^{[ 1 ] [ 5 ]} ) بواسطة جوليان سيوارد . يضغط هذا البرنامج معظم الملفات بكفاءة أعلى من خوارزميات الضغط القديمة LZW و Deflate ، ولكنه أبطأ. يتميز bzip2 بكفاءته العالية في ضغط البيانات النصية، كما أن عملية فك الضغط سريعة نسبيًا. يستخدم البرنامج عدة طبقات من تقنيات الضغط، مثل ترميز طول التشغيل (RLE)، وتحويل بوروز-ويلر (BWT)، وتحويل النقل إلى المقدمة (MTF)، وتشفير هوفمان . يضغط bzip2 البيانات في كتل يتراوح حجمها بين 100 و900 كيلوبايت، ويستخدم تحويل بوروز-ويلر لتحويل تسلسلات الأحرف المتكررة إلى سلاسل من الأحرف المتطابقة. ثم يتم تطبيق تحويل النقل إلى المقدمة وتشفير هوفمان. أداء الضغط غير متماثل، حيث تكون عملية فك الضغط أسرع من عملية الضغط.

لقد مرّت الخوارزمية بالعديد من القائمين على صيانتها منذ إصدارها الأولي، حيث تولى ميكا سنايدر مهمة صيانتها منذ يونيو 2021. وقد طرأت بعض التعديلات على الخوارزمية، مثل pbzip2 و lbzip2، والتي تستخدم تعدد الخيوط لتحسين سرعة الضغط على أجهزة الكمبيوتر متعددة المعالجات ومتعددة النوى.

يُعد bzip2 مناسبًا للاستخدام في تطبيقات البيانات الضخمة مع أطر الحوسبة العنقودية مثل Hadoop و Apache Spark ، حيث يمكن فك ضغط الكتلة المضغوطة دون الحاجة إلى معالجة الكتل السابقة.

تحاول أداة bzip2recover المرفقة استعادة الأجزاء القابلة للقراءة من بيانات bzip2 التالفة. وتعمل هذه الأداة عن طريق البحث عن كتل فردية وتفريغها في ملفات منفصلة. ^{[ 6 ]}

يستخدم برنامج bzip2 عدة طبقات من تقنيات الضغط المكدسة فوق بعضها البعض، والتي تحدث بالترتيب التالي أثناء الضغط وبالترتيب العكسي أثناء فك الضغط:

1. ترميز طول التشغيل (RLE) للبيانات الأولية.
2. تحويل بوروز-ويلر (BWT)، أو فرز الكتل.
3. تحويل النقل إلى المقدمة (MTF).
4. ترميز طول التشغيل (RLE) لنتيجة MTF.
5. ترميز هوفمان .
6. الاختيار بين جداول هوفمان المتعددة.
7. ترميز أحادي الأساس 1 لاختيار جدول هوفمان.
8. ترميز دلتا (Δ) لأطوال بتات ترميز هوفمان.
9. مصفوفة بتات متفرقة توضح الرموز المستخدمة.

يتم استبدال أي تسلسل من 4 إلى 255 رمزًا متكررًا متتاليًا بأول 4 رموز وطول تكرار يتراوح بين 0 و251. وبالتالي، AAAAAAABBBBCCCDيتم استبدال التسلسل بـ AAAA\3BBBB\0CCCD، حيث يمثل \3و \0القيمتين 3 و0 على التوالي. يتم تحويل سلاسل الرموز دائمًا بعد 4 رموز متتالية، حتى لو تم ضبط طول السلسلة على الصفر، للحفاظ على إمكانية عكس التحويل.

في أسوأ الأحوال، قد يتسبب ذلك في زيادة قدرها 1.25، وفي أفضل الأحوال، في انخفاض إلى أقل من 0.02. وبينما تسمح المواصفات نظريًا بتشفير سلاسل بطول 256-259، فإن المُشفِّر المرجعي لن يُنتج مثل هذا الناتج.

ذكر مؤلف برنامج bzip2 أن خطوة RLE كانت خطأً تاريخياً، وكان الهدف منها فقط حماية تطبيق BWT الأصلي من الحالات المرضية. ^{[ 11 ]}

يُعد تحويل بوروز-ويلر عملية فرز كتلي قابلة للعكس، وهي جوهر برنامج bzip2. الكتلة مكتفية ذاتيًا تمامًا، حيث يظل حجم مخزني الإدخال والإخراج متساويًا - في bzip2، يبلغ الحد الأقصى لحجم هذه المرحلة 900 كيلوبايت. لفرز الكتل، تُنشأ مصفوفة (افتراضية)، يحتوي صفها i على كامل المخزن المؤقت، مُدارًا ليبدأ من الرمز i . بعد التدوير، تُفرز صفوف المصفوفة أبجديًا (رقميًا). يُخزن مؤشر 24 بت يُشير إلى موضع البداية عندما تكون الكتلة غير مُحوّلة. عمليًا، ليس من الضروري إنشاء المصفوفة كاملةً؛ بل يُجرى الفرز باستخدام مؤشرات لكل موضع في المخزن المؤقت. مخزن الإخراج هو العمود الأخير من المصفوفة؛ يحتوي هذا المخزن على كامل المخزن المؤقت، ولكن مُعاد ترتيبه بحيث يُحتمل أن يحتوي على سلاسل طويلة من الرموز المتطابقة.

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

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

تُستبدل سلاسل الأصفار الطويلة في مخرجات تحويل النقل إلى المقدمة (الناتجة عن الرموز المتكررة في مخرجات تحويل المويجات الثنائية) بتسلسل من رمزين خاصين، RUNA وRUNB، يُمثلان طول التسلسل كرقم ثنائي. لا تُشفّر الأصفار الفعلية في المخرجات؛ إذ يُصبح الصفر الوحيد رمز RUNA. (تُنفّذ هذه الخطوة في الواقع بالتزامن مع تحويل النقل إلى المقدمة؛ فعندما يُنتج تحويل النقل إلى المقدمة صفرًا، فإنه يزيد عدادًا للتشفير باستخدام RUNA وRUNB).

0, 0, 0, 0, 0, 1يُمثَّل التسلسل بالرمز RUNA, RUNB, 1; RUNA, RUNBحيث يُمثِّل القيمة 5 كما هو موضح أدناه. ينتهي ترميز طول التشغيل بالوصول إلى رمز عادي آخر. تُعدّ عملية RLE هذه أكثر مرونة من خطوة RLE الأولية، إذ يُمكنها ترميز أعداد صحيحة طويلة كيفما تشاء (عمليًا، عادةً ما يكون هذا محدودًا بحجم الكتلة، بحيث لا تُرمِّز هذه الخطوة سلسلة أطول من 5).900,000 بايت  ). يتم ترميز طول التشغيل بهذه الطريقة: يتم تعيين قيم مكانية 1 للبت الأول، و2 للثاني، و4 للثالث، وهكذا في التسلسل، ثم يتم ضرب كل قيمة مكانية في خانة RUNB في 2، وجمع جميع القيم المكانية الناتجة (لقيم RUNA وRUNB على حد سواء). هذا مشابه للترقيم الثنائي التقابلي . وبالتالي ، ينتج عن التسلسل RUNA, RUNBالقيمة (1 + 2 × 2) = 5. كمثال أكثر تعقيدًا:

رونا رونب رونا رونا رونب (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49

تستبدل هذه العملية الرموز ذات الطول الثابت (من 0 إلى 258) برموز متغيرة الطول بناءً على تكرار استخدامها. تصبح الرموز الأكثر استخدامًا أقصر (2-3 بتات)، بينما يمكن تخصيص ما يصل إلى 20 بتًا للرموز النادرة. ويتم اختيار الرموز بعناية فائقة لضمان عدم الخلط بين أي تسلسل بتات ورمز آخر.

يُعدّ رمز نهاية التدفق مثيرًا للاهتمام بشكل خاص. إذا استُخدمت n بايتات (رموز) مختلفة في البيانات غير المضغوطة، فسيتألف رمز هوفمان من رمزي RLE (RUNA وRUNB)، و n - 1 رمزًا، ورمز واحد لنهاية التدفق. نظرًا للنتيجة المُجمعة لترميزي MTF وRLE في الخطوتين السابقتين، فلا حاجة أبدًا للإشارة صراحةً إلى الرمز الأول في جدول MTF (إذ ستكون قيمته صفرًا في MTF العادي)، مما يوفر رمزًا واحدًا لعلامة نهاية التدفق (ويُفسر سبب ترميز n - 1 رمزًا فقط في شجرة هوفمان). في الحالة القصوى حيث يُستخدم رمز واحد فقط في البيانات غير المضغوطة، لن يكون هناك أي رموز في شجرة هوفمان، وستتألف الكتلة بأكملها من RUNA وRUNB (مع تكرار البايت الواحد ضمنيًا) وعلامة نهاية التدفق بقيمة 2.

0: رونا،

1: RUNB،

2–257: قيم البايت 0–255،

258: نهاية التدفق، إنهاء المعالجة (قد يكون منخفضًا يصل إلى 2).

يمكن استخدام عدة جداول هوفمان متطابقة الحجم مع كتلة واحدة إذا كانت الفائدة المرجوة من استخدامها تفوق تكلفة إضافة جدول إضافي. يمكن أن يتراوح عدد الجداول بين جدولين وستة جداول، مع إعادة اختيار الجدول الأنسب قبل معالجة كل 50 رمزًا. يتميز هذا الأسلوب بديناميكية هوفمان سريعة الاستجابة دون الحاجة إلى توفير جداول جديدة باستمرار، كما هو الحال في DEFLATE . صُمم ترميز طول التشغيل في الخطوة السابقة لمعالجة الرموز التي يكون احتمال استخدامها العكسي أعلى من أقصر رمز هوفمان مستخدم.

في حال استخدام عدة جداول هوفمان، يتم اختيار كل جدول (مرقمة من 0 إلى 5) من قائمة باستخدام سلسلة بتات منتهية بصفر، يتراوح طولها بين 1 و6 بتات. ويتم الاختيار في قائمة MTF للجداول. ينتج عن استخدام هذه الميزة توسع أقصى يبلغ حوالي 1.015، ولكنه عادةً ما يكون أقل. من المرجح أن يتضاءل هذا التوسع بشكل كبير أمام ميزة اختيار جداول هوفمان الأكثر ملاءمة، ويتم تمثيل الحالة الشائعة المتمثلة في الاستمرار باستخدام جدول هوفمان نفسه ببت واحد. بدلاً من التشفير الأحادي، يُعد هذا في الواقع شكلاً متطرفاً من شجرة هوفمان، حيث يكون لكل رمز نصف احتمال الرمز السابق.

تُعدّ أطوال بتات ترميز هوفمان ضرورية لإعادة بناء كل جدول من جداول هوفمان الأساسية المستخدمة . يُخزّن طول كل بت كفرق مُشفّر عن طول بتات الترميز السابق. يعني البت الصفري (0) أنه يجب تكرار طول البت السابق للترميز الحالي، بينما يعني البت الواحد (1) أنه يجب قراءة بت إضافي وزيادة طول البت أو إنقاصه بناءً على تلك القيمة. في الحالة الشائعة، يُستخدم بت واحد لكل رمز في كل جدول، وفي أسوأ الحالات - الانتقال من الطول 1 إلى الطول 20 - يتطلب الأمر حوالي 37 بتًا. نتيجةً لترميز MTF السابق، تبدأ أطوال الترميز من 2-3 بتات (وهي رموز شائعة الاستخدام) وتزداد تدريجيًا، مما يعني أن تنسيق دلتا فعّال إلى حد كبير، حيث يتطلب حوالي 300 بت (38 بايت) لكل جدول هوفمان كامل.

تُستخدم خريطة بتات لتوضيح الرموز المستخدمة داخل الكتلة والتي يجب تضمينها في أشجار هوفمان. من المرجح أن تستخدم البيانات الثنائية جميع الرموز الـ 256 التي يمكن تمثيلها بواسطة بايت واحد، بينما قد تستخدم البيانات النصية مجموعة فرعية صغيرة فقط من القيم المتاحة، ربما تغطي نطاق ASCII بين 32 و126. سيكون تخزين 256 بتًا صفريًا غير فعال إذا كانت غير مستخدمة في الغالب. لذلك ، تُستخدم طريقة متفرقة : تُقسم الرموز الـ 256 إلى 16 نطاقًا، ولا يتم تضمين مصفوفة 16 بت إلا إذا كانت الرموز مستخدمة داخل تلك الكتلة. يُشار إلى وجود كل نطاق من هذه النطاقات الـ 16 بمصفوفة بتات إضافية 16 بت في البداية. تستخدم خريطة البتات الإجمالية ما بين 32 و272 بتًا من مساحة التخزين (4-34 بايتًا). على النقيض من ذلك، تُظهر خوارزمية DEFLATE غياب الرموز عن طريق ترميز الرموز على أنها ذات طول بت صفري باستخدام ترميز طول التشغيل وترميز هوفمان إضافي.

لا توجد مواصفات رسمية لـ bzip2، على الرغم من أنه تم استخلاص مواصفات غير رسمية من التنفيذ المرجعي. ^{[ 12 ]}

بشكل عام، .bz2يتكون التدفق من رأسية بحجم 4 بايت، متبوعة بصفر أو أكثر من الكتل المضغوطة، ثم علامة نهاية التدفق التي تحتوي على رمز التحقق الدوري (CRC) ذي 32 بت للنص الأصلي للتدفق بأكمله. تتم محاذاة الكتل المضغوطة على مستوى البتات ولا يتم إضافة أي حشو.

.magic:16 = 'BZ' التوقيع/الرقم السحري .version:8 = 'h' لـ Bzip2 (ترميز 'H'uffman)، '0' لـ Bzip1 (مهمل) حجم الكتلة .hundred_k_blocksize:8 = '1'..'9' حجم الكتلة 100 كيلوبايت - 900 كيلوبايت (غير مضغوط) .compressed_magic:48 = 0x314159265359 (BCD (pi)) .crc:32 = مجموع التحقق لهذا الجزء .randomised:1 = 0=>عادي، 1=>عشوائي (مهمل) .origPtr:24 = مؤشر البداية في BWT لما بعد إلغاء التحويل .huffman_used_map:16 = خريطة بتية، لنطاقات من 16 بايت، موجودة/غير موجودة .huffman_used_bitmaps:0..256 = خريطة بتية، للرموز المستخدمة، موجودة/غير موجودة (مضاعفات العدد 16) .huffman_groups:3 = 2..6 عدد جداول هوفمان المختلفة المستخدمة .selectors_used:15 = عدد مرات تبديل جداول هوفمان (كل 50 رمزًا) *.selector_list:1..6 = سلاسل بتات منتهية بصفر (0..62) من جدول هوفمان MTF (*selectors_used) .start_huffman_length:5 = 0..20 طول البتات الابتدائي لـ Huffman delta *.delta_bit_length:1..40 = 0 => الرمز التالي؛ 1 => تغيير الطول { 1=> إنقاص الطول؛ 0=> زيادة الطول } (*(الرموز+2)*المجموعات) .contents:2..∞ = دفق بيانات مشفر باستخدام هوفمان حتى نهاية الكتلة (بحد أقصى 7372800 بت) .eos_magic:48 = 0x177245385090 (BCD sqrt(pi)) .crc:32 = مجموع التحقق للتدفق بأكمله .padding:0..7 = محاذاة إلى البايت الكامل 

بسبب ضغط RLE في المرحلة الأولى (انظر أعلاه)، يبلغ الحد الأقصى لطول النص الأصلي الذي  يمكن أن يحتويه ملف bzip2 واحد بحجم 900 كيلوبايت حوالي 46  ميجابايت (45,899,236  بايت). يحدث هذا إذا كان النص الأصلي بأكمله يتكون من قيم متكررة ( .bz2في هذه الحالة، يكون طول الملف الناتج 46  بايت). ويمكن الحصول على ملف أصغر حجمًا يبلغ 40  بايت باستخدام مدخلات تحتوي على القيمة 251 فقط، بنسبة ضغط ظاهرية تبلغ 1147480.9:1.

يمكن فك ضغط كتلة مضغوطة في bzip2 دون الحاجة إلى معالجة الكتل السابقة. وهذا يعني إمكانية فك ضغط ملفات bzip2 بالتوازي، مما يجعلها صيغة مناسبة للاستخدام في تطبيقات البيانات الضخمة مع أطر الحوسبة العنقودية مثل Hadoop و Apache Spark . ^{[ 13 ]}

يضغط برنامج bzip2 معظم الملفات بكفاءة أعلى من خوارزميات الضغط القديمة LZW ( ملفات بامتداد .Z ) و Deflate ( ملفات بامتدادي .zip و .gz )، ولكنه أبطأ بكثير. أما برنامج LZMA فهو أكثر كفاءة في استخدام المساحة من bzip2، ولكنه أبطأ في سرعة الضغط، مع سرعة أكبر في فك الضغط. ^{[ 14 ]}

يضغط برنامج bzip2 البيانات في كتل يتراوح حجمها بين 100 و900 كيلوبايت ، ويستخدم تحويل بوروز-ويلر لتحويل تسلسلات الأحرف المتكررة إلى سلاسل من الأحرف المتطابقة. ثم يطبق تحويل نقل الأحرف إلى المقدمة وتشفير هوفمان . كان برنامج bzip، سلف bzip2 ، يستخدم التشفير الحسابي بدلاً من تشفير هوفمان، وذلك بسبب قيود براءة اختراع البرمجيات . ^{[ 15 ]} أما برنامج bzip3، ^{[ 16 ]} وهو برنامج ضغط حديث يشترك مع bzip2 في الأصل ومجموعة الخوارزميات، فقد عاد إلى استخدام التشفير الحسابي.

أداء bzip2 غير متناظر، حيث أن فك الضغط سريع نسبيًا. ونظرًا للوقت الطويل اللازم للضغط، تم إنشاء نسخة معدلة في عام 2003 تُسمى pbzip2، والتي استخدمت تعدد الخيوط لترميز الملف في أجزاء متعددة، مما أدى إلى تسريع شبه خطي على أجهزة الكمبيوتر متعددة المعالجات ومتعددة النوى. ^{[ 17 ]} اعتبارًا من مايو 2010 لم يتم دمج هذه الوظيفة في المشروع الرئيسي.

على غرار gzip ، يُعدّ bzip2 مجرد أداة لضغط البيانات. فهو ليس برنامجًا للأرشفة مثل tar أو ZIP؛ إذ لا يدعم تنسيق ملف bzip2 تخزين محتويات ملفات متعددة في ملف مضغوط واحد، كما أن البرنامج نفسه لا يمتلك أي إمكانيات للتعامل مع ملفات متعددة، أو التشفير، أو تقسيم الأرشيف. في نظام يونكس ، كان بالإمكان أرشفة الملفات بواسطة برنامج منفصل يُنشئ أرشيفًا ثم يُضغط باستخدام bzip2، وفك ضغطها عن طريق قيام bzip2 بفك ضغط ملف الأرشيف المضغوط، ثم يقوم برنامج منفصل بفك ضغطه. بعض برامج الأرشفة تدعم الضغط وفك الضغط بشكل مدمج، مما يُغني عن استخدام برنامج bzip2 لضغط الأرشيف أو فك ضغطه. كما يدعم GnuPG أيضًا ضغط وفك ضغط bzip2 بشكل مدمج.

• مقارنة تنسيقات الأرشيف
• مقارنة بين برامج أرشفة الملفات
• قائمة تنسيقات الأرشيف
• قائمة برامج أرشفة الملفات
• rzip

• أمر bzip2 - من مشروع معلومات لينكس (LINFO)
• bzip2 لنظام التشغيل ويندوز
• تمت أرشفة MacBzip2 في 6 فبراير 2005 على Wayback Machine (لنظام التشغيل Mac OS الكلاسيكي ؛ أما في نظام التشغيل Mac OS X ، فإن bzip2 القياسي متاح في سطر الأوامر).
• مقارنة الميزات ومعايير الأداء لأنواع مختلفة من تطبيقات bzip2 المتوازية المتاحة
• قد يكون برنامج ضغط bzip الأصلي مقيدًا ببراءات اختراع.