عرض مصدر ترميز شانون وفانو

'''[[ترميز]] شانون-فانو''' {{إنج|Shannon–Fano coding}} هو [[ترميز]] يستخدم ل[[ضغط بيانات|ضغط البيانات]] استناداً إلى مجموعة من الرموز واحتمالاتها، يُنسب إلى [[كلود شانون]] و[[روبرت فانو]].<ref>{{استشهاد بويب
| مسار        = http://www.pkware.com/documents/casestudies/APPNOTE.TXT
| عنوان      = <tt>APPNOTE.TXT</tt> - .ZIP File Format Specification
| تاريخ الوصول = 2008-01-06
| ناشر  = PKWARE Inc
| تاريخ       = 2007-09-28
| اقتباس      = 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.
| مسار أرشيف = https://web.archive.org/web/20141205201932/http://www.pkware.com/documents/casestudies/APPNOTE.TXT | تاريخ أرشيف = 05 ديسمبر 2014 }}</ref>

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

=== مثال ===
[[ملف:ShannonCodeAlg.svg|تصغير|300px|خوارزمية شانون-فانو]]

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

:{| 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

:<math>\frac{2\,\text{Bit}\cdot(15+7+6) + 3\,\text{Bit} \cdot (6+5)}{39\, \text{Symbol}} \approx 2.28\,\text{Bits per Symbol.}</math>

== خوارزمية [[ديفيد هوفمان|هوفمان]] ==
{{مفصلة|ترميز هوفمان}}
يتم إنشاء شجرة الترميز لشانون فانو من الجذر إلى الأوراق بينما يقوم [[ترميز هوفمان]] من الأوراق إلى جذر في الاتجاه المعاكس.
=== مثال ===
[[ملف:HuffmanCodeAlg.png|تصغير|300px|خوارزمية هوفمان]]

باستخدام نفس المثال السابق أعلاه لخمسة رموز مع ترددتها موضحة في الجدول التالية:
:{| 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

:<math>\frac{1\,\text{Bit}\cdot 15 + 3\,\text{Bit} \cdot (7+6+6+5)}{39\, \text{Symbol}} \approx 2.23\,\text{Bits per Symbol.}</math>

== انظر أيضاً ==
* [[ترميز هوفمان]]
== مراجع ==

{{مراجع}}
{{طرائق الضغط}}
{{شريط بوابات|تقنية المعلومات|علم الحاسوب}}

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