un

guest
1 / ?
back to lessons

كيفية بناء هوفمان للكود الأمثل

يقدم هامنج خوارزمية كود هوفمان كخوارزمية انشطارية تconstructs كودًا متوسط ​​طول أقل. الفكرة الرئيسية: بناء الشجرة من الأسفل إلى الأعلى، دائمًا دمج الأقل احتمالاً من الأعضاء.

المرحلة الصاعدة (بناء)

1. ترتيب جميع الرموز حسب الاحتمالية، من الأعلى إلى الأدنى.

2. أخذ الأقل احتمالاً من الرموز. دمجهم في رمز ميتا جديد مع احتمالية = مجموع كليهما.

3. إضافة الرمز الميتا في موقعه المرتبة.

4. تكرار ذلك حتى يبقى فقط اثنين من الرموز.

5. إسناد 0 و 1 للرموز المتبقية.

المرحلة العكسية (تسجيل الكودات)

إلغاء الدمج في العكس: عند كل تقسيم، يتلقى الرموز التي دمجت نفسها نفس القوائم المسبقة للوالد المشترك، بالإضافة إلى رقم 0 (أحد الأطفال) أو 1 (الطفل الآخر). الإسناد 0/1 عشوائي - أي منهم صحيح.

Huffman Build: Merge and Decode Tree

لماذا هذا الأمثل: إذا كان لدينا أي كود آخر لديه طول متوسط أقل L'، فإن تطبيق نفس التقليد الجانبي سينتج في النهاية عن رموز مع طول متوسط أقل من 1 بت - غير ممكن للكود 2-رمز. تناقض.

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

مثال من هامنج: أربعة رموز 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.

الكود النهائي: 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 بت.

تطبيق خوارزمية هوفمان على: p(X1)=0.4, p(X2)=0.3, p(X3)=0.2, p(X4)=0.1. إظهار جميع الخطوات الدمجية، والكود النهائي لكل رمز، وحساب L.

كود هوفمان غير الفريد

يلاحظ هامنج على اثنتين من المصادر لعدم الفريد:

1. التماثل العشوائي. في كل تقسيم ، يمكنك إعطاء 0 لأي طفل. تغيير 0 و 1 في كل مكان يعطي كودًا مختلفًا مع طول L identical.

2. التعادل. عندما يكون لكل عقدة احتمال متساوي ، يمكن أن يتم وضع أحدهما 'أعلى' (دمج أولاً). يمكن أن ينتج اختيار التعادل المختلف عن أشجار مختلفة الهيكل - 'طويلة' مقابل 'كثيفة' - مع نفس L ولكن توزيعات طول الكود المختلفة.

طويلة مقابل كثيفة

أشجار طويلة (مفرطة): رمز لكل مستوى عمق (هيكل فلكي). تتفاوت أطوال الكود: يحصل رمز واحد على كود قصير ، والآخر يتدفق إلى كودات أطول.

أشجار كثيفة (متوازنة): الرموز المنتشرة بشكل متساوي عبر مستويات العمق. تتفاوت أطوال الكود حول المتوسط. الانحراف الصغير.

أشجار هوفمان الطويلة مقابل الكثيفة

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

حساب الانحراف القياسي لطول الكود

不确定性长度码：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.

考慮4個等可能的符號（p = 0.25各）。計算H。然後比較：（a）密集樹{00，01，10，11}，所有長度為2，和（b）長樹長度{1，2，3，3}。分別計算L和Var。您應該偏好哪一個，且為什麼？

فوائد الضغط مقابل توزيع الرموز

قاعدة هامنج: يدفع ترميز هوفمان فقط عندما تختلف الاحتمالات الرمزية بشكل كبير.

احتمالات متساوية. إذا كانت جميع الرموز 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، ... إلى كودين طولهما متساوي في النهاية. هذا كود 'كوما': العلامة 0 التي تلي سلسلة من 1s تشبه العلامة الفاصلة.

يرجح هامنج: ضغط البيانات في الواقع (الاحتفاظ بالبيانات، архيف الملفات) يمكن أن يقلل من التخزين بنسبة تزيد عن النصف عندما يكون المصدر له احتمالات غير متساوية - النص الإنجليزي هو مثال بارز.

هوفمان ضد كود الحزمة: مقارنة رقمية

مثال هامنج الثاني: 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% من ضغط الكود المحدد.

عندما تختلف احتمالات الأsymbol بشكل كبير (1/3 مقابل 1/30 هنا، نسبة 10: 1)، يدفع الكود بأطوال متغيرة بشكل كبير.

ل المصدر الرمزي 8 الأصل يبلغ H ≈ 2.55 بت (لا تحتاج إلى التحقق من هذا). ترميز هامنج لهوفمان يصل إلى L ≈ 2.58 بت. يستخدم الكود الحزبي L = 3 بت. حاسبه: (أ) L / H للكود الهوفرماني، (ب) L / H للكود الحزبي، و (ج) ماذا يقول هذا النسبة المئوية حول كفاءة كل ترميز بالمقارنة مع الحد الأدنى النظري.

البرامج الذاتية التجميع

هامنج ينتهي بابته 11 بفكرة مدهشة: يمكن أن يكود معالج هوفمان نفسه. شجرة الترميز (التي تشرح لترميز الكود كيفية قراءة الرسالة المضغوطة) يتم إرسالها مع البيانات المضغوطة. الحصول على استقبال لا يحتاج إلى معرفة مسبقة عن الكود.

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

التنفيذي: يقرأ الرأس لاستعادة الشجرة، ثم يفك الكود باستخدامها.

نقطة هامنج: يمكن أن يعمل هذا الجسر بأكمله كوظيفة مكتبة بدون مشاركة إنسان. تُدعى وتضغط وتفك معالج الضغط والتنفيذ تلقائيًا. تنفيذ تنسيق الأرشيف الحديث (ZIP، gzip، bzip2) يطبق هذا المخطط بالضبط.

النظرية الأعمق: العقول في الخوارزمية وليس في جدول الكود الثابت. ت adapts إلى أي بيانات تتلقاها. هذا هو نمط ما يرى هامنج في جميع الأنظمة الهندسية العظمى: التكيف المبني، وليس المثبت على.

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