العشوائية المعلوماتية وأقصر ترميز

أكثر الحدود في هذا الميدان رخوة. تثبت أنّ الخطأ لا يتجاوز شيئاً ما، فيكون ذلك الشيء هائلاً، وتكون قيمة النتيجة في شكلها لا في رقمها.

والعشوائية المعلوماتية ليست من هذا النوع. إنّها أقصر ما يمكن أن يبلغه ترميز في المتوسّط، وثمّة ترميز يبلغها.

الادّعاء، على مصدر يمكن فحصه باليد

خذ أربعة رموز باحتمالات $\tfrac12$ و$\tfrac14$ و$\tfrac18$ و$\tfrac18$. العشوائية المعلوماتية تساوي

$$H = \sum_x p(x)\log_2\frac{1}{p(x)} = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75 \text{ bits}$$

والآن ابنِ أفضل ترميز بادئيّ، أي ترميزاً لا تكون فيه أيّ كلمة بدايةً لأخرى، فيُقرأ التدفّق بلا فواصل. بدمج أقلّ الرمزين احتمالاً مرّةً بعد مرّة تحصل على أطوال 1 و2 و3 و3 بتّات، ومتوسّطها

$$0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 \text{ bits}$$

أي العشوائية المعلوماتية بالضبط، إلى كلّ منزلة عشرية. أمّا ترميز ثابت الطول فيحتاج بتّين لكلّ رمز، فالتوفير 0.25 بتّة، أي 12.5٪.

وسبب المطابقة التامّة ظاهر في الحساب: كلّ طول مثاليّ $\log_2(1/p)$ هنا عدد صحيح، لأنّ كلّ احتمال قوّة للعدد اثنين. فيستطيع الترميز أن يعطي كلّ رمز الطول الذي يستحقّه بالضبط.

ما الذي يقوله الحدّ فعلاً

$$L \ge H$$

وهذا لكلّ ترميز وحيد فكّ الترميز، لا للتراميز البادئية وحدها.

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

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

حيث تكون البتّات الصحيحة أخشن ممّا ينبغي

غيّر المصدر إلى $(0.6,\ 0.25,\ 0.1,\ 0.05)$. العشوائية المعلوماتية 1.4905 بتّة، وأفضل ترميز بادئيّ متوسّطه 1.5500. ظهرت فجوة قدرها 0.0595 بتّة لكلّ رمز.

ولا عيب في الترميز؛ فهو مبرهَن الأمثلية بين التراميز البادئية لهذا المصدر. المشكلة في الحبيبيّة. فالطول المثاليّ لرمز احتماله 0.6 هو $\log_2(1/0.6) = 0.737$ بتّة، ولا كلمة ترميز طولها 0.737. وأفضل ما يمكن هو 1، فتدفع زيادةً قدرها 0.263 بتّة كلّما ظهر ذلك الرمز.

يبني الشكل أدناه الترميز بدل أن ينقله، وذلك لأي توزيع تضبطه. ابدأ من المصدر الثنائي الكسور تجد الفجوة صفرًا بالضبط. وأزِح أي احتمال عن قوة للعدد اثنين تظهر الفجوة فورًا، ويبيّن العمود الأيمن السبب: إذ يعرض الطول الذي يستحقّه كل رمز إلى جانب العدد الصحيح الذي لزم منحه إياه. ثم ارفع حجم الكتلة وراقب الفجوة تنغلق من فوق، بينما لا تتزحزح الإنتروبيا لكل رمز قيد أنملة.

الحيلة التي تغلق الفجوة

كفّ عن ترميز رمز واحد في المرّة. رمّز كتلاً منها، فيتوزّع خطأ التقريب على الكتلة:

اقتراب من فوق، دون تجاوز أبداً.

ويجدر التدقيق في سبب نجاح ذلك، لأنّ التفسير البديهيّ خاطئ. فالرموز هنا مستقلّة، فلا توجد بينها زيادة يمكن لكتلة أطول أن تستثمرها، ولا تتغيّر العشوائية لكلّ رمز. ما يتغيّر أنّ كتلة من أربعة لها 256 قيمة ممكنة، وأطوالها المثالية تُقارَب بأعداد صحيحة من البتّات مقاربةً أدقّ بكثير. فالهدر هو الكسر نفسه من بتّة موزّعاً على أربعة أضعاف الرموز.

ما الذي تقيسه العشوائية المعلوماتية

يغري أن تُقرأ بوصفها فوضى، وهذه القراءة غير ضارّة إلى أن تضرّ. والصوغ الدقيق هو متوسّط عدد أسئلة النعم أو لا اللازمة لتحديد النتيجة، حين يُسمح لك باختيار الأسئلة على الوجه الأمثل.

وهذا التأطير يفسّر شكل الصيغة. فرمز احتماله $p$ يحمل $\log_2(1/p)$ بتّة: اليقين يحمل صفراً، وحدث احتماله واحد في المليون يحمل نحو 20 بتّة. فالأحداث النادرة تفيد بالضبط لأنّها لم تكن متوقّعة، والعشوائية متوسّط تلك المفاجأة على كلّ ما يستطيع المصدر فعله.

ويفسّر أيضاً ما ليست هي: ليست خاصّية لسلسلة محارف. فالملفّ لا عشوائية له. المصدر له عشوائية، وتقديرك لها قولٌ عن النموذج الذي أحضرته.

ما الذي يمهّد له هذا

كلّ ما سبق افترض أنّك تعرف $p$. وأنت لا تعرفه أبداً. والدرس التالي يسأل عمّا يحدث حين تُرمّز مصدراً بأفضل ترميز لتوزيع خاطئ، ويتبيّن أنّ الجواب هو دالّة الخسارة التي كان كلّ مصنّف دربته يصغّرها أصلاً.