קוד האפמן

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
עץ האפמן שנוצר על פי התדירויות במשפט "this is an example of a huffman tree"

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

גילוי הקוד

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

רקע

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

נמחיש את יעילותה של גישה זו באמצעות דוגמה פשוטה. נניח שבשפה מסוימת השכיחות של האות א' היא מחצית מכלל האותיות. בקוד ASCII, שבו לכל תו מוקדשות 8 סיביות, מספר הסיביות הנדרש להצגת טקסט באורך n הוא 8n. נקודד כעת את התווים בדרך חדשה: האות א' תסומן בסיבית יחידה שערכה 0, וכל תו אחר יסומן בקוד ה-ASCII הרגיל שלו, שבתחילתו תתוסף הסיבית 1 (תוספת זו הכרחית, כדי שנוכל להבדיל בין סיבית 0 שמציינת את האות א, ובין סיבית 0 באמצע תו כלשהו). אורך הקוד הזה יהיה (בתוחלת) רק 5n, שהם חסכון של 3/8.

תיאור פורמלי

תיאור הקוד

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

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

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

תיאור הבעיה

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

מבחינה פורמלית, הקלט לבעיה הוא אוסף תווים, , ומספר הפעמים שכל תו מופיע בקבוצת התווים: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ c_1,c_2,\dots,c_n} .

הפלט הצפוי הוא קוד, שהוא אוסף הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ h_1,h_2,\dots,h_n} של מילים בינאריות. נסמן ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ |h_k|} את אורכה של המילה ה-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ k} .

היעד הוא שהקוד שיוחזר יהיה כזה כך ש- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \sum_{k=1}^n c_k\cdot|h_k|} יהיה מינימלי. הסכום הוא בדיוק מספר הביטים שנדרש לקידוד קבוצת התווים כולה, שכן עבור כל תו, אנו מכפילים את מספר המופעים שלה בקבוצה במספר הביטים שנדרשים כדי לייצג אותה.

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

האלגוריתם של האפמן הוא דוגמה לאלגוריתם חמדן. הוא מבצע בכל שלב את הפעולה שנראית, נקודתית, כפעולה המשתלמת ביותר, ומתבסס על כך שפתרון אופטימלי עבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n-1} אותיות יכול להפוך לפתרון אופטימלי עבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n} אותיות.

הרעיון באלגוריתם הוא כזה: נבנה את העץ הבינארי של הקוד "מלמטה למעלה". ראשית, נמצא את שתי האותיות שמספר המופעים שלהן מינימלי, וניצור צומת חדש, כך ששתי האותיות הללו יהיו בניו. כעת נתייחס לצומת החדש בתור אות חדשה, שמספר המופעים שלה הוא סכום מספרי המופעים של שתי האותיות שהן בניה. כך קיבלנו צמצום של הבעיה מבעיה ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n} אותיות לבעיה ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n-1} אותיות. נחזור על התהליך עד שנישאר עם צומת אחד בלבד - ראש העץ.

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

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

  1. צור תור עדיפויות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ Q} שיכיל צמתים המייצגים את כל האותיות, כאשר העדיפות בתור ניתנת לצומת שמייצגת את האות בעלת מספר המופעים הקטן ביותר.
  2. כל עוד בתור העדיפויות יש יותר מצומת אחד, בצע:
    1. צור צומת חדש, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ z} .
    2. הוצא מתור העדיפויות את שני האיברים העליונים, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ x,y} .
    3. הפוך את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ x,y} לבנים הימני והשמאלי של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ z} .
    4. קבע את מספר המופעים של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ z} להיות סכום מספרי המופעים של ו-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ y} .
    5. הכנס את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ z} לתור העדיפויות.
  3. הצומת הבודד שנותר בתור העדיפויות הוא שורש עץ הקוד המבוקש.
  4. קבע את מילת הקוד עבור כל אות, לפי המסלול מהשורש, לעלה שמייצג את האות. אם הקשת ההפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} ית מובילה לבן שמאלי, ערך הביט ההפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} י יהיה "0". אם היא מובילה לבן לבן ימני, ערכו יהיה "1".

סיבוכיות האלגוריתם היא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ O(n \log n)} פעולות. אם האותיות נתונות בצורה ממוינת, ידוע אלגוריתם עם זמן ריצה לינארי למציאת קוד האפמן.

אופטימליות הקוד

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

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

קישורים חיצוניים