Huffman κώδικες: παραδείγματα, εφαρμογές

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

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

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

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

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

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

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

Ο κώδικας του Huffman, παράδειγμα

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

• σε κάθε κόμβο δεν μπορεί να εισέλθει περισσότερο από ένα από τα τόξα?
• ένας από τους κόμβους πρέπει να είναι η ρίζα του δέντρου, δηλαδή δεν πρέπει να εισέλθει καθόλου τόξο.
• εάν από τη ρίζα για να αρχίσει να κινούνται κατά τόξα, αυτή η διαδικασία θα πρέπει να επιτρέπει την πλήρη είσοδο σε οποιονδήποτε από τους κόμβους.

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

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

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

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

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

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

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

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

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

Συμπέρασμα

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

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