Huffman κώδικες: αίτηση παραδείγματα

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

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

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

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

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

κώδικας Huffman, παράδειγμα

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

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

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

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

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

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

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

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

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

συμπέρασμα

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