קוד האפמן – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←קישורים חיצוניים: הלינק שבור |
הרחבה על שימוש בסיביות מסדר גבוה יותר לקוד האפמן |
||
שורה 82:
סיבוכיות האלגוריתם היא <math>\ O(n \log n)</math> פעולות. אם האותיות נתונות בצורה ממוינת, קיים אלגוריתם עם זמן ריצה ליניארי ב- n למציאת קוד האפמן.
=== הכללה לקידוד בסיביות מסדר N ===
עבור [[סיבית|סיביות]] מסדר <math>N>2 </math> (היכולות לייצג N ערכים), ה[[אנטרופיה בתרמודינמיקה ובתורת האינפורמציה|אנטרופיה]] של הקידוד תהיה <math>S_N=-\sum_i{P(i)\cdot \log_N{P(i)}} [\frac{Nbits}{symbol}] </math> והיא מהווה חסם תחתון נמוך יותר ל[[דחיסת נתונים|דחיסה משמרת נתונים]] של המידע, מאשר שימוש בביטים.
בניית קוד האפמן הפעם תתבצע ע"י יצירת הורה לN הבנים בעלי ה[[הסתברות]] הקטנה ביותר, והכנסת סכום N ההסתברויות לתור העדיפויות.
==== דוגמה עבור שימוש בטריטים ====
עבור מקור אותיות המייצר אותיות בקצב קבוע ובאופן בלתי תלוי, ההסתברות לקבלת כל אות נתונה על ידי: <math>P(A)=0.1,\quad P(B)=0.2, \quad P(C)=0.25,\quad, P(D)=0.3, \quad P(E)=0.15 </math>. נקודד בעזרת טריטים אשר יכול להכיל את שלושת הסימנים <math>(+,0,-) </math>. [[אנטרופיית שאנון|אנטרופיית]] המקור תחושב לפי הנוסחה: <math>S_3 = -\sum_{i=A}^E {P(i)\log_3{P(i)}} \approx 1.406 [\frac{Trits}{symbol}] </math>. חישוב קוד האפמן יעשה על פי הסכימה הבאה:
[[קובץ:Trits Huffman code.png|ממוזער|520x520 פיקסלים]]
כך שהקוד הוא: <math>C(A)=-- \quad, C(B)= -+\quad, C(C)=0 \quad,C(D)=+\quad C(E)=-0 </math>. קצב שליחת המידע במקרה זה יהיה <math>R=2\cdot(P(A)+P(B)+P(E))+1\cdot(P(C)+P(D))=1.45[\frac{Trits}{symbol}] </math> שאינו רחוק מה[[אנטרופיה בתרמודינמיקה ובתורת האינפורמציה|אנטרופיה]] של הקוד, שהיא כאמור החסם התחתון של קצב השידור.
==אופטימליות הקוד==
| |||