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

ترميز شانون-فانو  هو ترميز يستخدم لضغط البيانات استناداً إلى مجموعة من الرموز واحتمالاتها، يُنسب إلى كلود شانون وروبرت فانو.

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

مثال 

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

{| class="wikitable" border="0"
! الرمز
! 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. وهذا أقل فارق بين مجموع المجموعتين.

{| class="wikitable" border="0"
! الرمز
! E
! D
! C
! B
! A
|-
| الترميز
| 111
| 110
| 10
| 01
| 00
|}

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

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

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

مثال 

باستخدام نفس المثال السابق أعلاه لخمسة رموز مع ترددتها موضحة في الجدول التالية:
{| class="wikitable" border="0"
! الرمز
! E
! D
! C
! B
! A
|-
| العداد
| 5
| 6
| 6
| 7
| 15
|-
| الاحتمالات
| 0.12820513
| 0.15384615
| 0.15384615
| 0.17948718
| 0.38461538
|}
يعتبر ترميز هوفمان أفضل من شانون-فانو كما هو موضح في الجدول التالي:
{| class="wikitable" border="0"
! الرمز
! E
! D
! C
! B
! A
|-
| الترميز
| 111
| 110
| 101
| 100
| 0
|}

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

انظر أيضاً 
 ترميز هوفمان

مراجع 

توسيم
خوارزميات ضغط بيانات غير مضيعة
ضغط بيانات
علم الحاسوب
كلود شانون