אלגוריתם LZ : פשוט לשלוח קבצים
המוצר: אלגוריתם למפל-זיו לדחיסת מידע
המפתחים: פרופ' יעקב זיו ופרופ' אברהם למפל
שנת הפיתוח: 1977
פרופ'-מחקר יעקב זיו מהפקולטה להנדסת חשמל בטכניון ופרופ' אברהם למפל מהפקולטה למדעי המחשב, פרסמו ב-1977 את LZ77 - הגרסה הראשונה של אלגוריתם למפל-זיו, וב-1978 את הגרסה השנייה: LZ78.
שתי הגרסאות שימשו בסיס לטכנולוגיות דחיסה חיוניות כגון TIFF ,PNG ZIP, ו-GIF ומילאו תפקיד מרכזי בפורמטים PDF (למסמכים) ו-MP3 (למוזיקה). זהו אלגוריתם לדחיסת מידע ללא אובדן המידע, (lossless compression), וללא ידיעה מוקדמת של תכונותיהם. על בסיסו של האלגוריתם פותחו רבות מטכנולוגיות הדחיסה המשמשות כיום באינטרנט בהתקני זיכרון, במחשבים ובתקשורת.
האלגוריתם, ששינה את עולם הדחיסה, נולד מתוך נושא אחר לחלוטין: הפרופסורים זיו ולמפל, אז חוקרים צעירים בטכניון, חקרו את מידת הסיבוכיות של סדרה נתונה (או את מידת קרבתה לסדרה אקראית).
הם הגדירו מידה זו באמצעות המספר המקסימלי של תת-סדרות שונות המתקבלות על ידי פיסוק הסדרה. ואז הם הבינו שיש בידיהם כלי טוב לדחיסת סדרות.
האלגוריתם מצטיין בתכונות הבאות:
(א) אוניברסליות - לא חייבים לדעת מראש את תוכן הקלט
(ב) מהירות גבוהה – ליניארי עם מקדם קרוב ל-1
(ג) אופטימליות – עבור קלט ממקור ארגודי הפלט שואף לאופטימום (אנטרופתיה) ככל שאורך הקלט הולך וגדל
(ד) ככל שהקלט הולך וגדל שום מחשב או מכונה סופית אחרת לא יבצעו את הדחיסה טוב יותר מהאלגוריתם.
מפתחי האלגוריתם זכו בשורה ארוכה של פרסים יוקרתיים ובהם IEEE Golden Jubilee Award, פרס ACM לתיאוריה ויישום, מדליית המינגופרס רוטשילד. עם זאת, ולמרות חשיבותו הרבה והשימוש בו בכל רחבי העולם בכל רגע נתון, הם לא נהנו מהכנסות ישירות עליו.
אלגוריתם למפל-זיו תרם לעולם, ללא תמורה, טכנולוגיה חסרת תקדים המאפשרת העברת מידע ויזואלי ואחר במהירות גבוהה, ללא אובדן מידע. השפעתו ניכרת בחברות המפתחות טכנולוגיה (חברות התקשורת, הטלוויזיות וכדומה) ומגיעה לכל משתמשי הקצה, לרבות מיליארדי משתמשי הטלפון הסלולרי.
ב-2004 הכריז האיגוד הבינלאומי של מהנדסי החשמל והאלקטרוניקה (IEEE) כי אלגוריתם למפל-זיו הוא ״אבן דרך בהנדסת האלקטרוניקה והמחשבים״.
בתמונה: לוגו הטכניון המורכב משמות הקבצים בהם משתמשים באלגוריתם למפל-זיו לדחיסת מידע. יוצרת: ענת הר-גיל.
