לדחוס
25/07/2023
בקטנה: השנה, בהפרש של חודשיים בלבד, הלכו לעולמם שני מדעני מחשב מפורסמים: אברהם למפל ויעקב זיו, שהיו פרופסורים בטכניון ויצרו יחדיו אלגוריתם פשוט ויעיל לדחיסת מידע [1]. אלגוריתם זה – LZ77, שפורסם בשנת 1977, וממשיכיו כגון LZ78, חוללו מהפכה ונחשבים ציון דרך בתחום הדחיסה. לעיתים האלגוריתם מעורר נוסטלגיה בקרב אנשי מחשבים, המשוועים לפיתוחים פשוטים ואלגנטיים. מה הרעיונות היצירתיים שהובילו לפריצת הדרך? נספר. נוסף לכך, כהוקרה לפועלם של למפל וזיו, פיתחנו אפליקציה להדגמת השיטה [2].
בבדיחה ידועה, בחור מצטרף למועדון חברים ומוצא שהם עסוקים במיחזור בדיחות ישנות שכולם הכירו. כדי לחסוך בזמן, כאשר כל אחד מהם סיפר בדיחה הוא אמר רק את מספרה, למשל "מספר 22", וכולם שהכירו אותה צחקו. ואז אחר היה עונה לו: "מספר 7", וכולם התגלגלו מצחוק. ניסה הבחור את מזלו, וקרא "מספר 9", ואף אחד לא צחק. "תבין", אמר לו שכנו, "לא משנה הבדיחה, העיקר איך מספרים אותה".
הבדיחה הזכירה לנו את האלגוריתם שהחוקרים למפל וזיו פיתחו, שמטרתו להקטין את כמות הביטים הנשלחים למשל עבור הודעות טקסט, פעולה שנקראת דחיסה, ובכך להקטין את התעבורה בקווי תקשורת דיגיטלית. לצורך הדחיסה אפשר לבנות סוג מיוחד של מילון, המשייך קידוד מספרי קצר לכל קטע בהודעה שחוזר על עצמו. לאחר מכן, המשדר יוכל לשלוח את הקוד הקצר שנקרא לו "קוד דחיסה" במקום כל מופע של הקטע המקורי, וכך לחסוך בתעבורה. לדוגמה, בחלק הראשון של השיר "הבה נגילה", צירוף המילים "הבה נגילה" (9 תווים כולל הרווח) מופיע כמה פעמים, ולכן כדאי לבצע דחיסה. לשם כך נבנה מילון, נשים בו את המחרוזת "הבה נגילה", ונעניק לה קוד דחיסה קצר, נניח באורך של שני תווים. בהתאם, כשנעלה את הקטע הזה לרשת, כמות התעבורה – דהיינו מספר הביטים שישודרו, תהייה רק 2/9 ביחס לזו שנדרשת לשליחת הודעה שלא נדחסה.
ועם זאת, יש כמה בעיות: כדי שמקבל ההודעה יפענח אותה, צריך לשלוח לו גם את המילון. השליחה חייבת להיות יעילה, כי אם ההודעה החדשה המכילה את ההודעה הדחוסה וגם את המילון ארוכה מאורך ההודעה המקורית, מובן שאין טעם לדחוס. מכאן משתמע שהגיוני לדחוס רק קטעים שחוזרים כמה פעמים. כדי שהמילון שייבנה יהיה קומפקטי, צריך לבצע סריקה של ההודעה מתחילתה ועד סופה, ולבנות אותו כך שיכיל רק קטעים שיש בהם הרבה חזרות.
שיטות ליצירת מילון המתבססות על ניתוח סטטיסטי של ההודעות היו קיימות כבר בשנות ה־70. אולם בדרך זו המשַׁדר צריך לחכות לסיום התהליך של בניית המילון, ורק אז יוכל לשלוח את המילון ואחריו את ההודעה הדחוסה. תהליך כזה גורם להשהיה לא רצויה בשידור ובקליטה, ולכן צריך למצוא פתרון שיאפשר להתחיל לשלוח את ההודעה ללא השהיה, ובמקביל יאפשר לבנות ולשלוח גם את המילון. מאתגר! כיצד הייתם פותרים?
בשנות ה־70 אברהם למפל ויעקב זיו היו פרופסורים צעירים בטכניון; זיו בפקולטה להנדסת חשמל, ולמפל בפקולטה למדעי המחשב. הם נהיו חברים כאשר נפגשו בשירות מילואים, גילו עניין משותף בתורת האינפורמציה, והאתגר לשפר דחיסת טקסט ריתק אותם. זיו סיפר שלמרות שהאלגוריתם LZ77 [1] נראה כמו הברקה פשוטה, לקח להם כשנתיים להתווכח ולדון עליו לפני פרסום המאמר, הכולל ניתוח מתמטי תיאורטי.
ההברקה היצירתית: במקום שניתקע בהגיגים על המילון, נפנה לכיוון שונה לגמרי. במהלך כל שלב בשידור נבקש מהשולח והקולט לא לזרוק את האינפורמציה שכבר נשלחה והתקבלה, אלא שכל אחד יאגור אותה בזיכרון פנימי שלו (חוצץ – buffer). בהתחלה, התווים הראשונים של ההודעה ישלחו ללא דחיסה, והם ישמרו בחוצץ של השולח והקולט. עכשיו מגיע הקטע החכם: כאשר השולח ינסה לשלוח מחרוזת תווים חדשה, הוא יבצע חיפוש בזיכרון החוצץ: האם הוא כבר שלח בעבר מחרוזת זהה (למשל: האם "הבה נגילה" כבר הופיע)? אם כן, השולח ישלח במקומה קוד דחיסה קצר, למשל באורך של 2 תווים. קוד זה יכיל את מיקום המחרוזת בחוצץ (למשל מקום 10), ואת אורכה (9=). הקולט יזהה שזה קוד דחיסה, ומכיוון שהחוצץ שלו מכיל אותו תוכן כמו של השולח, הוא ישחזר בהצלחה את המחרוזת שנשלחה. פשוט, לא כן? בשיטה זו תוכן החוצץ הוא למעשה ה"מילון" שעליו דיברנו, והוא נבנה וגדל בהדרגה במהלך השליחה.
נפרט: בשיר "הבה נגילה" מופיע הקטע: "הבה נרננה, הבה נרננה, הבה הבה נרננה". אנחנו רוצים לשלוח אותו לחברים. בשלב הראשון, מכיוון שהחוצץ ריק, המשדר ישלח את "הבה נרננה, " הראשון (11 תווים כולל שני רווחים) ללא דחיסה, והאינפורמציה תישמר בזיכרון החוצץ של המשדר ושל הקולט. אולם כשהמשדר יגלה שהוא צריך לשלוח שוב אותה מחרוזת שנמצאת כבר בחוצץ, הוא ישלח במקומה את הקוד באורך של שני תווים המכיל קידוד של מיקומה ההתחלתי בחוצץ (0=) ואת אורכה (11=). בהמשך השיר מופיעה המילה "הבה" לבדה, ולכן המשדר ישלח הפעם קוד עם אורך אחר (4=), וכולי. לבסוף נגלה שבמקום לשלוח הודעה באורך של 32 תווים, שלחנו 11 תווים רגילים ו־4 קודי דחיסה שכל אחד מהם באורך 2 תווים. כלומר שלחנו הודעה באורך 19 תווים לעומת 32. יופי, אז הבה נרננה!
פסקה זו מיועדת לחובבי ביטים שרוצים להתעמק [3], השאר מוזמנים לדלג: בגרסה של האלגוריתם שתיארנו וששונה במקצת מהגרסה המקורית LZ77, כל תו מיוצג באמצעות שמונה (8) ביטים, ומתוכם שבעה (7) יכילו את הקידוד של התו, ועוד ביט בקרה יחיד שערכו אחד, המציין שזהו תו רגיל ולא קוד דחיסה. לעומת זאת, קוד דחיסה יכיל 16 ביטים: ביט הבקרה, שערכו אפס, 11 ביטים המכילים אינדקס לתחילת המחרוזת בזיכרון החוצץ (מספר עד 2,048) וארבעה (4) ביטים המייצגים את אורך המחרוזת (בין 1 ל־16). בשיטה זו, החוצץ שהוא גם המילון יכיל תמיד רק את 2,048 התווים האחרונים שכבר נשלחו, וגודל המחרוזת המקסימלי שאפשר לדחוס הוא 16 תווים. למרות המגבלות הללו, הדחיסה של טקסט ארוך יוצאת מוצלחת בדרך כלל. לכבוד הפוסט פיתחנו אפליקציה ב־JS הממחישה את השיטה. מוזמנים לנסות לדחוס [2].
האלגוריתם אומנם לא נרשם כפטנט, אבל הוא קצר הרבה שבחים והמחברים זכו להוקרה ולפרסים רבים. בעקבותיו נוצרו שלל גרסאות ששימשו בסיס לטכנולוגיות דחיסה כגון TIFF ,PNG ,ZIP, GIF ואחרים. לפי ACM, האגודה המקצועית הבינלאומית המרכזית שמאגדת בעלי מקצוע שקשורים למחקר ולפיתוח בתחום המחשוב: "השפעת עבודתם של הפרופסורים למפל וזיו כה עצומה, שהמחקר הנוכחי בתחום עודנו תוסס כפי שהיה לפני עשרות שנים" [4].
בהשראת זיו ולמפל זכרונם לברכה, אנו מצפים לעוד מחקרים כחול־לבן, שיהיו פורצי דרך וגם פשוטים דיים שיהיה קל וכיפי לכתוב עליהם פוסטים.
תמונה: מירי אורנשטיין באמצעות Midjourney.
פיתוח אפליקציה: טניה אורנשטיין.
עריכה: יהונתן הופמן.
מקורות והרחבות
[1] אלגוריתם LZ77
[2] קישור לאפליקציה
מהנדס מחשבים, חוקר ויזם בתחום החינוך המתמטי.
