ترميز هوفمان: ابنِ الشجرة واحسب كلفة الرسالة كاملة

يبني هوفمان شجرة بدمج أقل وزنين. الرموز أوراقها، ومساراتها كلمات ثنائية؛ تستعيد قراءة المسار الرمز. [1]

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

الخلاصة السريعة

• لتكرارات A:11، B:7، C:5، D:3، E:2 تعطي شجرتنا 60 بتًا لجسم رسالة من 28 رمزًا.
• ترميز ثابت من ثلاثة بتات لكل رمز يحتاج 84 بتًا للجسم نفسه. هذه مقارنة بين تمثيلين لأبجدية متفق عليها من خمسة رموز.
• الرسالة EDCAB تصبح 11101111110010 وتعود إلى الرموز الخمسة نفسها.
• عند إضافة رأسي التنسيق والتعبئة إلى بايتات، يكلف مثال الرسالة الواحدة 15 بايتًا بالترميز المتغير مقابل 12 بالثابت.
• نفذنا 781 اختبار ذهاب وعودة، وفحصنا 1680 شجرة مسماة للمثال؛ أصغر كلفة للجسم كانت 60 بتًا.

ابدأ بأبجدية وتكرارات معلنة

الأحرف اللاتينية هنا أسماء خمسة رموز مجردة. نختار رسالة أساسية فيها أحد عشر A، وسبعة B، وخمسة C، وثلاثة D، واثنان E. مجموعها 28. لا ندعي أن هذا توزيع حروف لغة أو عينة من ملفات فعلية.

للمقارنة الثابتة، نعلن الجدول A=000، B=001، C=010، D=011، E=100. تكفي ثلاثة بتات لأن لدينا ثماني كلمات ممكنة بهذا الطول وخمسة رموز فقط، بينما البتان يعطيان أربع كلمات لا تكفي. تكلفة الجسم 28×3=84 بتًا، قبل أي رأس أو تعبئة.

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

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

أنشئ أوراقًا بأوزان التكرارات. ادمج أقل وزنين تحت أبٍ وزنه مجموعهما، وأعده للمجموعة حتى تبقى شجرة. [1]

في التنفيذ الخاص بنا، عند تساوي الأوزان تسبق العقدة التي أُنشئت أولًا. نبدأ الأوراق بترتيب الأسماء، ونجعل أول عقدة نخرجها ابنًا أيسر. يثبت هذا الاتفاق الرسم والأكواد حتى يمكن للقارئ مطابقة النتيجة؛ الأوزان وحدها قد تسمح بأكثر من ترتيب للفروع.

اتبع الفرع الأيسر من الجذر فتصل مباشرة إلى A، ولذلك كلمته 0. للوصول إلى B خذ يمينًا ثم يسارًا: 10. ولـC يمينًا مرتين ثم يسارًا: 110. تبقى E=1110 وD=1111.

استعد الرسالة دون فواصل مخزنة

لا تبدأ كلمة بكلمة رمز آخر. عند بلوغ ورقة نخرج رمزها، ثم نستأنف القراءة من الجذر. [2]

نأخذ EDCAB لاختبار القراءة، ونكتب الكلمات بفواصل مرئية للتعليم: 1110 | 1111 | 110 | 0 | 10. الفواصل ليست جزءًا من الجسم المخزن. ضم الأجزاء يعطي أربعة عشر بتًا: 11101111110010.

عند البداية لا تقف بعد 1 أو 11 أو 111؛ ليست أي منها ورقة في شجرتنا. البت الرابع صفر فيكمل 1110 ويعطي E. نبدأ من الجذر مجددًا، ثم تخرج D وC وA وB بالترتيب.

إذا انتهى الجسم عند 111 فقد توقف في عقدة داخلية، فيرفضه فاك الترميز التعليمي باعتباره كلمة غير مكتملة. هذا اختبار للنهاية في مثالنا، ولا يجعل الشفرة نظام كشف شامل للأخطاء: تغيير بت قد يحوّل رسالة إلى أخرى قابلة للفك.

احسب الجسم من التكرار وطول الكلمة

الكلفة مجموع التكرار مضروبًا في طول الكلمة؛ قسمتها على عدد الرموز تعطي متوسط البتات. [2]

المتوسط 60/28=15/7، أي نحو 2.143 بت لكل رمز. ليس مطلوبًا أن تحمل كل ورقة هذا العدد الكسري؛ إنه متوسط كلمات بأطوال صحيحة. الفرق عن الجسم الثابت 84−60=24 بتًا، أي نحو 28.6% من تلك البتات الأربعة والثمانين فقط.

تغيير ترتيب الرموز مع إبقاء تكراراتها لا يغير هذا الجمع، لكن تغيير الرسالة إلى ED مثلًا يعطي ثمانية بتات بجدولنا مقابل ستة بالجدول الثابت. الجدول بُني للتكرارات المعلنة، ولا نعطي كل رسالة قصيرة نسبة التوفير نفسها.

أضف رأسًا محددًا قبل إعلان الحجم

يرسل مثال برنستون الشجرة وعدد الرموز قبل الجسم؛ لهذه المعلومات كلفة. [1]

نعرّف هنا تنسيقين تعليميين من إعداد المقال. يفترض الطرفان مسبقًا الأبجدية المرتبة ABCDE، ويعرفان أي التنسيقين يستعملان. في التنسيق الثابت نحفظ عدد الرموز في ثمانية بتات ثم الجسم ذي الثلاثة بتات لكل رمز. لا نحتاج جدولًا جديدًا لأن الجدول الثابت متفق عليه مسبقًا.

في التنسيق المتغير نحفظ عدد مدخلات الجدول في ثلاثة بتات، ثم عدد رموز الرسالة في ثمانية بتات. لكل مدخل نحفظ رقم الرمز في ثلاثة بتات، وطول كلمته في ثلاثة بتات، ثم الكلمة نفسها. يقتصر هذا التدريب على طول كلمة بين واحد وسبعة، وعدد رسالة لا يتجاوز 255؛ لا نزعم أنه تنسيق عام أو صيغة ZIP.

لدينا خمسة مدخلات ومجموع أطوال الكلمات 1+2+3+4+4=14. إذن رأس التنسيق المتغير 3+8+5×(3+3)+14=55 بتًا. مع الجسم يصبح المجموع 115 بتًا، بينما الثابت يحتاج 8+84=92.

التعبئة إلى مجموعات من ثمانية ترفع 115 إلى 120 بتًا، أي 15 بايتًا. وترفع 92 إلى 96، أي 12 بايتًا. هكذا لا يحقق توفير الجسم وحده توفيرًا في الرسالة القصيرة كاملة.

في الصف الأوسط يوجد فرق بت واحد قبل الحشو: 175 مقابل 176، لكنه يختفي في عدد البايتات. وفي الصف الثالث يستفيد الجسم الأكبر من الرأس نفسه، فتكون النتيجة أصغر بثلاثة بايتات. النتائج تخص الرأس الذي عرّفناه تحديدًا، لا جميع البرامج التي تستخدم هوفمان.

ما الذي أثبته الاختبار المنفذ؟

عدّ البرنامج جميع الأشكال الثنائية الكاملة ذات خمس أوراق: أربعة عشر شكلًا. وزع الرموز الخمسة على أوراق كل شكل بجميع الترتيبات المئة والعشرين، فحسب 1680 كلفة. لم يجد كلفة أقل من الستين التي أعطتها شجرتنا. يكفي فحص الأشجار الكاملة هنا لأن عقدة ذات ابن واحد يمكن حذفها لتقليل عمق أوراق موجبة الوزن تحتها.

هذا حصر خاص بخمسة رموز وتكراراتها، وليس تنفيذًا سريعًا للأبجديات الكبيرة. ولدنا أيضًا كل رسالة من هذه الأبجدية بطول صفر إلى أربعة، وعددها 1+5+25+125+625=781، وفحصنا تطابقها بعد الترميز والفك. اجتازت الحزم الثلاث ذات الرؤوس اختبارًا مستقلًا لإعادة قراءة الجدول واستعادة الرسالة.

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

المصادر

1. Princeton University — Data Compression، الشرائح 14–22: الشجرة، البناء، والفك ومعلومات الرسالة.
2. Virginia Tech OpenDSA — Huffman Coding Trees: خاصية البادئة والكلفة الوزنية.

الأعداد والأكواد المحسوبة والرأس التعليمي والرسوم أصلية لهذا المقال. الاختبارات الحسابية منفذة. أُعدت الصياغة والمراجعة الأولية بمساعدة الذكاء الاصطناعي، دون ادعاء مراجعة بشرية مستقلة.