ترميز شانون-فانو

ترميز شانون-فانو (بالإنجليزية: Shannon–Fano coding) عبارة عن ترميز يستخدم لضغط البيانات استناداً إلى مجموعة من الرموز واحتمالاتها

خوارزمية شانون-فانو

لبناء شجرة الترميز شانون-فانو يجب مراعاة التالي:

1. لأي قائمة معينة من الرموز ، يجب معرفة الاحتمالات تكرار الرمز أو حصر تكرار الرمز بحيث يكون لكل رمز تردد معروف.
2. يتم ترتيب القائمة الرموز وفقا للتردد (مقياس لتكرار) ، بحيث تكون الرموز الأكثر شيوعا في الجهة اليسرى ثم الذي يليه والذي يليه حتى يصبح الرمز الأقل شيوعا من القائمة في الجهة اليمنى.
3. يتم تقسيم قائمة إلى جزأين بحيث يكون مجموع تردد الرموز في النصف الأيمن مقرب بقدر مستطاع مجموع تردد الرموز في النصف الأيسر.
4. يتم تعيين الرقم 0 الي الجزاء الأيسر والرقم 1 الي الجزاء الأيمن من قائمة الرموز. وهذا يعني أن الرموز في النصف الأيسر سوف تبدأ بالرقم 0 والرموز في النصف الأيمن تبدأ بالرقم 1.
5. إذا كان هناك أكثر من رمز واحد في إحدى القوائم الناتجة عن ذلك التقسيم، يتم تكرر تطبيق الخطوات 3 و 4 على هذه القوائم المقسمة.

مثال

ملف:ShannonCodeAlg.svg

خوارزمية شانون-فانو

المثال التالي يظهر فيه نطبيق لخوارزمية شانون-فانو لبناء الشجرة لخمسة رموز مع ترددتها موضحة في الجدول التالية:

الرمز	A	B	C	D	E
العداد	15	7	6	6	5
الإحتمالات	0.38461538	0.17948718	0.15384615	0.15384615	0.12820513

كل الرموز يتم ترتيبها حسب التردد من اليسار إلى اليمين كما هو موضح في الفقرة (a) من الصورة. بعد ذلك يتم وضع الخط فاصل بين الرمز B و الرمز C موضح في الفقرة (b) بحيث يكون مجموع الجزاء الأيسر 22 مقرب لمجموع الجزاء الأيمن 17. وهذا أقل فارق بين مجاميع المجموعتين.

الرمز	A	B	C	D	E
الترميز	00	01	10	110	111

نتيجة ترميز شانون-فانو للرموز A B C بتان لكل رمز وثلاث بتات للرموز D E

$\frac{2\text{Bit}\cdot (15+7+6)+3\text{Bit}\cdot (6+5)}{39\text{Symbol}}\approx 2.28\text{Bits per Symbol.}$

خوارزمية هوفمان

طالع أيضاً: ترميز هوفمان

يتم إنشاء شجرة الترميز لشانون فانو من الجذر إلى الأوراق بينما يقوم ترميز هوفمان من الأوراق إلى جذر في الاتجاه المعاكس.

مثال

ملف:HuffmanCodeAlg.png

خوارزمية شانون-فانو

باستخدام نفس المثال السابق أعلاه لخمسة رموز مع ترددتها موضحة في الجدول التالية:

الرمز	A	B	C	D	E
العداد	15	7	6	6	5
الإحتمالات	0.38461538	0.17948718	0.15384615	0.15384615	0.12820513

يعتبر ترميز هوفمان أفضل من شانون-فانو كما هو موضح في الجدول التالي:

الرمز	A	B	C	D	E
الترميز	0	100	101	110	111

نتيجة ترميز هوفمان واحد بت للرمز A وثلاث بتات للرموز B C D E

$\frac{1\text{Bit}\cdot 15+3\text{Bit}\cdot (7+6+6+5)}{39\text{Symbol}}\approx 2.23\text{Bits per Symbol.}$

انظر أيضاً

• ترميز هوفمان

ca:Algorisme de Huffman cs:Shannonovo-Fanovo kódování de:Shannon-Fano-Kodierung Shannon–Fano coding]] es:Algoritmo de Huffman fr:Codage de Shannon-Fano ja:シャノン符号化 pl:Kodowanie Shannona-Fano pt:Codificação de Shannon-Fano ru:Алгоритм Шеннона — Фано