IMG·ARCH
العقدة 02شجرة المرمّز
SIGNAL
من الاحتمال إلى البِتّاتأربعة أجيال

ترميز الإنتروبي

عندنا رموز، لكلٍّ احتمال، ونريد كتابتها بأقرب ما يمكن إلى حدّ شانون H. سنبني أربعة أجيال يصلح كلٌّ خطأ سابقه: RLE → Huffman → الحسابي → ANS — وهي كلّ مرمّزات صيغ الصور قاطبةً.

مصدر برموز A:0.9 B:0.04 C:0.03 D:0.03. احسب H (ستجده أقلّ من بِت واحد بكثير).

صمّم أكواد بادئة (prefix-free). المشكلة: أقصر كود طوله بِت واحد على الأقل. فمتوسّطك ≥ ١ بِت/رمز مهما فعلت — لكن H أقلّ من ١! أنت محشور: شانون يقول الحدّ أقلّ من بِت، لكن "بِت واحد" أصغر عملة تملكها. كيف تنفق نصف بِت على رمز؟

الجيل الأول: Huffman — مثلى لكن صحيحة

الرمز الأشيع يستحق كوداً أقصر. مثّل الأكواد كشجرة ثنائية؛ كل ورقة رمز، والمسار إليها كوده — وشرط البادئة يتحقّق تلقائياً (كل الرموز أوراق). الخوارزمية الجشعة: ادمج أصغر عقدتين وزناً تكراراً حتى تبقى عقدة واحدة.

FIG 1 بناء شجرة Huffman — الرمز الأشيع أقرب للجذر
01 01 01 1.0 A0.9 → "0" .10 B.04 · C D A="0"(1b) · B="10"(2b) C/D="110/111"(3b)
الرمز المهيمن A يصل لورقة بعمق 1 (كود "0")، والنادر يغوص أعمق. لكن أقصر كود = بِت كامل — وهنا الفخّ.
جذر الفخّ — حدّ Huffman

متوسّط Huffman بين H و H+1، فلا يبلغ H لأنه ملزَم بأطوال صحيحة. على مصدر A:0.99, B:0.01: H≈0.08 بِت/رمز، لكن Huffman يعطي بِتّاً لكلٍّ = متوسّط ١ بِت = أسوأ من الأمثل ١٢ ضعفاً! ضاع الـ0.92 بِت في "تقريب نصف بِت لأعلى". هذا هو الثقب الذي يملؤه الجيل التالي — وهو سبب هجر الصيغ الحديثة لـHuffman.

الجيل الثاني: الترميز الحسابي — كتابة أجزاء البِت

المشكلة أن Huffman يخصّص كوداً لكل رمز فأقلّ عملة بِت كامل. الحلّ الثوري: رمّز الرسالة كلّها كعددٍ واحد. قسّم [0,1) بنسب الاحتمالات؛ كل رمز يختار شريحته فتصير مجالك الجديد؛ كرّر. أرسِل أي عدد في المجال النهائي.

FIG 2 الترميز الحسابي — تعشيش المجالات يبلغ H
A (.0–.6)BC/D «كبّر» شريحة A لتصير المجال الجديد، وقسّمها بنفس النسب AAAB عرض المجال النهائي = Π pᵢ bits = log₂(1/Π pᵢ) = Σ log₂(1/pᵢ) = N·H ⇒ يبلغ H بلا هدر التقريب. الرمز الواحد قد يكلّف 0.08 بِت فعلاً.
الكلفة موزّعة على العدد النهائي ولا تُقطّع لرموز منفصلة — لهذا يبلغ H حيث عجز Huffman. تأخّر تبنّيه بسبب براءات اختراع لا قصور تقني.

الجيل الثالث: ANS — سرعة Huffman بدقّة الحسابي

الحسابي يبلغ H لكنه بطيء. سؤال Duda (2009): اجمع سرعة جداول Huffman مع دقّة الحسابي → ANS (Asymmetric Numeral Systems): نظام عدّ غير متماثل حيث كل رمز "يدفع" log₂(1/pᵢ) بِت حسب احتماله. الحالة عدد صحيح x؛ الترميز يحوّله إلى x' ≈ x/pₛ. يصير بحثاً في جدول صغير — سرعة قريبة من Huffman، مع بلوغ H.

خصوصية تربك المبتدئ

ANS يفكّ بترتيب معكوس لترتيب الترميز (مكدّس LIFO). قيد معماري حقيقي يؤثّر على تنظيم الصيغ لبياناتها — ستراه يفسّر قرارات في العقدة ٠٨.

المرمّزيبلغ H؟السرعةصيغ تستعمله
RLEلافائقBMP, TIFF, ذيل DCT
HuffmanلاعالٍPNG (DEFLATE), JPEG
الحسابي/المدىنعممنخفضJPEG2000, JBIG2, VP8
ANSنعمعالٍJPEG XL, AVIF, Zstd
  1. اقرأ ملفاً، احسب تكرار البايتات، ابنِ شجرة Huffman، رمّز إلى تيّار بِتّات (جمّع البِتّات في بايتات يدوياً)، ثم اكتب الفكّاك. تحقّق من التطابق.
  2. قِس الهدر: صمّم مدخلاً ٩٩٪ بايت واحد و١٪ متنوّع. احسب الحجم الفعلي / الحجم النظري N·H. يجب أن يكون أكبر بكثير من ١.
  3. تحدٍّ: نفّذ ترميزاً حسابياً ثنائياً بسيطاً مع إعادة تطبيع، ورمّز المدخل الكارثي نفسه. شاهد 0.08 بِت/رمز تتحقّق فعلياً.

لا تنتقل قبل أن ترى رقم الهدر بعينيك. أن تقيس بنفسك أن Huffman أهدر ١٢ ضعفاً على مدخلٍ صمّمته = فهمٌ لا يُنسى.

الخلاصة

المرمّز يحوّل (رمز، احتمال) إلى بِتّات هدفه بلوغ H. Huffman محبوس فوق H بالتقريب الصحيح؛ الحسابي يبلغه بكتابة أجزاء البِت؛ ANS يجمع الدقّة بالسرعة. لكن المرمّز نصف القصّة — هو يفترض أن "النموذج" أعطاه احتمالات جيّدة. من أين تأتي الاحتمالات الجيّدة؟ هذا النموذج، وإليه ننتقل.