خلاصة أولًا: ترميز Huffman هو ترميز مثالي بطول متغير وبادئة، وفكرته الجوهرية هي "الأحرف عالية التكرار تأخذ رمزًا قصيرًا، والأحرف منخفضة التكرار تأخذ رمزًا طويلًا"، حيث يُنشئ جدول الترميز ببناء شجرة Huffman، مما يقلل الطول الإجمالي للترميز. خذ النص "ABRACADABRA" المكون من 11 حرفًا كمثال، يحتاج الترميز بطول ثابت إلى 33 بت، بينما لا يحتاج ترميز Huffman سوى 23 بت، أي توفير 30%. يُعد ترميز Huffman المكون الأساسي لصيغ الضغط الرئيسية مثل DEFLATE (ZIP/GZIP/PNG)، وتحتوي كل خوارزميات الضغط بدون فقدان تقريبًا على هذه المرحلة. فيما يلي شرح من إحصاء التردد إلى بناء شجرة Huffman وتوليد الترميز.
إذا لم تكن على دراية بالفرق بين الضغط بدون فقدان والضغط مع الفقدان، فننصح بقراءة الضغط بدون فقدان مقابل الضغط مع الفقدان: الفرق الجوهري.
أولًا: لماذا نحتاج إلى ترميز بطول متغير
يستخدم الكمبيوتر عادةً ترميزًا بطول ثابت لتخزين الأحرف، مثل ASCII الذي يستخدم 8 بتات لكل حرف، وUnicode الذي يستخدم 16-32 بتًا. ميزة الترميز بطول ثابت هي سهولة الوصول العشوائي، لكن به هدرًا كبيرًا — في النصوص الإنجليزية، يبلغ تكرار حرف e نحو 12.7%، في حين يبلغ تكرار z نحو 0.07% فقط، ومن غير المعقول استخدام ترميز بنفس الطول لهما. يُخصص الترميز بطول متغير أطوالًا مختلفة من كلمات الترميز حسب تكرار الأحرف، فكلما زاد التكرار كان الترميز أقصر، مما يضغط الحجم الإجمالي.
| طريقة الترميز | المبدأ | طول كلمة الترميز | غموض فك الترميز | التطبيقات الشائعة |
|---|---|---|---|---|
| الترميز بطول ثابت | كل حرف N بت ثابتة | ثابت | لا غموض | ASCII, Unicode |
| الترميز بطول متغير (غير بادئ) | تخصيص أطوال مختلفة حسب التكرار | متغير | قد يكون غامضًا | غير عملي |
| ترميز Huffman البادئ | حسب التكرار + قيد البادئة | متغير | لا غموض | DEFLATE, JPEG |
| الترميز الحسابي | تعيين الرسالة كاملة لعدد واحد | مستوى كسري | لا غموض | ZSTD, brotli |
القيد الأساسي في ترميز Huffman هو "البادئة": ترميز أي حرف ليس بادئة لترميز حرف آخر. فمثلًا إذا كان ترميز الحرف A هو "0"، فلا يمكن لأي ترميز حرف آخر أن يبدأ بـ "0"، بل يجب أن يبدأ بـ "1". وبهذا يُقرأ فك الترميز بتًا بتًا، وعند الوصول إلى كلمة ترميز كاملة يُفك الترميز فورًا، دون أي غموض.
ثانيًا: شرح تفصيلي لمبدأ ترميز Huffman
يتكون توليد ترميز Huffman من ثلاث خطوات: إحصاء التردد، وبناء شجرة Huffman، وتوليد جدول الترميز. العملية بأكملها هي خوارزمية جشعة — في كل مرة يتم اختيار أدنى عقدتين من حيث التكرار ودمجهما، حتى تتكون في النهاية شجرة ثنائية مثلى.
1. إحصاء التردد
الخطوة الأولى هي إحصاء تكرار كل حرف في البيانات المدخلة. خذ "ABRACADABRA" كمثال، نبدأ بإحصاء عدد مرات ظهور كل حرف.
| الحرف | عدد مرات الظهور | التكرار(%) | ترميز بطول ثابت (3 بت) |
|---|---|---|---|
| A | 5 | 45.5% | 000 |
| B | 2 | 18.2% | 001 |
| R | 2 | 18.2% | 010 |
| C | 1 | 9.1% | 011 |
| D | 1 | 9.1% | 100 |
5 أحرف، يحتاج الترميز بطول ثابت إلى ceil(log2(5))=3 بت/حرف، أي 33 بت لـ 11 حرفًا. لاحظ أن ترميز ASCII يحتاج إلى 11×8=88 بت، فالترميز بطول ثابت 3 بت يوفّر بالفعل 70%، لكن Huffman يمكنه ضغط أكثر.
2. بناء شجرة Huffman
بناء شجرة Huffman عملية جشعة: في كل مرة يتم اختيار أدنى عقدتين من حيث التكرار من جميع العقد ودمجهما في عقدة جديدة، يكون تكرار العقدة الجديدة مجموع تكرارهما. تتكرر العملية حتى تبقى عقدة جذر واحدة فقط.
| الخطوة | العملية | أدنى عقدتين قبل الدمج | العقدة الجديدة بعد الدمج | العقد المتبقية |
|---|---|---|---|---|
| 1 | دمج C(1) و D(1) | C:1, D:1 | CD:2 | A:5, B:2, R:2, CD:2 |
| 2 | دمج B(2) و R(2) | B:2, R:2 | BR:4 | A:5, CD:2, BR:4 |
| 3 | دمج CD(2) و BR(4) | CD:2, BR:4 | CDBR:6 | A:5, CDBR:6 |
| 4 | دمج A(5) و CDBR(6) | A:5, CDBR:6 | Root:11 | اكتمل |
بعد اكتمال البناء، انطلق من الجذر، وعلِّم الفرع الأيسر بـ 0 والفرع الأيمن بـ 1، والمسار إلى كل ورقة هو ترميز Huffman لذلك الحرف. الحرف A الأعلى تكرارًا (5 مرات) في الطبقة الثانية، وترميزه 1 بت فقط؛ أما C وD الأدنى تكرارًا فأعمق طبقة، وترميزهما 3 بت.
3. توليد جدول الترميز
تجوَّل من جذر شجرة Huffman إلى كل ورقة، وسجِّل تسلسل 0/1 على المسار، فتحصل على جدول الترميز.
| الحرف | التكرار | ترميز Huffman | طول الكلمة | مساهمة الترميز (بت) |
|---|---|---|---|---|
| A | 5 مرات | 0 | 1 | 5×1=5 |
| B | مرتان | 100 | 3 | 2×3=6 |
| R | مرتان | 101 | 3 | 2×3=6 |
| C | مرة واحدة | 110 | 3 | 1×3=3 |
| D | مرة واحدة | 111 | 3 | 1×3=3 |
التحقق من خاصية البادئة: ترميز A وهو "0" ليس بادئة لأي ترميز آخر؛ B "100" وR "101" وC "110" وD "111" ليست بادئة لبعضها. يُقرأ فك الترميز بتًا بتًا، وعند مواجهة "0" يكون A، وعند مواجهة "1" يُقرأ بتان إضافيتان لتمييز B/R/C/D، دون غموض.
ثالثًا: دراسة حالة عملية — مقارنة ترميز "ABRACADABRA"
الآن نستخدم جدول الترميز المُولَّد لترميز "ABRACADABRA" كاملًا، ونقارن فرق الحجم بين الترميز بطول ثابت وترميز Huffman.
النص الأصلي: A B R A C A D A B R A (11 حرفًا)
عملية الترميز:
| الموقع | الحرف | ترميز Huffman | البتات المتراكمة |
|---|---|---|---|
| 1 | A | 0 | 1 |
| 2 | B | 100 | 4 |
| 3 | R | 101 | 7 |
| 4 | A | 0 | 8 |
| 5 | C | 110 | 11 |
| 6 | A | 0 | 12 |
| 7 | D | 111 | 15 |
| 8 | A | 0 | 16 |
| 9 | B | 100 | 19 |
| 10 | R | 101 | 22 |
| 11 | A | 0 | 23 |
مقارنة كفاءة الترميز:
| طريقة الترميز | بت لكل حرف | إجمالي البتات | إجمالي البايتات | نسبة الضغط مقارنة بـ ASCII |
|---|---|---|---|---|
| ترميز ASCII | 8 | 88 | 11 | — (مرجع) |
| ترميز بطول ثابت 3 بت | 3 | 33 | 5 | 62.5% |
| ترميز Huffman | 2.09 (متوسط) | 23 | 3 | 73.9% |
| الحد الأدنى لإنتروبيا النظرية | 2.04 | 22.5 | 3 | 74.4% |
النتيجة: ضغط ترميز Huffman 11 حرفًا من 88 بت في ASCII إلى 23 بت، أي توفير 73.9%. وحتى مقارنة بالترميز بطول ثابت 3 بت، فهو يوفّر 30%. والحد الأدنى لإنتروبيا النظرية هو 22.5 بت، فلا يتجاوز ترميز Huffman الأمثل النظري سوى 0.5 بت، وتصل الكفاءة إلى 97.8%. هذا هو السبب في أن ترميز Huffman يُسمى "البادئة المثلى".
رابعًا: تطبيق ترميز Huffman في خوارزميات الضغط الرئيسية
نادرًا ما يُستخدم ترميز Huffman بمفرده، وعادةً ما يكون المرحلة الأخيرة من خط أنابيب الضغط — ترميز الإنتروبيا. تُستخدم في المرحلة الأولى خوارزميات القاموس مثل LZ77 لإزالة الأنماط المتكررة، ثم يُستخدم ترميز Huffman لضغط البيانات المتبقية حسب التكرار. يعرض الجدول التالي طريقة استخدام Huffman في صيغ الضغط الرئيسية.
| صيغة الضغط | مرحلة القاموس | مرحلة ترميز الإنتروبيا | متغير Huffman | نسبة الضغط النموذجية |
|---|---|---|---|---|
| DEFLATE (ZIP/GZIP) | LZ77 | Huffman | Huffman ثابت + ديناميكي | 50%–70% |
| PNG | LZ77 | Huffman | Huffman المدمج في DEFLATE | 50%–75% |
| JPEG | تحويل DCT | Huffman | ترميز منفصل لمعاملات DC/AC | 10:1 (بلا فقدان بصري) |
| ZSTD | متغير LZ77 | FSE/Huffman | إنتروبيا الحالات المحدودة + مزيج Huffman | 60%–80% |
| brotli | LZ77 + السياق | Huffman + حسابي | Huffman السياقي | 65%–85% |
| BZIP2 | تحويل BWT | Huffman | Huffman متعدد الجداول | 70%–85% |
للاطلاع على المبدأ التفصيلي لضغط القاموس LZ77، يمكن الرجوع إلى شرح خوارزمية LZ77: كيف يعمل ضغط القاموس؟. ولمعرفة تطبيق DEFLATE في صيغة PNG، يمكن الرجوع إلى شرح مبدأ ضغط PNG.
خامسًا: الأسئلة الشائعة FAQ
س1: ما هو ترميز Huffman؟
ترميز Huffman هو طريقة ترميز مثالية بطول متغير وبادئة، اقترحها David Huffman عام 1952. الفكرة الجوهرية: الأحرف عالية التكرار تُرمَّز بقصر، والأحرف منخفضة التكرار تُرمَّز بطول، مما يقلل الطول الإجمالي للترميز. يُنشئ جدول الترميز ببناء شجرة Huffman، ويضمن أن ترميز أي حرف ليس بادئة لترميز حرف آخر (خاصية البادئة)، فلا يحدث غموض في فك الترميز.
س2: لماذا يُعد ترميز Huffman البادئة المثلى؟
تعتمد مثالية ترميز Huffman على استراتيجية الجشع: في كل مرة يتم دمج أدنى عقدتين من حيث التكرار، فتوضع العقد منخفضة التكرار في طبقات عميقة من الشجرة (ترميز طويل)، والعقد عالية التكرار في طبقات سطحية (ترميز قصير). يمكن إثبات رياضيًا أنه لتوزيع ترددات أحرف معين، لا يقل متوسط طول الترميز لـ Huffman عن أي ترميز ببادئة آخر، أي يصل إلى الحد الأدنى النظري لإنتروبيا الترميز (إنتروبيا المصدر H). في مثال ABRACADABRA، ترميز Huffman 23 بت، والحد الأدنى للإنتروبيا النظرية 22.5 بت، والكفاءة 97.8%.
س3: ما الفرق بين ترميز Huffman والترميز الحسابي؟
ترميز Huffman يعمل على مستوى الأحرف، فيخصص لكل حرف كلمة ترميز مستقلة بطول متغير؛ أما الترميز الحسابي فيُعيِّن الرسالة كاملةً إلى عدد عشري في الفترة [0,1)، وتكون دقة الترميز أدق. ترميز Huffman تنفيذه بسيط وسرعته عالية، لكنه محدود بالترميز على مستوى الأحرف ولا يمكنه الاقتراب من إنتروبيا المصدر؛ أما الترميز الحسابي فنسبة ضغطه أعلى (يمكنه الاقتراب من الإنتروبيا)، لكنه أكثر تعقيدًا حسابيًا. يستخدم DEFLATE ترميز Huffman، وتجمع ZSTD وbrotli الحديثان بين الاثنين.
س4: في أي صيغ ضغط يُستخدم ترميز Huffman؟
ترميز Huffman هو المكون الأساسي لـ DEFLATE (ZIP/GZIP/PNG)، ويُستخدم مع LZ77؛ وتستخدم ZSTD ترميز FSE (إنتروبيا الحالات المحدودة) كبديل لـ Huffman مع مبدأ مماثل؛ كما يستخدم brotli وJPEG (معاملات DC/AC) ترميز Huffman. تتضمن جميع صيغ الضغط الرئيسية بدون فقدان تقريبًا Huffman أو أحد متغيراته كمرحلة ترميز إنتروبيا.
الخلاصة
ترميز Huffman هو حجر الأساس لخوارزميات الضغط، ومبدأه الأساسي "الأحرف عالية التكرار تأخذ رمزًا قصيرًا، والأحرف منخفضة التكرار تأخذ رمزًا طويلًا"، حيث يُنشئ ترميز البادئة المثلى ببناء شجرة Huffman. خذ "ABRACADABRA" كمثال، فالحرف الـ11 ضُغط من 88 بت في ASCII إلى 23 بت، ووصلت الكفاءة إلى 97.8% من الحد الأدنى للإنتروبيا النظرية. يوجد ترميز Huffman في جميع صيغ الضغط بدون فقدان تقريبًا، ويُشكِّل مع خوارزمية القاموس LZ77 خطوط أنابيب الضغط الكلاسيكية مثل DEFLATE/ZSTD.
تكمن النقاط الأساسية لفهم ترميز Huffman في ثلاث: أولًا، إحصاء التردد يحدد توزيع أطوال الترميز؛ ثانيًا، البناء الجشع لشجرة Huffman يضمن المثالية؛ ثالثًا، قيد البادئة يضمن خلو فك الترميز من الغموض. ويتقن ترميز Huffman، يفتح لك ذلك باب فهم جميع خوارزميات الضغط الحديثة.
توصيات ذات صلة
هل تحتاج إلى ضغط الملفات؟ جرّب SmartSlim
مبني على محرك ضغط Rust مطوّر داخليًا، يدعم أكثر من 40 صيغة في 10 فئات تشمل PDF والصور والفيديو وOffice وOFD، مع ضغط محلي لا تغادر فيه البيانات نطاقك.