להפוך פסקה שלמה לאות אחת: הצצה לדחיסת נתונים

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

האלגוריתם של Pied Piper כיכב בסדרה “עמק הסיליקון” | מקור: HBO

מאת ארתור אקרברג

האגדה מספרת על הסופר המפורסם ויקטור הוגו ששהה בחופשה ורצה לדעת כיצד מתקדמת מכירת סיפרו החדש “עלובי החיים”.

מה עשה? כתב למו”ל.

כאשר המו”ל פתח את המכתב הוא הופתע לגלות שהוא מכיל רק תו אחד: “?”

***

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

תו אחד: “?” שמחליף משפט אחד: “איך מתקדם מכירות הספר שלי?” – הוא דוגמה נהדרת לדחיסת נתונים.

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

שיט.

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

איך זה קשור לדחיסת נתונים?

כידוע מחשב צריך לייצג כל דבר בביטים עכשיו בוא נדמיין שיש לנו סידרת מספרים עם ערכים שנעים בין 0 ל-7:

5 ; 5 ; 4 ; 6 ; 2 ; 3 ; 1 ; 7 ; 6 ; 3 ; 0

אנחנו יכולים ליצג את הערכים בסידרה בעזרת 3 ביטים למספר. כלומר כדי לייצג את כל הסידרה אנחנו זקוקים ל 33 ביטים.

עכשיו נגיד שבמקום הסידרה הקודמת קיבלנו סידרה חדשה זהה למעט הסיפרה 3 שבאמצע הסידרה אשר הוחלפה במספר 12. השינוי הפשוט הזה מחייב אותנו לייצג את הערכים בעזרת 4 ביטים:

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

והנה דוגמה מהחיים האמיתים.

אתה גולש באייבי ואתה קונה שולה חלמונים בצורת תרנגולת. אתה לא צריך אותו, אתה אפילו לא מבשל, אבל הוא עלה רק 0.99 דולר. עוד מקרה של קנייה אימפולסיבית שמצטרפת לאוזני ספוק סיליקון (3 דולר), נורת אדיסון וינטג’ (5 דולר), כיסוי הלו קיטי לאייפון (4 דולר) ופוסטר של T-800 (רק 7 דולר). עד כה כולם סכומים קטנים. ואז אתה מתיישב בסלון מדליק את הטלויזיה וכלום. החרא לא נידלק, מוציא ריח שרוף במקום. בלי פאניקה, יש Wi-Fi, כמה קליקים באמזון ורכשת את ה-8K החדש (2300$). חברת האשראי שעוקבת אחרי הרכישות שלך ומאחסנת את הסכומים במאגרי הנתונים שלה, תיתקל באותה בעיה שהצגנו קודם. את סידרה הרכישות בסכומים הקטנים ניתן לייצג על ידי מספר קטן של ביטים אילולא היו אחת לכמה זמן גם רכישות בסכום יחסית גבוה.

איך נקטין את מספר הביטים שנידרשים לייצוג?

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

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

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

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

וככה זה נראה מהצד של חברת האשראי:

$341,445 ; $31,900 ; $28,500 ; $29,222 ; $28,119 ; $28,700 ; $30,500 ; $29,000

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

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

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

כוח דלתא

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

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

והינה דוגמה לדחיסה מוצלחת: שעון ריצה כלשהו המכיל 8 MB זיכרון דוגם קואורדינטות GPS כל שניה. גם אם היצרן מאפשר לשמור תיעוד שבוע אחורה, ניראה כי 8 MB זה די ויותר זיכרון לקואורדינטות GPS. עד שעושים את החשבון ומגלים שבשבעה ימים זה מסתכם ב- 600 אלף! דגימות.

דוגמה לדגימת GPS (קו אורך;  קו רוחב; גובה מעל פני הים): 483221123 ; 234234324 ; 122111.

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


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

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

א.ק.ג תקין ממוצע מכיל 5 נקודות קפיצה/נפילה (P,Q,R,S,T) שחוזרות על עצמם והאביזר מתעד את חתימת הזמן והגובה של כל נקודה כזאת.

את חתימת הזמן אנחנו יכולים לדחוס בקלות בדחיסת דלתא, אבל מה לגבי הנקודות?

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

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

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

אומנות הדחיסה

דחיסת נתונים נמצאת בכל מקום מסביבנו, רוב המשתמשים מודעים לה בעיקר בזכות קבצי ה-ZIP וה- RAR, אך במציאות, בזכות האינטרנט, אנו נחשפים אליה הרבה יותר. מאחורי הקלעים של שירותי ענן כמו Gmail ו-Dropbox, פועלים אלגוריתמים הדוחסים סוגי קבצים שונים בדחיסה המותאמת אילהם. כאמור, דחיסת נתונים מוצלחת מורכבת מהבנה מעמיקה של אופי המידע וממרכיב “סודי” נוסף. לא, לא אהבה, אלא יצירתיות. במאמר זה עברנו על מספר דוגמאות, חלקן פרקטיות לעיתים נדירות, אך כולן מספקות תובנות לדרכים אלטרנטיביות להצגת אותו המידע. עכשיו בהצלחה.

***

אגב, לפי האנקדוטה, המו”ל ענה לסופר: “!” ​

 

הכותב הינו חוקר עצמאי בתחום דחיסת נתונים

Avatar

כתב אורח

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

הגב

19 תגובות על "להפוך פסקה שלמה לאות אחת: הצצה לדחיסת נתונים"

avatar
Photo and Image Files
 
 
 
Audio and Video Files
 
 
 
Other File Types
 
 
 

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

סידור לפי:   חדש | ישן | הכי מדורגים
עידו
Guest

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

מי טו
Guest

הסבר מעולה, חבל שלא היה אותו שקיבלתי עונש מהמורה לכתוב 100 פעם ” יותר לא אשכח לתת לכלב אוכל שלא יהיה רעב ויאכל לי את השיעורי בית”

אביחי
Guest

מורה בלאי.
היא היתה צריכה לבקש ממך לכתוב “שיעורי הבית”, לא “השיעורי בית”.

brute force
Guest

לא ממש צריך דחיסה בשביל זה…
(++for( int i=0; i<100;i
;(” יותר לא אשכח לתת לכלב אוכל שלא יהיה רעב ויאכל לי את השיעורי בית” )print

אביחי
Guest

1. יש לך רווח מיותר בתחילת המשפט המודפס
2. חזרת על טעות הלשון המקורית

אני
Guest

כתבה טובה בלי פרסומות? שחקתם אותה. נהנתי

האיש שבקיר
Guest

כתבה יפה, אבל…
1. חבל שיש שימוש בשפה ברמה נמוכה/לא נאותה – “החרא לא נדלק”
ממש מיותר!!!
2. המינוח הנכון הוא: די והותר
ולא : די ויותר
צריך להעביר הגהה לפני שמפרסמים

אביחי
Guest

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

Asaf
Guest

הנה דחיסה:
:/

ASD
Guest

?

חזקיהו
Guest

????

חזקיהו
Guest

אחלה כתבה

אביעד
Guest

כתבה מדהימה!!!

אריה
Guest

מעניין!!
תביאו עוד כתבות בסגנון

מני
Guest

אחלה כתבה, הסבר מצויין!

מממיי
Guest

????

אלון
Guest

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

nope
Guest

כתבה מצויינת, כמה שגיאות כתיב קטנות אבל שטויות.
כן ירבו!

פייקבוק
Guest

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

wpDiscuz

תגיות לכתבה: