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

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

הוצג ב-1977 ונקרא גם Sliding Window. הרעיון המרכזי הוא להחליף מופעים חוזרים של נתונים בהפניה לעותק קודם שלהם. כל יחידת קידוד מורכבת מההתאמה הארוכה ביותר שנמצאה עד כה בתוספת תו אחד.

מוגדר מילון בגודל קבוע וחוצץ (חלון) באורך קבוע. החלון נע על המחרוזת בעזרת סמן. עבור כל מיקום נשמרים שלושה פרטים: מיקום ההתאמה במילון, אורך ההתאמה, והתו הבא מעבר להתאמה. אחרי שמירת הפרט, החלון מתקדם באורך ההתאמה ועוד אחד. לדוגמה: עם מילון ABCD והקידוד (2,6,E) מתקבל הפלט ABCDCDCDCDE. שיטה זו מהווה בסיס לשיפורים רבים.

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

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

LZSS היא נגזרת חשובה שפותחה ב-1982 ונמצאת בשימוש בארכיונים כמו PKZip ו-RAR. קיימות גם משפחות נוספות כמו LZR, LZB ו-LZH.

הוצג ב-1978 ונקרא גם Tree Based Algorithm. כאן הדחיסה מתבצעת על ידי מילון שבו כל כניסה שומרת צמד (אינדקס, תו). האינדקס מפנה לכניסה קודמת והמחרוזת נבנית בצירוף התו. המילון גדל תוך כדי קריאה; כאשר הוא מלא לא מוסיפים כניסות חדשות. למימוש יעיל משתמשים במבני עץ כמו Trie או עץ סיומות.

גרסאות של LZ78 ממומשות בכלים שונים. לדוגמה, ב-Zip ו-Unix Compress המימושים כוללים LZH, LZW ו-LZC.

נוצרו מגוון נגזרות, מהבולטות שבהן: LZW, LZC, LZMW ועוד.

LZW פותח על ידי למפל, זיו וטרי ולץ' ופורסם ב-1984. הוא מבוסס על LZ78, קל ליישום ומשפר ביצועים. LZW הפך נפוץ ובסיסי בכלים פופולריים, לדוגמה בפורמט GIF.

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

הרעיון הוא למצוא דברים שחוזרים על עצמם ולהפנות אליהם במקום לכתוב שוב. יש "חלון", אזור קטן שנע על הטקסט. הקידוד שומר מיקום, אורך והתו הבא. החלון מתקדם לפי האורך ועוד תו אחד. דוגמה קצרה: עם מילון ABCD והקוד (2,6,E) מקבלים ABCDCDCDCDE.

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

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

ב-LZ78 שומרים מילון של כניסות. כל כניסה מחזיקה מספר ותו. המחרוזת נבנית בעזרת חיבור כניסות קודמות. למימוש משתמשים בעצי מילון פשוטים.

גרסאות מפורסמות של המשפחה הזאת הן LZW ו-LZH. LZW נוצר ב-1984 ועוזר לדחוס תמונות בפורמט GIF.