איך דחיסת קבצים עובדת באמת: קידוד Huffman, LZ77 ו-DEFLATE — הסבר מעמיק

כל מפתח עבד עם קבצים דחוסים. אתה מחלץ חבילה, משרת תגובה מקודדת ב-gzip, או מייצא PNG — ודחיסה מתרחשת מאחורי הקלעים. אבל השאלה שרוב ההדרכות מדלגות עליה היא: למה זה עובד? למה אפשר לקחת קובץ טקסט של 500 KB ולהקטינו ל-180 KB בלי לאבד בייט אחד, אבל לא ניתן לדחוס קובץ ZIP בצורה משמעותית?

התשובה נמצאת בתורת האינפורמציה ובמספר אלגוריתמים אלגנטיים. המאמר הזה עובר על המנגנון האמיתי: מאנטרופיית שאנון דרך עצי Huffman ועד פורמט DEFLATE שעומד בבסיס ZIP, gzip ו-PNG.

למה קבצים ניתנים לדחיסה

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

דוגמה פשוטה. המחרוזת AAAAAAAAAA (עשר A) תופסת 10 בייטים ב-ASCII. אך תוכן המידע שלה טריוויאלי — ניתן לתאר אותה במדויק כ"עשר A". אלגוריתם דחיסה עושה בדיוק את זה — מחליף נתונים מפורטים ועודפים בתיאור קצר יותר.

קבצים אמיתיים מלאים בעודפות מסוג זה:

• טקסט עברי משתמש שוב ושוב במילים נפוצות וצירופי אותיות. "של", "את", "זה" מופיעים הרבה יותר מ-"xqz".
• קוד מקור הוא בעל מבנה חזרתי עמוק: function, return, const, הזחות, שורות ריקות.
• תמונות bitmap מכילות ריצות אופקיות ארוכות של פיקסלים זהים או כמעט זהים — בעיקר באזורי צבע שטוח.
• קבצי לוג חוזרים על חותמות זמן, שמות מארחים וקודי סטטוס אלפי פעמים.

ככל שהנתונים עודפים יותר, כך ניתן לדחוס אותם יותר. ככל שהם פחות עודפים — ויותר אקראיים — קשה יותר לדחוס אותם.

אנטרופיה: המגבלה הקשה של הדחיסה

המאמר של קלוד שאנון משנת 1948, A Mathematical Theory of Communication, הציג דרך מדויקת למדוד תוכן מידע: אנטרופיה, הנמדדת בביטים.

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

הנוסחה עבור מקור עם סמלים s₁, s₂, ..., sₙ והסתברויות p₁, p₂, ..., pₙ:

H = -Σ pᵢ × log₂(pᵢ)

מה זה אומר בפועל: נניח שיש לך קובץ עם שני תווים בלבד — A (מופיע 90% מהזמן) ו-B (מופיע 10% מהזמן).

H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 ביטים לסמל

קידוד פשוט משתמש ב-1 ביט לסמל (0 עבור A, 1 עבור B). אך האנטרופיה אומרת שהמינימום התיאורטי הוא 0.469 ביטים לסמל — פחות ממחצית. אלגוריתם דחיסה טוב מתקרב לגבול הזה.

כעת חשוב על קובץ אקראי לגמרי שבו כל ערך בייט (0–255) מופיע בהסתברות שווה (1/256 כל אחד):

H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 ביטים לבייט

שמונה ביטים לבייט — אנטרופיה מקסימלית. אין עודפות לנצל. זו הסיבה שלא ניתן לדחוס קובץ ZIP נוסף: הוא כבר קרוב לאנטרופיה המקסימלית. כל ביט נושא מידע; לא נותרו דפוסים להסרה.

קידוד אורך ריצה: הצורה הפשוטה ביותר

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

RLE מחליף ריצה של סמלים חוזרים במונה ובסמל:

מקור:  AAABBBBBCCDDDDDD
RLE:   3A 5B 2C 6D

מקור: 16 תווים. מקודד: 8 תווים. צמצום של 50%.

RLE משמש בשידור פקס (CCITT קבוצה 3/4), קבצי BMP ותת-שלב בתוך פורמטים מורכבים יותר. חולשתו ברורה: הוא מצליח גרוע עם נתונים ללא ריצות ארוכות. המחרוזת ABABABAB אין בה ריצות, כך ש-RLE מגדיל אותה על ידי הוספת מונים של 1 בכל מקום.

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

קידוד Huffman: קודים קצרים יותר לסמלים נפוצים

ב-ASCII הסטנדרטי, כל תו מקבל 8 ביטים ללא קשר לתדירות הופעתו. קידוד Huffman שובר הנחה זו. סמלים תכופים מקבלים קודים קצרים יותר; סמלים נדירים מקבלים קודים ארוכים יותר. אורך הקוד הממוצע יורד והקובץ מצטמצם.

בניית עץ Huffman

ניקח את המחרוזת AABBBCCCC (9 תווים). נספור תדירויות:

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

[A:2]  [B:3]  [C:4]

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

מזג [A:2] ו-[B:3] ← הורה [AB:5]:

      [AB:5]
      /     \
   [A:2]  [B:3]

[C:4]

מזג [C:4] ו-[AB:5] ← שורש [ABC:9]:

         [ABC:9]
         /      \
      [C:4]  [AB:5]
              /    \
           [A:2]  [B:3]

שלב 3. הקצה קודים על ידי סריקת העץ: קצה שמאל = 0, קצה ימין = 1.

חישוב חיסכון הביטים

עם קודי Huffman, קידוד AABBBCCCC עולה:

A × 2 הופעות × 2 ביטים = 4 ביטים
B × 3 הופעות × 2 ביטים = 6 ביטים
C × 4 הופעות × 1 ביט  = 4 ביטים
סה"כ = 14 ביטים

עם ASCII קבוע של 8 ביטים:

9 תווים × 8 ביטים = 72 ביטים

14 ביטים לעומת 72 ביטים — צמצום של 81% בדוגמת הצעצוע הזו. הרווחים האמיתיים קטנים יותר, אך העיקרון שומר על תוקפו.

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

LZ77 ו-LZ78: ניצול רצפים חוזרים

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

זה בדיוק מה שאברהם למפל ויעקב זיו תיארו במאמריהם משנות 1977 ו-1978, שנתנו לנו את LZ77 ו-LZ78.

LZ77: דחיסת חלון הזזה

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

נדמיין קידוד המחרוזת:

abcabc

עיבוד abc: אין היסטוריה קודמת, פולט ליטרלים a, b, c.

עיבוד abc השני: המקודד מחפש אחורה ומוצא abc המתחילה 3 מיקומים אחורה, באורך 3. פולט הפניה לאחור (היסט=3, אורך=3) במקום שלושה בייטים מילוליים.

המפענח, כשרואה (3, 3), חוזר 3 מיקומים במאגר הפלט שלו ומעתיק 3 בייטים — משחזר abc בדיוק.

בממשות, חיפוש ההתאמה מוגבל על ידי גודל החלון (gzip משתמש בחלון של 32 KB). חלון גדול יותר מוצא יותר התאמות אך עולה יותר בזיכרון ובזמן חיפוש.

ההפניה לאחור (היסט, אורך) היא בדרך כלל 2–3 בייטים. לכן, החלפת רצף חוזר של 10 בייטים בהפניה של 2 בייטים חוסכת 8 בייטים. ככל שההתאמה ארוכה יותר, יחס הדחיסה טוב יותר.

LZ78 ו-LZW

LZ78 בונה מילון מפורש של דפוסים שנמצאו במקום שימוש בחלון הזזה. LZW (Lempel-Ziv-Welch), נגזרת שלו, הפך מפורסם כאלגוריתם מאחורי דחיסת GIF וכלי Unix compress. LZW מקודד דפוסים כאינדקסים יחידים של מילון, ומגדיל את המילון בזמן אמת במהלך קידוד ופענוח.

DEFLATE: LZ77 בתוספת קידוד Huffman

DEFLATE, המוגדר ב-RFC 1951, משלב את LZ77 וקידוד Huffman בסדרה:

1. מעבר LZ77: מחליף רצפים חוזרים בהפניות לאחור (היסט, אורך). הפלט הוא זרם של ליטרלים והפניות לאחור.
2. מעבר Huffman: מחיל קידוד Huffman על הזרם הזה. ליטרלים תכופים מקבלים קודים קצרים; ערכי הפניות נדירים מקבלים קודים ארוכים יותר.

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

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

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

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

איפה DEFLATE חי בפורמטים אמיתיים של קבצים

ZIP

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

gzip

gzip עוטף זרם DEFLATE יחיד עם כותרת (מספר קסם, מערכת הפעלה, זמן שינוי) ומחסום CRC32. זהו פורמט הדחיסה הסטנדרטי עבור HTTP Content-Encoding: gzip וארכיונים .tar.gz. הסיומת .gz תמיד מייצגת זרם DEFLATE יחיד.

PNG

PNG משתמש ב-DEFLATE (דרך zlib) לדחיסת נתוני הפיקסלים שלו. לפני הדחיסה, PNG מחיל שלב סינון: הוא ממיר כל שורת פיקסלים להפרשים מניבוי (קידוד דלתא). זה מגדיל בצורה דרמטית את הריצות והחזרות שLZ77 יכול לנצל, ומשפר את הדחיסה באופן משמעותי. עבור צילומי מסך ודיאגרמות טיפוסיים, PNG דוחס ל-20–50% מגודל נתוני הפיקסלים הגולמיים. כלי דחיסת תמונות שמייצאים PNG מסתמכים על צינור העיבוד הזה.

zlib

zlib הוא פורמט עוטף סביב DEFLATE — הוא מוסיף כותרת של שני בייטים ומחסום Adler-32. זרמי PDF משתמשים ב-zlib/DEFLATE בעת דחיסת תוכן מוטמע (דחיסת PDF מקטינה גודל הקובץ על ידי דחיסה מחדש או הסרה של זרמים אלה). HTTP, WebSockets ופרוטוקולי רשת רבים משתמשים גם ב-zlib.

JPEG: גישה שונה

כדאי לעצור כאן כי JPEG משתמש באסטרטגיית דחיסה שונה לגמרי — כזו שמאבדת נתונים בכוונה.

JPEG מחיל טרנספורמציית קוסינוס בדידה (DCT) על בלוקי 8×8 פיקסלים. ה-DCT ממיר ערכי פיקסלים לרכיבי תדר (דומה לטרנספורמציית פורייה). לאחר מכן רכיבי תדר גבוה — פרטים עדינים — מכומתים בצורה אגרסיבית (מעוגלים לערכים גסים יותר או מסולקים לגמרי). המקדמים הנותרים מקודדים עם קידוד Huffman, אך שלב הכימות המאבד הוא מה שגורם ל-JPEG להיות הרבה יותר קטן מ-PNG עבור תצלומים.

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

עבור תצלום, JPEG באיכות 80 עשוי להשתמש ב-10% מהבייטים שPNG ללא אובדן ידרוש. עבור צילום מסך עם צבעים שטוחים וקצות חדים, PNG בדרך כלל מנצח מכיוון שאפקטי DCT גלויים ו-DEFLATE דוחס אזורים שטוחים בצורה מצוינת.

למה אי אפשר לדחוס קובץ ZIP עוד יותר

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

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

הרץ עליו דוחסן שני והוא לא ימצא ריצות (LZ77 לא מוצא התאמות ארוכות) ולא הטיית תדירות (Huffman רואה התפלגות סמלים כמעט אחידה). האנטרופיה כבר עומדת על 7.9+ ביטים לבייט. לא נותר מה לנצל.

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

השוואת אלגוריתמים

שים את הכל יחד

שרשרת הפעולות מנתונים גולמיים לבייטים דחוסים בקובץ דחוס ב-gzip:

1. קלט: זרם בייטים גולמי (לדוגמה, קובץ טקסט)
2. LZ77: סרוק הפניות לאחור עם חלון הזזה של 32 KB, ייצר זרם של ליטרלים וזוגות (היסט, אורך)
3. קידוד Huffman: בנה שני עצים — אחד לליטרלים/אורכים, אחד להיסטים — וקודד את פלט LZ77
4. בלוקי DEFLATE: ארוז את עצי Huffman ואת הנתונים המקודדים לבלוק אחד או יותר
5. עוטף gzip: הוסף כותרת gzip, הוסף CRC32 וגודל הקובץ המקורי
6. פלט: קובץ .gz, בדרך כלל 30–70% קטן יותר עבור קלט שניתן לדחוס

פתיחת הדחיסה רצה בסדר הפוך בדיוק: ניתוח כותרת gzip, קריאה ושחזור עצי Huffman מכותרות הבלוקים, פענוח זרם Huffman בחזרה לאסימוני LZ77, יישום הפניות לאחור לשחזור זרם הבייטים המקורי. פתיחת הדחיסה תמיד מהירה יותר מהדחיסה כי העבודה הקשה (חיפוש התאמות אופטימליות, בניית עצים אופטימליים) נעשית פעם אחת בלבד.

תובנות מרכזיות

• קבצים ניתנים לדחיסה כי הם מכילים עודפות — דפוסים חוזרים ותדירויות סמלים מוטות.
• אנטרופיית שאנון קובעת את הרצפה הקשיחה: נתונים אקראיים לגמרי לא ניתנים לדחיסה כי כל ביט כבר נושא מידע.
• RLE מטפל בחזרות באופן גס. קידוד Huffman מטפל בהטיית תדירות בצורה אלגנטית. LZ77 מטפל בחזרות רצפים ארוכות טווח.
• DEFLATE משרשר LZ77 ו-Huffman בסדרה, ולכן עולה על כל אחד מהאלגוריתמים לבדו. הוא המנוע בתוך ZIP, gzip, PNG וזרמי PDF דחוסים ב-zlib.
• JPEG נוקט גישה שונה בתכלית: כימות DCT עם אובדן ולאחריו Huffman ללא אובדן, מחליף דיוק פיקסל בצמצום גודל דרמטי.
• דחיסת קובץ דחוס לא משיגה דבר כי דחיסה טובה מייצרת פלט קרוב לאנטרופיה מקסימלית.

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