לאן נעלמו להם 44 גיגה בייט? להבין דחיסת נתונים

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

מקור: Pixabay, עיבוד תמונה

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

ויקיפדיה בגרסת האנגלית מכילה 3.5 מיליארד מילים. כל הידע האנושי דחוס ל-3.5 מיליארד מילים. איך אני יודע? קראתי בויקיפדיה.

***

חלקכם יופתעו לגלות כי גרסת הטקסט העדכנית של ויקיפדיה ניתנת להורדה בשלמותה. נכון לרגע כתיבת שורות אלו, הגרסה האנגלית של ויקי שוקלת 58GB אך מי שינסה להורידה ישמח לדעת שהוא מוריד קובץ דחוס ששוקל “רק” 14GB, כלומר רק רבע מגודל הקובץ המקורי.

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

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

Run-length encoding

לפעמים כשאנו דוחסים מידע אנו נתקלים בתבניות שחוזרות על עצמן. DNA לדוגמה מורכב מרצף של ארבעה נוקלאוטידים המכונים ACGT. הפיזור של הנוקליאוטידים ברצף אינו אחיד וישנם איזורים שבהם יש ריכוז גבוה של CG. קובץ אודיו של הקלטה עשוי להכיל איזורים של שקט אשר מתבטאים בדגימות חוזרות של 0 ווליום.

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

לבן; לבן; לבן...צהוב; צהוב; צהוב...לבן; לבן

בנסיבות מסוימות, פורמט BMP תומך בדחיסת RLE. אם נסיבות אלו התקיימו, קובץ הסמיילי יראה כך:

לבן X 114; צהוב X 11; לבן X 34 וכו'.

נחשו באיזו שיטה הקובץ קטן יותר.

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

דילול ביטים

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

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

תקן ASCII מכיל 256 תווים: 0-9, a-z, A-Z, סימני פיסוק, תווי בקרה, ומספר תווים נוספים. טקסט כלשהו באנגלית, נגיד סיפור ילדים, עשוי שלא להכיל מספרים, כמו כן, באנגלית טקסט נכתב לרוב באותיות קטנות, ולכן גם חלק מהאותיות הגדולות עשויות שלא להימצא. אומנם נהוג באנגלית לכתוב משפט באות ראשונה גדולה, אך חלק מהאותיות (V, K, Q, Z, X) נוטות להופיע פחות בתחילת משפט מאחרות (T, I, A, H, S). כלומר מאוד יתכן שניתן לייצג את אותו הטקסט ב-5 ביט (32 סימנים) במקום ב-8, חיסכון של 37.5% מנפח הבלוק.

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

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

יישום דחיסה

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

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

דוגמה 1:

“!!!!!!!!!!!!It’s over 9000” יקודד ל-It’s over 9000!!!!8

דוגמה 2:

“The password is 1111” יקודד ל-The password is 11110

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

כאשר אנו משתמשים ב-RLE מדוע אנו מקודדים את 4 הסימנים החוזרים הראשונים? ומדוע אנו טורחים לקודד 0 כאשר יש רק 4 חזרות?

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

כאשר נחיל את ה-RLE לפי החוקים של bzip2 על התמונה של הסמיילי, נקבל:

לבן; לבן; לבן; לבן; 110צהוב; צהוב; צהוב; צהוב; 7לבן; לבן; לבן; לבן30; וכו'.

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

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

Burrows–Wheeler transform

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

אז בו נעשה קסם, ניקח את המילה: “אברקדברה”, נוסיף לה בסופה את התו “$”. עתה נדמיין שהיא מופיעה על גלגל. נרשום את כל האותיות כפי שהן מופיעות על הגלגל לפי הסדר – החל מהאות א’. קיבלנו את אותה המילה. נעשה זאת פעם נוספת, אך הפעם נתחיל מהאות בית. נמשיך לעשות זאת שוב ושוב, כאשר בכל פעם נתחיל מנקודה אחרת.

כשנסיים נקבל את זה:

$אברקדברה

ברקדברה$א

רקדברה$אב

קדברה$אבר

דברה$אברק

ברה$אברקד

רה$אברקדב

ה$אברקדבר

אברקדברה$

נמיין את התוצאות לפי סדר אלפביתי ($ קודם ל-א’) ונקבל:

אברקדברה$

$אברקדברה

ברה$אברקד

ברקדברה$א

דברה$אברק

ה$אברקדבר

קדברה$אבר

רה$אברקדב

רקדברה$אב

ניקח, לפי הסדר, את התו האחרון בכל מילה, ונקבל ה$דאקררבב

מה שעשינו עכשיו זה ליישם Burrows–Wheeler transform. כדי להבין למה זה טוב נסתכל על התוצאה. ספציפית על האותיות “ררבב” שבסופה.


 

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

 


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

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

כדי להוציא את המיטב מ-BWT יש לבצעו על טקסטים ארוכים ולא על מילים בודדות. בעזרת כלי שזמין אונליין עשיתי BWT על ההתחלה של השיר Billie Jean (באותיות קטנות).

להלן התוצאה:

eddeeeemdii,afs,ellltdtnheeenye,drrreedutsardeeeeeeyeeeieeassnnnmgmnnn
edeet,ooododnndne ess neeedddww hhce nnnssnneiileaenn nnnn
khhhhmirccchhhhhhhihmhnhrjmbsmnubhecchvy o ntwtstttttttttsss t www
aalvlwwwb mew illlol iiiifffoaa a a eeoooiiioaa aaauuuieeooorih
hhd tr d lllooomyrrrm oooeoduf eaaae u $aa'ui u
oqoootabaeo rte

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

איך BWT עושה את זה? איך הוא לוקח טקסט אקראי והופך אותו לטקסט דחיס? איך הפעולות הפשוטות שעשינו גורמות לאותיות דומות להתאגד? התשובה המדעית היא מאגיה שחורה.

אנחנו יכולים עתה להריץ RLE על התוצאה, אבל במקום זאת בוא ניקח את זה שלב אחד קדימה…

Move-to-front transform

טרנספורמטור Move to front מתבצע לעיתים קרובות אחרי BWT, וכמוהו, גם הוא אינו דוחס את המידע אלא רק מארגן אותו בצורה נוחה יותר לדחיסה. נבנה גרסה בסיסית שלו על ידי כך שתחילה ניצור טבלה ברוחב 30 תאים ונמלא אותה באופן הבא: תו “$” בתא 0, תו ” ” (רווח) בתא 1, תו “’” (גרש) בתא 2, תו “,” (פסיק) בתא 3 והתווים a-z בתאים 4-29.

להלן החוקים:

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

נפעיל את ה-MTF על הפלט שקיבלנו קודם, כאשר עשינו BWT על Billie Jean:

MTF על “eddeeeem”, 8 התווים הראשונים של Billie Jean שעבר BWT

נקבל את התוצאה הבאה:

8 8 0 1 0 0 0 16 2 13 0 7 8 11 22 3 7 17 0 0 23 8 1 19 17 5 0 0 2 28 2 7 6 24 0 0 3 0 2 25 8 10 12 6 5 6 0 0 0 0 0 8 1 0 0 13 1 0 5 6 0 10 0 0 14 20 1 2 0 0 5 8 1 0 10 12 23 0 0 4 1 1 5 0 1 1 5 18 1 9 0 2 3 3 0 0 4 0 0 27 0 4 16 0 22 5 3 6 0 0 7 0 1 0 3 14 0 18 2 15 1 4 0 6 1 0 0 0 24 9 0 0 0 15 8 18 11 0 0 4 0 0 0 0 0 0 3 1 4 1 6 1 5 24 4 24 13 2 6 21 4 7 12 10 0 2 27 22 14 19 1 9 21 19 1 13 1 0 0 0 0 0 0 0 0 1 0 0 4 2 1 3 0 0 18 0 19 9 1 3 0 0 13 5 15 14 4 3 18 6 0 0 12 1 3 3 0 0 0 23 0 0 4 10 0 4 1 1 1 1 7 0 3 0 0 5 0 0 1 4 0 4 1 0 0 17 0 0 4 5 0 5 0 0 19 3 17 0 0 21 8 15 5 2 3 1 11 0 0 7 0 0 13 18 6 0 0 2 5 4 0 0 10 1 7 11 13 5 5 13 0 0 1 2 4 1 24 4 0 25 4 15 5 2 9 27 1 0 0 15 7 18 1 10 4 7 14 6 4

מה עשינו בזה ולמה זה טוב?

פועל יוצא של החוק השני של MTF הוא שכל רצף חוזר של תווים יניב מספר כלשהו ואחריו רצף של אפסים ללא קשר לסוג התווים. ואכן הפלט מורכב מ-34% של ‘0’. ככל שאות יותר נפוצה בטקסט כך היא תקודם בטבלה יותר פעמים ואכן הערך הנפוץ ביותר אחרי ‘0’ הוא ‘1’, שמופיע ב-11% מהפלט. מספרים נוספים אשר נפוצים בפלט: ‘2’, ‘3’, ‘4’ ו-‘5’. כלומר הפלט מורכב בעיקר מערכים נמוכים.

התכונה המיוחדת של MTF, בנסיבות הנכונות, היא לצמצם את מספר הסימנים בקטע ולהמיר אותם לערכים נמוכים. אלגורתמים של דחיסה יודעים לנצל את העובדה שיש פחות סימנים בבלוק. ראינו דוגמה לכך קודם. כמו כן, סוגים מסויימים של אלגוריתמים יודעים גם לנצל נטיה לערכים נמוכים. ולכן השלב הטבעי הבא יהיה להריץ אלגוריתם דחיסה מסוג זה, כגון גרסה מיוחדת של RLE או Arithmetic coding. אלו כבר, למאמר אחר.

פס ייצור של דחיסה

***

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

איך אני יודע? קראתי בויקיפדיה.

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


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


 

Avatar

כתב אורח

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

הגב

16 תגובות על "לאן נעלמו להם 44 גיגה בייט? להבין דחיסת נתונים"

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

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

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

מעניין מאוד, תודה על המאמר

גדי קוטלר
Guest

לכותב האלמוני, צור איתי קשר בבקשה בנושא..
gadykotler@gmail.com

איתן
Guest

למה אלמוני? כתוב את השם שלו מתחת לכותרת (ארתור אקרברג).
אגב אתה כבר ממש לא אלמוני לספאמרים :( להבא אל תפרסם את המייל שלך בריש גליי (בלי לבצע איזשהו עיוות מינימאלי, כמו @g.m.a.il או משהם כזה) – יש בוטיםצשסורקים פורומים ותגובות בשביל לשלוח ספאם.

ASD
Guest

אילו רק היה בג’ימייל איזשהו מנגנון סינון ספאם מובנה או משהו כזה, אה?

איתן
Guest

אילו הוא רק היה עושה את העבודה שלו…

מישהו
Guest

מתתי בדוגמא של ה over 9000 חוץ מזה אחלה מאמר

אלון
Guest

מעניין מאוד, אחלה מאמר !

nope
Guest

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

מקום
Guest

מאמר מצוין, תודה!

משתמש אובונטו
Guest

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

הכרת את הדברים מאוד בכלליות ועכשיו הרבה יותר מפורט. תמשיכו כך!

הרבה יותר טוב מאוד “מאמר” על סכנות הסייבר או משהו כזה.

משתמש אובונטו
Guest

ועכשיו בלי השגיאות:

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

הכרתי את הדברים מאוד בכלליות ועכשיו הרבה יותר מפורט. תמשיכו כך!

הרבה יותר טוב מ“מאמר” על סכנות הסייבר או משהו כזה.

יא מעייף
Guest

למתנשא:
בנוסף לשאר השגיאות שלך, כתובים התעליתם ולא התעלתם.

Daniel Raban
Member

מעניין ומעשיר

תודה רבה

אני
Guest

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

נהג חדש
Guest

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

Asaf
Guest

יפה.
(אגב, גם ב- DNA יש דחיסה בעזרת לולאות)

wpDiscuz

תגיות לכתבה: