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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

LZ77[עריכת קוד מקור | עריכה]

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

אלגוריתם[עריכת קוד מקור | עריכה]

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

סיבוכיות LZ77[עריכת קוד מקור | עריכה]

הנטל החישובי מצוי בשלב בו המקודד מחשב את ההתאמה ובונה את המילון. מימוש ברוטלי לכל התאמה mO(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 פותח על ידי אברהם למפל, יעקב זיו וטרי ולך. הוא פורסם על ידי ולך בשנת 1984 ומתבסס על האלגוריתם LZ78 שפותח על ידי למפל וזיו בשנת 1978. האלגוריתם פשוט למימוש ומספק שיפור משמעותי בביצועים מקודמו. גרסה זו הפכה פופולרית והיא עומדת בבסיס רבות מהדחיסות המסחריות כיום‏[3].

הערות שוליים[עריכת קוד מקור | עריכה]

  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. Information Theory, IEEE Transactions on, 23(3), 337-343.
  3. ^ Welch, T. A. (1984). A technique for high-performance data compression. Computer, 17(6), 8-19.