קוד הופמן

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים

[עריכה] מבוא

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

נמחיש את יעילותה של גישה זו באמצעות דוגמה פשוטה. נניח שנתונה מחרוזת בת 200 תווים, שמחציתם האות א. בקוד ASCII, שבו לכל תו מוקדשות 8 סיביות, אורכה של מחרוזת זו הוא 1,600 סיביות. נקודד כעת את התווים בדרך חדשה: האות א תסומן בסיבית יחידה שערכה 0, וכל תו אחר יסומן בקוד ה-ASCII הרגיל שלו, שבתחילתו תתוסף הסיבית 1 (תוספת זו הכרחית, כדי שנוכל להבדיל בין סיבית 0 שמציינת את האות א, ובין סיבית 0 באמצע תו כלשהו). אורך המחרוזת בקוד זה הוא 1,000 סיביות בלבד, שהם 63% מאורך המחרוזת המקורית.

[עריכה] היסטוריה

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

[עריכה] תיאור פורמלי

[עריכה] תיאור הקוד

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

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

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

[עריכה] תיאור הבעיה

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

מבחינה פורמלית, הקלט לבעיה הוא אוסף אותיות, \ a_1,a_2,\dots,a_n, ומספר הפעמים שכל אות מופיעה בטקסט: \ c_1,c_2,\dots,c_n.

הפלט הצפוי הוא קוד, שהוא אוסף \ h_1,h_2,\dots,h_n של מילים בינאריות. נסמן \ |h_k| את אורכה של המילה ה-\ k.

היעד הוא שהקוד שיוחזר יהיה כזה כך ש- \ \sum_{k=1}^n c_k\cdot|h_k| יהיה מינימלי. הסכום הוא בדיוק מספר הביטים שנדרש לקידוד הטקסט כולו, שכן עבור כל אות, אנו מכפילים את מספר המופעים שלה בטקסט במספר הביטים שנדרשים כדי לייצג אותה.

[עריכה] תיאור האלגוריתם

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

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

לצורך פעולתו, האלגוריתם זקוק למגננון שיאפשר לו למצוא במהירות את שתי האותיות בעלות המופעים המינימליים. לצורך כך ניתן להיעזר בתור עדיפויות (שניתן לממש על ידי ערמה).

מבחינה פורמלית:

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

[עריכה] אופטימליות הקוד

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

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