Κωδικοποίηση Χούφμαν
Η κωδικοποίηση Χούφμαν είναι μια μέθοδος συμπίεσης που δημοσιεύτηκε το 1952[1] από τον Ντέιβιντ Χούφμαν και έμελλε να γίνει πασίγνωστη. Εκδοχές του αλγορίθμου Χούφμαν χρησιμοποιούνται στη μετάδοση αντιγράφων και στις απεικονίσεις εγγράφων. Το πρότυπο JPEG ενσωματώνει την κωδικοποίηση Χούφμαν ως τελικό βήμα στη διαδικασία συμπίεσης εικόνας.
Η κωδικοποίηση Χούφμαν αποδεικνύεται βέλτιστη για ένα δεδομένο κείμενο, αν και ο πίνακας κωδικοποίησης πρέπει να μεταδίδεται μαζί με τα δεδομένα.
Αρχές λειτουργίας
[Επεξεργασία | επεξεργασία κώδικα]Ο αλγόριθμος Χούφμαν παράγει ένα κώδικα βασισμένο στην πιθανότητα εμφάνισης του κάθε συμβόλου σε ένα κείμενο. Σχεδόν σε όλα τα κείμενα, μερικά σύμβολα εμφανίζονται περισσότερες φορές από ότι άλλα. Προκαθορισμένες πιθανότητες εμφάνισης κάθε συμβόλου χρησιμοποιούνται για τη δημιουργία ενός πλήρους δυαδικού δέντρου από τη βάση προς τα επάνω (bottom-up). Αυτός ο τρόπος εγγυάται ότι τα σύμβολα που εμφανίζονται λιγότερο θα έχουν μακρύτερες σειρές δυαδικών ψηφίων. Στο δέντρο τα σύμβολα είναι φύλλα (τερματικοί κόμβοι - terminal nodes), οι διακλαδώσεις σημειώνονται με 0 ή 1 και η δυαδική αναπαράσταση της διαδρομής από τη ρίζα (root) μέχρι το σύμβολο είναι η συμπιεσμένη αναπαράστασή του ως σειρά δυαδικών ψηφίων.
Αλγόριθμος
[Επεξεργασία | επεξεργασία κώδικα]- Γίνεται καταγραφή συμβόλων και των αντίστοιχων πιθανοτήτων.
- Δημιουργείται ένας κόμβος (node) για κάθε σύμβολο στον οποίο σημειώνεται η αντίστοιχη πιθανότητα.
- Ακολουθεί εύρεση των δύο μικρότερων κόμβων οι οποίοι δεν έχουν κόμβο-πατέρα (parent node), και στη συνέχεια δημιουργείται ένας νέος διακλαδιζόμενος κόμβος στον οποίο σημειώνεται το άθροισμα των πιθανοτήτων που έχουν οι δύο κόμβοι-παιδιά (child nodes).
- Επαναλαμβάνεται το 3ο βήμα μέχρι όλοι οι κόμβοι εκτός από τη ρίζα (root) να έχουν κόμβο-πατέρα.
- Σημειώνεται με 0 και 1 κάθε ζεύγος ακμών. Η διαδρομή από τη ρίζα ως το δεδομένο φύλλο δείχνει τον κώδικα για το σύμβολο στο συγκεκριμένο φύλλο.
Παραπομπές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ "A Method for the Construction of Minimum-Redundancy Codes", βλ. εξωτερικούς συνδέσμους
Βιβλιογραφία
[Επεξεργασία | επεξεργασία κώδικα]- Lillian N. Cassel, Richard H. Austing, Computer Networks and Open Systems: An Application Development, Jones & Bartlett Publishers, ISBN 0-7637-1122-5
Εξωτερικοί σύνδεσμοι
[Επεξεργασία | επεξεργασία κώδικα]
Το άρθρο προέρχεται από το wiki.teilar.net[νεκρός σύνδεσμος]