شرح ضغط البيانات

كل صفحة ويب تفتحها، وكل ملف ZIP، وكل صورة PNG قد ضُغطت: صُغّرت دون أن تفقد بتًا واحدًا، ثم فُكّ ضغطها من جديد عند وصولها. والطرق التي تقف وراء ذلك بسيطة على نحو مدهش. فهي تبحث عما يتكرر، وتقول «مثل ما سبق» بدلًا من قوله مرة أخرى. وإلى أي حد تمضي هذه الفكرة، وأين تتوقف، قصة من أجمل القصص في علوم الحاسوب.

سطر من النص حلّت فيه محلَّ المقاطع المكررة أسهمٌ تشير إلى الخلف نحو أول ظهور لها، وإلى جانبه أعمدة تبيّن الحجم الأصلي والحجم بعد الضغط
سطر من النص حلّت فيه محلَّ المقاطع المكررة أسهمٌ تشير إلى الخلف نحو أول ظهور لها، وإلى جانبه أعمدة تبيّن الحجم الأصلي والحجم بعد الضغط

بلا فقد ومع فقد

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

ترميز طول التتابع

أبسط الطرق تضع مكان تتابع من الرموز المتطابقة عددَه والرمزَ نفسه: فاثنا عشر بكسلًا أبيض تصبح 12W. وقد استخدمتها أجهزة الفاكس وصيغ الصور النقطية المبكرة وصيغة الصور PCX، لأن الصفحات الممسوحة ضوئيًا والرسوم البسيطة مليئة بالتتابعات الطويلة. أما على النص العادي فهي عديمة الفائدة، بل ضارة: فالتتابعات نادرة، وكتابة عدد لكل حرف منفرد تضاعف الحجم. ولا يزال ترميز طول التتابع حيًا داخل طرق أخرى، لتتابعات الأصفار التي تبقى بعد تحويل أول.

LZ77: الإشارة إلى الخلف

في عام 1977 نشر Abraham Lempel و Jacob Ziv، وهما باحثان في التخنيون في إسرائيل، طريقة غيّرت هذا المجال. يحتفظ المرمِّز بنافذة من النص الذي عالجه للتو. فإذا كانت الأحرف التالية قد وردت من قبل في النافذة، كتب زوجًا من الأرقام: كم تبعد بداية النسخة السابقة إلى الخلف، وكم طولها. وإلا كتب الحرف نفسه. ولا يحتاج فاكّ الترميز إلى أي قاموس، بل إلى النص الذي أعاد بناءه فقط. بل يمكن للإحالة أن تتداخل مع النص الذي تُنتجه، فيصبح تتابع من 100 حرف متطابق حرفًا واحدًا وإحالة واحدة.

أبراهام ليمبل، الذي نشر مع يعقوب زيف في التخنيون عام 1977 طريقة النافذة والإحالات المعروفة اليوم باسم LZ77.
أبراهام ليمبل، الذي نشر مع يعقوب زيف في التخنيون عام 1977 طريقة النافذة والإحالات المعروفة اليوم باسم LZ77.

LZW: تعلّم قاموس

أما الطريقة الثانية لـ Lempel و Ziv، وهي LZ78، فتبني قاموسًا بدلًا من الرجوع إلى الخلف في نافذة. وتحسين Terry Welch لها عام 1984، أي LZW، يبدأ بقيم البايت الـ 256 كلها، ويرسل في كل خطوة رقم أطول سلسلة يعرفها، ثم يضيف تلك السلسلة مع الحرف التالي مدخلًا جديدًا. ويعيد فاكّ الترميز بناء القاموس نفسه من الأرقام وحدها. كانت LZW سريعة وبسيطة، ودخلت في أمر compress في Unix وصيغة الصور GIF وملفات TIFF، إلى أن أثارت براءات الاختراع المتعلقة بها نزاعًا طويلًا في تسعينيات القرن العشرين.

Deflate و ZIP وما بعدهما

طريقة deflate التي وضعها Phil Katz، وقُدّمت مع PKZIP 2 عام 1993، تجمع LZ77 مع ترميز هوفمان: فبعد العثور على التكرارات، تعطي أكثر القيم الحرفية والأطوال والمسافات شيوعًا أقصرَ الشيفرات البتية. وتُستخدم deflate في ZIP و gzip وصور PNG وضغط صفحات الويب، وهي الطريقة التي يقيسها العرض التوضيحي بأداة الضغط المدمجة في المتصفح. أما الطرق الأحدث مثل Zstandard و Brotli و xz فتستخدم نوافذ أكبر ومطابقة أذكى وترميز إنتروبيا أدق، وتقلّص الملفات المعتادة بنسبة إضافية من 10 إلى 30%.

لماذا لا يمكن تصغير كل شيء

لا توجد طريقة تستطيع تصغير كل ملف. فهناك 2ⁿ من الملفات طولها n بت، لكن لا يوجد إلا 2ⁿ − 1 من الملفات الأقصر من ذلك، فلو صغّرت طريقةٌ الملفاتِ كلها لانتهى ملفان إلى النتيجة نفسها ولما أمكن استعادتهما معًا: هذا هو مبدأ برج الحمام. ولذلك تكبّر كل أداة ضغط بعض المدخلات، وهي عادةً بيانات تبدو عشوائية مثل الملفات المشفّرة والملفات المضغوطة أصلًا والضجيج. وهذا أيضًا اختبار للعشوائية: البيانات التي لا تستطيع أي أداة ضغط تصغيرها تبدو عشوائية.

حد الإنتروبيا

أثبت كلود شانون عام 1948 أن إنتروبيا المصدر هي أصغر متوسط ممكن لعدد البتات لكل رمز في أي شيفرة بلا فقد. وإذا عُدّ النص الإنجليزي حرفًا حرفًا، كانت إنتروبيته نحو 4 بتات لكل حرف، أي نصف البتات الثمانية التي يُخزَّن بها. والطرق التي تستخدم السياق، مثل LZ77، تنزل على النص كثير التكرار تحت هذا الرقم المحسوب لكل حرف منفرد، لأن الإحالة الواحدة تمثل مقطعًا كاملًا دفعة واحدة. وأفضل أدوات الضغط الحديثة، التي تتنبأ بكل حرف انطلاقًا من كل ما سبقه، تهبط بالإنجليزية إلى أقل من 2 بت لكل حرف.

كلود شانون، الذي حدّد عام 1948 في مختبرات بل بدقة مقدار المعلومات في رسالة وقاسه بالبتات.
كلود شانون، الذي حدّد عام 1948 في مختبرات بل بدقة مقدار المعلومات في رسالة وقاسه بالبتات.

استكشفه بنفسك

افتح العرض التوضيحي لضغط البيانات لتشغيل LZ77 و LZW وترميز طول التتابع على فقرة، أو أغنية فيها لازمة، أو صف من البكسلات، أو جدول بيانات، أو أحرف عشوائية أو DNA، أو على نصك أنت. انقر أي إحالة في LZ77 لترى ما تنسخه، وراقب قاموس LZW وهو ينمو، وقارن كل الطرق بـ ZIP وبحد الإنتروبيا.

الأسئلة المتداولة

ماذا تعني نسبة ضغط 3 : 1؟

تعني أن الأصل أكبر من النسخة المضغوطة بثلاث مرات، فيشغل الملف المضغوط ثلث المساحة ويوفر ثلثيها. ويبلغ النص عادةً من 2 : 1 إلى 4 : 1 مع ZIP؛ أما البيانات كثيرة التكرار، مثل ملفات السجلات، فكثيرًا ما تبلغ أكثر من ذلك بكثير.

لماذا لا يفيد ضغط ملف ZIP مرة أخرى؟

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

لماذا تكون نافذة LZ77 الأكبر أفضل؟

النافذة الأكبر تتيح للمرمِّز العثور على تكرارات أبعد إلى الخلف، مثل لازمة تعود بعد عدة مقاطع. والثمن أن كتابة كل مسافة تحتاج إلى بتات أكثر وأن البحث يستغرق وقتًا أطول، ولهذا تتوقف deflate عند 32 KB بينما تسمح الطرق الأحدث بعدة ميغابايتات.

هل الضغط هو نفسه التشفير؟

لا. الضغط يجعل البيانات أصغر ويمكن لأي أحد عكسه؛ أما التشفير فيجعل البيانات غير مقروءة دون مفتاح. وكثيرًا ما يُجمع بينهما، وعندئذ يجب ضغط البيانات أولًا: فالبيانات المشفّرة تبدو عشوائية ولا يعود ممكنًا ضغطها.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

افتح العرض التوضيحي لضغط البيانات