מטבע שאי אפשר לחזות
הטילו מטבע הוגן ורשמו מה יצא: 1 לעץ, 0 לפלי. לפני כל הטלה אין לכם מושג איזו ספרה תבוא, ואחריה אתם יודעים בדיוק. השינוי הזה, מאי־ידיעה לידיעה, הוא מה שהמילה מידע מציינת במדע ובהנדסה. אין לזה שום קשר לשאלה אם ההודעה חשובה או נכונה. המידע מודד כמה ספק ההודעה מסירה.
עכשיו הפכו את המטבע ללא הוגן, כך שייפול על עץ תשע פעמים מתוך עשר. הסרט מתמלא באחדות, ואפשר היה לנחש את רובו בלי להסתכל. הטלה שיכולתם לנחש מראש מספרת לכם מעט. מטבע שתמיד נופל על עץ לא מספר לכם כלום: ידעתם את התשובה עוד לפני שנחת.
הפתעה שנמדדת בסיביות
קלוד שאנון הפך את הרעיון הזה לחשבון ב־1948. ההפתעה של תוצאה שמתרחשת בהסתברות p היא −log₂ p סיביות. לעץ במטבע הוגן יש הסתברות ½, ולכן הוא נושא סיבית אחת בדיוק: תשובה אחת לשאלת כן או לא. במטבע הלא הוגן, עץ (0.9) נושא רק 0.15 סיביות, ואילו הפלי הנדיר (0.1) נושא 3.32 סיביות. אירועים נדירים הם חדשות גדולות; אירועים צפויים הם חדשות קטנות.
הלוגריתם לפי בסיס 2 הוא מה שהופך את היחידה לסיבית. שתי הטלות הוגנות נושאות 2 סיביות, וכדי להבחין בין ארבע תוצאות בעלות אותה הסתברות צריך שתי ספרות בינאריות. ההפתעות של אירועים בלתי תלויים מתחברות.
אנטרופיה היא ההפתעה הממוצעת
מטבע לא הוגן מייצר בעיקר הפתעות קטנות, ומדי פעם הפתעה גדולה. הממוצע על פני הטלות רבות הוא האנטרופיה של המטבע:
H = −p log₂ p − (1 − p) log₂ (1 − p)
במטבע של 90% זה 0.9 × 0.15 + 0.1 × 3.32 ≈ 0.47 סיביות להטלה. העקומה היא גבנון: 0 סיביות כשהתוצאה ודאית, לכאן או לכאן, ועלייה עד לשיא של סיבית אחת בדיוק במטבע הוגן, שבו הכי קשה לנחש. מטבע של 75% עדיין נושא 0.81 סיביות להטלה; מטבע של 99%, רק 0.08.
נסו: תחת מדידה ודחיסה, התקדמו עד אנטרופיה, ואז העלו את הסיכוי לעץ עד 90%. הסמן מחליק במורד העקומה אל 0.47 סיביות, והתצוגה מראה כמה קטנה נעשתה ההפתעה של עץ. העלו אותו עד 100% והסמן יורד לאפס.
נתונים צפויים נדחסים
האנטרופיה היא לא רק הגדרה. שאנון הוכיח שזה מספר הסיביות להטלה הקטן ביותר שקוד כלשהו יכול להסתפק בו בממוצע כדי לרשום את ההטלות במדויק. לכן היא גבול שאי אפשר לעבור בדחיסה, והיא מסבירה למה נתונים צפויים מתכווצים.
הסרט השני של המכונה מראה שיטת דחיסה אמיתית, קוד האפמן, שדייוויד האפמן פיתח כשהיה סטודנט ופרסם ב־1952. הקוד קורא את ההטלות בגושים ונותן לכל גוש אפשרי מילת קוד, קצרה לגושים נפוצים וארוכה לנדירים, ומסדר אותן כך שאף מילת קוד אינה ההתחלה של מילה אחרת, ואפשר לקרוא את הסרט בחזרה בלי רווחים. במטבע של 90% ובגושים של ארבע, גוש שכולו עץ מופיע בערך ב־66% מהפעמים ונכתב כסיבית אחת. גוש עם פלי אחד דורש 3 או 4 סיביות, וגוש של ארבעה פלי דורש 10. רוב הגושים מתכווצים, מעטים מתארכים, ובממוצע המטבע עולה 0.49 סיביות להטלה, מול גבול אנטרופיה של 0.47. בהרצה אחת של 100 הטלות הסרט הגיע ל־48 סיביות.
מטבע הוגן אי אפשר לדחוס בכלל. כל גוש סביר בדיוק כמו כל גוש אחר, ולכן אף גוש לא ראוי למילת קוד קצרה, והסרט התחתון ארוך בדיוק כמו העליון. דחיסה עובדת בזכות הימור על מה שסביר; כששום דבר אינו סביר יותר מדבר אחר, אין על מה להמר.
כמה קרוב קוד יכול להגיע?
הורידו את גודל גוש הקוד להטלה אחת: הסרט התחתון הופך להעתק של העליון, יהיה המטבע אשר יהיה. להטלה בודדת יש רק שתי תוצאות, ומילת קוד לא יכולה להיות קצרה מסיבית אחת, ולכן קידוד של הטלה אחת בכל פעם לא חוסך דבר. גושים ארוכים יותר נותנים לקוד יותר עם מה לעבוד. במטבע של 90%, גושים של 2, 3, 4 ו־6 עולים 0.65, 0.53, 0.49 ו־0.47 סיביות להטלה. קוד האפמן על גושים של k הטלות נוחת תמיד בין האנטרופיה לבין האנטרופיה ועוד 1/k סיביות להטלה.
המטבע הוודאי מראה את אותו גבול מהצד השני. האנטרופיה שלו אפס, ובכל זאת הקוד עדיין מוציא סיבית אחת על כל גוש, רבע סיבית להטלה בגושים של ארבע. גושים ארוכים יותר, או הקידוד האריתמטי שמשמש בתוכנות דחיסה מודרניות, מתקרבים לאפס.
בכל קטע קצר של הסרט הספירה יכולה לצאת מעט מעל הגבול או מעט מתחתיו, כי רצף מוצלח של עץ זול לכתיבה. הגבול מתקיים בממוצע, ועל פני רצפים ארוכים הספירות מתקרבות אליו.
מה המודל הזה משאיר בחוץ
כל הטלה כאן בלתי תלויה באחרות, ולכולן אותו סיכוי, והוא ידוע. נתונים אמיתיים כמעט אף פעם אינם כאלה. בטקסט באנגלית, אחרי q כמעט תמיד בא u, ומילים שלמות חוזרות על עצמן; תוכנות דחיסה כלליות, כמו אלה שמאחורי קובצי ZIP, מוצאות את הדפוסים והחזרות האלה, ולא רק תמהיל לא אחיד של סמלים, ולכן הן יכולות להצליח הרבה יותר מקוד שיודע רק באיזו תדירות מופיעה כל אות. הקוד כאן גם בנוי מתוך ידיעת הסיכוי האמיתי של המטבע; תוכנת דחיסה אמיתית צריכה להעריך אותו מתוך הנתונים. קודי האפמן מתקרבים לאנטרופיה רק בגושים ארוכים, והמכונה עוצרת בשש הטלות. הסיבוב, הקפיצות והנחיתה של המטבעות מצוירים לשם הבהירות ולא מחושבים מהפיזיקה, ומטבע אמיתי שמוטל נוטה מעט מאוד ליפול על הצד שפנה למעלה בתחילת ההטלה.