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

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

LZ77

האלגוריתם הוצג על ידי למפל וזיו בעבודתם בשנת 1977, מכונה גם Sliding Window LZ. האלגוריתם משיג דחיסה על ידי החלפה של מופעים חוזרים של מידע, במצביע לעותק יחיד של אותה פיסת מידע, במופע הראשון שלו בקלט הרצפים הלא דחוס. הרעיון בבסיס הקידוד הוא כי כל מילה בקידוד היא המילה הארוכה ביותר שנראתה עד לאותה נקודת זמן, בתוספת של אות אחת^[2].

אלגוריתם

בדחיסה מוגדר מילון בגודל קבוע וחוצץ (Buffer) באורך קבוע. החוצץ, שנקרא גם "חלון", מתקדם על המחרוזת בעזרת סמן (cursor) ונשמרים שלושה נתונים – מיקום ההתאמה הארוכה ביותר שמתחילה במילון ביחס לסמן, האורך של ההתאמה הארוכה ביותר, והתו הבא בחוצץ מעבר להתאמה הארוכה שנמצאה. בתום שמירת הנתונים, החלון מקודם באורך ההתאמה שנמצאה ועוד 1. בצורה זו, החלון נע על המחרוזת ומכאן שמו הנוסף של האלגוריתם Sliding Window. בפרישה, הפורש מחזיק את אותו המילון כמו הדוחס. עוברים על הקידודים, כך שכל קידוד שנפרש משורשר לסוף המחרוזת שכבר נפרשה.[2] לדוגמה: עבור המילון ABCD, והקידוד (2,6,E) הפלט יהיה ABCDCDCDCDE כאשר 2 הוא המיקום, 6 הוא האורך ו- E הוא התו הבא. אלגוריתם זה הוא בסיס להתפתחותם של אלגוריתמים יעילים יותר מאותה משפחה.

סיבוכיות LZ77

הנטל החישובי מצוי בשלב בו המקודד מחשב את ההתאמה ובונה את המילון. מימוש ברוטלי לכל התאמה m $O(m2)$ כאשר m הוא גודל החוצץ. מקובל השימוש בטבלת גיבוב לביצוע ההתאמות. הקטנת החוצץ תגרום להקטנת הסיבוכיות אך ייתכן ויפגע קצב הדחיסה.

מימושים

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

אלגוריתם LZSS משפר את אלגוריתם LZ77 על ידי שימוש בדגל של ביט אחד לציון האם חתיכת המידע הבאה צריכה להיות מקודדת כתווים או כצמד אורך-מרחק ומקודדים לתווים אם הצמד אורך-מרחק ארוך יותר.

בפורמט PalmDoc הצמד אורך-מרחק מקודד על ידי רצף של שני בתים. מתוך 16 הביטים הבונים את שני הבתים, 11 ביטים משמשים לקידוד המרחק, 3 ביטים משמשים לקידוד האורך, ושני הביטים הנותרים מציינים למפענח את תחילתם של שני הבתים אותם צריך לפענח. במשחקים רבים של Electronic Arts הגודל בבתים של הצמד אורך-מרחק נשמר בתוך הבית הראשון המכיל את אורך-מרחק בעצמם, כתלות אם הבית הראשון מתחיל ב 0, 10, 110 או 111. אורך הצמד אורך-מרחק יכול להיות בין 1 ל-4 בתים.

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

גרסאות של LZ77

Lempel–Ziv–Storer–Szymanski LZSS הוא נגזרת של אלגוריתם LZ77. הוא נוצר בשנת 1982 על ידי ג'יימס סטורר ותומס זימנסקי. ההבדל העיקרי בין LZSS ו-LZ77 הוא שבאחרון, ההפניות במילון יכולות להיות לעיתים ארוכות יותר מהקטע המקורי טרם הקידוד. באלגוריתם LZSS אם הקטע המקודד הוא ארוך יותר מקטע המקור, אזי נשמר קטע המקור. בנוסף, LZSS משתמש בדגל של ביט אחד לייצוג האם האיבר הבא שצריך לפענח הוא קוד המקור עצמו (בתים) או הצמד אורך-מרחק. ארכיונים פופולריים כמו PKZip, ARJ, RAR, ZOO, LHarc משתמשים ב LZSS ולא ב LZ77.

גרסאות נוספות הן LZR, LZB, LZH .

LZ78

הוצג על ידי למפל וזיו בשנת 1978 ומכונה גם בשם Tree Based Algorithm. האלגוריתם משיג דחיסה על ידי החלפת מידע שחוזר על עצמו במצביע במילון למופע יחיד של אותו מידע.

אלגוריתם

כל כניסה במילון מחזיקה את הצמד אינדקס ותו $Dictionary[...]=(index,character)$ כאשר אינדקס הוא אינדקס של כניסה קודמת במילון, והתו ישורשר לתו בכניסה אליה מצביע האינדקס. לדוגמה עבור המילון D ו- "abc" מחרוזת הקלט $D[k]=(j,'c'),D[j]=(i,'b'),D[i]=(0,'a')$ כאשר אינדקס 0 מציין את התו הראשון של המחרוזת. האלגוריתם מאתחל את האינדקס האחרון המתאים (last matching index) ב-0 והאינדקס הפנוי הבא (next available index) ב-1. עבור כל תו במחרוזת הקלט, המילון מחפש התאמה של הצמד {תו, אינדקס אחרון מתאים}. אם נמצאה התאמה בכניסה מסוימת במילון, אזי האינדקס האחרון המתאים מקבל את ערך האינדקס של הכניסה שנמצאה. אם לא נמצאה כניסה מתאימה, נוצרת כניסה חדשה במילון {תו, הכניסה האחרונה המתאימה} = [הכניסה הבאה הפנויה]D כאשר הכניסה האחרונה המתאימה מאופסת, והכניסה הבאה הפנויה מקודמת. כאשר המילון מלא לא ניתן להוסיף כניסות חדשות. כאשר מגיעים לסוף המחרוזת המקודדת, האלגוריתם מציין אינדקס אחרון מתאים. המחרוזות מאוחסנות במילון בסדר הפוך והמפענח יודע להתמודד עם הפרישה. למימוש יעיל של האלגוריתם משתמשים במעבר על עץ סיפות (עץ סיומות, Suffix Tree) או עץ Trie. העץ ישמש כמילון השומר את המילים המקודדות, כאשר מבנה העץ הוא היררכי.

מימושים

ב- Zip, Unzip ממומש האלגוריתם LZH, ב- Unix Compress ממומש LZW ו- LZC

גרסאות של LZ78

LZW, LZC, LZT, LZMW, LZJ, LZFG.

LZW

האלגוריתם LZW או Lempel-Ziv-Welch פותח על ידי אברהם למפל, יעקב זיו וטרי ולץ' (Terry Welch). הוא פורסם על ידי ולץ' בשנת 1984 ומתבסס על האלגוריתם LZ78 שפותח על ידי למפל וזיו בשנת 1978. האלגוריתם פשוט למימוש ומספק שיפור משמעותי בביצועים מקודמו. גרסה זו הפכה פופולרית והיא עומדת בבסיס רבות מכלי הדחיסה המסחריים בהם נעשה שימוש במאה ה-21, כדוגמת פורמט GIF^[3].

לקריאה נוספת

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

קישורים חיצוניים

מדיה וקבצים בנושא אלגוריתם למפל-זיו בוויקישיתוף

אלגוריתם LZ : פשוט לשלוח קבצים, באתר "חדשנות ישראלית"

הערות שוליים

^ Wyner, A. D., & Ziv, J. (1994). The sliding-window Lempel-Ziv algorithm is asymptotically optimal. Proceedings of the IEEE, 82(6), 872-877.
^ Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3), 337-343.
^ Welch, T. A. (1984). A technique for high-performance data compression. Computer, 17(6), 8-19.

[1] Wyner, A. D., & Ziv, J. (1994). The sliding-window Lempel-Ziv algorithm is asymptotically optimal. Proceedings of the IEEE, 82(6), 872-877.

[2] Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3), 337-343.

[3] Welch, T. A. (1984). A technique for high-performance data compression. Computer, 17(6), 8-19.

[1]

[2]

[3]