דחיסה
הוצג| English | משמעות |
|---|---|
| compression/kəmˈpreʃn/ | דחיסה |
| lossless/ˈlɒsləs/ | ללא איבוד נתונים |
| lossy/ˈlɒsi/ | עם איבוד נתונים |
| bandwidth/ˈbændwɪdθ/ | רוחב פס |
| run-length encoding/rʌn leŋθ enˈkəʊdɪŋ/ | הצפאת אורך ריצה |
| dictionary coding/ˈdɪkʃənəri ˈkəʊdɪŋ/ | הצפאת מילון |
| Huffman coding/ˈhʌfmən ˈkəʊdɪŋ/ | הצפאת הופמן |
| spatial/ˈspeɪʃl/ | מרחבי |
| temporal/ˈtempərəl/ | זמני |
השלושה אותיות שהפכו את האינטרנט לאפשרי
- בשנת 1987 מתכנן בשם פיל קאץ כתב תוכנת דחיסה והציג את פורמט הקובץ לרשות הציבור. הוא כינה אותו ZIP. הוא היה בן 24.
- ללא הרעיון הזה, אין כלל דבר העובד באינטרנט. שנייה אחת בלבד של וידאו HD ללא דחיסה שוקלת כ-187 MB; סרט באורך שעתיים יצריך 1.3 טרה-בייט. הזרמתו באמצעות חיבור ביתי היא אריתמטית בלתי אפשרית.
- הסרטים צופים בהם הם כמעט אלףית מהגודל הזה, ועדיין נראים נכון, משום הדחיסה מושכת דברים שהעין שלך מעולם לא הייתה מבחינה בהם.
- שיעור זה עוסק ב-דחיסה: שתי המשפחות, שלושת שיטות הדחיסה האובדניות (lossless), וכיצד להצדיק אחת לקובץ נתון.
דחיסה אובדנית ואובדנית (Lossless and Lossy)
- דחיסה מקטינה את גודל הקובץ, חוסכת מקום אחסון ורוחב פס העברה, ומאיצה הורדות וזרימות.
- דחיסה אובדנית (Lossless) היא דחיסה שממנה ניתן לשחזר את הנתונים המקוריים בדיוק. ZIP ו-PNG הן דחיסות אובדניות.
- דחיסה אובדנית (Lossy) מסירה לעולם חלק מהנתונים, ולכן לא ניתן לשחזר את המקור. JPEG, MP3 ווידאו זורם הן דחיסות אובדניות.
שחזור בדיוק, או הצטמצמות משמעותית יותר
דחיסה ללא איבוד נתונים פירושה:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
דחיסה ללא איבוד נתונים מאפשרת לשחזר את הנתונים המקוריים במדויק — דבר הכרחי בטקסט, בתוכנות ובZIP/PNG.
התאם כל רעיון דחיסה למשמעות שלו.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
דחיסה ללא איבוד נתונים שומרת על כל ביט (נדרש עבור טקסט/קוד); דחיסה עם איבוד נתונים מחליפה איכות באופן של קובץ (תמונות, אודיו).
דחיסה ללא איבוד נתונים משחזרת את הנתונים המקוריים בדיוק (נדרש עבור טקסט ותוכניות), בעוד שדחיסה עם איבוד נתונים מסירה באופן צמיתי חלק מהנתונים כדי להקטין את הקובץ (משמשת לתמונות ולאודיו).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לכן תוכנית או קובץ ZIP חייבים להיות ללא איבוד נתונים, אך תמונה או שיר יכולים להשתמש בדחיסה עם איבוד נתונים.
דוגמה מפורטת: הנמנת בחירה
- חברה מארכבת את טבלאות החשבונאות שלה. איזה סוג דחיסה, ולמה? אובדנית, משום שטבלאת החשבונות חייבת לשוחזר בדיוק; שינוי בערך אחד יהפוך את החשבונות לא incorrect.
- צלם מעלה תמונות חופשה לגלריה בטלפון. אובדנית, משום שתמונות נצפות על מסך קטן שבו הפרטים הנמחקים אינם נראים, והקבצים הקטנים יותר נטענים מהר יותר וחוסכים מקום אחסון.
- קבע את הסוג, ולאחר מכן תן את הסיבה ממצב העניינים. "אובדנית קטנה יותר" לבדו אינו הצדקה.
איזה קובץ יש לדחס ללא איבוד נתונים?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
קוד מקור חייב לשוחזר בדיוק — שינוי באות בודד עשוי לפגוע בו — ולכן הוא זקוק לדחיסה ללא איבוד נתונים.
קידוד אורך רצף (Run-length encoding)
- קידוד אורך רצף (RLE) מחליף רצף של ערכים חוזרים בערך אחד ובספירה: במקום שמונה פיקסלים לבים זהים, נשמור "8, לב".
- זו שיטה מצוינת עבור נתונים עם רצפים ארוכים, כמו אייקונים, דיאגרמות, סריקות שחור-לב ושטחים בצבע אחיד.
- היא חסרת תועלת, ועלולה להפוך קובץ לגדול יותר, בנתונים רועשים כמו צילום, שבו כמעט שני ערכים שכנים אינם שווים.
כל שורה הופכת לספירות וצבעים
אנקודינג בטווח רצף (Run-length encoding) עובד הטוב ביותר על נתונים שמכילים:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
RLE מחליף רצף של ערכים זהים במספר + ערך, ולכן הוא מצטיין באזורים אחידים אך חסר ערך בנתונים רועשים.
דוגמה מפורטת: קידוד שורה ב-RLE
- שורה בתמונה בשחור-לבן של 8 פיקסלים קוראת: לבן לבן לבן שחור שחור לבן לבן לבן. קדדו אותה ב-RLE.
- שלושה לבנים, שני שחורים, שלושה לבנים, לכן
3W 2B 3W, או כזוגות,(3, 0) (2, 1) (3, 0)אם לבן הוא 0. - שמונה ערכים הפכו לשלושה זוגות. כעת קודדו
W B W B W B W B. שמונה רצפים של אחד:1W 1B 1W 1B 1W 1B 1W 1B, שמאחסן יותר מהמקורי. זו בדיוק הסיבה ש-RLE אינו משמש בתמונות.
אנכוד רצפים (שיטה ללא איבוד נתונים)
אנכוד רצפים מחליף רצף של ערכים חוזרים בערך אחד ובספירה. השיטה היא ללא איבוד נתונים — הנתונים המקוריים נבנים מחדש במדויק — אך היא צמצמת נתונים רק אם יש בהם רצפים ארוכים.
אנקוד את שורת הפיקסלים W W W B B W W W באמצעות אנקודינג בטווח רצף, בשימוש הצורה 3W 2B 3W.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
שלושה לבנים, שני שחורים, שלושה לבנים. שמונה ערכים הופכים לשלושה זוגות, אך שורה מתחלפת הייתה הופכת לשמונה זוגות וגדלה.
אנקודינג בטווח רצף תמיד מקטין את גודל הקובץ.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
על נתונים שאין בהם רצפים, כמו תמונה או דפוס מתחלף, לכל רצף יש אורך של אחד והאנקודינג מאחסן יותר מהמקורי.
קידוד במילון וקידוד הופמן
- קידוד במילון, המשמש ב-ZIP וב-PNG, בונה מילון של רצפי בייטים חוזרים ומחליף כל התגלות באינדקס קצר. הוא מתאים בטקסט ובקוד תוכנה, שם מילים ודפוסים חוזרים.
- קידוד הופמן מעניק קודים קצרים לסמלים נפוצים וקודים ארוכים לסמלים נדירים, כך שאורך הממוצע של הקוד יורד. במילה "BANANA" האות A היא הנפוצה ביותר וקובעת את הקוד הקצר ביותר.
- שניהם לא מאבדים נתונים: המחולל בונה מחדש את הבית המקורי ביט על ביט.
אנקודינג הופמן מקטין גודל באמצעות:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
שיטת האופן מקצה את הקודים הקצרים ביותר לסמלים התורכנים ביותר, ובכך מצמצמת את אורך הקוד הממוצע.
התאם כל שיטת דחיסה ללא איבוד נתונים למנגנון הפעולה שלה.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
שלושת השיטות הן ללא איבוד נתונים: המפענח בונה מחדש את הבית המקורי באופן מדויק.
שיטות מאבדות נתונים
- תמונות (JPEG): פרטים עדינים והבדלי צבע שהעיין קשה להבחין בהם נמחקים.
- צליל (MP3, AAC): גוונים שאנו שומעים בעדיפות נמוכה מוסרים, לצד צלילים שקטים המוסתרים על ידי צלילים חזקים יותר באותו רגע.
- וידאו: דחיסה מרחבית פועלת בתוך כל מסגרת, כמו ב-JPEG, ודחיסה זמנית מאחסנת את רוב המסגרות כהפרשים בלבד מהמסגרת הקודמת, מכיוון שמסגרות עוקבות הן כמעט זהות.
דחיסה זמנית של וידאו פועלת על ידי:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
דחיסה זמנית אוספת את ההבדלים בין כל מסגורה למסגורה הקודמת לה, שכן רוב התמונה נשאר זהה בין מסגורות. (דחיסה מרחבית מטפלת בפרטים בתוך המסגורה.)
דוגמה מפורטת: כיצד סוגי קובץ שונים נדחסים
- קובץ טקסט: קידוד במילון וקידוד הופמן הופכים מילים חוזרות ואותיות נפוצות לקודים קצרים. הקובץ חייב להישאר ללא אובדן נתונים, כי שינוי באות אחת משנה את המשמעות.
- תמונת BITMAP: RLE עבור רצפים של פיקסלים זהים באייקונים ובתרשימים; JPEG מאבד נתונים לצילומים; או הפחתת עומק הצבע או הרזולוציה, שזה גם מאבד נתונים.
- גרפיקה וקטורית: רשימת השרטוט כבר קטנה. הסירו אובייקטי שרטוט שאינם נדרשים, אחסנו קואורדינטות עם פחות מקומות עשרוניים, או יישמו שיטה ללא אובדן נתונים כמו ZIP לקובץ.
- קובץ צליל: MP3 או AAC מאבד נתונים מסירים מה שהאוזן לא שומעת; הורדת קצב הדגימה או העומק הם גם מאבד נתונים; פורמטים ללא אובדן נתונים שומרים על כל דגימה וצוחצים פחות.
איך ניתן להקטין תיקון גרפיקה וקטורית? סמן את כולם החלופות הנכונות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
קובץ וקטורי הוא רשימת ציור ולא פיקסלים, ולכן אין לו עומק צבע. עומק צבע שייך לרשתות פיקסלים (bitmaps).
מדוע הזרמת מידע חייבת להיות אובדנית
- וידאו HD גולמי הוא ג'יגה-בייטים לדקה, וערוץ ביתי מעביר מספר בריבים לשנייה.
- דחיסה ללא איבוד נתונים בוידאו מגיעה לכדי פי שניים לערך, מה שאינו מספיק כלל, ולכן התמונה תמשיך להקפיא כדי לבצע טעינה (buffer).
- דחיסה אובדנית מגיעה לכדי פי מאה או יותר על ידי פליטת פרטים שהצופה לא מבחין בהם בקצב רגיל. הסיבה קשורה לרוחב הפס ולקצב העברת המידע, ולא רק לכך שהקובץ "קטן יותר".
מדוע זרימת וידאו בזמן אמת משתמשת בדחיסה עם איבוד נתונים?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
וידאו HD גולמי הוא ג'יגה-байטים לדקה; רק דחיסה עם איבוד נתונים מצמצמת אותו מספיק כדי להזרים בזמן אמת ללא קפיאות.
סימונים נופלים מהיד
- דחיסה ללא איבוד נתונים פירושה שהמקור משוחזר בדיוק; דחיסה אובדנית פירושה שהוא לא יכול להיות. המשפט "דחיסה אובדנית מאבדת איכות" מפספס את העובדה שהנתונים נעלמו לצמיתות.
- RLE עשוי להגדיל קובץ רועש. ציינו היכן הוא עובד והיכן הוא אינו עובד.
- דחיסת וידאו היא מרחבית וזמנית; הזמנית מאחסנת את ההבדלים בין מסגרות.
- תשובת "הצדקה" מקשרת את השיטה לשימוש בקובץ: דיוק לחשבונאות ותמונות רפואיות, גודל לקומפרסיה זורמת ולגלריות טלפון.
הבנתך מושלמת
- דחיסה חוסכת אחסון ורוחב פס; ללא איבוד נתונים משחזרת את המקור בדיוק, אובדנית מסירה נתונים לצמיתות
- שיטות ללא איבוד נתונים: RLE (ערך וכמות, טוב לסדרות חוזרות, רע ברעש), קידוד מילון (רצפים חוזרים למדדים קצרים), קידוד הופמן (מדדים קצרים לסמלים נפוצים)
- שיטות אובדניות מוותרות על מה שמעין או האוזן מפספסים; בוידאו נוסף מרחבי בתוך מסגרה וזמני בין מסגרות
- הצדקה לפי השימוש: נתונים מדויקים פירושו ללא איבוד נתונים, רוחב פס מוגבל לקומפרסיה זורמת פירושו אובדנית