كيف يبني هوفمان الترميز الأمثل
يقدم هامينج ترميز هوفمان كخوارزمية جشعة تبني ترميزاً خالياً من البادئات بأقل متوسط طول. الفكرة الأساسية: بناء الشجرة من الأسفل إلى الأعلى، دائماً دمج الرمزين الأقل احتمالاً.
مسار البناء الأمامي (الإنشاء)
1. رتّب جميع الرموز حسب الاحتمالية، من الأعلى إلى الأقل.
2. خذ الرمزين الأقل احتمالاً. ادمجهما في رمز شامل جديد بحيث تكون احتمالية = مجموع الاثنين.
3. أدرج الرمز الشامل في موضعه المرتب.
4. كرّر حتى يتبقى رمزان فقط.
5. أسند 0 و 1 للرمزين المتبقيين.
مسار البناء العكسي (إسناد الرموز)
تراجع عن الدمجات بترتيب معاكس: عند كل فصل، يستقبل الرمزان اللذان تم دمجهما نفس البتات البادئة لرمزهما الأب المدمج، بالإضافة إلى بت إضافي 0 (فرع واحد) أو 1 (فرع آخر). إسناد 0/1 اعتباطي — كلاهما صحيح.
لماذا هذا أمثل: إذا كان لأي ترميز آخر متوسط طول أصغر L'، تطبيق نفس التقليل الأمامي سينتج في النهاية عن رمزين بمتوسط طول أقل من 1 بت — مستحيل لترميز ثنائي الرموز. تناقض.
تتبع الخوارزمية
مثال من هامينج: أربعة رموز A و B و C و D بـ p(A)=0.5 و p(B)=0.25 و p(C)=0.125 و p(D)=0.125.
المسار الأمامي:
الخطوة 1: مرتبة: A(0.5) و B(0.25) و C(0.125) و D(0.125). الاثنان الأقل: C و D.
الخطوة 2: ادمج CD بـ p=0.25. القائمة الجديدة: A(0.5) و B(0.25) و CD(0.25).
الخطوة 3: الاثنان الأقل: B(0.25) و CD(0.25). ادمج BCD بـ p=0.5.
الخطوة 4: يتبقى رمزان: A(0.5) و BCD(0.5). أسند A=0 و BCD=1.
المسار العكسي:
BCD → B تستقبل 10 و CD تستقبل 11. CD → C تستقبل 110 و D تستقبل 111.
الترميز النهائي: A=0 (l=1) و B=10 (l=2) و C=110 (l=3) و D=111 (l=3).
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 بت.
رموز هوفمان المتعددة الصحيحة
يلاحظ هامينج مصدرين لعدم الفرادة:
1. إسناد 0/1 اعتباطي. عند كل فصل، يمكنك إسناد 0 لأي فرع. تبديل 0 و 1 طوال الطريق يعطي ترميزاً مختلفاً بـ L متطابقة.
2. كسر التعادل. عندما تملك عقدتان احتمالية متساوية، يمكن وضع أي منهما 'أعلى' (مدمجة أولاً). خيارات كسر تعادل مختلفة قد تنتج أشجاراً مختلفة هيكلياً — 'طويلة' مقابل 'كثيفة' — بنفس L لكن بتوزيعات أطوال ترميز مختلفة.
أشجار طويلة مقابل كثيفة
شجرة طويلة (منحرفة): رمز واحد في كل مستوى عمق (هيكل فيبوناتشي). أطوال الترميز تتنوع بشكل كبير: رمز واحد يستقبل ترميزاً قصيراً، والآخرون ينسلون إلى رموز أطول.
شجرة كثيفة (متوازنة): الرموز موزعة بالتساوي عبر مستويات العمق. أطوال الترميز تتجمع بالقرب من المتوسط. تباين أقل.
توصية هامينج: عندما يكون أمامك خيار، فضّل الشجرة الكثيفة. نفس L، لكن تباين أقل في أطوال الترميز → وقت فك تشفير أكثر انتظاماً → متطلبات مخزن مؤقت أصغر في التطبيقات الفورية.
حساب تباين طول الترميز
تباين أطوال الترميز: Var = E[l²] − (E[l])²
للترميز {A=0 l=1 و B=10 l=2 و C=110 l=3 و D=111 l=3} مع p=[0.5, 0.25, 0.125, 0.125]:
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
ترميز كثيف بديل لرموز احتمالية متساوية يستخدم كل رموز بطول-2: L=2 و Var=0.
مكاسب الضغط مقابل توزيع الرموز
قاعدة هامينج: ترميز هوفمان مفيد فقط عندما تختلف احتمالية الرموز بشكل كبير.
احتمالية موحدة. إذا كان لكل 2^k رموز احتمالية موحدة 1/2^k، هوفمان ينتج ترميز كتلة: كل رمز يستقبل طول k. L = H = k. لا توجد مكاسب مقابل ترميز الكتلة البسيط.
احتمالية منحرفة. إذا هيمن رمز واحد (p >> 1/2^k للآخرين)، هوفمان يسند له ترميزاً قصيراً جداً (طول 1 أو 2)، مما يقلل L بشكل كبير.
رمز الفاصلة (مصطلح هامينج). عندما تتجاوز كل احتمالية 2/3 من المجموع المتبقي، هوفمان بشكل طبيعي ينتج: p(s1)→0 و p(s2)→10 و p(s3)→110 و ...، وصولاً إلى رمزين متساويي الطول في النهاية. هذا 'رمز فاصلة': الصفر اللاحق بعد سلسلة من الآحاد يعمل كفاصلة.
يلاحظ هامينج: ضغط البيانات الحقيقي (النسخ الاحتياطي، تأرشيف الملفات) قد يقطع التخزين بأكثر من نصف عندما تملك المصدر احتمالية منحرفة — نصوص اللغة الإنجليزية كمثال رئيسي.
ترميز هوفمان مقابل ترميز الكتلة: مقارنة رقمية
مثال هامينج الثاني: p(s1)=1/3 و p(s2)=1/5 و p(s3)=1/6 و p(s4)=1/10 و p(s5)=1/12 و p(s6)=1/20 و p(s7)=1/30 و p(s8)=1/30.
ترميز الكتلة: 8 رموز → 3 بتات لكل → L_block = 3.
هامينج يحسب رمز هوفمان ويبلغ L_Huffman ≈ 2.58 بت.
المدخرات: (3 − 2.58)/3 ≈ 14% ضغط على ترميز الكتلة.
عندما تختلف احتمالية الرموز بشكل كبير (1/3 مقابل 1/30 هنا، نسبة 10:1)، ترميز الطول المتغير يدفع بشكل كبير.
البرامج ذاتية التجميع
ينهي هامينج الفصل 11 بفكرة مذهلة: مشفر هوفمان يمكنه تشفير نفسه. شجرة فك التشفير (التي تخبر فاك التشفير كيفية قراءة الرسالة المضغوطة) يتم إرسالها مع البيانات المضغوطة. المستقبل لا يحتاج معرفة سابقة بالترميز.
المشفر: ينموذج البيانات، يقدّر الاحتمالية، ينشئ ترميز هوفمان، يشفّر شجرة فك التشفير كرأس، ثم يشفّر البيانات.
فاك التشفير: يقرأ الرأس لإعادة بناء الشجرة، ثم يفك تشفير البيانات باستخدامها.
نقطة هامينج: خط الأنابيب بالكامل يمكنه أن يعمل كدالة مكتبة بدون تدخل بشري. تستدعيها، تضغط وتفك ضغط تلقائياً. تنسيقات التأرشيف الحديثة (ZIP، gzip، bzip2) تطبق بالضبط هذا النمط.
المبدأ الأعمق: الذكاء في الخوارزمية، وليس في جدول ترميز ثابت. الخوارزمية تتكيف مع أي بيانات تتلقاها. هذا هو النمط الذي يرى هامينج عبر كل الأنظمة الهندسية الرائعة: القابلية للتكيف مدمجة، وليس مرفقة.