אלגוריתם למפל-זיו – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←LZW: מחיקת הפניה עצמית |
תיקון קישור לפירושונים |
||
שורה 1:
'''אלגוריתם למפל-זיו''' הוא [[אלגוריתם]] ל[[דחיסת נתונים]] שפותח על ידי [[אברהם למפל]] ו[[יעקב זיו (מדען)|יעקב זיו]] מ[[הטכניון]]. במשך השנים התפתחו אלגוריתמים שונים על בסיס האלגוריתם למפל-זיו אשר שיפרו את הביצועים בצורה משמעותית והתגבשה משפחה של אלגוריתמים. הדחיסה היא מסוג [[דחיסת נתונים|דחיסה משמרת מידע]], המאפשרת שיחזור המידע הדחוס במלואו (ללא עיוות). האלגוריתם מתבסס על חלוקת המחרוזת המקודדת לתת-מחרוזות הנקראות פסקאות בתהליך המכונה פיסוק. כל פסקה מותאמת למחרוזת מעל א"ב סופי ונבנה מילון בתהליך דינמי. האלגוריתם הוא אוניברסלי, הדחיסה היא אסימפטוטית אופטימלית ולא נדרש ידע קודם של התוכן הנדחס{{הערה|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). A universal algorithm for sequential data compression. Information Theory, IEEE Transactions on, 23(3), 337-343.}}.
| |||