Ο αλγόριθμος του Huffman χρησιμοποιείται για τη συμπίεση ή την κωδικοποίηση δεδομένων. Κανονικά, κάθε χαρακτήρας σε ένα αρχείο κειμένου αποθηκεύεται ως οκτώ bits (ψηφία, είτε 0 είτε 1) που αντιστοιχούν σε αυτόν τον χαρακτήρα χρησιμοποιώντας μια κωδικοποίηση που ονομάζεται ASCII. Ένα αρχείο που κωδικοποιείται με Huffman διασπά την άκαμπτη δομή των 8-bit έτσι ώστε οι πιο συχνά χρησιμοποιούμενοι χαρακτήρες να αποθηκεύονται σε λίγα bit (το 'a' θα μπορούσε να είναι "10" ή "1000" και όχι το ASCII, το οποίο είναι "01100001"). Οι λιγότερο συνηθισμένοι χαρακτήρες, λοιπόν, συχνά καταλαμβάνουν πολύ περισσότερα από 8 bit (το 'z' μπορεί να είναι "00100011010"), αλλά επειδή εμφανίζονται τόσο σπάνια, η κωδικοποίηση Huffman, στο σύνολό της, δημιουργεί ένα πολύ μικρότερο αρχείο από το πρωτότυπο.
Βήματα
Μέρος 1 από 2: Κωδικοποίηση
Βήμα 1. Μετρήστε τη συχνότητα κάθε χαρακτήρα στο αρχείο που πρόκειται να κωδικοποιηθεί
Συμπεριλάβετε έναν εικονικό χαρακτήρα για να σημειώσετε το τέλος του αρχείου - αυτό θα είναι σημαντικό αργότερα. Προς το παρόν, ονομάστε το EOF (τέλος αρχείου) και σημειώστε το ότι έχει συχνότητα 1.
Για παράδειγμα, εάν θέλετε να κωδικοποιήσετε ένα αρχείο κειμένου που διαβάζει "ab ab cab", θα έχετε 'a' με συχνότητα 3, 'b' με συχνότητα 3, '' (διάστημα) με συχνότητα 2, 'c' με συχνότητα 1, και EOF με συχνότητα 1
Βήμα 2. Αποθηκεύστε τους χαρακτήρες ως κόμβους δέντρων και τοποθετήστε τους σε ουρά προτεραιότητας
Θα χτίσετε ένα μεγάλο δυαδικό δέντρο με κάθε χαρακτήρα ως φύλλο, οπότε θα πρέπει να αποθηκεύσετε τους χαρακτήρες σε μορφή τέτοια ώστε να μπορούν να γίνουν κόμβοι του δέντρου. Τοποθετήστε αυτούς τους κόμβους σε μια ουρά προτεραιότητας με προτεραιότητα τον κάθε κόμβο ως χαρακτήρα.
- Ένα δυαδικό δέντρο είναι μια μορφή δεδομένων όπου κάθε κομμάτι δεδομένων είναι ένας κόμβος που μπορεί να έχει έως έναν γονέα και δύο παιδιά. Συχνά σχεδιάζεται ως διακλαδισμένο δέντρο, εξ ου και το όνομα.
- Μια ουρά είναι μια εύστοχα ονομαζόμενη συλλογή δεδομένων όπου το πρώτο πράγμα που μπαίνει στην ουρά είναι επίσης το πρώτο πράγμα που εμφανίζεται (όπως η αναμονή στην ουρά). Σε μια ουρά προτεραιότητας, τα δεδομένα αποθηκεύονται σύμφωνα με την προτεραιότητά τους, έτσι ώστε το πρώτο πράγμα που βγαίνει να είναι το πιο επείγον πράγμα, το πράγμα με τη μικρότερη προτεραιότητα, και όχι το πρώτο πράγμα που ενσωματώνεται.
- Στο παράδειγμα "ab ab cab", η ουρά προτεραιότητάς σας θα μοιάζει με αυτήν: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Βήμα 3. Ξεκινήστε να χτίζετε το δέντρο σας
Αφαιρέστε (ή αφαιρέστε) τα δύο πιο επείγοντα πράγματα από την ουρά προτεραιότητας. Δημιουργήστε έναν νέο κόμβο δέντρου για να είστε ο γονέας αυτών των δύο κόμβων, αποθηκεύοντας τον πρώτο κόμβο ως αριστερό παιδί και τον δεύτερο ως δεξιό παιδί. Η προτεραιότητα του νέου κόμβου πρέπει να είναι το άθροισμα των προτεραιοτήτων του παιδιού του. Στη συνέχεια, τοποθετήστε αυτόν τον νέο κόμβο στην ουρά προτεραιότητας.
Η ουρά προτεραιότητας μοιάζει τώρα με αυτήν: {'': 2, νέος κόμβος: 2, 'a': 3, 'b': 3}
Βήμα 4. Ολοκληρώστε την κατασκευή του δέντρου σας:
επαναλάβετε το παραπάνω βήμα έως ότου υπάρχει μόνο ένας κόμβος στην ουρά. Σημειώστε ότι εκτός από τους κόμβους που δημιουργήσατε για τους χαρακτήρες και τις συχνότητές τους, θα πραγματοποιήσετε επίσης αποστράγγιση, μετατροπή σε δέντρα και επανέκδοση γονικών κόμβων, κόμβων που είναι ήδη δέντρα.
- Όταν τελειώσετε, ο τελευταίος κόμβος στην ουρά θα είναι η ρίζα του δέντρου κωδικοποίησης, με όλους τους άλλους κόμβους να διακλαδίζονται από αυτό.
- Οι πιο συχνά χρησιμοποιούμενοι χαρακτήρες θα είναι τα φύλλα πιο κοντά στην κορυφή του δέντρου, ενώ οι σπάνια χρησιμοποιούμενοι χαρακτήρες θα τοποθετηθούν στο κάτω μέρος του δέντρου, πιο μακριά από τη ρίζα.
Βήμα 5. Δημιουργήστε έναν χάρτη κωδικοποίησης. Περπατήστε μέσα από το δέντρο για να φτάσετε σε κάθε χαρακτήρα. Κάθε φορά που επισκέπτεστε το αριστερό παιδί ενός κόμβου, αυτό είναι ένα "0". Κάθε φορά που επισκέπτεστε το σωστό παιδί ενός κόμβου, αυτό είναι «1». Όταν φτάσετε σε έναν χαρακτήρα, αποθηκεύστε τον χαρακτήρα με την ακολουθία 0 και 1 που χρειάστηκε για να φτάσετε εκεί. Αυτή η ακολουθία είναι η κωδικοποίηση του χαρακτήρα όπως στο συμπιεσμένο αρχείο. Αποθηκεύστε τους χαρακτήρες και τις ακολουθίες τους σε έναν χάρτη.
- Για παράδειγμα, ξεκινήστε από τη ρίζα. Επισκεφθείτε το αριστερό παιδί της ρίζας και, στη συνέχεια, επισκεφθείτε το αριστερό παιδί αυτού του κόμβου. Δεδομένου ότι ο κόμβος στον οποίο βρίσκεστε τώρα δεν έχει παιδιά, έχετε φτάσει σε έναν χαρακτήρα. Αυτό είναι ' '. Αφού περπατήσατε αριστερά δύο φορές για να φτάσετε εδώ, η κωδικοποίηση για '' είναι "00".
- Για αυτό το δέντρο, ο χάρτης θα μοιάζει με αυτόν: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Βήμα 6. Στο αρχείο εξόδου, συμπεριλάβετε τον χάρτη κωδικοποίησης ως κεφαλίδα
Αυτό θα επιτρέψει την αποκωδικοποίηση του αρχείου.
Βήμα 7. Κωδικοποιήστε το αρχείο
Για κάθε χαρακτήρα στο αρχείο που πρόκειται να κωδικοποιηθεί, γράψτε τη δυαδική ακολουθία που έχετε αποθηκεύσει στο χάρτη. Μόλις ολοκληρώσετε την κωδικοποίηση του αρχείου, φροντίστε να προσθέσετε το EOF στο τέλος.
- Για το αρχείο "ab ab cab", το κωδικοποιημένο αρχείο θα έχει την εξής μορφή: "1011001011000101011011".
- Τα αρχεία αποθηκεύονται ως byte (8 bit ή 8 δυαδικά ψηφία). Επειδή ο αλγόριθμος κωδικοποίησης Huffman δεν χρησιμοποιεί τη μορφή 8-bit, τα κωδικοποιημένα αρχεία συχνά δεν θα έχουν μήκη πολλαπλάσια του 8. Τα υπόλοιπα ψηφία θα συμπληρωθούν με 0s. Σε αυτήν την περίπτωση, δύο 0 θα προστεθούν στο τέλος του αρχείου, το οποίο μοιάζει με άλλο χώρο. Αυτό θα μπορούσε να είναι πρόβλημα: πώς θα μπορούσε ο αποκωδικοποιητής να ξέρει πότε να σταματήσει να διαβάζει; Ωστόσο, επειδή συμπεριλάβαμε έναν χαρακτήρα τέλους αρχείου, ο αποκωδικοποιητής θα φτάσει σε αυτό και στη συνέχεια θα σταματήσει, αγνοώντας οτιδήποτε άλλο έχει προστεθεί μετά.
Μέρος 2 από 2: Αποκωδικοποίηση
Βήμα 1. Διαβάστε σε αρχείο κωδικοποιημένο από Huffman
Αρχικά, διαβάστε την κεφαλίδα, η οποία πρέπει να είναι ο χάρτης κωδικοποίησης. Χρησιμοποιήστε αυτό για να δημιουργήσετε ένα δέντρο αποκωδικοποίησης με τον ίδιο τρόπο που δημιουργήσατε το δέντρο που χρησιμοποιήσατε για την κωδικοποίηση του αρχείου. Τα δύο δέντρα πρέπει να είναι πανομοιότυπα.
Βήμα 2. Διαβάστε δυαδικά ένα ψηφίο τη φορά
Διασχίστε το δέντρο καθώς διαβάζετε: αν διαβάζετε σε '0', πηγαίνετε στο αριστερό παιδί του κόμβου στον οποίο βρίσκεστε και αν διαβάζετε σε '1', πηγαίνετε στο δεξί παιδί. Όταν φτάσετε σε ένα φύλλο (ένας κόμβος χωρίς παιδιά), έχετε φτάσει σε έναν χαρακτήρα. Γράψτε τον χαρακτήρα στο αποκωδικοποιημένο αρχείο.
Λόγω του τρόπου αποθήκευσης των χαρακτήρων στο δέντρο, οι κωδικοί για κάθε χαρακτήρα έχουν μια ιδιότητα προθέματος, έτσι ώστε η δυαδική κωδικοποίηση κανενός χαρακτήρα να μην μπορεί να συμβεί στην αρχή της κωδικοποίησης ενός άλλου χαρακτήρα. Η κωδικοποίηση για κάθε χαρακτήρα είναι εντελώς μοναδική. Αυτό κάνει την αποκωδικοποίηση πολύ πιο εύκολη
Βήμα 3. Επαναλάβετε μέχρι να φτάσετε στο EOF
Συγχαρητήρια! Αποκωδικοποιήσατε το αρχείο.
