"Institute of Educational Policy" Books

Search

Go
Show

Συμπίεση LZW

Πολλά αρχεία, ιδιαίτερα αρχεία χαρακτήρων, έχουν συμβολοσειρές που επαναλαμβάνονται συχνά, για παράδειγμα το άρθρο «τον». Για την αναπαράσταση της λέξης αυτής με χρήση του κώδικα ASCII χρειάζονται 5 bytes, αν συμπεριλάβουμε τα κενά πριν και μετά τη λέξη. Αν αντιστοιχίσουμε έναν αριθμό σε ολόκληρη τη λέξη (π.χ. το 256 που έχει 2 bytes μήκος), τότε με 2 bytes αντικαθιστούμε παντού τα 5 bytes του άρθρου «τον».

Αυτή είναι η προσέγγιση που ακολουθείται στον αλγόριθμο LZW, ο οποίος παρουσιάστηκε από τους J. Ziv και A. Lempel το 1977, και τροποποιήθηκε από τον Τ. Welch το 1984.

Ο αλγόριθμος ξεκινά φτιάχνοντας ένα λεξικό όλων των ακολουθιών χαρακτήρων (συμβολοσειρών) που εμφανίζονται στο υπό συμπίεση αρχείο. Στο λεξικό αυτό, που ονομάζεται και πίνακας αναφορών, αποθηκεύεται για κάθε συμβολοσειρά ο αριθμός των εμφανίσεων της και δίπλα ένας μοναδικός κωδικός που αντιστοιχεί σε αυτή. Στη φάση της συμπίεσης αντικαθιστούμε κάθε συμβολοσειρά με τον κωδικό της, ο οποίος έχει πολύ μικρότερο μέγεθος από αυτή. Επιπλέον, στο τέλος προσθέτουμε και το λεξικό, ώστε να μπορεί να γίνει η αποσυμπίεση. Για την αποσυμπίεση γίνεται κατ' αρχήν ανάγνωση του λεξικού και αντικατάσταση των κωδικών με τις αντίστοιχες αρχικές συμβολοσειρές. Ο αλγόριθμος LZW χρησιμοποιείται με επιτυχία για αρχεία με μεγάλη κανονικότητα και συχνές επαναλήψεις μεγάλων συμβολοσειρών.

Τα αρχεία τύπου «zip» δημιουργούνται με συμπίεση βασισμένη στον αλγόριθμο LZW.