( Huffman Code )
Γλώσσα προγραμματισμού : C
Εργασία στο μάθημα : Προγραμματισμός Συστημάτων
Υπεύθυνος Καθηγητής : Κωνσταντίνος Μαργαρίτης
Φοιτητής : Βασίλης Στεφανίδης
Το αντικείμενο της εργασίας αυτής είναι η συμπίεση ενός αρχείου κειμένου με σκοπό την εξοικονόμιση χώρου. Για το σκοπό αυτόν χρησιμοποιήσαμε τον κώδικα Huffman. Στην αρχή παρατίθεται μια βήμα προς βήμα παρουσίαση του κώδικα συμπίεσης με γραφικές απεικονίσεις και με πίνακες , καθώς και με το αντίστοιχο τμήμα του προγράμματος που είναι υπεύθυνο για την πραγματοποίηση κάθε βήματος. Στο τέλος παραθέτουμε το πλήρες πρόγραμμα.
Ξεκινόντας το πρόγραμμα, λαμβάνει ένα κείμενο από το αρχείο Input.txt και αφού επεξεργασθεί τα δεδομένα, τα συμπιέζει. Η γλώσσα προγραμματισμού που χρησιμοποιήθηκε είναι η C. Το αρχείο που χρησιμοποιούμε για την παρουσίαση αυτού του προβλήματος, περιέχει τη φράση : "THIS IS A GOOD EXAMPLE TO PRESENT HUFFMANs COMPRESS CODE"
Στον πίνακα που ακολουθεί δημιουργείται ένας κατάλογος συχνοτήτων εμφάνισης των γραμμάτων μέσα στο κείμενο. Το κομμάτι του προγράμματος το οποίο είναι υπεύθυνο για την κατασκευή του πίνακα αυτού είναι το :
(τμήμα κώδικα προγράμματος Link)
ΣΥΧΝΟΤΗΤΕΣ
A | 3 | G | 1 | M | 3 | S | 6 | Y | ||||||
B | H | 2 | N | 2 | T | 3 | Z | |||||||
C | 2 | I | 2 | O | 5 | U | 1 | sp | 9 | |||||
D | 2 | J | P | 3 | V | |||||||||
E | 6 | K | Q | W | ||||||||||
F | 2 | L | 1 | R | 2 | X | 1 |
Έτσι δημιουργούνται οι εξής συχνότητες ( space=9, A=3, C=2,D=2, E=6, F=2, G =1, H=2, I=2, L =1, M=3, N=2, O=5, P=3, R=2, S=6, T=3, U =1, X=1, )
Έπειτα παίρνουμε τις δυο πιο μικρές τιμές συχνοτήτων (τις L= 1, U = 1) και κατασκευάζουμε ένα δυαδικό δέντρο με κορυφές τις οποίες ονομάζουμε ανάλογα με το γράμμα που αντιπροσωπεύουν :
Το τμήμα του προγράμματος που είναι υπεύθυνο γι' αυτή τη σχεδίαση του δυαδικού δένδρου είναι :
(τμήμα κώδικα προγράμματος Link)
Έπειτα αλλάζουμε αυτές τις συχνότητες, με το άθροισμά τους, λαμβάνοντας μια καινούρια σειρά συχνοτήτων, (sp=9, A=3, C=2,D=2, E=6, F=2, G =1, H=2, I=2, M=3, N=2, O=5, P=3, R=2, S=6, T=3, X=1, 27=L&U=2 ) και ξανά λαμβάνουμε τις δυό μικρότερες συχνότητες (τις G= 1, X = 1)και φτιάχνουμε το στοιχείο 28 με συχνότητα 2
Τώρα οι συχνότητες που έχουμε είναι : (sp=9, A=3, C=2,D=2, E=6, F=2, H=2, I=2, M=3, N=2, O=5, P=3, R=2, S=6, T=3, 27=L&U=2 , 28=G&X=2)
Προσθέτουμε δυο από τις μικρότερες συχνότητες (τις 28=G&X= 2, R = 2) και προκύπτει το στοιχείο 29 με συχνότητα 4
και παίρνουμε την καινούρια ομάδα συχνοτήτων (sp=9, A=3, C=2,D=2, E=6, F=2, H=2, I=2, M=3, N=2, O=5, P=3, S=6, T=3, 27=L&U=2 , 29=28&R=4 )
και πάλι προσθέτουμε δυό από τις μικρότερες συχνότητες ( το 27=L&U=2 ) και ( και το N=2 ) και προκύπτει το στοιχείο 30 με συχνότητα 4 :
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, A=3, C=2,D=2, E=6, F=2, H=2, I=2, M=3, O=5, P=3, S=6, T=3, 29=28&R=4, 30=27&N=4 )
προσθέτουμε δυό από τις μικρότερες συχνότητες ( H=2 και το I=2) και προκύπτει το στοιχείο 31 με συχνότητα 4:
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, A=3, C=2,D=2, E=6, F=2, M=3, O=5, P=3, S=6, T=3, 29=28&R=4, 30=27&N=4, 31=Η&Ι=4)
εκτελούμε την ίδια διαδικασία για τις ( D=2 και το F=2 ) και προκύπτει το στοιχείο 32 με συχνότητα 4:
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, A=3, C=2, E=6, M=3, O=5, P=3, S=6, T=3, 29=28&R=4, 30=27&N=4, 31=Η&Ι=4, 32=D&F=4)
εκτελούμε την ίδια διαδικασία για τις ( M=3 και το C=2 ) και προκύπτει το στοιχείο 33 με συχνότητα 5:
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, A=3, E=6, O=5, P=3, S=6, T=3, 29=28&R=4, 30=27&N=4, 31=Η&Ι=4, 32=D&F=4, 33=M&C=5)
εκτελούμε την ίδια διαδικασία για τις ( T=3 και το P=3 ) και προκύπτει το στοιχείο 34 με συχνότητα 6:
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, A=3, E=6, O=5, S=6, 29=28&R=4, 30=27&N=4, 31=Η&Ι=4, 32=D&F=4, 33=M&C=5, 34=T&P=6)
εκτελούμε την ίδια διαδικασία για τις ( 30=4 και το A=3 ) και προκύπτει το στοιχείο 35 με συχνότητα 7 :
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, E=6, O=5, S=6, 29=28&R=4, 31=Η&Ι=4, 32=D&F=4, 33=M&C=5, 34=T&P=6, 35=30&Α=7 )
εκτελούμε την ίδια διαδικασία για τις ( 31=4 και το 29=4 ) και προκύπτει το στοιχείο 36 με συχνότητα 8 :
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, E=6, O=5, S=6, 32=D&F=4, 33=M&C=5, 34=T&P=6, 35=30&Α=7, 36=31&29=8)
εκτελούμε την ίδια διαδικασία για τις ( Ο=5 και το 32=4 ) και προκύπτει το στοιχείο 37 με συχνότητα 9 :
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, E=6, S=6, 33=M&C=5, 34=T&P=6, 35=30&Α=7, 36=31&29=8, 37=Ο&32=9)
εκτελούμε την ίδια διαδικασία για τις ( S=6 και το 33=5 ) και προκύπτει το στοιχείο 38 με συχνότητα 11 :
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, E=6, 34=T&P=6, 35=30&Α=7, 36=31&29=8, 37=Ο&32=9, 38=S&33=11 )
εκτελούμε την ίδια διαδικασία για τις ( 34=6 και το E=6 ) και προκύπτει το στοιχείο 39 με συχνότητα 12 :
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, 35=30&Α=7, 36=31&29=8, 37=Ο&32=9, 38=S&33=11, 39=34&E=12 )
εκτελούμε την ίδια διαδικασία για τις ( 36=8 και το 35=7 ) και προκύπτει το στοιχείο 40 με συχνότητα 15 :
η καινούρια ομάδα συχνοτήτων είναι : (sp=9, 37=Ο&32=9, 38=S&33=11, 39=34&E=12, 40=36&35=15 )
εκτελούμε την ίδια διαδικασία για τις ( 38=11 και το Sp=9 ) και προκύπτει το στοιχείο 41 με συχνότητα 20 :
η καινούρια ομάδα συχνοτήτων είναι : (37=Ο&32=9, 39=34&E=12,40=36&35=15, 41=38&Sp=20)
εκτελούμε την ίδια διαδικασία για τις ( 39=12 και το 37=9 ) και προκύπτει το στοιχείο 42 με συχνότητα 21 :
η καινούρια ομάδα συχνοτήτων είναι : (40=36&35=15, 41=38&Sp=20,42=39&37=21)
εκτελούμε την ίδια διαδικασία για τις ( 42=21 και το 40=15 ) και προκύπτει το στοιχείο 43 με συχνότητα 36 :
η καινούρια ομάδα συχνοτήτων είναι : (41=38&Sp=20, 43=42&40=36)
εκτελούμε την ίδια διαδικασία για τις ( 43=36 και το 41=20 ) και προκύπτει το στοιχείο 44 με συχνότητα 56 :
η καινούρια ομάδα συχνοτήτων είναι : (44=43&41=56)
η οποία είναι και η τελευταία συχνότητα που προκύπτει
Το παρακάτων δένδρο είναι το όλα μαζί τα προηγούμενα
Aπό το παραπάνω τελικό δένδρο παράγεται ο κώδικας του παρακάτω πίνακα :
Space | 00 | F | 11000 | M | 0101 | S | 011 | ||||
A | 1000 | G | 101011 | N | 10010 | T | 11111 | ||||
C | 0100 | H | 10111 | O | 1101 | U | 100110 | ||||
D | 11001 | I | 10110 | P | 11110 | X | 101010 | ||||
E | 1110 | L | 100111 | R | 10100 |
(τμήμα κώδικα προγράμματος Link)
Χρησιμοποιόντας τον κώδικα αυτόν το μήνυμα
THIS IS A GOOD EXAMPLE TO PRESENT HUFFMANs COMPRESS CODE
γίνεται
1111110111101100110010000010101111011101110010011101010101000010111110100111111000111111101 0011110101001110011111010010111110010111100110110001100001011000100100110001001101010111101 010011100110110001001101110011110
Συνολικά χρειαζόμαστε 215 bit. Κανονικά το κείμενο καταλαμβάνει
56(χαρακτήρες) x 1(byte/χαρακτήρα) x (8bit/byte) = 448 bit ( δηλ. συμπίεση, σε ποσοστό 50%)
Επίσης εάν χρησιμοποιούσαμε μια πλή κωδικοποίηση (5 bit για κάθε χαρακτήρα - αφού έχουμε 26 χαρακτήρες και ένα το κενό συν δύο για κόμμα και τελεία ) θα χρειαζόμασταν
56(χαρακτήρες) x 5(bit/χαρακτήρα) = 280 bit
Τέλος παραθέτω όλο το πρόγραμμα