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

'''אלגוריתם למפל-זיו''' הוא [[אלגוריתם]] ל[[דחיסת נתונים]] שפותח על ידי [[אברהם למפל]] ו[[יעקב זיו (מדען)|יעקב זיו]] מ[[הטכניון]]. במשך השנים התפתחו אלגוריתמים שונים על בסיס אלגוריתם למפל-זיו, ואלו שיפרו את ביצועי דחיסת הנתונים בצורה משמעותית. הדחיסה היא מסוג [[דחיסת נתונים|דחיסה משמרת מידע]], המאפשרת את שחזור המידע הדחוס במלואו, ללא עיוות. האלגוריתם מתבסס על חלוקת המחרוזת המקודדת לתת-מחרוזות הנקראות פסקאות בתהליך המכונה פיסוק. כל פסקה מותאמת למחרוזת מעל אלפבית סופי ונבנה מילון בתהליך דינמי. האלגוריתם הוא אוניברסלי, הדחיסה היא אסימפטוטית אופטימלית, ואין נדרש ידע קודם של התוכן הנדחס{{הערה|Wyner, A. D., & Ziv, J. (1994). The sliding-window Lempel-Ziv algorithm is asymptotically optimal. Proceedings of the IEEE, 82(6), 872-877.}}. בריאיון עם פרופ' זיו הוא נתן כהמחשה לאלגוריתם את [[תפילת אבינו מלכנו]] המופיעה ב[[מחזור תפילה|מחזורי התפילה היהודיים]], שבה המילים "אבינו מלכנו" מופיעות רק במשפט הראשון, ואילו ביתר המשפטים מסתפקים באזכור והפניה אליהן.

==LZ77==
האלגוריתם הוצג על ידי למפל וזיו בעבודתם בשנת [[1977]], מכונה גם Sliding Window LZ. האלגוריתם משיג דחיסה על ידי החלפה של מופעים חוזרים של מידע, במצביע לעותק יחיד של אותה פיסת מידע, במופע הראשון שלו בקלט הרצפים הלא דחוס. הרעיון בבסיס הקידוד הוא כי כל מילה בקידוד היא המילה הארוכה ביותר שנראתה עד לאותה נקודת זמן, בתוספת של אות אחת{{הערה|Ziv, J., & Lempel, A. (1977). [https://www2.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1977_universal_algorithm.pdf A universal algorithm for sequential data compression]. IEEE Transactions on Information Theory, 23(3), 337-343.}}.

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

===סיבוכיות LZ77===
הנטל החישובי מצוי בשלב בו המקודד מחשב את ההתאמה ובונה את המילון. מימוש ברוטלי לכל התאמה m<math>O(m2)</math> כאשר 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. האלגוריתם משיג דחיסה על ידי החלפת מידע שחוזר על עצמו במצביע במילון למופע יחיד של אותו מידע.

===אלגוריתם===
כל כניסה במילון מחזיקה את הצמד אינדקס ותו <math>Dictionary[...] = (index, character)</math> כאשר אינדקס הוא אינדקס של כניסה קודמת במילון, והתו ישורשר לתו בכניסה אליה מצביע האינדקס. לדוגמה עבור המילון D ו- "abc" מחרוזת הקלט <math>D[k] = (j, 'c'), D[j] = (i, 'b'), D[i] = (0, 'a')</math> כאשר אינדקס 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|מאה ה-21]], כדוגמת פורמט [[GIF]]{{הערה|Welch, T. A. (1984). A technique for high-performance data compression. Computer, 17(6), 8-19.}}.

==לקריאה נוספת==
* {{חמי-שולמן|הפרק "בור סוד שאינו מאבד טיפה", עמ' 128–129}}

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{חדשנות|אלגוריתם LZ : פשוט לשלוח קבצים|6}}

==הערות שוליים==
{{הערות שוליים}}

{{מיון רגיל:למפל זיו}}
[[קטגוריה:אלגוריתמים]]
[[קטגוריה:דחיסת נתונים]]
[[קטגוריה:ישראל: המצאות]]