Κωδικοποίηση Χούφμαν

Η κωδικοποίηση Χούφμαν είναι μια μέθοδος συμπίεσης που δημοσιεύτηκε το 1952 από τον Ντέιβιντ Χούφμαν και έμελλε να γίνει πασίγνωστη. Εκδοχές του αλγορίθμου Χούφμαν χρησιμοποιούνται στη μετάδοση αντιγράφων και στις απεικονίσεις εγγράφων. Το πρότυπο JPEG ενσωματώνει την κωδικοποίηση Χούφμαν ως τελικό βήμα στη διαδικασία συμπίεσης εικόνας.

Η κωδικοποίηση Χούφμαν αποδεικνύεται βέλτιστη για ένα δεδομένο κείμενο, αν και ο πίνακας κωδικοποίησης πρέπει να μεταδίδεται μαζί με τα δεδομένα.

Αρχές λειτουργίας

Ο αλγόριθμος Χούφμαν παράγει ένα κώδικα βασισμένο στην πιθανότητα εμφάνισης του κάθε συμβόλου σε ένα κείμενο. Σχεδόν σε όλα τα κείμενα, μερικά σύμβολα εμφανίζονται περισσότερες φορές από ότι άλλα. Προκαθορισμένες πιθανότητες εμφάνισης κάθε συμβόλου χρησιμοποιούνται για τη δημιουργία ενός πλήρους δυαδικού δέντρου από τη βάση προς τα επάνω (bottom-up). Αυτός ο τρόπος εγγυάται ότι τα σύμβολα που εμφανίζονται λιγότερο θα έχουν μακρύτερες σειρές δυαδικών ψηφίων. Στο δέντρο τα σύμβολα είναι φύλλα (τερματικοί κόμβοι - terminal nodes), οι διακλαδώσεις σημειώνονται με 0 ή 1 και η δυαδική αναπαράσταση της διαδρομής από τη ρίζα (root) μέχρι το σύμβολο είναι η συμπιεσμένη αναπαράστασή του ως σειρά δυαδικών ψηφίων.

Αλγόριθμος

1. Γίνεται καταγραφή συμβόλων και των αντίστοιχων πιθανοτήτων.
2. Δημιουργείται ένας κόμβος (node) για κάθε σύμβολο στον οποίο σημειώνεται η αντίστοιχη πιθανότητα.
3. Ακολουθεί εύρεση των δύο μικρότερων κόμβων οι οποίοι δεν έχουν κόμβο-πατέρα (parent node), και στη συνέχεια δημιουργείται ένας νέος διακλαδιζόμενος κόμβος στον οποίο σημειώνεται το άθροισμα των πιθανοτήτων που έχουν οι δύο κόμβοι-παιδιά (child nodes).
4. Επαναλαμβάνεται το 3ο βήμα μέχρι όλοι οι κόμβοι εκτός από τη ρίζα (root) να έχουν κόμβο-πατέρα.
5. Σημειώνεται με 0 και 1 κάθε ζεύγος ακμών. Η διαδρομή από τη ρίζα ως το δεδομένο φύλλο δείχνει τον κώδικα για το σύμβολο στο συγκεκριμένο φύλλο.

Βιβλιογραφία

• Lillian N. Cassel, Richard H. Austing, Computer Networks and Open Systems: An Application Development, Jones & Bartlett Publishers, ISBN 0-7637-1122-5

Εξωτερικοί σύνδεσμοι

• D. Huffman, A Method for the Construction of Minimum-Redundancy Codes

Το άρθρο προέρχεται από το wiki.teilar.net