איך אלגוריתם דחיסה מקטין קובץ בלי לאבד ממנו מידע¶
לוחצים על קובץ, בוחרים "דחוס ל-ZIP", והוא הופך לקטן משמעותית, ואז אפשר לחלץ אותו בחזרה למקור המדויק, בית אחר בית, בלי לאבד אף פרט. זה נשמע כמעט כמו סתירה - איך אפשר להקטין מידע בלי לזרוק כלום? הסוד הוא שדחיסה בלי אובדן (lossless compression) לא זורקת מידע, היא פשוט מוצאת ייצוג חכם יותר לאותו מידע בדיוק.
התובנה המרכזית - כמעט כל קובץ מכיל יתירות¶
קבצים אמיתיים כמעט אף פעם לא אקראיים לגמרי. טקסט בעברית מכיל אותיות מסוימות בתדירות גבוהה בהרבה מאחרות, קוד מקור חוזר על אותן מילות מפתח שוב ושוב, ותמונה מכילה לרוב אזורים גדולים בצבע דומה. אלגוריתמי דחיסה מנצלים בדיוק את התבניות החוזרות האלה - ככל שיש יותר יתירות בקובץ המקורי, כך יש יותר מה "לחסוך" בדחיסה שלו.
שיטה ראשונה - קידוד הופמן, לתת לנפוץ ייצוג קצר¶
תארו לעצמכם קובץ טקסט שבו האות א' מופיעה אלף פעמים, והאות ץ' מופיעה פעם אחת. בייצוג רגיל, שתי האותיות תופסות בדיוק אותו מספר סיביות. קידוד הופמן (Huffman coding) עושה משהו חכם - הוא נותן לסמלים שמופיעים הרבה קוד בינארי קצר מאוד, ולסמלים נדירים קוד ארוך יותר. כך שאם א' מקבלת קוד באורך שתי סיביות בלבד, וץ' מקבלת קוד באורך שמונה סיביות, סך הכל הקובץ קטן משמעותית, כי החיסכון על האות הנפוצה חוזר על עצמו אלף פעמים.
הדרך שבה בונים את עץ הקידוד היא אלגנטית - סופרים כמה פעם כל סמל מופיע, ובונים עץ בינארי מלמטה למעלה, כשמתחילים תמיד עם שני הסמלים הכי נדירים ומאחדים אותם לצומת אחד, שוב ושוב, עד שנשאר צומת שורש בודד. המסלול מהשורש לכל סמל בעץ הוא בדיוק הקוד הבינארי שלו, וסמלים נדירים, שהצטרפו מאוחר לתהליך האיחוד, מסתיימים עמוק יותר בעץ, ולכן מקבלים קוד ארוך יותר.
שיטה שנייה - LZ77, למצוא חזרות ולהחליף אותן בהפניה¶
שיטה שנייה, שמשמשת בבסיס פורמטים כמו ZIP ו-PNG, מתמקדת לא בסמלים בודדים אלא ברצפים שחוזרים על עצמם. אלגוריתם בשם LZ77 סורק את הקובץ עם "חלון" שמסתכל אחורה על מה שכבר נכתב. כשהוא מוצא רצף שכבר הופיע קודם - למשל, מחרוזת "שלום עולם" שמופיעה פעמיים - הוא לא כותב אותה שוב במלואה. הוא כותב במקום הפניה קצרה - "לך אחורה כך וכך תווים, והעתק משם כך וכך תווים". הפניה כזאת תופסת הרבה פחות מקום מהטקסט המקורי שהיא מייצגת.
רוב אלגוריתמי הדחיסה הפופולריים בפועל, כמו זה שמאחורי ZIP או GZIP, בעצם משלבים את שתי הטכניקות - קודם LZ77 כדי למצוא ולקצר חזרות, ואז קידוד הופמן כדי לדחוס עוד יותר את מה שנשאר.
דחיסה עם אובדן - כשמוכנים לוותר על דיוק תמורת גודל¶
לצד דחיסה בלי אובדן, קיימת גם דחיסה עם אובדן (lossy compression), שנפוצה בעיקר בתמונות וסרטונים, כמו JPEG. הרעיון שם שונה לגמרי - במקום לשמור על כל בית מקורי, מזהים אילו פרטים העין האנושית כמעט לא מבחינה בהם (שינויי צבע עדינים מאוד, פרטים בתדר גבוה), וזורקים אותם בכוונה. זה מאפשר דחיסה חזקה בהרבה, במחיר של אובדן קבוע ובלתי הפיך של פרטים - זו הסיבה שאי אפשר לחלץ קובץ JPEG בחזרה לאיכות המקורית המדויקת שלו, בניגוד לקובץ ZIP.
למה כדאי להבין את זה, גם אם לא כותבים אלגוריתם דחיסה בעצמכם¶
הבנה בסיסית של דחיסה מסבירה למה קובץ טקסט דוחס הרבה יותר טוב מקובץ תמונה, למה דחיסת קובץ שכבר דחוס כמעט לא עוזרת, ולמה לפעמים כדאי לדחוס נתונים לפני שליחה ברשת ולפעמים לא. זה בדיוק סוג ההבנה הבסיסית של אלגוריתמים שבונים בהדרגה בקורס התכנות הבסיסי שלנו, לצד מבני נתונים ואלגוריתמים אחרים שחוזרים כל הזמן בעולם התכנות האמיתי.
קורס התכנות הבסיסי שלנו בונה את ההבנה האלגוריתמית הזאת שלב אחר שלב.
יש לכם שאלה על איך לדחוס משהו ביעילות בפרויקט שלכם? שאלו בדיסקורד.
לסיכום¶
דחיסה בלי אובדן לא זורקת מידע, היא פשוט מייצגת אותו בצורה חכמה יותר - קידוד הופמן נותן לסמלים נפוצים קוד קצר יותר, ו-LZ77 מחליף רצפים חוזרים בהפניות אחורה. שתי הטכניקות האלה, לרוב יחד, הן הבסיס לכמעט כל כלי דחיסה בלי אובדן שתשתמשו בו.