الكود كشجرة
الكود الخالي من البادئات يعكس شجرة ثنائية: الجذر يمثل بداية فك التشفير، الفروع اليسرى تمثل البت 0، الفروع اليمنى تمثل البت 1، و الأوراق تمثل الكلمات الترميزية الكاملة.
القيد الهندسي: كل ورقة تنهي مسار من الجذر إلى الورقة. لا يمكن لأي ورقة أن يكون لها سليل (إذا كان لديها واحد، ستكون كلمتها الترميزية بادئة للكلمة الترميزية للسليل، مما ينتهك خاصية الخلو من البادئات).
هذا يعطي عدم المساواة كرافت تفسيراً هندسياً:
كل ورقة في العمق d 'تحتل' جزء 2^(−d) من السعة الكلية للشجرة. السعة الإجمالية لشجرة ثنائية كاملة في العمق D هي 1. يستخدم الكود الخالي من البادئات أوراقاً في أعماق مختلفة؛ مجموع كرافت يقيس الاحتلال الكلي.
مجموع كرافت = 1: كود كامل (كل مسار ينتهي بورقة — معبأ بشكل مثالي).
مجموع كرافت < 1: كود غير كامل (سعة شجرة غير مستخدمة — يمكن إضافة المزيد من الرموز).
مجموع كرافت > 1: مستحيل للأكواد الخالية من البادئات (بعض المسارات يجب أن تشارك ورقة).
الأوراق الأعمق = الأكواد الأطول = سعة أقل
ورقة في العمق 1 تحتل نصف سعة الشجرة (2^(−1) = 0.5).
ورقة في العمق 3 تحتل ثمن (2^(−3) = 0.125).
وضع كلمة ترميزية قصيرة عالية في الشجرة يحجب جميع نسلها من الاستخدام — أنت تبدل كود قصير واحد بأكواد محتملة طويلة عديدة.
بناء شجرة خالية من البادئات
فكر في 5 رموز بأطوال l = {1, 2, 3, 3, 3}. مجموع كرافت = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
هذا يتجاوز 1: هذه الأطوال غير متوافقة مع كود خالي من البادئات. يجب أن يزداد طول واحد على الأقل.
إصلاح: تغيير l_1 من 1 إلى 2. الأطوال الجديدة {2, 2, 3, 3, 3}: مجموع كرافت = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1. صحيح، لكن غير كامل.
إصلاح: غيّر l_1 من 2، أضف l_2 = 3 لاستخدام السعة المتبقية. مجموع كرافت = 0.875؛ المتبقي = 0.125 = 2^(−3): مساحة لورقة عمق-3 واحدة أخرى.
لماذا الإنتروبيا تحدد طول الكود
عدم المساواة كرافت يحدد بنية الكود (يجب أن تناسب الأطوال الشجرة). إنتروبيا شانون تحدد كفاءة الكود (متوسط الطول لا يمكن أن يتغلب على حد نظري).
أطوال الكود الأمثل. لرمز بـ احتمال p_i، طول الكود المثالي هو log₂(1/p_i). الرموز النادرة تستحق أكواد طويلة؛ الرموز المتكررة تستحق أكواد قصيرة. هذا يعكس المساواة كرافت: 2^(−l_i) = p_i عندما l_i = log₂(1/p_i).
لكن log₂(1/p_i) نادراً ما يكون عدد صحيح. التقريب لأعلى إلى ⌈log₂(1/p_i)⌉ يعطي طول هوفمان، الذي يرضي H ≤ L < H + 1.
القراءة الهندسية. رسم كل رمز كنقطة على الشجرة الثنائية في العمق l_i. مجموع كرافت يقيس الغطاء الكلي للأوراق. الإنتروبيا تقيس متوسط موزون للعمق، موزون بالاحتمال. نظرية شانون: متوسط العمق الموزون بالاحتمال ≥ محتوى المعلومات الموزون بالاحتمال.
التحقق من حد الإنتروبيا
المثال العملي: p = [1/2, 1/4, 1/8, 1/8] للرموز {A, B, C, D}.
الأطوال المثالية: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
هذه كلها أعداد صحيحة — مطابقة مثالية. كود هوفمان: A=0, B=10, C=110, D=111.
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75.
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75. L = H بالضبط: كود أمثل.
مثال عملي كامل
خط أنابيب كامل: بالنظر إلى الاحتمالات، احسب الإنتروبيا، تحقق من أن الكود يرضي الحد.
المصدر: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
H = 1.75 بت (محسوب أعلاه).
كود بلوك ساذج: 4 رموز → 2 بت لكل واحد → L = 2.0. الزائد فوق الإنتروبيا: 2.0 − 1.75 = 0.25 بت/رمز = 12.5% هدر.
يوفر كود الطول المتغير 12.5% مقارنة برمز بطول ثابت. بالنسبة للرسائل الكبيرة، هذا كبير.
معدل إنتروبيا الإنجليزية. قدّر شانون إنتروبيا الإنجليزية المكتوبة بـ حوالي 1.0 إلى 1.3 بت لكل حرف، رغم استخدام أكواس ASCII بـ 5 بت. تعكس النسبة 4:1 الزيادة الهائلة من الحروف الشائعة في اللغة الطبيعية — تتجمع الحروف الشائعة، تتكرر الكلمات، القواعد تحد من التسلسلات.
الضغط لا يمكن أن يتغلب على الإنتروبيا
نسبة الضغط: H / (طول كود البلوك). بالنسبة لمثالنا: 1.75/2.0 = 0.875 — كفاءة 87.5%.
هل يمكنك الضغط أكثر؟ فقط باستخدام السياق: إذا قمت برمز أزواج أو ثلاثيات من الرموز معاً، قد تكون الإنتروبيا المشتركة H(X,Y) أقل من 2·H(X) بسبب الاعتماديات الإحصائية. هذا هو امتداد نظرية الترميز بدون ضوضاء إلى n-grams.