דחיסה.

שלב 1 מתוך 5

מילים קצרות למה שנפוץ

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

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

שלב 2 מתוך 5

אין על מה להמר

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

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

שלב 3 מתוך 5

גושים ארוכים יותר

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

שלב 4 מתוך 5

אף מילה אינה התחלה של אחרת

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

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

שלב 5 מתוך 5

הגבול

שאנון הוכיח שהאנטרופיה היא לא רק ממוצע: היא מספר הסיביות להטלה הקטן ביותר שקוד כלשהו יכול להסתפק בו בממוצע בלי לאבד מידע. קוד האפמן על גושים של $k$⁠ הטלות נוחת תמיד בין $H$⁠ לבין $H + \tfrac{1}{k}$⁠. בגושים של שש הטלות, כמו עכשיו, הוא כבר על הגבול.

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