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

"פרופ' אמריטוס למפל ז"ל היה מקור השראה לכולנו… מעטים החוקרים שמחקריהם השפיעו באופן כה נרחב על הקדמה הטכנולוגית ועל חיי היום-יום שלנו," כך ספד נשיא הטכניון לפרופ' אברהם למפל, שהלך לעולמו ב-3 בפברואר השנה. 

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


אברהם למפל ב-2007 | מקור: ויקיפדיה, נחלת הכלל 

המפגש בין דחיסה להצפנה

למפל, יליד פולין, עלה לישראל בשנת 1948, למד לתוארי בוגר, מוסמך ודוקטורט בהנדסת חשמל בטכניון והשלים את הדוקטורט בשנת 1967, עם תזה שעסקה בתורת הגרפים. עשור לאחר מכן הוענק לו תואר פרופסור מטעם הטכניון ובשנים 1981 עד 1984 כיהן כדיקן הפקולטה למדעי המחשב בטכניון. 

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

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

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

נושא הדוקטורט של יעקב זיו היה העברת מידע בערוץ דיגיטלי; למפל עצמו התעניין בהצפנה, פעולה שגם היא דורשת קידוד של מידע ואז פענוח שלו בצורה יעילה. המפגש ביניהם הוביל את השניים לפיתוח אלגוריתם הדוחס מידע תוך שמירה על המידע כולו, כניגוד לשיטות אחרות (כמו JPEG) הדוחסות את המידע תוך ויתור על חלק ממנו. שתי גרסאות של האלגוריתם פורסמו בזו אחר זו ב-1977 ו-1978 ומכונות, בהתאם, אלגוריתם למפל-זיו 77 ו-78 (LZ78, LZ77).


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

אלגוריתם למפל-זיו: "אין צורך בחזרות"

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

האלגוריתם הזה היה הבסיס לטכנולוגיות דחיסה שמיליארדי משתמשים נעזרים בהן מדי יום, בכל מקום: PDF (מסמכים כתובים); PNG ,GIF ,TIFF (תמונות); MP3 (מוזיקה); ZIP (דחיסת קבצים, למשל כשאנחנו רוצים לשלוח קובץ גדול מאוד בדואר אלקטרוני, שרוחב הפס שלו קטן). "שיטת למפל-זיו" נקבעה כתקן בינלאומי. בשנת 2004 הכריז האיגוד הבינלאומי של מהנדסי החשמל והאלקטרוניקה (IEEE) כי אלגוריתם למפל-זיו הוא אבן דרך בהנדסת אלקטרוניקה ומחשבים. נשיא הארגון הוסיף כי "האלגוריתם תרם תרומה משמעותית להפיכתה של רשת האינטרנט לאמצעי אפקטיבי בתקשורת הגלובלית".

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

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

 

0 תגובות