Article on other languages:
- ترميز_هوفمان
- Huffmanovo_kódování
- Shannon-Fano-Kodierung#Huffman-Code
- Huffman_coding
- Codificación_Huffman
- Huffmani_kodeerimine
- کدگذاری_هافمن
- Huffmanin_koodaus
- Codage_de_Huffman
- קוד_הופמן
- Codifica_di_Huffman
- ハフマン符号
- 허프만_부호화
- Huffmancodering
- Kodowanie_Huffmana
- Codificação_de_Huffman
- Алгоритм_Хаффмана
- Huffmankodning
- รหัสฮัฟแมน_และ_รหัสแชนนอน-ฟาโน
- Huffman_kodu
- Mã_Huffman
- 霍夫曼编码
 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
Η κωδικοποίηση Huffman είναι μια μέθοδος συμπίεσης που δημοσιεύτηκε το 1952[1] από τον David Huffman και έμελλε να γίνει πασίγνωστη. Εκδοχές του αλγορίθμου Huffman χρησιμοποιούνται στη μετάδοση αντιγράφων και στις απεικονίσεις εγγράφων. Το πρότυπο JPEG ενσωματώνει την κωδικοποίηση Huffman ως τελικό βήμα στη διαδικασία συμπίεσης εικόνας.
Η κωδικοποίηση Huffman είναι αποδεικνύεται βέλτιστη για ένα δεδομένο κείμενο, αν και ο πίνακας κωδικοποίησης πρέπει να μεταδίδεται μαζί με τα δεδομένα.
Πίνακας περιεχομένων |
Αρχές λειτουργίας
Ο αλγόριθμος Huffman παράγει ένα κώδικα βασισμένο στην πιθανότητα εμφάνισης του κάθε συμβόλου σε ένα κείμενο. Σχεδόν σε όλα τα κείμενα, μερικά σύμβολα εμφανίζονται περισσότερες φορές από ότι άλλα. Προκαθορισμένες πιθανότητες εμφάνισης κάθε συμβόλου χρησιμοποιούνται για τη δημιουργία ενός δυαδικού δέντρου από τη βάση προς τα επάνω (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 0763711225
Εξωτερικοί σύνδεσμοι
D. Huffman, A Method for the Construction of Minimum-Redundancy Codes
Το άρθρο προέρχεται από το wiki.teilar.net
