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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

خوارزمية شانون-فانو[عدل]

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

  1. لأي قائمة معينة من الرموز يتوجب معرفة جميع الاحتمالات وذلك بحصر جميع الرموز و تكرارها بحيث يكون لكل رمز تردد معروف.
  2. يتم ترتيب قائمة الرموز وفقا للتردد بحيث تكون الرموز الأكثر شيوعا في الجهة اليسرى الذي يليه ثم يليه حتى يصبح الرمز الأقل شيوعاً من القائمة في الجهة اليمنى.
  3. يتم تقسيم قائمة الرموز إلى جزأين بحيث يكون مجموع تردد الرموز في النصف الأيمن مقرب بقدر المستطاع لمجموع تردد الرموز في النصف الأيسر.
  4. يتم تعيين الرقم 0 إلى الجزاء الأيسر ، والرقم 1 إلى الجزاء الأيمن من قائمة الرموز. وهذا يعني أن الرموز في النصف الأيسر سوف تبدأ بالرقم 0 والرموز في النصف الأيمن تبدأ بالرقم 1.
  5. إذا كان هناك أكثر من رمز واحد في إحدى القوائم الناتجة عن ذلك التقسيم، يتم تكرار تطبيق الخطوات 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.}

انظر أيضاً[عدل]


Computer.svg هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال بحاجة للتوسيع. شارك في تحريرها.