> shannon | fano | entropy <
// Shannon-Fano – ترميز إنتروبي من الأعلى إلى الأسفل لضغط البيانات
معتمد على الإنتروبيا
يستخدم نظرية المعلومات لإنشاء شيفرات فعّالة بطول متغيّر.
نهج من الأعلى إلى الأسفل
يقسم الرموز بشكل تكراري إلى مجموعات ذات احتمالات متقاربة.
خوارزمية تاريخية
طريقة رائدة أثّرت في العديد من تقنيات الضغط الحديثة.
>> معلومات تقنية
كيف يعمل ترميز شانون–فانو؟:
يرتّب ترميز شانون–فانو الرموز حسب التكرار، ثم يقسمها تكراريًا إلى مجموعتين لهما احتمال إجمالي متقارب قدر الإمكان. كل عملية تقسيم تضيف بتًا إلى الشيفرة (0 لليسار و1 لليمين). النتيجة هي شيفرة سابقة بطول متغيّر.
مثال على عملية الترميز:
النص: "AAABBCD" التكرارات: A:3, B:2, C:1, D:1 التقسيم: [A] | [B,C,D] الشيفرات: A: 0 B: 10 C: 110 D: 111 الناتج المرمّز: 0 0 0 10 10 110 111
لماذا تستخدم شانون–فانو؟:
- >سهل التنفيذ
- >نِسَب ضغط جيدة
- >أهمية تاريخية
- >مفيد في التعليم وشرح المفاهيم
- >شيفرات سابقة (Prefix codes)
>> الأسئلة الشائعة
ما هو ترميز شانون–فانو؟
ترميز شانون–فانو هو تقنية ترميز إنتروبي طوّرها كلود شانون وروبرت فانو في أربعينيات القرن الماضي. يُعد من أوائل الخوارزميات التي استخدمت شيفرات بطول متغيّر تعتمد على احتمالات الرموز.
شانون–فانو أم هوفمان؟
كلاهما ينتج شيفرات بطول متغيّر، لكن ترميز هوفمان أمثل ويعطي أقصر طول متوسط للشيفرة. شانون–فانو أبسط، لكنه قد ينتج شيفرات أطول قليلاً. هوفمان يبني الشجرة من الأسفل إلى الأعلى، بينما شانون–فانو من الأعلى إلى الأسفل.
كيف يتم تقسيم الرموز؟
تُرتَّب الرموز حسب التكرار، ثم تُقسَّم إلى مجموعتين ذواتي احتمال إجمالي متقارب قدر الإمكان. تتكرر العملية تكراريًا حتى تحتوي كل مجموعة على رمز واحد فقط.
هل ما زال شانون–فانو مستخدمًا اليوم؟
يُستخدم شانون–فانو اليوم في الغالب لأغراض تاريخية وتعليمية. في الاستخدام العملي استُبدل إلى حد كبير بترميز هوفمان الذي يضمن الأمثلية، لكنه لا يزال مهمًا لفهم مبادئ ضغط البيانات.
// مثال محلول
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// أمثلة برمجية
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> المزيد من الأسئلة
س: بماذا يختلف شانون-فانو عن هوفمان؟
ج: يقسّم شانون-فانو قائمة الرموز المرتبة من الأعلى إلى الأسفل إلى نصفين متقاربين في مجموع التكرارات، بينما يبني هوفمان الشجرة من الأسفل بدمج أندر الرموز. هوفمان مثالي بالبرهان أما شانون-فانو فلا دائماً.
س: هل شانون-فانو مثالي دائماً؟
ج: لا. في المثال يحتاج 89 بتاً مقابل 87 لهوفمان. كلاهما ينتج رموزاً بلا بادئات لكن قاعدة التقسيم في شانون-فانو قد تختار تقسيمات غير مواتية.
س: أين يُستخدم شانون-فانو؟
ج: أساساً كطريقة تاريخية وتعليمية (كلود شانون وروبرت فانو، 1948/49). توجد منه صيغة في خوارزمية IMPLODE لصيغة ZIP، وتستخدم الضاغطات الحديثة هوفمان أو الترميز الحسابي.