איך עובד כיווץ מידע? העולם הזה וכל מה שבו - הכל 0110100101111 • עידו גנדל נכנס לעובי הקורה כדי להסביר לכם איך אפשר לקחת נתונים ולאחסן אותם בפחות מקום

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

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

הנתונים ונסלק, בשאיפה, קצת מהערפל שאופף את התחום המרתק הזה.

בעולם המחשבים, היחידה הבסיסית ביותר של נתונים היא הביט (Bit ובעברית "סיבית"), שיכול לקבל את הערכים 0 או 1. כלומר, כדי לאחסן רשימה של אפסים ואחדים (בלי שום דחיסה), נזדקק לכל הפחות למספר זהה של ביטים במחשב. יחידה שימושית יותר היא הבייט (Byte), שאורכו שמונה ביטים והוא מסוגל לאחסן, בייצוג בינארי, מספרים בין 0 ל-255. קוד ASCII, שמוכר כמעט בכל מחשב בעולם, מגדיר רשימה תקנית של תווים ואותיות אנגליות שתואמים למספרים 0-127 (למשל, קוד ASCII של התו "A" הוא 65). לכן, כדי לשמור את המחרוזת "Data" בקוד ASCII נזדקק לארבעה בייטים – אחד ל-"D", אחד ל-"a" וכן הלאה. כמה בייטים צריך כדי לאחסן את המחרוזת "בסיעתא דשמיא"?קודים ותבניות

אלף שירים על כרטיס *כזה* קטן (צ': GettyImages)

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

לו יהי
לו יהי
אנא לו יהי
כל שנבקש לו יהי

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

X=לו יהי
X
X
אנא X
כל שנבקש X

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

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

לכובע שלי שלוש פינות
שלוש פינות לכובע שלי
לולא היו לו שלוש פינות
לא היה זה הכובע שלי

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

X=כובע שלי
Y=שלוש פינות
לX Y
Y לX
לולא היו לו Y
לא היה זה הX

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

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

הלו קיטי שולטתתתתתתתתתתתתתתתתתתתתתתתת!!!!!!!!!1 (אורך: 47 תווים)

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

X=תתתתתתתתתתתת
הלו קיטי שולטXX!!!!!!!!!1 (39 תווים)

או אולי

X=תתתתתת
הלו קיטי שולטXXXX!!!!!!!!!1 (35 תווים)

בסדר, בסדר, היא שולטתת!!!1 לפטופ של הלו קיטי (צ': יח"צ)

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

הלו קיטי שולט#24#ת!!!!!!!!!1 (28 תווים בלבד!)

ואם נכווץ את המחרוזת המלאה בשיטה זו, נקבל

הלו קיטי שולט#24#ת#9#!1 (23 תווים – למעלה מ-50% דחיסה)

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

הלו קיטי שולטתתתתתתתתתתתתת!!!1 ומי שחושב אחרת הוא &@#$%%**(*%T@#!!!

לשמר או לאבד?שתי שיטות הדחיסה שהצגנו עד כה מאפשרות לשחזר את הנתונים המקוריים בצורה מדויקת, אלא שלפעמים אנחנו בכלל לא צריכים את הצורה המדויקת. מה כבר היינו מפסידים אם היינו כותבים את המשפט ההוא פשוט כך: "הלו קיטי שולטת!"? שום דבר מהותי לא היה הולך לאיבוד, והיינו משיגים כמעט 70% דחיסה. דוגמה נוספת: אם המשקל מראה 1500.0013201092 גרם פיסטוק חלבי, למה לא לומר פשוט קילו וחצי?

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

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