דחיסת המידע של למפל וזיו

כמעט בכל מייל ותמונה שאנו שולחים בטלפון או במחשב, מבוצעת דחיסה אפקטיבית של המידע ללא איבודים (lossless compression). האלגוריתמים המוצלחים ביותר הומצאו על ידי שני פרופסורים להנדסת חשמל מן הטכניון – אברהם למפל ויעקב זיו. אין לתאר את מהפכת המידע המודרנית וכמות הביטים הבלתי ניתנת לתפיסה המועברת בין בני האדם ללא הדחיסות המשמעותיות LZ77 (פורסמה בשנת 1977), LZ78 (פורסמה בשנת 1978) וגרסאות מתקדמות רבות נוספות.

על אלגוריתם למפל-זיו

פרופ' יעקב זיו

פרופ’ יעקב זיו

האלגוריתם של למפל וזיו הוא הבסיס לפורמטים דוחסים מסוג GIF, TIFF ,PNG ZIP ואחרים. הוא מהווה חלק חשוב גם בדחיסת PDF ובהפעלת MP3. בניגוד לדוחסים סטטיסטיים שהיו ידועים כבר בשנות ה-50, דוחס LZ הוא דטרמיניסטי ויעיל במיוחד. בדוחס סטטיסטי, כמו אלגוריתם שנון-פאנו או אלגוריתם הפמן, מסדרים את ההודעות לפי סדר שכיחות יורד ומקצים קודים חדשים לכל הודעה. הודעה שכיחה מקבלת מספר קטן של ביטים והודעה נדירה מקבלת מספר גדול של ביטים, אך הודעה נדירה אינה משפיעה בהרבה על הקצב הממוצע של המידע. אם האלגוריתם יעיל אפשר להגיע לרמת דחיסה אופטימלית כך שאורך המילה הממוצעת שווה לאנטרופיה (“קידוד אנטרופי”). חסרונה של השיטה הסטטיסטית בהיקף העיבוד הרב שיש להשקיע בהיכרות מוקדמת עם ההודעות. השיטה של LZ מבוססת על בנייה ראשונית של מילון מחרוזות מבלי לדעת את התכונות הסטטיסטיות שלהן. הרעיון הוא להשתמש במצביעים במקום לשכפל את המידע שוב ושוב. חלק מן ההשראה של למפל וזיו מיוחס לסידור התפילות. אם יש תפילות חוזרות כמו “אבינו מלכנו” אין צורך לשדר אותן כל פעם מחדש אלא מספיק לשדר את שם התפילה והצד השני כבר ידע למה הכוונה.  הגרסה הראשונה של האלגוריתם פורסמה בשנת 1977 ונקראת LZ77. גירסה חשובה נוספת LZ78 פורסמה בשנת 1978 וידועות עוד גרסאות מוצלחות נוספות אשר שיפרו את הביצועים במידה ניכרת. אלגוריתם LZW שפותח עם וולש, מתכנת שעבד עם פרופ’ למפל בשנת 1984 הוא כנראה היעיל ביותר. האלגוריתמים השונים מבוססים על חלוקת המחרוזת המקודדת לתת מחרוזות הנקראות פסקאות. כל פסקה מתאימה למחרוזת מעל מילון סופי הנבנה עם הפעלת הדוחס. אין צורך בידע קודם של התוכן וכאמור גם אין צורך בעיבוד סטטיסטי של שכיחויות. אלגוריתם LZ הוא מאבני היסוד של תורת האינפורמציה ונחשב לאחד ההישגים הטכנולוגיים המזהירים שהומצאו בישראל.

levine1 levine2
הביוגרפיה של פרופ’
יעקב זיו

פרופ' אברהם למפל

פרופ’ אברהם למפל

יעקב זיו נולד ב-27 בנובמבר 1931 בטבריה. אביו בן ציון זיו היה מורה ומנהל בטבריה וברעננה. יעקב זיו סיים תואר ראשון ותואר שני בהנדסת חשמל בטכניון בשנים 1954 ו-1957 והשלים דוקטורט במכון הטכנולוגי של מסצ’וסט MIT בשנת 1962. בשנים 1955-1959 עבד ברשות לפיתוח אמצעי לחימה (רפא”ל) שם עסק במחקר ופיתוח של מערכות תקשורת. בשנת 1962 עם שובו מלימודי הדוקטורט בארצות הברית שב לרפא”ל וניהל את המחלקה לתקשורת. בשנים 1968-1970 עסק במחקר במעבדות בל שאליהן שב מספר פעמים כמדען אורח. בשנת 1970 הצטרף לסגל הטכניון, שם שימש בין היתר דיקן הפקולטה להנדסת חשמל ומשנה לנשיא לעניינים אקדמיים. עסק במחקרים תיאורטיים של תורת האינפורמציה ודחיסת מידע. בשנת 1981 נבחר כחבר באקדמיה הישראלית למדעים ואף שימש כנשיאה בשנים 1996-2004. זכה פעמיים בפרס בטחון ישראל וגם בפרס ישראל. בשנת 1998 נבחר כחבר האקדמיה האמריקאית לאמנויות ומדעים ובשנת 2004 לחבר באקדמיה הלאומית למדעים של ארצות הברית. בשנת 1995 זכה במדליית המינג של ארגון IEEE ובשנת 1997 זכה בפרס שנון של IEEE. קיבל גם את פרס מרקוני על שם ממציא הרדיו. בשנת 2008 זכה בפרס חזית הידע של קרן BBVA הספרדית על המצאותיו פורצות הדרך בתחום דחיסת המידע ותורת האינפורמציה. סכום הפרס 400 אלף יורו הוא השני בגודלו אחרי פרס נובל. בנימוקים לפרס צוינה תרומתו של יעקב זיו הניכרת בכל היבט של חיי היום יום שלנו. אחסון והעברה יעילה של טקסט, נתונים, תמונות וידאו, טכנולוגיות דחיסת אינפורמציה בזיכרונות מחשב, מודמים, הפצת תוכנה וקבצים – כל אלה נשענים כיום על רעיונותיו והמצאותיו של פרופ’ יעקב זיו. תרומותיו החלוציות לתורת המידע הניעו והנחו דורות של אנשים באקדמיה ובתעשייה. הפרס הוא הבעת הכרה בתפקידו המרכזי ביצירת טכנולוגיות המשפיעות באופן עמוק ונרחב על עידן המידע.

הביוגרפיה של פרופ’ אברהם למפל
אברהם למפל נולד ב-10 בפברואר 1936 בלבוב שבפולין. בנם של יצחק ופרידה למפל עלה לישראל בשנת 1948. בשנת 1963 סיים לימודי תואר ראשון ובשנת 1965 סיים לימודי תואר שני. השלים דוקטורט בפקולטה להנדסת חשמל בטכניון בשנת 1967. החל משנת 1977 כיהן כפרופסור בטכניון ופיתח עם פרופ’ יעקב זיו את האלגוריתם למפל-זיו לדחיסת מידע. בשנים 1981-1984 כיהן כראש הפקולטה למדעי המחשב בטכניון. בשנת 2007 זכה במדליית המינג של ארגון IEEE ובשנת 2010 קיבל את פרס רוטשילד. בשנת 1993 הצטרף לחברת היולט פאקרד בחיפה והקים את השלוחה הישראלית של מעבדות החברה בחיפה. רשם שמונה פטנטים בארצות הברית וקיבל תעודות הוקרה לרוב.

נספח: תיאור מתמטי של אלגוריתם LZ על פי www.cs.technion.ac.il/~itai/Courses/ds2/lectures/…/LempelZiv.doc

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

איתחול המילון: האותיות ב- ממופות לקודים לפי הסדר “הטבעי” שלהן (למשל ASCII).
נסמן את הקוד של מחרוזת ע”י , ואת המחרוזת המתאימה לקוד ע”י .

אלגוריתם דחיסה/פרישה:

levine3

אבחנה: בכל פעם שמגיעים לשורה 6 מילון הדחיסה = מילון הפרישה ולכן הפרישה מצליחה.
מה עושים כשנגמרים הקודים?
– אפשר למחוק את המילון ולהתחיל מחדש (מתאים לקובץ ארוך שמשתנה הדרגתית)
– אפשר להשאר עם המילון הקיים (מתאים לקובץ חדגוני)
– אפשר להגדיל את האורך של הקודים
– אפשר למחוק מחרוזות נדירות (מצריך איסוף סטטיסטיקות)
העיקר הוא שהפורש והדוחס עושים את אותו הדבר.
הערת מימוש: בכל שלב, הוא ה-של השלב הקודם. כלומר, כשמוסיפים מילה למילון, מוסיפים למעשה מילה קיימת בתוספת אות אחת. לכן נוכל לקודד את המילה החדשה במקום קבוע: האינדקס של המילה הקודמת + האות שהוספנו.
הערת יעילות: עבור קלטים קצרים, ייתכן מצב בו הפלט ארוך מהקלט ולכן הרווח שלילי, אך עבור קלטים ארוכים האלג’ הוכיח את עצמו כיעיל ונעשה בו שימוש נרחב (למשל compress של Unix).

מראי מקום
Ziv, J.. and Lempel, A. “A Universal Algorithm for Sequential Data Compression”,
IEEE Transactions on Information Theory, Vol. 23, pp. 337-343, 1977.
Ziv, J. and Lempel, A. “Compression of Individual Sequences via Variable-rate Coding”, IEEE Transactions on Information Theory, Vol. 24, pp. 530-536, 1978.
Welch, T, “A Technique for High Performance Data Compression”, Computer 17 (6), pp. 8-19, 1984.
S.M. Choudhary, A.S. Patel and S.J, Parmar, “Study of LZ77 and LZ78 Data Compression Techniques”, International Journal of Engineering Science and Innovative Technology (IJESIT), Volume 4, Issue 3, May 2015.
math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf

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

גרסאות של LZ

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

תגובות סגורות