תמליל > דחיסה

בדחיסה של תמליל, בניגוד לדחיסה של מדיות אחרות, איננו רוצים לאבד את המידע עצמו או חלקים ממנו. אנו מעוניינים לדחוס קובץ תמליל על-מנת שהוא יתפוס מקום קטן יותר בזיכרון, וכן כדי להעבירו בקלות ברשת. שתי השיטות הבאות משתמשות בשני אלגוריתמים בסיסיים של דחיסת נתונים, שמייצרים יחסי-דחיסה טובים ורצים בזמן לינארי.
השיטה הראשונה הוצעה על-ידי הופמן (Huffman) בשנת 1951. שיטה זו היא שיטת קידוד סטטיסטי, שנקבע על-פי שכיחויות הסמלים.
על-פי שיטה זו נבנה קוד מיוחד הניתן לקידוד אופטימלי, תוך מתן חשיבות לקריטריוני הדחיסה. שיטת הופמן מספקת קידוד סטטיסטי אופטימלי. לשיטה זו קיימת גירסה דינמית, שבה ספירת הסמלים מתבצעת בזמן הקידוד. הפקודה "compact" במערכת הפעלה UNIX מיישמת גירסה זו.
השיטה השנייה הומצאה על-ידי למפל וזיו (Lempel & Ziv) בשנת 1977. שיטה זו משתמשת בקידוד מקטעים. המקטעים נשמרים במילון, שנבנה במהלך תהליך הדחיסה. כאשר נתקלים תוך כדי סריקת התמליל המקורי במופע של מקטע שכבר נמצא במילון, מקטע זה מוחלף באינדקס שלו במילון. במודל שבו מקטעים מתוך התמליל מוחלפים במצביעים למופעים הקודמים של מקטע זה, ניתן להוכיח ששיטת הדחיסה של למפל-זיו היא אופטימלית בצורה אסימפטוטית עבור תמלילים מספיק ארוכים המספקים תנאים טובים לחלוקה הסתברותית של סמלים. המילון מהווה מרכיב מרכזי של האלגוריתם. בנוסף, שימוש בטכניקת גיבוב (Hashing) מייעל את יישום השיטה. וולך (Welch) שיפר טכניקה זו בשנת 1984, והיא מיושמת בפקודה "compress" במערכת הפעלה UNIX.



מבוא לדחיסה של תמליל

למידע נוסף על דחיסת תמליל

שאלון ידע - תמליל
  אודות האתר - מפת האתר - עמוד הבית  
© כל הזכויות שמורות למערכת המידע איתן