IMG·ARCH
العقدة 03شجرة النموذج · اللاخسارة
SIGNAL
أول صيغتين حقيقيتينGIF ضد PNG

النمذجة والتنبّؤ: شجرة اللاخسارة

كيف نجعل البِكسلات متوقَّعة فينخفض إنتروبيها قبل المرمّز؟ هنا تتشكّل GIF و PNG، وتظهر أشهر قصّة في تاريخ صيغ الصور: كيف كادت براءةُ اختراعٍ واحدة تقتل GIF فأنجبت PNG.

سطر سماء متدرّج 40 42 45 47 48 48 49 …: فروقه الأفقية تنهار لأصفار. ممتاز. لكن سطر علم مخطّط 12 12 12 200 200 200 12 12 12 …: فروقه تصير 0 0 188 0 0 -188 … — تذبذب، لا أصفار!

صورة واحدة فيها سماء (يبرع التنبّؤ الأفقي) وأعلام (يفشل). لو ألزمتها بنموذج واحد تخسر في نصفها. كيف تختار النموذج المناسب لكل جزء؟ ومن يدفع ثمن إخبار الفكّاك؟ وماذا عن شعار ABCABC المتكرّر — أي نموذج يلتقط تكرار المقاطع بدل العلاقة بالجار؟

عائلتان من النماذج اللاخسارة

اللغز كشف عائلتين، وهما تقريباً كل النمذجة اللاخسارة:

تنبّؤ
من الجيران (PNG)
قاموس
تكرار مقاطع (GIF/LZ)

عائلة القاموس: LZ و LZW وقصّة GIF

أبسط تكرار غير متتالٍ هو تكرار مقطع ظهر سابقاً. LZ77 (نافذة منزلقة، تُخرج (مسافة، طول، الرمز)) قلب DEFLATE/PNG. LZW يبني قاموساً ينمو ذاتياً ويُعاد بناؤه في الفكّاك دون إرساله — وهو ما اختارته GIF.

ليش تاريخي — القانون يصمّم الصيغ

GIF (1987) اختار LZW، المحميّ ببراءة Unisys. في 1994 بدأت Unisys المطالبة برسوم على كل برنامج يكتب GIF ("GIF Tax"). ردّ المجتمع بتصميم صيغة بديلة حرّة عمداً → وُلد PNG (1996) باختيار DEFLATE لا LZW، ليس لأنه أفضل تقنياً، بل لتفادي البراءة. ستراه يتكرّر مع الترميز الحسابي في JPEG، ومع AVIF/JPEG XL. البراءات خيطٌ أحمر يشرح نصف قرارات المجال.

عائلة التنبّؤ: مرشّحات PNG واشتقاق Paeth

حلّ PNG عبقريّ: كل سطر يختار مرشّحه ويخبر الفكّاك ببايت واحد. خمسة مرشّحات تتنبّأ بقيمة كل بايت ثم تخزّن الفرق:

FIG 1 جيران PNG ومرشّحاته الخمسة
الجوار C B A X X = الحالي 0 None : pred = 0 1 Sub : pred = A 2 Up : pred = B 3 Average : pred = (A+B)/2 4 Paeth : pred = Paeth(A,B,C) خزّن (X − pred): إنتروبيه أقلّ p = A + B − C اختر الأقرب لـp من {A,B,C} ⇒ يتبع الحافة تلقائياً
Paeth: يحسب تقدير متوازي الأضلاع p=A+B−C ثم يختار الجار الأقرب إليه — فيتكيّف مع الحواف الأفقية والرأسية بلا أي بيانات إضافية.
بذرة ستنفجر لاحقاً

"التنبّؤ من السياق" هنا هو جذر intra-prediction في فيديو HEVC/AV1 (العقدة ٠٦): Paeth على منشّطات — تنبّؤ اتّجاهي ببلوكات كاملة و٣٥+ اتجاهاً. الجذر هنا.

ليش — المرشّح لا يضغط

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

الصيغتان — فلسفتان متعاكستان

FIG 2 GIF و PNG — تركيب اللبنات
GIF لوحة ألوان ≤256 LZW (قاموس) يفترض الصورة قليلة الألوان PNG مرشّح لكل سطر DEFLATE = LZ77+Huffman truecolor + alpha، حرّ
GIF يفترض فقر الألوان (ممتاز للشعارات، كارثي للصور)؛ PNG يعتمد على التنبّؤ ويدعم الألوان الكاملة والشفافية — لكن كليهما لاخسارة فيبقيان ضخمين للصور الفوتوغرافية.
  1. نفّذ المرشّحات الخمسة. لكل سطر اختر ذا أقلّ مجموع قيم مطلقة للفروقات (هو فعلاً ما تستعمله libpng).
  2. مرّر الناتج على مرمّز Huffman من العقدة ٠٢. قارن الحجم مع تطبيق Huffman مباشرة بلا مرشّحات — كم وفّر التنبّؤ؟
  3. اصنع صورة نصفها تدرّج ونصفها خطوط حادّة. تحقّق أن مرمّزك اختار مرشّحات مختلفة للنصفين تلقائياً. اطبع التوزيع.
  4. تحدٍّ: نفّذ LZW من الصفر، طبّقه على ABABAB…، وراقب القاموس يلتقط AB, ABA, ABAB…. اشتقّ بنفسك كيف يعرف الفكّاك القاموس دون إرساله.
الخلاصة

النمذجة اللاخسارة عائلتان: تنبّؤ مكاني (PNG) وقاموس (LZ/LZW). GIF وُلد من LZW فجرّته لأزمة براءة، و PNG وُلد ردّاً عليها حرّاً. العائق الجوهري: كلاهما لاخسارة → ضخم للصور الفوتوغرافية، لأنهما يحفظان تفاصيل لا تراها العين أصلاً. هذه الثغرة ستقتحمها الشجرة الخَسورة — بعد أن نفهم العين.