קוד שאנון-פאנו

קוד שאנון-פאנו אשר שייך לתחום דחיסת נתונים וקרוי על שם קלוד שאנון ורוברט פאנו, הוא טכניקה לבניית קוד תחיליות (כלומר כל מחרוזת ביטים שמייצגת סמל אינה תחילית של מחרוזת המייצגת סמל אחר) המבוססת על קבוצה של סמלים והתדירות שהם מופיעים. הרעיון הכללי הוצע במאמר של שאנון "A Mathematical Theory of Communication" משנת 1948 שהציג את תחום תורת האינפורמציה. השיטה מיוחסת לפאנו שמאוחר יותר פרסם אותה כדו"ח מדעי.^[1] יש לשים לב ולא להתבלבל עם קוד שאנון או עם קוד שאנון-פאנו-אליאס (נקרא גם "קוד אליאס") אשר מתייחסים לדברים שונים.

בקוד שאנון-פאנו, הסמלים מסודרים לפי ההסתברויות שהם נמצאים, מהגדול לקטן ואז הם מחולקים לשתי קבוצות כך שסכום ההסתברויות בכל קבוצה שווה כמה שאפשר לקבוצה השנייה. כל סמל מקבל את הספרה הראשונה של קוד התחיליות שלו, הסמלים בקבוצה הראשונה מקבלים "0" והסמלים בקבוצה השנייה מקבלים "1". עבור כל קבוצה שנשאר בה יותר מסמל אחד, התהליך חוזר על עצמו וכל סמל יקבל ספרה נוספת. כאשר בקבוצה נשאר רק סמל אחד - הקוד עבור אותו סמל הושלם ואותו קוד לא יופיע בתחילת קוד של סמל אחר.

האלגוריתם מייצר קוד יעיל מאוד של מילות קוד בעלות אורך שונה. אולם קוד שאנון-פאנו לא תמיד יוצר קוד תחיליות אופטימלי. לדוגמה, עבור הקבוצה של ההסתברויות {0.35, 0.17, 0.17, 0.16, 0.15} קוד שאנון-פאנו יוצר קוד לא אופטימלי.

קוד האפמן ליצירת קוד תחיליות, כמעט תמיד קל יותר לחישוב ומייצר תמיד קוד תחיליות אופטימלי. כיוון שכך, קוד שאנון-פאנו כמעט שלא בשימוש.

קוד שאנון-פאנו משמש בשיטת הדחיסה IMPLODE, שהיא חלק מפורמט ZIP.^[2]

תיאור האלגוריתם

בונים עץ שאנון-פאנו על-פי חוקיות שנקבעה על מנת להגדיר טבלת סמל-קוד יעילה. האלגוריתם עובד כך:

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

כל הסמלים ממוינים לפי תדירות משמאל לימין כמתואר בטבלה. לפי שלב 3 של האלגוריתם, נשים קו מפריד בין הסמלים B ו-C כך שסכום הקבוצה השמאלית יהיה 22 וסכום הימנית יהיה 17 - החלוקה שנותנת את ההפרש הקטן ביותר שניתן בין החלקים.

על פי החלוקה הזאת, עבור כל אחד מ-A ו-B, ישויך קוד שמתחיל בביט שערכו "0" ועבור C, D ו-E קוד שמתחיל ב-"1" כפי שמתואר בטבלה השנייה. לאחר מכן (שלב 4) החלק השמאלי של העץ מקבל חלוקה חדשה בין A ו-B, מה שמשאיר את A בתור עלה עם קוד 00 ואת B בתור עלה עם קוד 01.

אחרי ארבעה תהליכי חלוקה, נוצר העץ של הקוד. בעץ הסופי, שלושת הסמלים עם התדירויות הגבוהות, קיבלו קוד של שני ביטים כל אחד ושני הסמלים עם הכמות הקטנה יותר, שלושה ביטים כל אחד, כמו שמתואר בטבלה למטה

סמל	E	D	C	B	A
קוד	111	110	10	01	00

כתוצאה מכך ש-A, B ו-C מקבלים שני ביטים כל אחד ו-D ו-E מקבלים 3, ממוצע הביטים הוא:

${\displaystyle {\frac {2\,{\text{bits}}\cdot (15+7+6)+3\,{\text{bits}}\cdot (6+5)}{39\,{\text{symbols}}}}\approx 2.28\,{\text{bits per symbol.}}}$

קוד האפמן

ערך מורחב – קוד האפמן

אלגוריתם שאנון-פאנו, לא תמיד יוצר קוד תחיליות אופטימלי. בשנת 1952, דייוויד האפמן פרסם אלגוריתם אחר, שיוצר עץ אופטימלי עבור כל קבוצת סמלים עם הסתברות נתונה. העץ של האפמן נבנה מהעלים לכיוון השורש - מלמטה למעלה, בניגוד לעץ שאנון-פאנו שנבנה מהשורש לעלים - מלמעלה למטה. האלגוריתם עובד כך:

1. צור תור עדיפויות ${\displaystyle \ Q}$ שיכיל צמתים המייצגים את כל הסמלים, ממוינים על פי הסתברות הופעתם.
2. כל עוד בתור העדיפויות יש יותר מצומת אחד, בצע:
   1. צור צומת חדש, ${\displaystyle \ z}$.
   2. הוצא מתור העדיפויות את שני האיברים העליונים, ${\displaystyle \ x,y}$ - בעלי ההסתברות הנמוכה ביותר.
   3. הפוך את ${\displaystyle \ x,y}$ לבנים הימני והשמאלי של ${\displaystyle \ z}$.
   4. קבע את ההסתברות של ${\displaystyle \ z}$ להיות סכום ההסתברויות של ${\displaystyle \ x}$ ו-${\displaystyle \ y}$.
   5. הכנס את ${\displaystyle \ z}$ לתור העדיפויות.
3. הצומת הבודד שנותר בתור העדיפויות הוא שורש עץ הקוד המבוקש.
4. הקוד עבור כל סמל יקבע לפי המסלול מהשורש לעלה שמייצג את הסמל. אם הקשת ה${\displaystyle n}$ית מובילה לבן שמאלי, ערך הביט ה${\displaystyle n}$י יהיה "0". אם היא מובילה לבן לבן ימני, ערכו יהיה "1".

דוגמה

קוד האפמן

נשתמש באותם תדירויות כמו שהשתמשנו בדוגמה של שאנון-פאנו, כלומר:

סמל	E	D	C	B	A
כמות	5	6	6	7	15
הסתברות	0.12820513	0.15384615	0.15384615	0.17948718	0.38461538

על פי האלגוריתם של האפמן, ל-D ו-E יש את ההסתברות הנמוכה ביותר ולכן יהיו בנים לצומת בעלת ההסתברות של D ו-E ביחד, כלומר 0.28205128. הזוג הבא בתור הוא B וC ויהיו בנים לצומת בעלת ההסתברות של B וC ביחד, כלומר 0.33333333. זה משאיר את BC ו-DE עם ההסתברות הנמוכה ביותר בתור ולכן גם הם יהיו בנים לצומת BCDE שבתורה תהיה יחד עם A, בן לצומת אחרונה.

אורכי הקודים עבור הסמלים יהיו הפעם: ביט 1 ל-A ו-3 ביטים עבור שאר הסמלים.

סמל	E	D	C	B	A
קוד	111	110	101	100	0

כתוצאה מכך ש-A מקבל ביט 1 וכל אחד מהשאר מקבלים 3 ביטים, ממוצע הביטים הוא:

${\displaystyle {\frac {1\,{\text{bit}}\cdot 15+3\,{\text{bits}}\cdot (7+6+6+5)}{39\,{\text{symbols}}}}\approx 2.23\,{\text{bits per symbol.}}}$

שזה פחות מהתוצאה שיצאה לנו עבור האלגוריתם של שאנון-פאנו.

הערות שוליים

1. Fano 1949
2. "APPNOTE.TXT - המפרט של פורמט ZIP".