ترميز هوفمان التكيفي (الديناميكي): شرح مبسّط لكيفية عمله والفرق عن هوفمان الثابت

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

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

لماذا نحتاج نسخة تكيفية أصلاً؟

هوفمان الكلاسيكي (الثابت) يحتاج مرورَين على البيانات: الأول لحساب كم مرة يتكرر كل رمز، والثاني للترميز الفعلي. هذا ممتاز لملف موجود على القرص تعرف محتواه كاملاً. لكن ماذا لو كانت البيانات تصل تدفقاً حياً (بث، اتصال شبكي، مستشعر) ولا تملك ترف قراءتها مرتين؟ هنا يتفوّق النوع التكيفي: مرور واحد فقط، ولا حاجة لتخزين النص كاملاً في الذاكرة، ولا لإرسال الشجرة كحمولة إضافية.

هوفمان الثابت مقابل هوفمان التكيفي

المعيار	هوفمان الثابت	هوفمان التكيفي (الديناميكي)
عدد المرورات على البيانات	مروران	مرور واحد
معرفة التكرارات مسبقاً	مطلوبة	غير مطلوبة
إرسال الشجرة/الجدول مع البيانات	ضروري	غير ضروري (يُعاد بناؤها عند الطرفين)
ملاءمة البثّ الحيّ	ضعيفة	ممتازة
التعقيد البرمجي	أبسط	أعقد (تحديث مستمر للشجرة)
التكيّف مع تغيّر نمط النص	لا يتكيّف	يتكيّف تدريجياً

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

الآلية تعتمد على مفهومَين محوريَّين يجب أن يفهمهما أي مبتدئ:

1. عقدة NYT (Not Yet Transmitted): عقدة خاصة تمثّل «رمز لم يظهر بعد». عند مقابلة رمز جديد لأول مرة، تُرسِل رمز عقدة NYT ثم التمثيل الثنائي الخام للرمز الجديد، ثم تُضيفه إلى الشجرة.
2. خاصية الأشقّاء (Sibling Property): يجب أن تبقى العُقد مرتّبة بحيث لا تقلّ أوزان العُقد كلما صعدنا من الأوراق نحو الجذر. الحفاظ على هذا الترتيب هو ما يضمن أن الترميز يظل مثالياً لحظياً.

سير العمل العملي عند المُرسِل:

1. ابدأ بشجرة تحتوي عقدة NYT فقط.
2. اقرأ الرمز التالي. إن كان جديداً: أرسل مسار NYT + الرمز الخام، ثم أنشئ له ورقة جديدة. إن كان مألوفاً: أرسل مساره الحالي في الشجرة.
3. زِد وزن الرمز بمقدار واحد.
4. أعِد ترتيب الشجرة إن لزم للحفاظ على خاصية الأشقّاء (قد يتطلب هذا تبديل عُقد).
5. كرّر حتى نهاية البيانات.

المُستقبِل يفعل العكس بالخوارزمية نفسها، فيصل الطرفان إلى الشجرة ذاتها في كل خطوة دون أي تنسيق إضافي. هذا التزامن هو جوهر الفكرة.

خوارزميتا FGK وVitter

عملياً لا تُنفَّذ الفكرة عشوائياً، بل عبر خوارزمية محدّدة:

• FGK (نسبةً إلى Faller وGallager وKnuth): أول صياغة عملية، تعتمد على تبديل العُقد لاستعادة خاصية الأشقّاء بعد كل تحديث.
• خوارزمية Vitter (تُعرف بـ Algorithm V): تحسين لاحق يقلّل عدد التبديلات ويعطي طول ترميز أقرب إلى الأمثل، وهي الأكثر استخداماً عند الحاجة إلى كفاءة أعلى.

الفرق بينهما تفصيلي، لكن يكفي المبتدئ أن يعرف أن Vitter عادةً «أنظف» وأكثر توفيراً في عدد البتات.

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

هنا نصحّح خطأً شائعاً: ZIP وRAR لا يستخدمان هوفمان التكيفي، بل هوفمان ثابتاً ضمن خوارزمية DEFLATE (جدول يُحسب لكل كتلة). الاستخدامات الحقيقية للنوع التكيفي تشمل:

• بروتوكولات ضغط قديمة في المودمات مثل معيار V.42bis كجزء من منظومتها.
• سيناريوهات البثّ ونقل البيانات لحظياً حيث لا يمكن المرور على البيانات مرتين.
• أنظمة مدمجة محدودة الذاكرة لا تستطيع تخزين النص كاملاً لحساب التكرارات.

في معظم أدوات الضغط الحديثة الشائعة، طغت خوارزميات أقوى مثل عائلة LZ (كما في gzip وZstandard)، لكن يبقى هوفمان التكيفي مثالاً تعليمياً ممتازاً ولبنة داخل أنظمة أكبر.

نصيحة عملية وخطأ شائع

الخطأ الأكثر تكراراً عند تنفيذ الخوارزمية يدوياً هو نسيان مزامنة تحديث الشجرة بين المُرسِل والمُستقبِل بالترتيب نفسه؛ أي فارق ولو بخطوة واحدة يفسد فكّ الترميز بالكامل بعده. القاعدة الذهبية: نفّذ خطوة التحديث بعد معالجة الرمز مباشرة وبنفس التسلسل عند الطرفين. ونصيحة عملية للاختبار: ابدأ بنصوص قصيرة جداً (مثل «aabbc») وارسم الشجرة يدوياً بعد كل رمز لتتأكد أن التنفيذ يطابق النظرية قبل الانتقال لملفات كبيرة.

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

هل «الديناميكي» و«التكيفي» في هوفمان شيء واحد؟ نعم، الاسمان لنفس الفكرة. التمييز الحقيقي هو بين هوفمان الثابت (مرورين، شجرة مُرسَلة) وهوفمان التكيفي/الديناميكي (مرور واحد، شجرة تُبنى لحظياً).

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

هل يُستخدم في ضغط الصور والفيديو؟ هوفمان (غالباً بجداول ثابتة أو محدّدة مسبقاً) يظهر كمرحلة أخيرة في معايير مثل JPEG، أما النسخة التكيفية فنادرة في هذه المعايير الحديثة ويغلب استخدامها في سياقات البثّ والأنظمة المدمجة.

ما علاقته بخوارزمية LZ؟ هما مختلفان: LZ يستغل تكرار المقاطع عبر مؤشرات، وهوفمان يستغل تكرار الرموز المفردة. كثير من الأنظمة تدمجهما معاً للحصول على ضغط أعلى.