Κωδικοί Huffman: παραδείγματα, εφαρμογή

Προς το παρόν, λίγοι άνθρωποι σκέφτονταιπώς λειτουργεί η συμπίεση αρχείων. Σε σύγκριση με το παρελθόν, η χρήση προσωπικού υπολογιστή έχει γίνει πολύ πιο εύκολη. Και σχεδόν όλοι όσοι εργάζονται με το σύστημα αρχείων χρησιμοποιούν αρχεία. Αλλά λίγοι άνθρωποι σκέφτονται πώς λειτουργούν και πώς συμπιέζονται τα αρχεία. Η πρώτη έκδοση αυτής της διαδικασίας ήταν οι κωδικοί Huffman και χρησιμοποιούνται μέχρι σήμερα σε διάφορα δημοφιλή αρχεία. Πολλοί χρήστες δεν σκέφτονται καν πόσο εύκολο είναι να συμπιέσουν ένα αρχείο και πώς λειτουργεί. Σε αυτό το άρθρο, θα δούμε πώς συμβαίνει η συμπίεση, ποιες αποχρώσεις βοηθούν στην επιτάχυνση και την απλούστευση της διαδικασίας κωδικοποίησης, και επίσης θα καταλάβουμε ποια είναι η αρχή της δημιουργίας ενός δέντρου κωδικοποίησης.

Ιστορικό αλγορίθμου

Ο πρώτος αλγόριθμος για αποτελεσματική συμπεριφοράΗ κωδικοποίηση των ηλεκτρονικών πληροφοριών έγινε ένας κωδικός που πρότεινε ο Huffman στα μέσα του εικοστού αιώνα, δηλαδή το 1952. Αυτός είναι αυτή τη στιγμή το κύριο βασικό στοιχείο των περισσότερων προγραμμάτων που έχουν σχεδιαστεί για τη συμπίεση πληροφοριών. Προς το παρόν, μερικές από τις πιο δημοφιλείς πηγές που χρησιμοποιούν αυτόν τον κωδικό είναι αρχεία ZIP, ARJ, RAR και πολλές άλλες.

Επίσης, εφαρμόζεται αυτός ο αλγόριθμος Huffmanσυμπίεση εικόνων JPEG και άλλων γραφικών αντικειμένων. Λοιπόν, όλα τα σύγχρονα φαξ χρησιμοποιούν επίσης κωδικοποίηση που εφευρέθηκε το 1952. Παρά το γεγονός ότι έχει περάσει τόσος χρόνος από τη στιγμή που δημιουργήθηκε ο κώδικας, εξακολουθεί να χρησιμοποιείται στα νεότερα κελύφη και στον εξοπλισμό των παλαιών και σύγχρονων τύπων.

Η αρχή της αποτελεσματικής κωδικοποίησης

Ο αλγόριθμος Huffman βασίζεται στο σχήμασας επιτρέπει να αντικαταστήσετε τους πιο πιθανούς, πιο κοινούς χαρακτήρες με κωδικούς του δυαδικού συστήματος. Και αυτά που είναι λιγότερο κοινά αντικαθίστανται με μεγαλύτερους κωδικούς. Η μετάβαση στους κωδικούς Long Huffman πραγματοποιείται μόνο αφού το σύστημα χρησιμοποιήσει όλες τις ελάχιστες τιμές. Αυτή η τεχνική σάς επιτρέπει να ελαχιστοποιήσετε το μήκος του κώδικα για κάθε χαρακτήρα του αρχικού μηνύματος στο σύνολό του.

Το σημαντικό σημείο είναι ότι στην αρχήΗ πιθανότητα εμφάνισης γραμμάτων πρέπει να είναι ήδη γνωστή. Από αυτούς θα συντεθεί το τελικό μήνυμα. Με βάση αυτά τα δεδομένα, δημιουργείται ένα δέντρο κώδικα Huffman, βάσει του οποίου θα πραγματοποιηθεί η διαδικασία κωδικοποίησης επιστολών στο αρχείο.

Παράδειγμα κώδικα Huffman

Για να απεικονίσετε τον αλγόριθμο, πάρτεγραφική έκδοση της δημιουργίας ενός δέντρου κώδικα. Για να είναι αποτελεσματική η χρήση αυτής της μεθόδου, αξίζει να αποσαφηνιστεί ο ορισμός ορισμένων από τις τιμές που είναι απαραίτητες για την έννοια αυτής της μεθόδου. Το σύνολο ενός συνόλου τόξων και κόμβων που κατευθύνονται από κόμβο σε κόμβο ονομάζεται γράφημα. Το ίδιο το δέντρο είναι ένα γράφημα με ένα σύνολο συγκεκριμένων ιδιοτήτων:

• κάθε κόμβος δεν μπορεί να περιέχει περισσότερα από ένα τόξα.
• Ένας από τους κόμβους πρέπει να είναι η ρίζα του δέντρου, δηλαδή, τα τόξα δεν πρέπει να εισέρχονται καθόλου.
• Εάν αρχίσετε να κινείτε κατά μήκος τόξων από τη ρίζα, αυτή η διαδικασία θα σας επιτρέψει να φτάσετε σε οποιονδήποτε από τους κόμβους.

Υπάρχει επίσης μια τέτοια έννοια που περιλαμβάνεται στους κωδικούςΟ Huffman μοιάζει με ένα φύλλο σε ένα δέντρο. Αντιπροσωπεύει έναν κόμβο από τον οποίο δεν πρέπει να βγαίνουν τόξα. Εάν δύο κόμβοι συνδέονται με ένα τόξο, τότε ένας από αυτούς είναι γονέας, ο άλλος είναι παιδί, ανάλογα με τον κόμβο που εξέρχεται από το τόξο και από ποιον εισέρχεται. Εάν δύο κόμβοι έχουν τον ίδιο γονικό κόμβο, συνήθως αναφέρονται ως αδελφοί κόμβοι. Εάν, εκτός από τα φύλλα, οι κόμβοι έχουν πολλά τόξα, τότε αυτό το δέντρο ονομάζεται δυαδικό. Αυτό είναι ακριβώς το δέντρο Huffman. Ένα χαρακτηριστικό των κόμβων αυτής της κατασκευής είναι ότι το βάρος κάθε γονέα είναι ίσο με το άθροισμα του βάρους όλων των κομβικών παιδιών.

Αλγόριθμος κατασκευής δέντρων Huffman

Η δημιουργία ενός κώδικα Huffman γίνεται με γράμματααλφάβητο εισαγωγής. Δημιουργείται μια λίστα με αυτούς τους κόμβους που είναι δωρεάν στο μελλοντικό δέντρο κώδικα. Το βάρος κάθε κόμβου σε αυτήν τη λίστα πρέπει να είναι το ίδιο με την πιθανότητα εμφάνισης του γράμματος μηνύματος που αντιστοιχεί σε αυτόν τον κόμβο. Στην περίπτωση αυτή, επιλέγεται ανάμεσα σε πολλούς ελεύθερους κόμβους του μελλοντικού δέντρου, επιλέγεται αυτός που έχει το μικρότερο βάρος. Επιπλέον, εάν παρατηρηθούν οι ελάχιστοι δείκτες σε πολλούς κόμβους, τότε μπορείτε ελεύθερα να επιλέξετε οποιοδήποτε από τα ζεύγη.

Στη συνέχεια δημιουργείται ο γονέας.κόμβος, ο οποίος θα πρέπει να ζυγίζει όσο το άθροισμα αυτού του ζεύγους κόμβων ζυγίζει. Μετά από αυτό, ο γονέας αποστέλλεται στη λίστα με δωρεάν κόμβους και τα παιδιά καταργούνται. Σε αυτήν την περίπτωση, τα τόξα λαμβάνουν τους αντίστοιχους δείκτες, αυτούς και μηδενικά. Αυτή η διαδικασία επαναλαμβάνεται όσο είναι απαραίτητο για να αφήσει μόνο έναν κόμπο. Στη συνέχεια, τα δυαδικά ψηφία γράφονται από πάνω προς τα κάτω.

Βελτίωση της αποτελεσματικότητας συμπίεσης

Για να βελτιώσετε την απόδοση συμπίεσης, πρέπει να το κάνετεΚατά τη δημιουργία ενός δέντρου κώδικα, χρησιμοποιήστε όλα τα δεδομένα σχετικά με την πιθανότητα εμφάνισης γραμμάτων σε ένα συγκεκριμένο αρχείο που επισυνάπτεται στο δέντρο και μην τους επιτρέπετε να διασκορπίζονται σε μεγάλο αριθμό εγγράφων κειμένου. Εάν διαβάσετε πρώτα αυτό το αρχείο, μπορείτε να υπολογίσετε αμέσως στατιστικά στοιχεία σχετικά με τη συχνότητα εύρεσης γραμμάτων από το αντικείμενο προς συμπίεση.

Επιταχύνετε τη διαδικασία συμπίεσης

Για να επιταχύνετε τον αλγόριθμο, προσδιορίζοντας γράμματαΕίναι απαραίτητο να πραγματοποιείται όχι σύμφωνα με τους δείκτες της πιθανότητας εμφάνισης ενός συγκεκριμένου γράμματος, αλλά σύμφωνα με τη συχνότητα εμφάνισής του. Αυτό καθιστά τον αλγόριθμο απλούστερο και πολύ πιο γρήγορο για εργασία. Αποφεύγει επίσης τις λειτουργίες κινούμενου σημείου και διαίρεσης.

Επιπλέον, λειτουργώντας σε αυτήν τη λειτουργία, η δυναμικήΟ κωδικός Huffman, ή μάλλον ο ίδιος ο αλγόριθμος, δεν υπόκειται σε αλλαγές. Αυτό οφείλεται κυρίως στο γεγονός ότι οι πιθανότητες είναι ευθέως ανάλογες με τις συχνότητες. Αξίζει να δοθεί ιδιαίτερη προσοχή στο γεγονός ότι το τελικό βάρος του αρχείου ή ο λεγόμενος ριζικός κόμβος θα είναι ίσο με το άθροισμα του αριθμού των γραμμάτων στο αντικείμενο προς επεξεργασία.

Συμπέρασμα

Κωδικοί Huffman - απλοί και μακροχρόνιοιένας αλγόριθμος που εξακολουθεί να χρησιμοποιείται από πολλά γνωστά προγράμματα και εταιρείες. Η απλότητα και η σαφήνεια του επιτρέπουν να επιτύχετε αποτελεσματικά αποτελέσματα συμπίεσης αρχείων οποιουδήποτε μεγέθους και να μειώσετε σημαντικά τον χώρο αποθήκευσης. Με άλλα λόγια, ο αλγόριθμος Huffman είναι ένα μακροχρόνιο μελετημένο και καλά αναπτυγμένο σχήμα, η συνάφεια του οποίου δεν μειώνεται μέχρι σήμερα.

Και χάρη στην ικανότητα μείωσης του μεγέθους του αρχείου,η μετάδοσή τους μέσω δικτύου ή με άλλα μέσα γίνεται ευκολότερη, ταχύτερη και πιο βολική. Δουλεύοντας με τον αλγόριθμο, μπορείτε να συμπιέσετε απολύτως οποιαδήποτε πληροφορία χωρίς να βλάψετε τη δομή και την ποιότητά του, αλλά με τη μέγιστη επίδραση της μείωσης του βάρους του αρχείου. Με άλλα λόγια, η κωδικοποίηση Huffman υπήρξε και παραμένει η πιο δημοφιλής και τρέχουσα μέθοδος συμπίεσης μεγέθους αρχείου.