لماذا استراتيجية الجشع هي الأمثل
خوارزمية هوفمان هي خوارزمية جشعة : في كل خطوة، تقوم باختيار الخيار الأفضل محليًا (دمج النقاط الأقل تكلفة) دون النظر إلى الأمام. الخوارزميات الجشعة ليست دائمًا جيدة بشكل عام - لكن هنا هي.
حجة الأمثل
ت suppose a code C has minimum average length L. Consider the two symbols with lowest probability, say p_a and p_b. In any optimal code, these two symbols must appear as sibling leaves at the deepest level of the tree. Why?
إذا لم يكن هناك وريث مشترك، يمكنك تبادل الرمز الأعمق مع رمز قصير - مما يقلل من L. لذلك يجب أن يكون الأوراق الأعمق رموزًا أقل احتمالية.
الآن، إذا دمجت a و b في رمز ورمز (ب 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 ✓
Step 1: Lowest two: C(0.2), D(0.1). Merge → CD(0.3). List: A(0.4), B(0.3), CD(0.3).
Step 2: Lowest two: B(0.3), CD(0.3) (tie — either valid). Merge → BCD(0.6). List: A(0.4), BCD(0.6).
Step 3: Merge A(0.4), BCD(0.6) → root(1.0). Assign A=0, BCD=1.
Backward: 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.
Code-Length Variance
Two Huffman codes may achieve the same L but have different code-length distributions. The variance of code lengths measures this spread:
Var(l) = E[l²] − (E[l])²
where E[l] = L (average code length) and E[l²] = Σ p_i · l_i².
Why variance matters:
1. Buffer requirements. In real-time decoding, each symbol takes a variable number of bits. High variance means some symbols take many bits — you need a larger input buffer to guarantee you can always read a complete symbol.
2. Decoding latency. High-variance codes have long worst-case decoding paths. Low-variance (bushy) codes bound the worst-case more tightly.
3. Robustness. A lost bit in a high-variance code causes more synchronization damage because long codewords must be fully re-read.
Hamming's recommendation: when multiple valid Huffman codes exist (tie-breaking choices), prefer the one with lower variance — the bushy tree.
Computing Variance for Two Trees
Using p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 and the code 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
مثال نهاية إلى نهاية لجافا كود هوفمان 3-رمز
مثال نهاية إلى نهاية كامل: بناء كود هوفمان، حساب 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) → الجذر (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 بت.
الانتروبيا: H = −0.6·log2 (0.6) − 0.3·log2 (0.3) − 0.1·log2 (0.1)
log2 (0.6) ≈ -0.737، log2 (0.3) ≈ -1.737، log2 (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 بت.
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.
المرحلة التالية: خط طويل من المعدات
قيمات log2 للمرجع: log2 (0.5) = -1.000، log2 (0.25) = -2.000، log2 (0.125) = -3.000، log2 (0.375) ≈ -1.415، log2 (0.625) ≈ -0.678.