από τον Nuclear/ the Lab
Η ιδέα πίσω από τη συμπίεση Huffman είναι απλή, από μία σειρά από Bytes να βρούμε αυτά που επαναλαμβάνονται πιο συχνά και να τα κωδικοποιήσουμε με λιγότερα bits από ότι άλλα που δεν είναι τόσο συχνά.
Έχουμε π.χ. μία σειρά από bytes (χαρακτήρες για παράδειγμα): "ΑΥΤΟ ΕΙΝΑΙ ΕΝΑ ΤΕΣΤ"(εικ. 1) αυτή η σειρά πιάνει αρχικά 19 χαρακτήρες Χ 1 byte ο καθένας, 19 Bytes = 152 bits ...
|
|
Πρώτα κάνουμε έναν πίνακα με τους χαρακτήρες που υπάρχουν και πόσες φορές υπάρχει ο καθένας (εικ. 2) |
Μετά φτιάχνουμε το Huffman tree ως εξής:
|
Παίρνουμε τα γράμματα και τα τοποθετούμε με την σειρά εμφάνισης. Παίρνουμε τα 2 τελευτέα (μικρότερη συχνότητα) και τα τοποθετούμε κατω απο ενα node που δημιουργούμε, αυτο το node εχει κάποιο βάρος (weight) το οποίο ειναι το άρθροισμα των συχνοτήτων των 2 χαρακτήρων που έχει για children (δες εικ. 3) Ανάλογα με το βάρος του node, το τοποθετούμε στή σειρά που του αντιστοιχεί ανάμεσα στους υπόληπους χαρακτήρες ... Ξαναπαίρνουμε τα 2 τελευταία (Σημ. ανάμεσα στα τελευταία δεν αποκλείετε να είναι και το node που δημιουργήσαμε πρίν) και τα κάνουμε children ενός νέου node, στο οποίο αναθέτουμε πάλι το ανάλογο βαρος, και το τοποθετούμε στη σειρά ανάλογα με το βάρος του... Eπαναλαμβάνουμε αυτή τη διαδικασία μέχρι να μείνουμε με ένα μόνο node το οποίο θα είναι η κορυφή (root) του δέντρου μας (εικ. 4) |
|
Αφού κάνουμε το δέντρο βρίσκουμε τον κωδικό με τον οποίο θα κωδικοποιήσουμε κάθε χαρακτήρα ως εξής:
|
Ακολουθούμε το δέντρο (εικ. 4) και βλέπουμε τη διαδρομή που ακολουθήσαμε για να φτάσουμε σε κάθε γράμμα, όπως είπα παραπάνω τα αριστερά φύλλα είναι 0 και τα δεξιά 1, έτσι για να φτάσουμε στο Α η πορεία είναι "αριστερό->αριστερό" (00) έτσι ο κωδικός του Α είναι 00 .. στο Τ είναι "Δεξί->Αριστερό->Δεξί" (1->0->1) άρα ο κωδικός του Τ είναι 101, στο Ε "1->1->1" άρα ο κωδικός είναι 111. Έτσι αφού είχαμε τοποθετήσει τα πιο συχνά στην κορυφή, βλέπουμε ότι τα πιο συχνά γράμματα έχουν μικρότερο κωδικό. (εικ. 4) |
|
Τέλος κωδικοποιούμε την σειρά από χαρακτήρες που είχαμε με τον αντίστοιχο κωδικό και βγαίνει ο κωδικός της εικόνας 6 ο οποίος είναι 59bits δηλαδή έχουμε συμπίεση 59/152 περίπου 72% συμπίεση! Βέβαια τέλος πρέπει να προσθέσουμε στην αρχή του αρχείου τον πίνακα των συχνοτήτων για την αποσυμπίεση... |
|
Διαβάζουμε τον πίνακα με τις συχνότητες απο την αρχή του αρχείου και ξαναφτιάχνουμε το δέντρο, μετά διαβάζοντας bit προς bit τα συμπιεσμένα δεδομένα ακολουθούμε το δέντρο και αντικαθιστούμε τους κωδικούς με τους χαρακτήρες που αντιστοιχούν ...
Ελπίζω να βοήθησα στιν κατανόηση του αλγοριθμου συμπίεσης Huffman. Για διορθόσεις, σχόλια ή και για ότι αλλο μπορείτε να επικοινονήσετε μαζί μου στο email: nuclear@siggraph.org