📨 لغز الملف الذي يتقلّص
تسحب مستندًا نصيًّا إلى مجلد ZIP. كان حجمه 100 كيلوبايت، فإذا به 40 كيلوبايت. تعيد فتحه : لم يختفِ أي حرف. كيف يكون ذلك ممكنًا ؟ من أين جاءت هذه المساحة الموفّرة، إذا لم يُفقَد شيء ؟
الجواب يكمن في فكرة بسيطة على نحو مذهل. في الحاسوب، كل حرف يشغل عادةً 8 بتات (بايت واحد)، سواء كان متكررًا أو نادرًا. فحرف E، الحاضر في كل مكان في الفرنسية، وحرف W، الذي يكاد لا يُعثَر عليه، يكلّفان تمامًا الشيء نفسه. يا له من تبذير ! الفكرة العبقرية : إعطاء رموز قصيرة للحروف المتكررة ورموز طويلة للحروف النادرة. في المتوسط، تقصر الرسالة. هذا هو كل سرّ ترميز هوفمان.
🌳 ابنِ شجرة هوفمان
اختر كلمة، ثم ادمج خطوة بخطوة العقدتين الأقل تكرارًا. تمنح الشجرة النهائية كل حرف رمزه الأمثل.
اختر كلمة وانقر على «خطوة» لدمج أصغر تكرارين.
ASCII (8 بتات)
—
هوفمان
—
الضغط
—
الطول المتوسط : — بت/حرف
🎓 واجب طالب غيّر العالم
عام 1951، في معهد MIT. اقترح الأستاذ روبرت فانو على طلبته خيارًا : اجتياز الامتحان النهائي، أو تسليم واجب يحلّ مشكلة مفتوحة — إيجاد الرمز الثنائي الأقصر الممكن لتمثيل مجموعة من الرموز. لم يكن أحد، ولا حتى فانو ولا زميله الشهير كلود شانون، يعرف إن كانت توجد حقًّا حلّ أمثل.
طالب عمره 25 سنة، دافيد أ. هوفمان، اختار الواجب. كافح أسابيع دون نجاح، وكان على وشك التخلّي عنه ليراجع للامتحان. وهناك، وهو يرمي ملاحظاته، جاءه الإلهام : بدلًا من بناء الشجرة من الأعلى إلى الأسفل (كما كان الجميع يحاول)، يجب بناؤها من الأسفل إلى الأعلى، انطلاقًا من الرموز الأكثر ندرة. منهجه، المنشور عام 1952، لم يكن بسيطًا فحسب، بل مُبرهَنًا على كونه أمثل. لقد تفوّق، دون أن يدري، على أستاذه نفسه.
🔑 القاعدة الذهبية: رمز بلا بادئة
إذا كان E يساوي 0 وT يساوي 01، فلدينا
مشكلة : عند قراءة 01، لا يعرف الحاسوب إن كان ذلك « T »
أم « E متبوعًا بشيء ما ». لفك الترميز دون أدنى لبس،
يفرض هوفمان شرطًا :
رمز بادئي («بلا بادئة»). لا يكون أي رمز حرف هو
بداية رمز آخر. إذا كان A = 0، فلا يمكن
لأي حرف آخر أن يبدأ بـ 0. والنتيجة : نقرأ
تدفق البتات من اليسار إلى اليمين، وبمجرد أن نتعرّف على رمز، فهو حتمًا ذاك بالذات.
لا حاجة لفاصل، ولا لبس.
هذا بالضبط ما تضمنه شجرة ثنائية : كل حرف هو
ورقة. للوصول إلى ورقة، ننزل مسجّلين 0 عند كل انعطاف
إلى اليسار و1 إلى اليمين. وبما أن الورقة لا تكون أبدًا على طريق ورقة
أخرى، فلا يمكن لرمزها أن يكون أبدًا بادئة رمز آخر. الخاصية مجانية.
🛠️ الخوارزمية الجشعة، في أربع مراحل
منهج هوفمان هو خوارزمية جشعة : في كل خطوة، تتخذ الاختيار الذي يبدو الأفضل في تلك اللحظة — دمج الرمزين الأكثر ندرة — دون أن تعود أبدًا إلى الوراء. وهنا، أعجوبة، يؤدي هذا الاختيار المحلي إلى النتيجة المثلى إجماليًّا.
- العدّ. نُحصي تكرار كل حرف في النص.
- ورقة لكل حرف. يصير كل حرف عقدة معزولة، موسومة بتكراره. نضعها في طابور أولوية (أصغر التكرارات أولًا).
- دمج الأصغرين. نسحب العقدتين الأقل تكرارًا وننشئ عقدة أبًا تكرارها هو مجموعهما. نعيدها إلى الطابور.
- نعيد الكرّة إلى أن تبقى عقدة واحدة فقط : جذر الشجرة. تُقرأ الرموز عندئذٍ من الجذر نحو كل ورقة (يسار = 0، يمين = 1).
لماذا نبدأ بالأكثر ندرة ؟ لأن دمج عقدتين يدفعهما درجة أعمق في الشجرة — فيمنحهما رمزًا أطول. نريد أن نُطيل بالأولوية الحروف النادرة، وأن نُبقي المتكررة قرب الجذر، حيث تكون الرموز قصيرة. العب بالتمثيل البصري أعلاه لتراها تولد خطوة بخطوة.
🏆 لماذا هو حقًّا الأفضل
أمثلية هوفمان ليست انطباعًا : إنها تُبرهَن. تستند الحجة إلى ملاحظة لا تُدحض : في رمز أمثل، يجب على الرمزين الأقل تكرارًا حتمًا أن يكونا الأعمق في الشجرة، وأن يكونا شقيقين (تحت العقدة الأب نفسها). وإلا، لأمكن تبديلهما بأوراق أعمق وتقصير المجموع — وهذا تناقض.
وهذا بالضبط ما يفعله هوفمان منذ دمجه الأول. وبتكرار الحجة على الشجرة المختزَلة (بالتراجع)، نُبرهن على أنه لا يمكن لأي رمز بادئي أن يكون أفضل. من بين كل الرموز الممكنة، يبلغ رمز هوفمان الطول المتوسط الأدنى.
الطول المتوسط. إذا كان للحرف i تكرار pi ورمز طوله ℓi، فإن الكلفة المتوسطة لكل حرف هي مجموع pi × ℓi. يجعل هوفمان هذا المجموع أصغر ما يمكن — وهذا هو تعريف الأمثلية ذاته.
📏 الحد الأقصى المطلق: إنتروبيا شانون
هل يمكن الضغط إلى ما لا نهاية ؟ لا. برهن كلود شانون عام 1948 أنه توجد أرضية مطلقة، هي إنتروبيا المصدر : العدد المتوسط للبتات الضرورية حقًّا لترميز رمز. حرف باحتمال p يحمل log2(1/p) بت من المعلومات : الأحداث النادرة « مفاجئة » فهي مكلفة، والمتكررة شبه مجانية.
الإنتروبيا ≤ هوفمان < الإنتروبيا + 1
يقترب ترميز هوفمان من أرضية شانون بفارق أقل من بت واحد لكل رمز. لا يمكنه النزول تحت الإنتروبيا (لكان ذلك فقدانًا للمعلومات)، ولا يبتعد عنها أبدًا بأكثر من بت واحد. إنه أفضل ما في العالمين : أمثل ومحدود بالنظرية.
نقطة ضعفه الصغيرة الوحيدة : يتلقى كل حرف عددًا صحيحًا من البتات. عندما تساوي الإنتروبيا المثالية، لنقل، 2,3 بت، يضطر هوفمان إلى التقريب. تقنيات أحدث (الترميز الحسابي، الترميز بالـ مجال / range coding) تمحو هذا التبذير الأخير الصغير بترميز كسور من البت — لكنها تستند جميعًا إلى الحدس نفسه الذي أسّسه هوفمان.
🌍 هوفمان في كل مكان (حقًّا في كل مكان)
بعد سبعين سنة، يعمل رمز هوفمان مليارات المرات في الثانية في العالم، شبه خفيٍّ دائمًا :
- ZIP, gzip, PNG : خوارزمية DEFLATE التي تشغّلها تجمع بين قاموس (LZ77) وترميز هوفمان نهائي.
- JPEG : بعد تحويل الصورة، تُضغط معاملاتها بهوفمان.
- MP3, AAC : الصوت الرقمي، بعد تحليله إلى ترددات، يمرّ هو أيضًا عبر جداول هوفمان.
- الفاكس، المودِم، بروتوكولات الشبكة : حيثما نُرسل بيانات، نسعى أولًا إلى تقصيرها.
مع كل صورة ترسلها، وكل أغنية تستمع إليها بالبث، وكل صفحة ويب تُحمَّل، تعمل فكرة طالب عمره 25 سنة بهدوء من أجلك.
🎒 الرابط مع برنامجك
ترميز هوفمان نقطة التقاء رائعة بين عدة مفاهيم تصادفها في دروس المعلوميات والرياضيات :
- الأشجار الثنائية : الأوراق، الجذر، العمق، الاجتياز — هوفمان أكثر تطبيقاتها أناقة.
- الخوارزميات الجشعة : حالة نموذجية يَضمن فيها الاختيار المحلي الأمثل الأمثلية الإجمالية (نادر، وقابل للبرهنة).
- طوابير الأولوية (الأكوام) : البنية التي تتيح سحب العنصرين الأصغرين بكفاءة في كل خطوة.
- اللوغاريتمات & الاحتمالات : الإنتروبيا، log2، الأمل الرياضي لطول رمز — الرياضيات وراء الضغط.
- التعقيد : يكلّف بناء الشجرة O(n log n) بفضل طابور الأولوية.