ישנם מקרים רבים בהם נסכים לאבד חלק מן המידע כדי לקבל דחיסה טובה הרבה יותר מזו שניתן היה לקבל ללא איבוד מידע. במקרים של מידע חושי כגון תמונה, קול או סרט, ההנחה היא שהחושים האנושיים ממילא אינם מסוגלים להבחין בווריאציות קטנות ולכן לא נורא אם אובד חלק מהמידע, בתנאי, שהמידע שהולך לאיבוד יהיה שולי מבחינת חשיבותו ומבחינת יכולת ההבחנה של התפיסה החושית שלנו. כך לדוגמה פורמט MP3 מסוגל לדחוס שיר שאורכו 3 דקות ל-3MB במקום 32MB בגודלו המקורי מבלי שרוב האנשים יוכלו להבחין בין השיר המקורי לדחוס. המצאת פורמט ה-MP3 אפשרה הפצה יעילה של מוזיקה על גבי האינטרנט ובניית נגנים זעירים שלא מכילים חלקים נעים.
באופן דומה, בקובץ JPEG מפורקת התמונה לתמונת שחור-לבן ולתמונות הצבע שלה. תמונת השחור לבן נשמרת בדיוק גבוה ואילו הצבעים יכולים להישמר בדיוק יותר נמוך כי הם לא משפיעים על חדות התמונה וכי העין האנושית לא מסוגלת להבחין בהבדלים בין כל הגוונים השונים. לאחר מכן נדחסות כל התמונות על ידי פירוק לתדרים המרחביים שבהם (ולבסוף הפעלת קוד הופמן).
בטלפונים סלולרים, לדוגמה, דוחסים את הקול המשודר במספר טכניקות. אחת היעילות ביותר שבהם היא שכאשר צד מסוים בשיחה שותק, הטלפון שלו משדר סימן מיוחד שמפורש על ידי הצד השני בהשמעת רעש שקט במיוחד. כך נחסך שידור של מידע לא רלוונטי בתשתיות סלולריות יקרות. מדובר על מעל ל-50% חיסכון (בהנחה ששני הצדדים לא מדברים במקביל). טכניקות נוספות עושות שימוש במאפיינים של הקול האנושי. מסיבה זו בטלפונים חדשים, במהלך שיחת טלפון, קול אדם נשמע ברור וחד ואילו מוזיקה נשמעת מעוותת ומתכתית.
בווידאו מקובלת דחיסה שבה שומרים רק את ההבדל בין תמונה אחת ("frame") לזו שבאה אחריה. ולא את כל התמונות באופן מלא. כך קובץ MPEG יכול להכיל לא 24 או 30 תמונות לשנייה אלא תמונה אחת לשנייה ("Key Frame") ואת השינויים בה (דלתא) לאורך אותה השנייה.
תוכנות דוחסות ומפענחות במחשב האישי.
קיימים מקודדים שדוחסים את המידע (encoders) ופורסים אותו (decoders) בפורמטים שונים. בגלל שהתקנים בתחום הגרפי הם ותיקים ויציבים, לתוכנות גרפיות בדרך כלל יהיו את שתי האופציות, והדחיסה והפריסה הן שקופות למשתמש בזמן קריאת הקובץ ושמירתו. לעומת זאת בקובצי אודיו ווידאו התקנים משתנים ולכן לעיתים לא בכל מחשב זמינות יכולות פענוח של כל הפורמטים, ויהיה צורך להוריד פורס חדש לפורמט הנדרש (קודק). ישנם פורמטים שאי אפשר להוסיף תמיכה בהם לתוכנות סטנדרטיות, ויש צורך בתוכנה ייעודית שמטפלת בהם.
הדחיסות מתחלקות לסוגי קבצים שונים:
מטען יסודי
קוד האפמן
קוד האפמן הוא שיטה לקידוד סימנים, כגון תווי טקסט, ללא אובדן נתונים.
הקוד שייך למשפחה שימושית של קודים המכונה קודי תחיליות (ראו למטה), ובמשפחה זו הוא הקוד המספק דחיסת נתונים מרבית, כלומר מאחסן את הסימנים במספר מזערי של סיביות, על פי הקריטריון המפורט בהמשך. השיטה מתבססת על הקצאת אורך משתנה לסימנים על פי שכיחותם, כך שסימן נפוץ יוצג באמצעות מספר קטן של סיביות. לרוב ניתן לחסוך באמצעות שיטה זו בין 20% ל-90% משטח האחסון. קוד האפמן הוא גרסה כללית יותר של עקרון קידוד הנקרא "קידוד אנטרופיה".
גילוי הקוד.
בשנת 1951, במסגרת לימודיו לדוקטורט ב־MIT, למד דייוויד האפמן קורס בתורת האינפורמציה שהייתה אז בחיתוליה. המרצה בקורס רוברט פאנו הציע לתלמידים לבחור בין עבודה מסכמת ובין מבחן מסכם. העבודה שהציע פאנו הייתה בנושא מציאת הקוד הבינארי היעיל ביותר - בעיה שהייתה פתוחה באותו הזמן; הקוד הטוב ביותר שהיה ידוע נקרא קוד שאנון-פאנו. האפמן, שלא הצליח להוכיח שאף אחד מהקודים הקיימים הוא יעיל ביותר, עמד להיכנע ולהתחיל ללמוד לבחינה המסכמת, כאשר עלה במוחו הרעיון להשתמש בעצים בינאריים ממוינים על פי תדירות האותיות, כשבנייתם היא מהעלים כלפי מעלה. במהרה הוכיח כי שיטתו היא היעילה ביותר. האפמן עקף את המגבלה המרכזית בקוד שאנון-פאנו על ידי כך שבנה את העץ מלמטה למעלה, ולא להפך.
רקע.
במערכות סימנים מקובלות, כגון קוד ASCII, ניתן אורך אחיד לכל הסימנים במערכת. זו שיטה פשוטה, אך היא אינה יעילה מבחינת נפח האחסון שהיא צורכת: מוטב היה להקצות קוד קצר לסימנים הנפוצים, גם על חשבון הארכה של הקוד המתאים לסימנים הנדירים. יעילות של קוד כזה תלויה רק בשכיחות הסימנים בשפה, ולא בסדר שבו הם מופיעים בטקסט נתון. יישום של גישה זו קיים כבר בקוד מורס לטלגרף אלחוטי. לאות הנפוצה 'ו' משמש בקוד מורס הקוד . ("נקודה"), ואילו לאות 'ע' משמש הקוד - - - . ("קו-קו-קו-נקודה").
נמחיש את יעילותה של גישה זו באמצעות דוגמה פשוטה. נניח שבשפה מסוימת השכיחות של האות א' היא מחצית מכלל האותיות. בקוד ASCII, שבו לכל תו מוקדשות 8 סיביות, מספר הסיביות הנדרש להצגת טקסט באורך n הוא 8n. נקודד כעת את התווים בדרך חדשה: האות א' תסומן בסיבית יחידה שערכה 0, וכל תו אחר יסומן בקוד ה-ASCII הרגיל שלו, שבתחילתו תתווסף הסיבית 1 (תוספת זו הכרחית, כדי שנוכל להבדיל בין סיבית 0 שמציינת את האות א, ובין סיבית 0 באמצע תו כלשהו). אורך הקוד הזה יהיה (בתוחלת) רק 5n, שהם חיסכון של 3/8.
תיאור פורמלי.
תיאור הקוד.
קוד האפמן הוא קוד תחיליות, כלומר מחרוזת ביטים שמייצגת אות לעולם אינה מהווה תחילית של מחרוזת המייצגת אות אחרת. קוד כזה מבטיח אפשרות יחידה לפיענוח, ויתרה מזאת, הפיענוח מהיר, שכן מספיק לעבור על הרצף המקודד פעם אחת מההתחלה ועד הסוף תוך שמירת מעט מידע.
קוד מסוג זה ניתן לייצג על ידי עץ בינארי, כאשר עלי העץ מייצגים את האותיות המקודדות, וצמתי העץ מסומנים ב-0 או 1. כאשר רוצים לפענח רצף ביטים כלשהו, הולכים על העץ על פי הביטים שנקלטים עד אשר מגיעים לעלה. האות המאוחסנת בעלה היא האות המפוענחת.
כאשר הקוד הוא אופטימלי, העץ יהיה עץ מלא. כלומר, לכל צומת שאינו עלה יהיו בדיוק שני בנים. לדוגמה, נניח כי בקוד כלשהו לשורש של העץ יש רק בן אחד, שאליו מובילה הקשת 0. פירוש הדבר הוא שבקוד לא יהיו כלל אותיות שקידודן מתחיל ב-1, וזהו בזבוז של מקום (כי אפשר היה, לכל הפחות, לתת לאות כלשהי את הקידוד "1", ובכך לחסוך במקום).
תיאור הבעיה.
בהינתן שכיחות התווים בשפה, הבעיה האלגוריתמית היא בניה מהירה של קוד יעיל, הממיר את התווים לרצפים קצרים של סיביות. לאחר שהקוד נבנה, אפשר לבצע קידוד ופענוח במעבר אחד על התווים, ולכן הבעיה המשמעותית היחידה היא במציאת הקוד. היעילות של קוד תלויה כאמור במספר המופעים של כל תו בשפה, ולכן לא קיים קוד אחיד שנותן קידוד אופטימלי לכל קבוצת תווים: אם שכיחות התווים שונה, יש להפעיל את האלגוריתם ולבנות את הקוד המתאים מחדש.
מבחינה פורמלית, הקלט לבעיה הוא אוסף תווים, formula_1, ומספר הפעמים שכל תו מופיע בקבוצת התווים: formula_2.
הפלט הצפוי הוא קוד, שהוא אוסף formula_3 של מילים בינאריות. נסמן ב-formula_4 את אורכה של המילה ה-formula_5.
היעד הוא שהקוד שיוחזר יהיה כזה כך ש- formula_6 יהיה מינימלי. הסכום הוא בדיוק מספר הביטים שנדרש לקידוד קבוצת התווים כולה, שכן עבור כל תו, אנו מכפילים את מספר המופעים שלו בקבוצה במספר הביטים שנדרשים כדי לייצג אותו.
תיאור האלגוריתם.
האלגוריתם של האפמן הוא דוגמה לאלגוריתם חמדן. הוא מבצע בכל שלב את הפעולה שנראית, נקודתית, כפעולה המשתלמת ביותר, ומתבסס על כך שפתרון אופטימלי עבור formula_7 אותיות יכול להפוך לפתרון אופטימלי עבור formula_8 אותיות.
הרעיון באלגוריתם הוא כזה: נבנה את העץ הבינארי של הקוד "מלמטה למעלה". ראשית, נמצא את שתי האותיות שמספר המופעים שלהן מינימלי, וניצור צומת חדש, כך ששתי האותיות הללו יהיו בניו. כעת נתייחס לצומת החדש בתור אות חדשה, שמספר המופעים שלה הוא סכום מספרי המופעים של שתי האותיות שהן בניה. כך קיבלנו צמצום של הבעיה מבעיה ב-formula_8 אותיות לבעיה ב-formula_7 אותיות. נחזור על התהליך עד שנישאר עם צומת אחד בלבד - ראש העץ.
לצורך פעולתו, האלגוריתם זקוק למנגנון שיאפשר לו למצוא במהירות את שתי האותיות בעלות המופעים המינימליים. לצורך כך ניתן להיעזר בתור עדיפויות (שניתן לממש על ידי ערימה).
מבחינה פורמלית:
סיבוכיות האלגוריתם היא formula_22 פעולות. אם האותיות נתונות בצורה ממוינת, קיים אלגוריתם עם זמן ריצה ליניארי ב- n למציאת קוד האפמן.
הכללה לקידוד בסיביות מסדר N.
עבור סיביות מסדר formula_23 (היכולות לייצג N ערכים), האנטרופיה של הקידוד תהיה formula_24 והיא מהווה חסם תחתון נמוך יותר לדחיסה משמרת נתונים של המידע, מאשר שימוש בביטים.
בניית קוד האפמן הפעם תתבצע על ידי יצירת הורה לN הבנים בעלי ההסתברות הקטנה ביותר, והכנסת סכום N ההסתברויות לתור העדיפויות.
דוגמה עבור שימוש בטריטים.
עבור מקור אותיות המייצר אותיות בקצב קבוע ובאופן בלתי תלוי, ההסתברות לקבלת כל אות נתונה על ידי: formula_25. נקודד בעזרת טריטים אשר יכול להכיל את שלושת הסימנים formula_26. אנטרופיית המקור תחושב לפי הנוסחה: formula_27. חישוב קוד האפמן יעשה על פי הסכימה הבאה:
כך שהקוד הוא: formula_28. קצב שליחת המידע במקרה זה יהיה formula_29 שאינו רחוק מהאנטרופיה של הקוד, שהיא כאמור החסם התחתון של קצב השידור.
אופטימליות הקוד.