ما معنى Huffman Coding في الخوارزميات وهياكل البيانات؟ شرح مبسّط بمثال عملي

ترميز هوفمان (Huffman Coding) هو خوارزمية لضغط البيانات دون فقدان (Lossless)، فكرتها بسيطة وذكية: بدل أن نمنح كل رمز في النص العدد نفسه من البِتّات، نمنح الرموز الأكثر تكرارًا رموزًا ثنائية قصيرة، والرموز النادرة رموزًا أطول. النتيجة أن حجم الملف يصغر مع إمكانية استعادته حرفًا بحرف بلا أي خسارة. ابتكرها الطالب ديفيد هوفمان عام 1952، وما زالت حتى اليوم جزءًا داخليًا من صيغ مثل ZIP وJPEG وMP3.

الفكرة في جملة واحدة

في الترميز التقليدي «ثابت الطول» يأخذ حرف نادر مثل «ض» العدد نفسه من البِتّات الذي يأخذه حرف شائع مثل «ا». هذا هدر. هوفمان يقول: لماذا نضيّع بِتّات على الحروف الشائعة؟ فيعطيها أقصر رمز ممكن، ويعوّض بإطالة رموز الحروف النادرة التي نادرًا ما تظهر أصلًا. المحصلة النهائية: متوسط عدد البِتّات لكل رمز ينخفض.

كيف تعمل الخوارزمية خطوة بخطوة

1. احسب التكرار: مرّ على النص واحسب كم مرة يظهر كل رمز.
2. أنشئ عقدة لكل رمز: ضع كل رمز مع تكراره في قائمة (عمليًا: طابور أولوية / Priority Queue).
3. ادمج الأصغرين: خذ العقدتين الأقل تكرارًا وادمجهما في عقدة أب مجموع تكرارها = مجموعهما.
4. كرّر: أعد الدمج حتى تتبقى عقدة واحدة هي «جذر الشجرة».
5. وزّع الرموز: انزل من الجذر، اجعل كل تفرّع لليسار = 0 ولليمين = 1، والمسار من الجذر إلى كل ورقة هو رمزها الثنائي.

مثال عملي محسوب بالكامل

لنرمّز الكلمة ABRACADABRA (11 حرفًا). التكرارات: A = 5، B = 2، R = 2، C = 1، D = 1.

نبني الشجرة بدمج الأصغرين تباعًا:

• C(1) + D(1) = عقدة بوزن 2
• B(2) + R(2) = عقدة بوزن 4
• عقدة(2) + عقدة(4) = عقدة بوزن 6
• A(5) + عقدة(6) = الجذر بوزن 11

توزيع الرموز الناتج:

• A = 0 (بِت واحد فقط لأنه الأكثر تكرارًا)
• B = 110
• R = 111
• C = 100
• D = 101

نحسب الحجم: A أخذ 5×1 = 5 بِت، وB أخذ 2×3 = 6، وR أخذ 2×3 = 6، وC أخذ 1×3 = 3، وD أخذ 1×3 = 3. المجموع = 23 بِت.

لو استخدمنا ترميزًا ثابت الطول، فخمسة رموز مختلفة تحتاج 3 بِتّات لكل رمز، أي 11×3 = 33 بِت. وفّر هوفمان نحو 30% على نصّ صغير جدًا، والفارق يكبر كلما زاد تفاوت التكرارات.

لماذا لا تختلط الرموز عند فك الضغط؟

قد تتساءل: إذا كان A = 0 وطوله بِت واحد، كيف يعرف الحاسوب أين ينتهي رمز ويبدأ آخر؟ السر أن رموز هوفمان «خالية من البادئة» (Prefix-Free): لا يوجد رمز يمثّل بداية رمز آخر. فمثلًا لا يبدأ أي رمز آخر بالرقم 0 المفرد، لذا حين يقرأ فاكّ الضغط 0 يعرف فورًا أنه A. هذه الخاصية هي ما يجعل فك الضغط سريعًا وأحاديًا لا لبس فيه.

أين تُستخدم فعليًا

• ضغط الملفات: جزء من خطوة الترميز داخل ZIP وGZIP (ضمن خوارزمية DEFLATE).
• الصور: المرحلة الأخيرة في ضغط JPEG تستخدم ترميز هوفمان لتقليل حجم المعاملات.
• الصوت والفيديو: يظهر داخل صيغ مثل MP3 وبعض معايير الفيديو كطبقة ترميز إنتروبي.

هوفمان مقابل الترميز ثابت الطول

البند	ثابت الطول	هوفمان
طول الرمز	متساوٍ لكل الرموز	متغيّر حسب التكرار
كفاءة الضغط	ضعيفة عند تفاوت التكرارات	عالية
يحتاج جدول/شجرة	لا	نعم، يُحفظ مع الملف
سرعة الترميز	أسرع قليلًا	أبطأ قليلًا لبناء الشجرة
النوع	—	ضغط بلا فقدان

أخطاء ومفاهيم شائعة

• ليس مناسبًا دائمًا: إذا كانت كل الرموز متساوية التكرار تقريبًا، فلن يوفّر هوفمان شيئًا يُذكر، وقد يكبر الملف قليلًا بسبب حفظ الشجرة.
• الشجرة جزء من الملف: لفكّ الضغط تحتاج شجرة هوفمان نفسها، لذا تُخزَّن أو يُعاد بناؤها، وهذا يشكّل عبئًا صغيرًا يهمل مع الملفات الكبيرة.
• ليس تشفيرًا: هوفمان يضغط ولا يحمي؛ من يملك الشجرة يقرأ المحتوى بسهولة.
• ليس الأفضل مطلقًا: خوارزميات أحدث مثل الترميز الحسابي (Arithmetic Coding) قد تتفوّق عليه في بعض الحالات.

الأسئلة الشائعة

هل ترميز هوفمان بلا فقدان؟ نعم، تسترجع البيانات الأصلية كاملة بلا أي تغيير، بعكس الضغط «مع فقدان» مثل خفض جودة صورة.

هل هو أفضل خوارزمية ضغط؟ لا توجد خوارزمية «أفضل» مطلقًا. هوفمان ممتاز وبسيط، لكن الترميز الحسابي أو خوارزميات القاموس مثل LZ77 قد تتفوّق حسب نوع البيانات، ولذلك تدمج الصيغ الحديثة أكثر من تقنية معًا.

ما الفرق بينه وبين ZIP؟ ZIP ليس خوارزمية واحدة بل حزمة؛ يستخدم داخليًا DEFLATE التي تجمع ضغط القاموس (LZ77) مع ترميز هوفمان في مرحلته الأخيرة.

كم يبلغ تعقيده الزمني؟ بناء الشجرة يتم عادة في زمن قدره O(n log n) حيث n عدد الرموز المميزة، وهو سريع جدًا عمليًا.