كيف يعمل ضغط الملفات فعلاً: شرح Huffman Coding وLZ77 وDEFLATE

كل مطوّر يتعامل مع الملفات المضغوطة. تفكّ ضغط حزمة، وتُرسل استجابة مشفّرة بـ gzip، أو تُصدّر ملف PNG — والضغط يعمل في الخلفية طوال الوقت. لكنّ السؤال الذي تتجاهله معظم الشروحات هو: لماذا يعمل هذا أصلاً؟ لماذا يمكنك أخذ ملف نصي بحجم 500 كيلوبايت وتقليصه إلى 180 كيلوبايت دون أن تفقد بايتاً واحداً، بينما لا تستطيع ضغط ملف ZIP مرة أخرى بشكل ملموس؟

الجواب يكمن في نظرية المعلومات وعدد من الخوارزميات الأنيقة. تستعرض هذه المقالة الآلية الحقيقية: من إنتروبيا شانون إلى أشجار Huffman، ووصولاً إلى صيغة DEFLATE التي تُشغّل ZIP وgzip وPNG.

لماذا يمكن ضغط الملفات

يمكن ضغط الملفات لأنها تحتوي على تكرار — أنماط ومتكرّرات وتسلسلات يمكن التنبؤ بها، تحمل معلومات أقل مما يوحي به عدد بايتاتها الخام.

فكّر في مثال بسيط. السلسلة AAAAAAAAAA (عشر حرفات A) تأخذ 10 بايتات بترميز ASCII. لكن محتواها المعلوماتي بسيط للغاية: يمكنك وصفها تماماً بعبارة "عشر حرفات A". خوارزمية الضغط تفعل بالضبط ذلك — تستبدل البيانات المطوّلة والمكرّرة بوصف أقصر.

الملفات الحقيقية مليئة بهذا النوع من التكرار:

• النص العربي يستخدم الكلمات الشائعة والتركيبات الحرفية باستمرار. كلمات مثل "في" و"من" و"على" تظهر بكثرة أكبر بكثير من تركيبات نادرة.
• الشيفرة المصدرية تمتلك بنية متكررة بعمق: function وreturn وconst ومستويات المسافة البادئة والأسطر الفارغة.
• صور النقطية تحتوي على سلاسل أفقية طويلة من البكسلات المتطابقة أو شبه المتطابقة — خاصة في المناطق ذات الألوان الموحّدة.
• ملفات السجلات تكرر الطوابع الزمنية وأسماء المضيفين ورموز الحالة آلاف المرات.

كلما كانت البيانات أكثر تكراراً، كانت أكثر قابلية للضغط. وكلما كانت أقل تكراراً — أي أكثر عشوائية — كلما صعب ضغطها.

الإنتروبيا: الحدّ الصارم للضغط

قدّم كلود شانون في ورقته البحثية عام 1948 A Mathematical Theory of Communication طريقة دقيقة لقياس محتوى المعلومات: الإنتروبيا، تُقاس بالبتّات.

تجيب إنتروبيا شانون على السؤال: كم بتّاً تحتاج فعلاً في المتوسط لتمثيل رمز واحد من هذا المصدر؟

الصيغة لمصدر بالرموز s₁, s₂, ..., sₙ والاحتمالات p₁, p₂, ..., pₙ:

H = -Σ pᵢ × log₂(pᵢ)

ما معنى هذا عملياً؟ افترض أن لديك ملفاً يحتوي على حرفين فقط: A (يظهر 90% من الوقت) وB (يظهر 10% من الوقت).

H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 بت لكل رمز

الترميز البسيط يستخدم 1 بت لكل رمز (0 لـ A، و1 لـ B). لكن الإنتروبيا تقول إن الحد الأدنى النظري هو 0.469 بت لكل رمز — أقل من النصف. الخوارزمية الجيدة تقترب من هذا الحد.

الآن فكّر في ملف عشوائي تماماً تظهر فيه كل قيم البايتات (0–255) باحتمال متساوٍ (1/256 لكل منها):

H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 بت لكل بايت

ثمانية بتّات لكل بايت — إنتروبيا قصوى. لا يوجد أي تكرار يمكن استغلاله. لهذا لا يمكنك ضغط ملف ZIP مرة أخرى: إنه بالفعل قريب من الإنتروبيا القصوى. كل بت يحمل معلومة؛ لم يتبقَّ أي نمط يمكن حذفه.

ترميز الجريان: أبسط الأشكال

قبل الوصول إلى الخوارزميات الأثقل، يوضح ترميز طول الجريان (RLE) الفكرة الأساسية بصورة واضحة.

يستبدل RLE سلسلة من الرموز المكررة بعدّاد والرمز:

الأصل:  AAABBBBBCCDDDDDD
RLE:    3A 5B 2C 6D

الأصل: 16 حرفاً. المُشفَّر: 8 أحرف. توفير بنسبة 50%.

يُستخدم RLE في إرسال الفاكس (CCITT المجموعة 3/4) وملفات BMP وكخطوة فرعية داخل صيغ أكثر تعقيداً. نقطة ضعفه واضحة: أداؤه رديء مع البيانات التي لا تحتوي على سلاسل طويلة من التكرارات. السلسلة ABABABAB لا تحتوي على جريانات، لذا يجعلها RLE أكبر بإضافة عدّادات 1 في كل مكان.

هذا الضعف بالذات هو ما يدفع نحو أساليب أكثر تطوراً.

ترميز Huffman: رموز أقصر للرموز الأكثر شيوعاً

في ASCII القياسي، يحصل كل حرف على 8 بتّات بغض النظر عن مدى تكراره. ترميز Huffman يكسر هذا الافتراض. الرموز الشائعة تحصل على رموز أقصر، والرموز النادرة تحصل على رموز أطول. متوسط طول الرمز ينخفض ويتقلّص الملف.

بناء شجرة Huffman

لنأخذ السلسلة AABBBCCCC (9 أحرف). نحسب التكرارات:

الخطوة 1. ضع كل رمز في عقدة ورقية بوزن يساوي تكراره.

[A:2]  [B:3]  [C:4]

الخطوة 2. دمج العقدتين الأخف وزناً باستمرار في عقدة أب وزنها مجموعهما، حتى تبقى شجرة واحدة.

دمج [A:2] و[B:3] ← أب [AB:5]:

      [AB:5]
      /     \
   [A:2]  [B:3]

[C:4]

دمج [C:4] و[AB:5] ← جذر [ABC:9]:

         [ABC:9]
         /      \
      [C:4]  [AB:5]
              /    \
           [A:2]  [B:3]

الخطوة 3. تخصيص الرموز بالتنقل في الشجرة: الحافة اليسرى = 0، الحافة اليمنى = 1.

حساب توفير البتّات

مع رموز Huffman، يكلّف ترميز AABBBCCCC:

A × 2 تكرار × 2 بت = 4 بت
B × 3 تكرارات × 2 بت = 6 بت
C × 4 تكرارات × 1 بت = 4 بت
المجموع = 14 بت

مع ASCII الثابت بـ 8 بتّات:

9 أحرف × 8 بت = 72 بت

14 بت مقابل 72 بت — توفير 81% في هذا المثال المبسّط. المكاسب الفعلية أقل، لكن المبدأ صحيح.

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

LZ77 وLZ78: استغلال التسلسلات المتكررة

يعمل ترميز Huffman على ترددات الرموز الفردية. لكنه يفوّت فئة أكبر من التكرار: التسلسلات المتكررة. كلمة function في الشيفرة المصدرية تحمل 8 بايتات في كل مرة تظهر فيها. لو أمكنك استبدال الظهور الثاني وما بعده بمؤشر يشير إلى الأول، لوفّرت بشكل ملحوظ.

هذا تحديداً ما وصفه أبراهام ليمبل ويعقوب زيف في أوراقهما البحثية عامَي 1977 و1978، مما أعطانا LZ77 وLZ78.

LZ77: ضغط النافذة المنزلقة

يحتفظ LZ77 بـنافذة منزلقة — مخزن مؤقت للبيانات التي شوهدت مؤخراً. أثناء معالجة البيانات الجديدة، يبحث المُشفِّر للخلف عبر النافذة ليجد أطول تطابق لما يأتي بعد ذلك. إن وجده، يُصدر مرجعاً خلفياً (الإزاحة، الطول) بدلاً من البايتات الحرفية.

فكّر في ترميز السلسلة:

abcabc

معالجة abc: لا يوجد تاريخ سابق، يُصدر الحروف a وb وc.

معالجة abc الثانية: يبحث المُشفِّر للخلف ويجد abc تبدأ منذ 3 مواضع، بطول 3. يُصدر المرجع الخلفي (إزاحة=3، طول=3) بدلاً من ثلاثة بايتات.

المُفكّك عند رؤية (3, 3) يعود 3 مواضع في مخزنه المؤقت وينسخ 3 بايتات — مُعيداً بناء abc بالكامل.

في التطبيق الفعلي، يُقيَّد البحث عن التطابقات بحجم النافذة (يستخدم gzip نافذة 32 كيلوبايت). النافذة الأكبر تجد تطابقات أكثر لكن بتكلفة ذاكرة ووقت بحث أكبر.

المرجع الخلفي (الإزاحة، الطول) عادةً ما يكون 2–3 بايتات. استبدال تسلسل 10 بايتات متكرر بمرجع من بايتين يوفّر 8 بايتات. كلما طال التطابق، كانت النسبة أفضل.

LZ78 وLZW

يبني LZ78 قاموساً صريحاً للأنماط المكتشفة بدلاً من استخدام نافذة منزلقة. أصبح LZW (Lempel-Ziv-Welch)، وهو مشتق منه، مشهوراً بوصفه الخوارزمية وراء ضغط GIF والأداة compress في Unix. يُشفِّر LZW الأنماط كمؤشرات قاموس مفردة، وينمو القاموس أثناء التشفير وفكّه.

DEFLATE: LZ77 مع ترميز Huffman

DEFLATE، المُعرَّف في RFC 1951، يجمع بين LZ77 وترميز Huffman بالتسلسل:

1. مرحلة LZ77: استبدال التسلسلات المتكررة بمراجع خلفية (الإزاحة، الطول). الناتج تيار من الحروف الحرفية والمراجع الخلفية.
2. مرحلة Huffman: تطبيق ترميز Huffman على ذلك التيار. الحروف الشائعة تحصل على رموز قصيرة؛ قيم المراجع النادرة تحصل على رموز أطول.

تهاجم التقنيتان أنواعاً مختلفة من التكرار. يُزيل LZ77 التكرار بعيد المدى، ثم يُزيل ترميز Huffman التكرار القائم على التردد فيما تبقّى. معاً يحقّقان نسب ضغط لا يستطيع أيٌّ منهما تحقيقها بمفرده.

تُنظَّم بيانات DEFLATE في كتل. يمكن لكل كتلة أن تستخدم واحداً من ثلاثة أنماط:

• بدون ضغط — للبيانات التي سيوسّع الضغطُ ناتجَها (بيانات عشوائية بالفعل)
• رموز Huffman ثابتة — جدول رموز متفق عليه مسبقاً يوفّر تكلفة تخزين شجرة مخصصة
• رموز Huffman ديناميكية — شجرة مخصصة مُحسَّنة لهذه الكتلة تحديداً، مخزّنة في ترويسة الكتلة

يُستخدم النمط الديناميكي لمعظم البيانات القابلة للضغط. يحلل المُشفِّر الكتلة، يبني شجرة Huffman مثلى، يخزّنها في بداية الكتلة، ثم يُشفِّر البيانات باستخدام تلك الشجرة.

أين يعيش DEFLATE في صيغ الملفات الحقيقية

ZIP

تخزّن ملفات ZIP كل مدخل بشكل مستقل بتيار DEFLATE مضغوط خاص به. يعني هذا الضغط لكل مدخل أنك تستطيع استخراج ملف واحد من ZIP دون فكّ ضغط الأرشيف بأكمله. يدعم صيغة ZIP أيضاً وضع "التخزين" (بدون ضغط) للملفات المضغوطة بالفعل.

gzip

يلفّ gzip تيار DEFLATE واحداً بترويسة (الرقم السحري، نظام التشغيل، وقت التعديل) ومجموع تدقيق CRC32. إنه صيغة الضغط القياسية لـ HTTP Content-Encoding: gzip وأرشيفات .tar.gz. الامتداد .gz دائماً تيار DEFLATE واحد.

PNG

يستخدم PNG ضغط DEFLATE (عبر zlib) لضغط بيانات البكسل. قبل الضغط، يطبّق PNG خطوة فلترة: يحوّل كل صف من البكسلات إلى فروق عن تنبؤ (ترميز دلتا). هذا يزيد بشكل كبير من التسلسلات والتكرارات التي يمكن لـ LZ77 استغلالها، مما يحسّن الضغط بشكل ملحوظ. بالنسبة لقصاصات الشاشة والرسوم البيانية النموذجية، يضغط PNG إلى 20–50% من حجم بيانات البكسل الخام. أدوات ضغط الصور التي تُصدر PNG تعتمد على هذه السلسلة.

zlib

zlib صيغة غلاف حول DEFLATE — تضيف ترويسة من بايتين ومجموع تدقيق Adler-32. تستخدم تيارات PDF ضغط zlib/DEFLATE لضغط المحتوى المضمَّن (يقلّل ضغط PDF من حجم الملف بإعادة ضغط هذه التيارات أو حذفها). HTTP وWebSockets والعديد من بروتوكولات الشبكة تستخدم zlib أيضاً.

JPEG: نهج مختلف

يستحق الأمر التوقف هنا، لأن JPEG يستخدم استراتيجية ضغط مختلفة تماماً — استراتيجية تفقد البيانات عمداً.

يطبّق JPEG تحويل جيب تمام منفصل (DCT) على كتل 8×8 بكسل. يحوّل DCT قيم البكسل إلى مركّبات ترددية (مشابه لتحويل فورييه). ثم تُكمَّم المركّبات عالية التردد — التفاصيل الدقيقة — بقوة (تُقرَّب إلى قيم أخشن أو تُتخلّص منها كلياً). المعاملات المتبقية تُشفَّر بترميز Huffman، لكن خطوة التكميم المفقود للبيانات هي ما يجعل JPEG أصغر بكثير من PNG للصور الفوتوغرافية.

المقايضة: لا يستطيع JPEG إعادة بناء البكسلات الأصلية بشكل مثالي. PNG يستطيع ذلك. هذا هو الفرق بين الضغط مع الفقدان وبدونه، الذي نتناوله بعمق في مقالتنا عن تحويل الملفات مع الفقدان وبدونه.

بالنسبة لصورة فوتوغرافية، قد لا يستخدم JPEG عند جودة 80 سوى 10% من البايتات التي سيحتاجها PNG بلا فقدان. أما لقطة الشاشة ذات الألوان الموحّدة والحواف الحادة، فالغالب فوز PNG لأن تشويهات DCT مرئية ولأن DEFLATE يضغط المناطق المستوية بكفاءة عالية جداً.

لماذا لا يمكنك ضغط ملف ZIP مرة أخرى

هذا مصدر شائع للارتباك. إذا كان الضغط يعمل بالبحث عن أنماط، فلماذا لا ينتج عن ضغط ملف مضغوط بالفعل تقريباً أي شيء؟

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

مرّر ضاغطاً ثانياً عليه ولن يجد تسلسلات (LZ77 لن يجد تطابقات طويلة) ولا انحيازاً في التردد (Huffman يرى توزيعاً شبه منتظم للرموز). الإنتروبيا بالفعل عند 7.9+ بت لكل بايت. لم يتبقّ شيء للاستغلال.

هذا أيضاً هو السبب في أنك لا ينبغي أن تضغط أبداً وسائط مضغوطة بالفعل. لفّ JPEG داخل ZIP يكلّفك نفقات ZIP بدون أي فائدة في الحجم. الأمر نفسه ينطبق على MP3 وMP4 وHEIC — كلها صيغ مضغوطة تجلس بالفعل قرب سقف إنتروبيتها.

مقارنة الخوارزميات

تجميع الصورة كاملة

سلسلة العمليات من البيانات الخام إلى البايتات المضغوطة في ملف مضغوط بـ gzip:

1. الإدخال: تيار بايتات خام (مثلاً ملف نصي)
2. LZ77: فحص المراجع الخلفية بنافذة منزلقة 32 كيلوبايت، لإنتاج تيار من الحروف وأزواج (الإزاحة، الطول)
3. ترميز Huffman: بناء شجرتين — واحدة للحروف/الأطوال وأخرى للإزاحات — وترميز ناتج LZ77
4. كتل DEFLATE: تعبئة أشجار Huffman والبيانات المُشفَّرة في كتلة أو أكثر
5. غلاف gzip: إضافة ترويسة gzip في البداية، وإلحاق CRC32 وحجم الملف الأصلي
6. الناتج: ملف .gz، أصغر عادةً بنسبة 30–70% للإدخال القابل للضغط

تسير عملية فكّ الضغط عكسياً بالضبط: تحليل ترويسة gzip، قراءة وإعادة بناء أشجار Huffman من ترويسات الكتل، فكّ ترميز تيار Huffman إلى رموز LZ77، تطبيق المراجع الخلفية لإعادة بناء تيار البايتات الأصلي. فكّ الضغط دائماً أسرع من الضغط لأن العمل الشاق (البحث عن التطابقات المثلى، بناء الأشجار المثلى) يُنجز مرة واحدة فقط.

أبرز ما يجب تذكّره

• الملفات قابلة للضغط لأنها تحتوي على تكرار — أنماط متكررة وترددات رموز منحازة.
• تضع إنتروبيا شانون الحدّ الأدنى المطلق: البيانات العشوائية حقاً لا يمكن ضغطها لأن كل بت يحمل معلومة بالفعل.
• RLE يتعامل مع التكرار بطريقة بدائية. ترميز Huffman يتعامل مع انحياز التردد بأناقة. LZ77 يتعامل مع تكرار التسلسلات بعيدة المدى.
• DEFLATE يسلسل LZ77 وHuffman، لذا يتفوق على كل خوارزمية بمفردها. إنه المحرك داخل ZIP وgzip وPNG وتيارات PDF المضغوطة بـ zlib.
• JPEG يتبع نهجاً مختلفاً جذرياً: تكميم DCT مع فقدان تليه Huffman بلا فقدان، يتداول دقة البكسل مقابل تقليص حجم هائل.
• ضغط ملف مضغوط لا يُجدي شيئاً لأن الضغط الجيد ينتج مخرجات قريبة من الإنتروبيا القصوى.

فهم هذه الخوارزميات يهمّك عند اختيار الصيغة أو تشخيص ملفات ضخمة بشكل غير متوقع أو تصحيح أخطاء في سلسلة ضغط. في المرة القادمة التي تستخدم فيها ضغط PDF أو تستخرج ملف ZIP أو تُصدر PNG لـ ضغط الصور، ستعرف تماماً ما يفعله البرنامج بباياتك.