דחיסת נתונים

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

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

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

קיימים פורמטים דחוסים ופחות דחוסים. דוגמאות חשובות: ZIP, MP3, JPEG, PNG. קבצים לא דחוסים יכולים להיות גדולים מאוד; לדוגמה תמונה ב-BMP יכולה להיות כ־1,000,000 בתים (1MB), ואותה תמונה ב־JPEG אחרי דחיסה יכולה להיות כ־50,000 בתים (50KB), יחס של כ־1:20.

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

בדחיסה משמרת (Lossless) אפשר לשחזר בדיוק את המקור. טכניקות אלה מנצלות חוקיות מתמטית במידע.

RLE (Run Length Encoding) היא טכניקה פשוטה וללא איבוד. היא מקצרת רצפים שחוזרים על ידי ציון היחידה ומספר החזרות. למשל רצף ארוך של פיקסלים לבנים יכול להיקוד כ"12 לבן" במקום לחזור על כל פיקסל בנפרד. זה חוסך מקום במיוחד בקבצים בעלי חזרות רבות.

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

משפחת אלגוריתמים של למפל־זיו (LZ, LZW) משתמשת במילון של צירופים שחוזרים ונשלח מצביע למילון במקום כל הצירוף. שיטות אלה מיושמות ב־ZIP, gzip ובפורמטים כמו GIF ו־PNG.

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

בדחיסה מאבדת (Lossy) מוותרים על חלק מהמידע כדי לזכות בדחיסה גדולה יותר. כשמדובר במדיה חושית, כמו קול ותמונה, מניחים שהעין או האוזן לא יבחינו בשינויים קטנים. לכן פורמט MP3 מקצר שיר של 32MB ל־3MB במקרים רבים, בלי שרוב האנשים יבחינו בהבדל. פורמט JPEG מפרק תמונה למרכיבים ובהם מרכיב השחור־לבן והשכבות הצבעוניות, ודוחס לפי תדרים כך שהעין לא תשים לב לאיבוד קטן של צבעים.

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

בווידאו שומרים לעיתים רק את ההבדלים בין פריימים (מסגרות). בפורמט MPEG שמים מסגרת מפתח (Key Frame) אחת ומייצגים אחריה את השינויים בלבד.

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

הדחיסות מתחלקות לסוגי קבצים שונים:

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

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

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

בדחיסה משמרת אפשר להחזיר את הקובץ בדיוק כמו שהיה.

RLE היא דרך פשוטה. אם יש 12 פיקסלים לבנים, רושמים "12 לבן" במקום כל פיקסל בנפרד.

אותיות נפוצות מקבלות קוד קצר. אותיות נדירות מקבלות קוד ארוך. כך חוסכים מקום.

LZ שומר מילון של צירופים שחוזרים. במקום לחזור על מילה כותבים הפניה למילון.
פורמטים שמבוססים על זה הם ZIP ו־PNG.

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

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

יש תוכנות שמדחסות וקוראות קבצים. לפעמים צריך להוסיף "קודק" כדי לראות או לשמוע פורמט חדש.

הדחיסות מתחלקות לסוגי קבצים שונים: