דחיסת נתונים

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים

[עריכה] עקרונות דחיסת הנתונים

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

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

בעולם המחשב קיימים פורמטים שונים לקבצים דחוסים, ובהם ZIP, MP3, MPEG, DIVX, JPEG. לעומתם, קיימים סוגי קבצים של מידע לא דחוס כגון BMP ו-WAV (קובץ WAV גם הוא דחוס לעתים). מידע שמאוחסן בקבצים כאלו גדול משמעותית מהקבצים הדחוסים. כך תמונה לא דחוסה (בקובץ BMP) יכולה להגיע לגודל של כ-1,000,000 בתים (1MB) ואילו אותה תמונה דחוסה (בקובץ JPEG) יכולה להיות בגודל של כ-50,000 בתים (50KB) - יחס של 1:20.

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

בדחיסה ניתן להבחין בין שני סוגים עיקריים: דחיסה משמרת (Lossless) ודחיסה מאבדת (Lossy). בדחיסה משמרת, המידע הדחוס משוחזר בדיוק מלא למידע המקורי. לעומת זאת בדחיסה מאבדת המידע המשוחזר קרוב מאוד אך לא זהה למידע המקורי. פורמט ZIP הוא דוגמה לדחיסה משמרת, ולכן מתאימה לשמירת קבצים כלליים. JPEG הוא פורמט של דחיסה מאבדת של תמונה, ולכן תמונת JPEG לעולם לא תהיה זהה לתמונה המקורית. ה-JPEG מתוכנן בצורה כזו שעין אנוש לא תבחין בהבדל.

[עריכה] טכניקות דחיסה

[עריכה] דחיסה משמרת מידע

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

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

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

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

ללללללללללללשללללללללשששששללללללללללללללללללללללשלללללללללללללללל

ואילו המידע הדחוס יהיה (הפסיקים והרווחים הוספו להבהרת הדוגמה):

12ל, ש, 8ל, 5ש, 22ל, ש, 16ל

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

מלבד קוד הופמן ו-RLE, אחת מטכניקות הדחיסה ללא איבוד מידע המקובלת ביותר כיום מבוססת על אלגוריתם שפיתחו פרופ' אברהם למפל ופרופ' יעקב זיו מהטכניון בחיפה. וריאציות שונות של שיטת למפל זיו (LZ, LZW) מיושמות כיום בתוכנות דחיסה פופולריות כגון PkZip ו-gzip, ובפורמטים ליצוג תמונות כגון GIF ו-PNG.

טכניקות דחיסה נוספות כגון PPM, CTW, ו-BWT משיגות ביצועים טובים יותר (חיסכון בתווים) בתמורה לאיטיות מסוימת יחסית ל-LZ.

[עריכה] דחיסה מאבדת מידע

ערך מורחב – דחיסה מאבדת נתונים

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

באופן דומה, בקובץ JPEG מפורקת התמונה לתמונת שחור-לבן ולתמונות הצבע שלה. תמונת השחור לבן נשמרת בדיוק גבוה ואילו הצבעים יכולים להשמר בדיוק יותר נמוך כי הם לא משפיעים על חדות התמונה וכי העין האנושית לא מסוגלת להבחין בהבדלים בין כל הגוונים השונים. לאחר מכן נדחסות כל התמונות על פירוק לתדרים המרחביים שבהם (ולבסוף הפעלת קוד הופמן).

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

בוידאו מקובלת דחיסה שבה שומרים רק את ההבדל בין תמונה אחת (frame) לזו שבאה אחריה. ולא את כל התמונות באופן מלא. כך קובץ MPEG יכול להכיל לא 24 או 30 תמונות לשנייה אלא תמונה אחת לשנייה (Key Frame) ואת השינויים בה (דלתא) לאורך אותה השנייה.

[עריכה] תוכנות דוחסות ומפענחות במחשב האישי

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

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

  • קבצים כלליים - ZIP, GZ, ARJ, LAZ, RAR, CAB, ACE, TAR
  • קובצי התקנה - MSI, RPM, DEB
  • קובצי מראה של CD שמיועדים לצריבה - ISO
  • קובצי תמונה - JPEG, GIF, TIFF, PNG
  • קובצי קול - MP3, WMA, Ogg, AAC, Ape, Ram, Rmm, FLAC
  • קובצי וידאו - ,MPEG1-4, DIVX, MJPEG, WMV, Ogm

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

[עריכה] קישורים חיצוניים

שפות אחרות