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

ארתור אקרברג, חוקר עצמאי בתחום דחיסת הנתונים, מספר את הסיפור על אלגוריתם הדחיסה של האפמן, עליו מתבססים למשל קובצי ה-MP3 וה-JPEG

מקור: Pexels

מאת: ארתור אקרברג, חוקר עצמאי בתחום דחיסת הנתונים

כשאתם מצלמים, הוא שם.

כשאתם מאזינים למוזיקה, הוא שם.

כשאתם גולשים באינטרנט, הוא שם.

המאמר הזה מוקדש לו.

***

שיעור ציור

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

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

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

מילון

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

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

001010010100

אופס, נתקלנו בבעיה, את הרצף ניתן לשחזר בשתי צורות שונות:

00-101-00-101-00

001010010100

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

מילון חדש

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

ב-1948 פרסם המתמטיקאי קלוד שאנון את המאמר “תאוריה מתמטית של תקשורת”. מאמר זה יהווה את הבסיס לתיאורית האינפורמציה, תאוריה חשובה שעוסקת באספקטים שונים של מידע לרבות כימות ומדידה של מידע. במאמר זה שאנון גם יגדיר את המושג אנטרופיה (של המידע) כ”כמה מידע בממוצע מוכל/מיוצר ביחידות מידה של ביט”.

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

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


להפוך פסקה שלמה לאות אחת: הצצה לדחיסת נתונים


לטפס על האוורסט

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

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

ואז היה לו רגע של יוריקה!

השיטה של האפמן:

  • רושמים את מספר ההופעות של כל סימן (או את ההסתברות)
  • מעל רושמים את סכום המספרים הנמוכים ביותר ומחברים אליהם קו
  • חוזרים על השלב הקודם שוב ושוב (גם לסכומי מספרים) עד שמגיעים לסכום המספרים הסופי.

כדי לדעת את הקוד החדש של כל ערך נרד מהסכום הסופי לאורך הקווים אל מספר הופעותיו. בכל צומת קווים אם נפנה שמאלה נרשום 0 ואם נפנה ימינה נרשום 1 (אפשר גם הפוך).

ציור בתוכנה שלנו של 250 פיקסלים המורכב מ-19 פיקסלים אדומים, 22 כתומים, 24 צהובים, 40 כחולים ו-70 סגולים על רקע ירוק (75 פיקסל) יראה כך:

“העץ” נבנה הפוך לכיוון החצים, קריאת הקוד היא עם כיוון החצים

 

 

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

הקודים שהאלגוריתם של האפמן מייצר הם לא רק יעילים אלא גם בעלי תכונה מיוחדת נוספת: הם ניתנים לפענוח מיידית. סט הקודים: 11 ; 110 לדוגמה אינו בעל תכונה זאת. כאשר נקרא את הפלט 11 לא נוכל לדעת אם זהו הקוד 11 או ההתחלה של 110 עד שלא נקרא תו נוסף. הסיבה לעיקוב בפענוח הוא ש-11 מהווה קידומת של 110. כנגד כל היגיון בריא דווקא קודים שאינם מהווים קידומת של קודים אחרים בסט, כגון האפמן, נקראים קודי קידומת (Prefix codes).

הפתיח של “מלחמת הכוכבים” – פרק 4: “IT IS A PERIOD OF CIVIL WAR…” עם 46% דחיסה לא כולל מילון


לאן נעלמו להם 44 גיגה בייט? להבין דחיסת נתונים


לדחוס מילון דחיסה

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

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

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

אחרי שנעשה זאת לכל הצבעים נקבל:

1111010111010000011001100010110011

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

11101010-10101011010011000011011001100011010110011011

52 התווים מלה מהווים מילון שלם. נשתמש במילון זה כבסיס למילון בעל נפח מופחת.

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

נקבל מילון בעל 40 ביטים כפי שמופיע מטה.

000-0000110000110010110100101101101101010

ננסה לצמצם עוד בעזרת הטכניקה הבאה:

  • נסדר את הקודים לפי אורך מהקצר לארוך (שחור>חום>סגול>ירוק>אדום>כתום>צהוב>כחול)
  • בכל קבוצת אורך נסדר לפי סדר הצבעים. (שחור>חום>ירוק>סגול>אדום>כתום>צהוב>כחול)
  • ניקח את הקוד הראשון (11) ונחליף אותו בקוד המורכב מאפסים באורך זהה
  • המספר הבינארי הבא יחליף את הקוד הבא בסדר
  • אם הקוד החדש קצר מהישן, נוסיף אפסים עד אשר יהיו באורך זהה
  • נחזור על פעולות 4 ו-5 עד אחרון הצבעים

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

המילון החדש יכיל רק 24 ביטים:

000-000011011011010011010

ממבט במילון ניתן לראות שהקוד הקצר ביותר הראשון (שאינו אפס ביט) הוא באורך 2 ביט ומיקומו הוא שש. נסיק מכך שמדובר בצבע הירוק אשר ממוקם שישי בסדר הצבעים והקוד עצמו, לפי סעיף 3 של השיטה, הינו “00”. את שאר הקודים ניתן לשחזר בצורה דומה.

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

000010101111100010011100110

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

***

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

ואז הגיע קידוד אריתמטי…


המאמר הזה הוא המאמר השלישי בסדרה. אל תפספו את המאמר הראשון ואת המאמר השני

למידע נוסף על האנטרופיה של המידע והנוסחה של שאנון

Avatar

כתב אורח

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

הגב

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

avatar
Photo and Image Files
 
 
 
Audio and Video Files
 
 
 
Other File Types
 
 
 

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

סידור לפי:   חדש | ישן | הכי מדורגים
אריק
Guest

כתבה מרתקת, תודה!

עומרי
Guest

וואו!! סיפור והסבר מעולים אפילו לאנשים לא מהתחום כמוני.. תודה

דג ברשת
Guest

מעניין ומרתק! תודה !

david
Guest

סוף סוף כתבה מעניינת !!
ישר כח

מתן
Guest

אחת הכתבות המעניינות שקראתי.
תודה רבה!

ליאור
Guest

כתבה מעולה

עומרי
Guest

רגע רגע רגע, jpg וmp3 לא מבוססים עם המרת פורייה, חיתוך החלקים הפחות משמעותיים והמרת פוריה נוספת? או שאני מפספס משהו והקידוד הראשוני שלפני ההמרת פוריה מבוצעת באמצעות הופמן?

ארתור אקרברג
Guest

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

אנה
Guest

מענייו מאוד, תודה, ממשיכה הישר למאמרים הקודמים בסדרה:)

אוהב עמו
Guest

שבת בהוקר יום יפה. הסבר מצויין, על כוס קפה. תודה.

ברק
Guest

מה לגבי LZW שעליו מבוססות תוכנות דחיסה כגון zip ו rar הוא יותר טוב או פחות ולמה?

yoni
Guest

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

איך בונים מילון תוך כדי? מילים במילון מפנות למילים קודומות + תוספת

ניר
Guest

הכתבה מזכירה לי את ריצ’ארד מהסדרה ‘עמק הסיליקון’.

יניב
Guest

כתבה מעניינת

דרור
Guest

תודה

One Nose
Guest

איך אני אוהב תוכן איכותי :)

תודה!

נתנאל
Guest

סחתיין על הכתבה, כן יירבו

פרק שמונה האגדי
Guest
פרק שמונה האגדי

הדרך הכי טובה זו הדרך שהומצאה בsilicon valley עונה 1 פרק שמונה

wpDiscuz

תגיות לכתבה: