Προτεινόμενοι Σύνδεσμοι:    greece   -   greece hotels   -   ειδησεις   -   greece news   -   ταβλι στο internet   -   livescore   -   νέα
 easypedia

Easypedia.gr
Ελλάδα
Αρχαία Ελλάδα
Ελληνες
Πρωθυπουργοί
Οικονομία
Γεωγραφία
Ιστορία
Γλώσσα
Πληθυσμός
Μυθολογία
Πολιτισμός & Τέχνες
Ζωγραφική
Θέατρο
Κινηματογράφος
Λογοτεχνία
Μουσική
Αρχιτεκτονική
Γλυπτική
Αθλητισμός
Μυθολογία
Θρησκεία
Θετικές & Φυσικές Επιστήμες
Ανθρωπολογία
Αστρονομία
Βιολογία
Γεωλογία
Επιστήμη υπολογιστών
Μαθηματικά
Τεχνολογία
Φυσική
Χημεία
Ιατρική
Φιλοσοφία & Κοινωνικ. Επιστήμες
Αρχαιολογία
Γλωσσολογία
Οικονομικά
Φιλοσοφία
Ψυχολογία
Γεωγραφία
Ασία
Αφρική
Ευρώπη
Πόλεις
Χώρες
Θάλασσες
Ιστορία
Ελληνική Ιστορία
Αρχαία Ιστορία
Βυζάντιο
Ευρωπαϊκή Ιστορία
Πόλεμοι
Ρωμαϊκή Αυτοκρατορία
Σύγχρονη Ιστορία
 

Κωδικοποίηση Huffman

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

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

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

Πίνακας περιεχομένων

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

Ο αλγόριθμος Huffman παράγει ένα κώδικα βασισμένο στην πιθανότητα εμφάνισης του κάθε συμβόλου σε ένα κείμενο. Σχεδόν σε όλα τα κείμενα, μερικά σύμβολα εμφανίζονται περισσότερες φορές από ότι άλλα. Προκαθορισμένες πιθανότητες εμφάνισης κάθε συμβόλου χρησιμοποιούνται για τη δημιουργία ενός δυαδικού δέντρου από τη βάση προς τα επάνω (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 0763711225

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

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

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