Συμπίεση αρχείων. Αλγόριθμοι και λογισμικό για σύγκριση.

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

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

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

Αλγόριθμοι συμπίεσης

Μια πρώτη διάκριση μεταξύ των αλγορίθμων συμπίεσης μπορεί να προσδιοριστεί μεταξύ lossless αλγόριθμους, δηλαδή χωρίς καμία απώλεια ποιότητας και lossy αλγόριθμους, όπου η μείωση του χώρου στο δίσκο συνοδεύεται από απώλεια της ποιότητας. Συχνά είναι δύσκολο να αντιληφθεί την επιδείνωση της ποιότητας του: για παράδειγμα στην περίπτωση της κωδικοποίησης MP3 για αρχεία ήχου.

Μεταξύ των πιο ευρέως χρησιμοποιούμενων αλγορίθμων αναγνώριση χωρίς αμφιβολία το «αλγόριθμο Huffman, η« Shannon-Fano αλγόριθμο και «αλγόριθμος Lempel, Ziv και Welch. Αν και δεν πρόκειται σε θεωρητικές εξηγήσεις, εξετάζουμε τα κύρια χαρακτηριστικά της «αλγόριθμο Huffman, η οποία χαρακτήρισε την ιστορία των τεχνικών συμπίεσης.

Αναφερόμαστε στους αναγνώστες ενδιαφέρονται για περισσότερες λεπτομέρειες σχετικά με τις τεχνικές του Shannon-Fano και Lempel-Ziv-Welch συνδέσεις σε περισσότερες συγκεκριμένες για αυτό το θέμα:

• Shannon-Fano Αλγόριθμος: http://www.binaryessence.com/dct/en000041.htm
• Αλγόριθμος Lempel, Ziv και Welch http://www.dsi.unifi.it/ ~ resp / LZW.pdf

Ο αλγόριθμος Huffman

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

• Αναλύεται και υπολογίζεται ο αριθμός των περιστατικών από τα βασικά στοιχεία του αρχείου για να συμπιεστεί: το άτομο χαρακτήρες σε ένα αρχείο κειμένου, το pixel σε ένα αρχείο εικόνας.
• Τα δύο στοιχεία που συγκεντρώνονται σε ένα λιγότερο συχνή κατηγορία που αντιπροσωπεύει και τους δύο. Έτσι, για παράδειγμα, αν Χ και Υ εμφανίζεται 8 φορές 7 φορές, δημιουργεί την κατηγορία XY, με 15 υποτροπές. Εν τω μεταξύ, οι συνιστώσες Χ και Υ θα λάβουν ένα διαφορετικό δείκτη που τους χαρακτηρίζει ως στοιχεία που εγγράφονται στο «ένωση.
• Τα επόμενα δύο στοιχεία που αναφέρονται λιγότερο συχνά στο αρχείο και να κάθεται ως μια νέα κατηγορία, χρησιμοποιώντας την ίδια διαδικασία που περιγράφεται στο βήμα 2. Η ομάδα XY μπορεί με τη σειρά του και αρχίζει να σχηματίσουν νέες ενώσεις, για παράδειγμα, η κατηγορία XYZ. Όταν συμβαίνει αυτό, το Χ και Υ δίνεται ένα νέο αναγνωριστικό που τελειώνει με την Ένωση επεκτείνει τον κωδικό που προσδιορίζει μοναδικά κάθε ένα από τα δύο γράμματα στο συμπιεσμένο αρχείο θα δημιουργηθεί.
• Είναι τότε που δημιουργήθηκε για τα επόμενα βήματα, ένα δέντρο αποτελείται από μια σειρά από δυαδικά καταστημάτων, μέσα στο οποίο εμφανίζονται πιο συχνά και στα επόμενα στοιχεία σπανιότερες συνδυασμούς στο αρχείο, ενώ τα στοιχεία είναι σπάνια πιο συχνά. Σύμφωνα με το μηχανισμό που περιγράφεται, αυτό σημαίνει ότι τα σπάνια στοιχεία της μη συμπιεσμένα αρχεία που σχετίζονται με μήκος κωδικό αναγνώρισης, η οποία αυξάνεται κάθε στοιχείο μιας νέας ένωσης. Τα στοιχεία επαναλαμβάνονται πιο συχνά, αντί του αρχικού αρχείου δεν υπάρχει στο «δέντρο των ενώσεων, ώστε κωδικό αναγνώρισης τους θα είναι όσο το δυνατόν συντομότερη.
• Συμπιεσμένο αρχείο δημιουργείται, αντικαθιστώντας κάθε στοιχείο του αρχικού αρχείου, ο κωδικός που παράγεται στο τέλος της αλυσίδας των ενώσεων με βάση τη συχνότητα του στοιχείου αυτού στο έγγραφο προέλευσης.

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

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

• <<
• 1
• 2
• >>