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

ترميز شانون-فانو (بالإنجليزية: Shannon–Fano coding)‏ هو ترميز يستخدم لضغط البيانات استناداً إلى مجموعة من الرموز واحتمالاتها، يُنسب إلى كلود شانون وروبرت فانو.^[1]

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

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

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

مثال

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

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

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

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

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

نتيجة ترميز شانون-فانو للرموز 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.}}

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

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

مثال

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

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

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

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

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

نتيجة ترميز هوفمان واحد بت للرمز 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.}}

انظر أيضاً

ترميز هوفمان

مراجع

^ "APPNOTE.TXT - .ZIP File Format Specification". PKWARE Inc. 28 سبتمبر 2007. مؤرشف من الأصل في 2014-12-05. اطلع عليه بتاريخ 2008-01-06. The Imploding algorithm is actually a combination of two distinct algorithms. The first algorithm compresses repeated byte sequences using a sliding dictionary. The second algorithm is used to compress the encoding of the sliding dictionary output, using multiple Shannon–Fano trees.

[1] "APPNOTE.TXT - .ZIP File Format Specification". PKWARE Inc. 28 سبتمبر 2007. مؤرشف من الأصل في 2014-12-05. اطلع عليه بتاريخ 2008-01-06. The Imploding algorithm is actually a combination of two distinct algorithms. The first algorithm compresses repeated byte sequences using a sliding dictionary. The second algorithm is used to compress the encoding of the sliding dictionary output, using multiple Shannon–Fano trees.

[1]