لماذا الاستراتيجية الجشعة مثلى
خوارزمية هوفمان هي خوارزمية جشعة: في كل خطوة، تختار الحل الأمثل محليًا (دمج العقدتين الأرخص) دون النظر للأمام. الخوارزميات الجشعة ليست دائمًا مثلى عالميًا؛ لكنها كذلك هنا.
حجة الأمثلية
افترض أن الكود C له الحد الأدنى من متوسط الطول L. اعتبر الرمزين ذوي أقل احتمالية، لنقل p_a و p_b. في أي كود مثالي، يجب أن يظهر هذان الرمزان كأوراق شقيقة في أعمق مستوى من الشجرة. لماذا؟
إذا لم يشاركا والدًا، يمكنك استبدال الرمز الأعمق برمز أقصر — مما يقلل L. لذلك يجب أن تكون أعمق الأوراق هي الرموز الأقل احتمالية.
الآن، إذا دمجت a و b في رمز وسيط ab (مع p_ab = p_a + p_b)، فإن أي كود مثالي للأبجدية المختزلة بدون رمز واحد هو بالضبط كود هوفمان على المشكلة المختزلة. الاستقراء يكمل الحجة.
وجهة نظر هندسية
تبني خوارزمية هوفمان الشجرة الثنائية من الأسفل للأعلى، موضعية الرموز الأقل احتمالية على أعمق عمق. هذا يقلل Σ p_i · depth(i) = L.
وجهة نظر معادلة: أنت تسند تسميات إلى أوراق الشجرة لتقليل طول المسار المرجح، حيث وزن كل ورقة هو احتماليتها.
تنفيذ الخطوات الجشعة
الاحتماليات: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. المجموع = 1.0 ✓
الخطوة 1: أقل اثنين: C(0.2), D(0.1). دمج → CD(0.3). القائمة: A(0.4), B(0.3), CD(0.3).
الخطوة 2: أقل اثنين: B(0.3), CD(0.3) (تعادل — أي منهما صحيح). دمج → BCD(0.6). القائمة: A(0.4), BCD(0.6).
الخطوة 3: دمج A(0.4), BCD(0.6) → root(1.0). أسند A=0, BCD=1.
للخلف: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 bits.
تباين طول الكود
قد يحقق كودا هوفمان نفس L لكنهما لهما توزيعات مختلفة لأطوال الأكواد. تباين أطوال الأكواد يقيس هذا الانتشار:
Var(l) = E[l²] − (E[l])²
حيث E[l] = L (متوسط طول الكود) و E[l²] = Σ p_i · l_i².
لماذا يهم التباين:
1. متطلبات المخزن المؤقت. في فك التشفير في الوقت الفعلي، يستغرق كل رمز عددًا متغيرًا من البتات. التباين العالي يعني أن بعض الرموز تستغرق عددًا كبيرًا من البتات — تحتاج إلى مخزن مؤقت للإدخال أكبر لضمان أنه يمكنك دائمًا قراءة رمز كامل.
2. كمون فك التشفير. أكوادالتباين العالي لها مسارات فك تشفير طويلة في أسوأ الحالات. أكوادالتباين المنخفض (الكثيفة) تحد من حالة أسوأ بشكل أكثر إحكامًا.
3. الدقة. فقدان بتة واحدة في كود عالي التباين يسبب ضررًا أكبر في المزامنة لأن كلمات الكود الطويلة يجب أن تُقرأ بالكامل من جديد.
توصية هامينج: عندما توجد عدة أكواد هوفمان صحيحة (خيارات كسر التعادل)، فضل الواحد ذو التباين المنخفض — الشجرة الكثيفة.
حساب التباين لشجرتين
باستخدام p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 و الكود A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
كود هوفمان ثلاثي الرموز من البداية للنهاية
مثال كامل من البداية للنهاية: بناء كود هوفمان، حساب L، حساب H، التحقق من L ≥ H، حساب Var.
المصدر: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
بناء هوفمان:
الخطوة 1: مرتبة: X(0.6), Y(0.3), Z(0.1). أقل اثنين: Y(0.3), Z(0.1).
دمج → YZ(0.4). القائمة: X(0.6), YZ(0.4).
الخطوة 2: دمج X(0.6), YZ(0.4) → root(1.0). أسند X=0, YZ=1.
YZ → Y=10, Z=11.
الكود: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 bits.
الإنتروبيا: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 bits.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% فوق الإنتروبيا.
التباين: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
دورك: خط أنابيب كامل
قيم log₂ للمرجع: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.