ما معنى static Huffman coding؟ شرح الترميز الثابت لهوفمان بمثال محلول
الترميز الثابت لهوفمان (static Huffman coding) هو الصيغة الكلاسيكية الأصلية لخوارزمية هوفمان لضغط البيانات بلا فقد: تُحسب ترددات الرموز مرة واحدة على كامل البيانات قبل بدء الترميز، ثم تُبنى شجرة واحدة ثابتة تُستخدم لترميز الملف كله من أوله إلى آخره. أما عبارة «see Huffman coding» التي تلاحقها في المعاجم التقنية فلا تعني مصطلحًا مختلفًا؛ إنها مجرد إحالة معجمية تقول لك إن «static Huffman coding» مرادف لخوارزمية هوفمان الأساسية، وأن التفاصيل مشروحة تحت المدخل الأصلي «Huffman coding».
الفكرة الجوهرية بسيطة: الرموز الأكثر تكرارًا تأخذ أكوادًا (سلاسل بتات) أقصر، والرموز النادرة تأخذ أكوادًا أطول. النتيجة أن متوسط عدد البتات لكل رمز ينخفض مقارنةً بالترميز ذي الطول الثابت (مثل 8 بت لكل حرف في ASCII)، من دون أن نفقد أي معلومة عند فك الضغط.
static أم adaptive؟ الفرق الحقيقي
الالتباس الأشهر هو بين النسخة الثابتة والنسخة المتكيّفة (adaptive أو dynamic). الفرق ليس في جودة الضغط النظرية بل في متى تُبنى الشجرة وهل يحتاج فاكّ الضغط إلى جدول مرفق.
| الجانب | static Huffman | adaptive / dynamic Huffman |
|---|---|---|
| حساب الترددات | مرة واحدة على كامل البيانات مسبقًا | تُحدَّث الشجرة رمزًا برمز أثناء المعالجة |
| عدد المرور على البيانات | مرّتان (قراءة ثم ترميز) | مرور واحد فقط |
| تخزين الجدول مع الملف | نعم، يجب إرفاق الشجرة أو الترددات | لا، يُعيد الفاكّ بناءها بنفس الخطوات |
| الملاءمة | ملفات معروفة كاملة على القرص | بثّ حيّ (streaming) لا تعرف نهايته |
| التعقيد | أبسط وأسرع تنفيذًا | أعقد لكنه يتكيّف مع تغيّر التوزيع |
الخلاصة العملية: إن كان الملف كاملًا أمامك واستقرار توزيع الرموز فيه معقول، فالنسخة الثابتة أبسط وكافية. إن كنت تضغط تدفقًا لا نهاية معروفة له، فالنسخة المتكيّفة تجنّبك تخزين الجدول والمرور مرتين.
كيف تُبنى الشجرة خطوة بخطوة
- احسب تكرار كل رمز في البيانات.
- اجعل كل رمز «عقدة» مستقلة، ورتّبها في طابور أولوية حسب التردد تصاعديًا.
- اسحب أصغر عقدتين، وادمجهما في عقدة أب تردده = مجموع ترددَيهما.
- أعِد إدخال العقدة المدموجة إلى الطابور.
- كرّر حتى تبقى عقدة واحدة هي جذر الشجرة.
- امنح كل فرع يسار قيمة 0 وكل فرع يمين قيمة 1، فيصبح كود كل رمز هو المسار من الجذر إليه.
الأكواد الناتجة خالية من البادئة (prefix-free)، أي لا يكون كود أي رمز بداية لكود رمز آخر، وهذا ما يسمح بفك الضغط بلا لبس ولا فواصل.
مثال محلول: ترميز ABRACADABRA
خذ النص ABRACADABRA (11 رمزًا). الترددات:
- A: 5، B: 2، R: 2، C: 1، D: 1
نبني الشجرة: ندمج C(1)+D(1)=2، ثم B(2)+R(2)=4، ثم (CD)(2)+(BR)(4)=6، وأخيرًا A(5)+6=11 عند الجذر. أحد الأكواد المثلى الناتجة:
- A:
0 - C:
100 - D:
101 - B:
110 - R:
111
يصبح ترميز النص كاملًا: 0 110 111 0 100 0 101 0 110 111 0 = 23 بت فقط. قارنها بـ 88 بت لو استخدمنا 8 بت لكل حرف بأسلوب ASCII، أو 33 بت بطول ثابت من 3 بتات. هذا هو مكسب الضغط بلا فقد.
ملاحظة مهمة: قد تحصل على أكواد مختلفة قليلًا (مثلًا R بطول بتّين) بحسب طريقة كسر التعادل عند تساوي الترددات، لكن متوسط الطول الكلي يبقى هو نفسه الأمثل (23 بت هنا). فلا تظن أن اختلاف الأكواد عن مرجع آخر يعني خطأً.
أين يُستخدم فعليًا
الترميز الثابت لهوفمان ليس درسًا نظريًا فقط؛ إنه جزء من صيغ تستعملها يوميًا:
- صيغة JPEG للصور: يُطبَّق هوفمان كخطوة أخيرة على المعاملات المكمَّمة لضغطها.
- DEFLATE وهو قلب صيغ ZIP وgzip وملفات PNG: يمزج بين هوفمان وخوارزمية LZ77.
- ضغط النصوص والبيانات حيث يكون توزيع الرموز غير متساوٍ بوضوح.
نصيحة عملية وخطأ شائع
الخطأ الأكثر تكرارًا عند المبتدئين هو نسيان تكلفة الجدول. في النسخة الثابتة يجب أن تُرفق الشجرة (أو الترددات) داخل الملف المضغوط ليتمكن الطرف الآخر من فك الضغط. بالنسبة للملفات الصغيرة جدًا قد يلتهم هذا الجدول مكسب الضغط كله، بل قد يصبح الناتج أكبر من الأصل. لذا هوفمان يتألق مع الملفات المتوسطة والكبيرة ذات التوزيع المائل، لا مع بضعة بايتات.
نصيحة إضافية: هوفمان أمثل فقط ضمن قيد «عدد صحيح من البتات لكل رمز». إن احتجت ضغطًا أعلى وكان توزيعك شديد الميل، فقد يتفوق الترميز الحسابي (arithmetic coding) لأنه يخصّص أجزاءً كسرية من البتة لكل رمز.
الأسئلة الشائعة
هل static Huffman ضغط بلا فقد؟ نعم، تمامًا. تسترجع البيانات الأصلية بت ببت من دون أي خسارة، على عكس الضغط الفاقد مثل ما يحدث لجودة صورة JPEG في خطواتها الأخرى.
لماذا يقول القاموس «see Huffman coding»؟ لأنها ليست خوارزمية منفصلة، بل الاسم التقليدي للنسخة الأساسية من هوفمان. الإحالة تدلّك على المدخل الأصلي الذي يشرح التفاصيل.
هل هوفمان يعطي دائمًا أفضل ضغط ممكن؟ هو الأمثل بين الأكواد التي تعطي كل رمز عددًا صحيحًا من البتات. لكنه ليس الأفضل مطلقًا؛ الترميز الحسابي قد يتجاوزه على البيانات شديدة الانحياز.
متى أفضّل النسخة المتكيّفة؟ حين تضغط تدفقًا حيًّا لا تعرف طوله سلفًا، أو حين تريد تجنّب المرور مرتين وتخزين الجدول مع الملف.