ترميز Shannon-Fano: شرح مبسّط مع مثال عملي والفرق عن هوفمان
ترميز Shannon-Fano (شانون-فانو) هو خوارزمية لضغط البيانات بلا فقدان، تعمل بإعطاء الرموز الأكثر تكرارًا أكوادًا ثنائية قصيرة والرموز النادرة أكوادًا أطول، بحيث يصغر الحجم الإجمالي للملف. الفكرة الجوهرية بسيطة: رتّب الرموز حسب تكرارها، ثم قسّمها مرارًا إلى مجموعتين متقاربتين في مجموع الاحتمالات، وأعطِ كل انقسام بِتًا واحدًا (0 أو 1). في هذا الشرح ستفهم كيف يعمل بالضبط عبر مثال محلول كاملًا، ولماذا حلّ محلّه غالبًا ترميزُ هوفمان.
من أين جاء وما فكرته الأساسية
طوّره كلود شانون وروبرت فانو في أواخر الأربعينيات ضمن نظرية المعلومات. المبدأ مأخوذ مباشرة من فكرة شانون: الرمز الذي يظهر كثيرًا يحمل «مفاجأة» أقل، فيستحق تمثيلًا أقصر. هذا ما يُسمّى الترميز حسب التكرار (Entropy Coding)، ويشترك فيه شانون-فانو مع هوفمان وترميزات حديثة أخرى.
نقطة مهمة كثيرًا ما تُخلط: شانون-فانو ليس تشفيرًا أمنيًا، بل ضغط. لا يوجد فيه «مفتاح سرّي»؛ أي شخص يملك جدول الأكواد يستطيع فكّ الضغط.
كيف يعمل خطوة بخطوة
الخوارزمية تتبع نهج «فرّق تسُد» من الأعلى إلى الأسفل:
- احسب تكرار (أو احتمال) كل رمز في البيانات.
- رتّب الرموز تنازليًا حسب التكرار.
- قسّم القائمة إلى مجموعتين بحيث يكون مجموع تكرارات كل مجموعة متقاربًا قدر الإمكان.
- أضِف بِت
0لأكواد المجموعة الأولى و1لأكواد المجموعة الثانية. - كرّر الخطوتين 3 و4 داخل كل مجموعة على حدة حتى تصبح كل مجموعة رمزًا واحدًا.
الناتج النهائي هو شيفرة بادئية (Prefix Code): لا يكون أي كود بدايةً لكود آخر، ولذلك يمكن فكّ التسلسل الثنائي دون فواصل أو التباس.
مثال عملي محلول بالكامل
لنفترض أن لدينا خمسة رموز بالتكرارات التالية (المجموع = 57):
| الرمز | التكرار |
|---|---|
| E | 20 |
| D | 15 |
| C | 10 |
| B | 7 |
| A | 5 |
الترتيب تنازليًا جاهز: E, D, C, B, A. نبحث عن نقطة القطع الأقرب إلى النصف (28.5):
- القطع الأول:
E, D(مجموعها 35) مقابلC, B, A(مجموعها 22). نعطي المجموعة الأولى0والثانية1. - داخل
E, D: نقسم إلىE=0وD=1. إذًا E = 00 وD = 01. - داخل
C, B, A(مجموعها 22، النصف 11): نقطع بينC(10) وB, A(12). فيصبحC=10. - داخل
B, A:B=0وA=1، أي B = 110 وA = 111.
جدول الأكواد النهائي:
| الرمز | الكود | عدد البتات |
|---|---|---|
| E | 00 | 2 |
| D | 01 | 2 |
| C | 10 | 2 |
| B | 110 | 3 |
| A | 111 | 3 |
متوسط طول الكود = (20×2 + 15×2 + 10×2 + 7×3 + 5×3) ÷ 57 ≈ 2.35 بت لكل رمز، مقابل 3 بتات لو استخدمنا تمثيلًا ثابتًا لخمسة رموز. هذا هو الوفر الذي يحقّقه الضغط.
شانون-فانو أم هوفمان؟
هذا هو السؤال العملي الأهم، لأن هوفمان هو البديل المباشر والأكثر استخدامًا اليوم:
| المعيار | شانون-فانو | هوفمان |
|---|---|---|
| اتجاه البناء | من الأعلى للأسفل (تقسيم) | من الأسفل للأعلى (دمج) |
| الأمثلية | جيّد لكن ليس مضمونًا الأمثل | مثالي دائمًا (أقصر متوسط طول) |
| نوع الكود | بادئي | بادئي |
| صعوبة الفهم | أبسط قليلًا للمبتدئ | متوسط |
| الاستخدام الفعلي | تعليمي وتاريخي غالبًا | مستخدم في ZIP وJPEG وغيرها |
الخلاصة العملية: إن أردت أفضل ضغط ممكن اختر هوفمان؛ ويبقى شانون-فانو ممتازًا لفهم مبدأ الترميز حسب التكرار وكخطوة أولى قبل دراسة هوفمان.
خطأ شائع يقع فيه المبتدئون
عند القطع، لا يكفي أن «تنصّف عدد الرموز»؛ المطلوب تنصيف مجموع التكرارات. لو قسمت E,D,C في جهة وB,A في الأخرى لأن العدد 3 مقابل 2، لحصلت على تقسيم غير متوازن (35 مقابل… بل 45 مقابل 12) وضغطٍ أسوأ. راقب دائمًا مجموع الاحتمالات، لا عدد العناصر. وتذكّر أن التعادل التام نادر، فاختر الأقرب للنصف واثبت على قاعدة واحدة عند التساوي.
الأسئلة الشائعة
هل ترميز شانون-فانو بلا فقدان؟ نعم، تمامًا. يمكن استرجاع البيانات الأصلية بت ببت دون أي خسارة، شأنه شأن هوفمان وZIP.
لماذا لا يُستخدم كثيرًا اليوم؟ لأن هوفمان يضمن متوسط طول أقصر أو مساوٍ بالتكلفة الحسابية نفسها تقريبًا، فلا سبب عملي لتفضيل شانون-فانو خارج التعليم.
هل يصلح لأي نوع من البيانات؟ يعمل حيث تتفاوت تكرارات الرموز بوضوح (نصوص مثلًا). أما البيانات العشوائية أو المضغوطة مسبقًا فلا يوفّر فيها شيئًا يُذكر.
ما الفرق بينه وبين الضغط بالفقدان مثل JPEG؟ شانون-فانو بلا فقدان ويحافظ على كل بت. الضغط بالفقدان يحذف تفاصيل يصعب على الحواس ملاحظتها ليصغّر الحجم أكثر، وهو أسلوب مختلف كليًا في الهدف.