איך זה עובד: דחיסת נתונים
אנחנו דוחסים ופותחים כל הזמן קבצי מוזיקה, קבצי וידאו וגם תמונות. השיטות שונות אבל המשמעות זהה: הנתונים מגיעים
השבוע לא נפרק שום מכשיר. במקום זאת, נדבר על נושא שרלוונטי לטכנולוגיה המודרנית לא פחות מכל רכיב אלקטרוני: דחיסת נתונים. אם ראיתם משהו ביוטיוב לאחרונה, האזנתם לקובץ MP3, התקנתם תוכנה או אפליקציה, צילמתם או אפילו סתם דיברתם בסלולרי, המכשירים בהם השתמשתם דחסו נתונים או חילצו אותם בחזרה. באחריות.
עוד ב-ynet מדע:
הדור הצעיר אולי לא יבין בכלל למה צריך לדחוס נתונים. הרי התקשורת האלחוטית והחוטית כיום מהירה כל כך, בשביל מה להתאמץ? כדי לענות על כך, בואו נעשה חישוב זריז. נניח שיש סרטון וידאו ברזולוציה של 640x400, בערך מה שמקבלים כברירת מחדל ביוטיוב. כל פיקסל צבעוני על המסך מצריך שלושה בייטים (אדום, ירוק, כחול) – סה"כ 768,000 בייטים לפריים יחיד. נכפיל בעשרים פריימים בשנייה ונקבל כחמישה-עשר מגהבייט לשנייה. יותר מהחיבור הביתי שלכם לאינטרנט. כל המולטימדיה שסביבנו לא היתה אפשרית כלל אלמלא דחיסת הנתונים.
אחרי שהבנו בשביל מה לדחוס, צריך להבחין בין שני סוגי דחיסה: דחיסה משמרת מידע (Lossless), כזו שאפשר לאחזר ממנה את הנתונים המקוריים בדיוק מושלם עד הביט האחרון, ודחיסה מאבדת מידע (Lossy) שמעניקה תוצאה שהיא רק דומה למקור. הסוג הראשון מיועד לרוב למידע מספרי, טקסטואלי או בינארי (כגון קובצי הפעלה במחשב), שכל פספוס בו כלול להיות קריטי, ואילו הסוג השני משמש למדיה – תמונות, צלילים ווידאו, שהדיוק המוחלט בהם אינו חיוני לצופה או המאזין האנושי.
הדחיסה משמרת המידע מתבססת על שתי עובדות פשוטות: כמעט כל רצף נתונים כולל תת-רצפים שחוזרים על עצמם, והשכיחות של כל תת-רצף כזה שונה. לדוגמה, ניקח את הטקסט של ספר התורה (לא כולל סימני הניקוד והפיסוק). הוא כולל עשרים ושבע אותיות (יש גם סופיות, זוכרים?) ולא כולן מופיעות באותה שכיחות. אותיות אהו"י, למשל, נפוצות הרבה יותר מאשר האותיות ף' או צ'.
דמיינו מחסן ובו עשרים ושבע חביות מלאות באותיות מפלסטיק, כל חבית מוקדשת לאות מסוימת. בנינו רובוט שמסוגל ללכת ולהביא אות אחת כל פעם, מכל חבית שנגיד לו. האם יש דרך לסדר את החביות כך שאם נגיד לרובוט להביא את כל האותיות בתורה לפי הסדר, ההתרוצצות שלו הלוך-ושוב תהיה מינימלית? כמובן: הפתרון הוא לסדר את החביות כך שככל שאות מסוימת נפוצה יותר בטקסט, כך החבית שלה קרובה יותר לנקודת המוצא של הרובוט. עבור האותיות הנפוצות ביותר הוא בקושי יצטרך לזוז, ואם במקרה תגיע אות נדירה, הוא יעשה טיול ארוך – אך המרחק הממוצע עדיין יהיה הרבה יותר קטן מאשר אם כל החביות ימוקמו באותו מרחק בדיוק.
רוב האלגוריתמים של דחיסה משמרת מידע עובדים בשיטה דומה לזו. כלומר, ארגון היחידות הבסיסיות של רצף הנתונים לפי השכיחות ויצירת "קודים" קצרים יותר עבור היחידות הנפוצות יותר. האלגוריתמים המתוחכמים יודעים גם לזהות יחידות ארוכות יותר מאשר אות בודדת. נניח המילה "דחיסה" שמופיעה בטקסט הזה פעמים רבות.
בהגדרה, היעילות של דחיסה כזו יורדת ככל שהנתונים אקראיים יותר, שאין בהם תבניות חוזרות ושהשכיחות של כל היחידות הבסיסיות בהם דומה. לכן, דחיסה של טקסט אמיתי תהיה יעילה הרבה יותר מדחיסה של רצף אותיות אקראי. כמו כן, הקובץ הדחוס "מעלים" הרבה מהסדירות שבקובץ המקורי ונראה אקראי יותר, וזו הסיבה לכך שאי אפשר לדחוס קובץ דחוס. אילו זה היה אפשרי, היינו חוזרים על הפעולה שוב ושוב כל קובץ בעולם היה מצטמצם בסופו של דבר לביטים ספורים – וזה כמובן מופרך.
דחיסה משמרת מידע קיימת במחשב שלכם ברמות שונות, החל מתוכנת ה-zip הנפוצה ועד לחומרה של הדיסק הקשיח, שמבצעת לעתים דחיסה בלי לשאול אותנו ובלי שנדע על כך בכלל.
הסיפור הופך מורכב עוד יותר כשאנו עוברים לדחיסה מאבדת מידע. התשובה לשאלות על איזה מידע לוותר ועל כמה ממנו לוותר תלויה גם בהעדפות שלנו וגם באופי של הנתונים המקוריים: הדחיסה של קובצי שמע תהיה חסרת ערך לחלוטין לדחיסה של וידאו, ולהיפך.
פירוק אזורי
בואו נדבר על וידאו. בתמונה הבאה נראים שני פריימים מסרטון שהכנתי (שמדגים משחק פונג במחשב דרך ארדואינו – על זה תוכלו לקרוא בקרוב בבלוג שלי). שימו לב שהחצי התחתון של התמונה שונה לחלוטין בין פריים לפריים, אך החלק העליון – משמאל, מעל ומימין לחלון השחור זהה לחלוטין.
אלגוריתמים רבים לדחיסת וידאו מפרקים, בין השאר, את התמונה לאזורים, ובודקים אילו אזורים נשארו זהים (או כמעט-זהים) בין פריים לפריים. אם יש כאלה, לא צריך לשמור את המידע שהם מכילים בכל פריים בנפרד – מספיק לציין ש"כאן נשאר מה שהופיע קודם". ככל שהאלגוריתם חכם יותר, כך הוא מסוגל לזהות אזורים כאלה בצורה חכמה יותר (אפילו כאלה שהופיעו מספר פריימים לאחור!), לזהות אזורים שנשארו זהים ורק זזו מעט, וכן הלאה.
גם פורמט דחיסת התמונות הפופולרי jpg מחלק את התמונה לאזורים, אך כמובן שכאן היחס אליהם הוא שונה כי אין פריימים נוספים לקחת בחשבון. לכל אזור מוגדרת רשימת פרמטרים ומידע לצורך שחזור, וככל שהדחיסה חזקה יותר, כך הפרמטרים והמידע הללו בסיסיים יותר (וגוזלים פחות מקום), עד לרמה שנראית בתמונה למטה מימין, כאשר אזורים מרובעים שלמים פשוט נצבעים בצבע ממוצע כלשהו.
שיטות המתמטיות לדחיסה עשויות להיות שונות מאד, אך התוצאה זהה: ויתור על פרטים קטנים שהעין לא מבחינה בהם, או מבחינה בקושי. זה מה שקורה גם בדחיסת צליל: האלגוריתמים מנסים לאתר דקויות שהאוזן לא קולטת (או כמעט לא קולטת), או כאלה שרמקולים זולים ממילא לא מסוגלים לשחזר, ומחליפים אותן בצלילים או תבניות פשוטים אחרים.
לדחיסת נתונים, מכל הסוגים, יש מחיר: הזמן או כוח העיבוד שנדרשים כדי להחזיר את הנתונים למצבם המקורי. כשמדובר בתוכן שמגיע בזמן אמת מהאינטרנט, לדוגמה שיחת וידאו, מהירות השחזור היא קריטית, ורובנו לא נהיה מוכנים להמתין אפילו דקה לפענוח מקדים של סרט שהורדנו מהרשת. ככל שהתוכן באיכות טכנית גבוהה יותר, כך אנו זקוקים למחשבים חזקים יותר – ואלה בתורם מאפשרים דחיסה משופרת ותוכן באיכות עוד יותר גבוהה. במילים אחרות, זהו "מרוץ חימוש" שכולם מרוויחים ממנו, ואם נדמה לכם שהמרוויח העיקרי הוא יצרני המחשבים, נסו להיזכר – אם כבר נולדתם אז – כמה זמן חיכיתם בשנות התשעים עד להטענת הזוועה הקצרה הזאת:
