Πώς λειτουργεί η συμπίεση αρχείων;

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

Πως λειτουργεί, λοιπόν?

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

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

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

Πάρτε αυτό το σύντομο κομμάτι του κειμένου για παράδειγμα:

Ο αλγόριθμος LZ77 θα εξετάσει αυτό το κείμενο, θα συνειδητοποιήσει ότι επαναλαμβάνει το "howtogeek" τρεις φορές και το αλλάζει σε αυτό:

Στη συνέχεια, όταν θέλει να διαβάσει το κείμενο πίσω, θα αντικαταστήσει κάθε περίπτωση του (h) με το "howtogeek", επαναφέροντας μας στην αρχική φράση.

Ονομάζουμε συμπίεση όπως αυτό "χωρίς απώλειες" - τα δεδομένα που εισάγετε είναι τα ίδια με τα δεδομένα που βγάζετε. Τίποτα δεν χάθηκε.

Στην πραγματικότητα, το LZ77 δεν χρησιμοποιεί μια λίστα με κλειδιά, αλλά αντικαθιστά το δεύτερο και το τρίτο περιστατικό με έναν σύνδεσμο πίσω στη μνήμη:

Έτσι τώρα, όταν φτάνει στο (h), θα κοιτάξει πίσω στο "howtogeek" και να διαβάσει αυτό αντ 'αυτού.

Αν σας ενδιαφέρει μια λεπτομερέστερη εξήγηση, αυτό το βίντεο από το Computerphile είναι πολύ χρήσιμο.

Τώρα, αυτό είναι ένα ιδανικό παράδειγμα. Στην πραγματικότητα, το μεγαλύτερο μέρος του κειμένου είναι συμπιεσμένο με πλήκτρα τόσο μικρά όσο με λίγους χαρακτήρες. Για παράδειγμα, η λέξη "η" θα συμπιεστεί ακόμα και όταν εμφανίζεται με λέξεις όπως "εκεί", "τους" και "τότε". Με το επαναλαμβανόμενο κείμενο, μπορείτε να πάρετε κάποια τρελή αναλογία συμπίεσης. Πάρτε αυτό το αρχείο κειμένου με τη λέξη "howtogeek" επαναλαμβανόμενες 100 φορές. Το αρχικό αρχείο κειμένου είναι μεγέθους τριών kilobytes. Όταν συμπιέζεται, όμως, χρειάζεται μόνο 158 byte. Αυτό είναι σχεδόν 95% συμπίεση.

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

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

Πώς λειτουργεί η συμπίεση εικόνας και βίντεο?

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

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

Ακολουθεί ένα παράδειγμα. Αυτό είναι ένα screenshot που πήρα που δεν έχει συμπιεστεί καθόλου.

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

Φαίνεται αρκετά κακό, σωστά?

Λοιπόν, αυτό είναι μόνο ένα χειρότερο σενάριο, εξάγοντας σε ποιότητα JPEG 0% κάθε φορά. Για λόγους σύγκρισης, εδώ είναι ένα 50% JPEG ποιότητας, το οποίο είναι σχεδόν αδιαίρετο από την εικόνα πηγή PNG, εκτός αν το φυσήξετε και να κοιτάξετε προσεκτικά.

Το PNG για αυτήν την εικόνα ήταν 200 KB σε μέγεθος, αλλά αυτό το JPEG 50% ποιότητας είναι μόνο 28 KB.

Έτσι πώς εξοικονομείται τόσο πολύς χώρος; Λοιπόν, ο αλγόριθμος JPEG είναι ένα κατόρθωμα της μηχανικής. Οι περισσότερες εικόνες αποθηκεύουν μια λίστα με αριθμούς, με κάθε αριθμό να αντιπροσωπεύει ένα μόνο εικονοστοιχείο.

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

Αυτό δίνει στους JPEGs έναν τεράστιο υψηλό λόγο συμπίεσης, ο οποίος μπορεί να μειώσει ένα αρχείο που θα είναι πολλαπλά megabytes κάτω από μερικά kilobytes, ανάλογα με την ποιότητα. Φυσικά, αν το χρησιμοποιείτε πάρα πολύ, καταλήγετε σε αυτό:

Αυτή η εικόνα είναι φρικτή. Ωστόσο, οι μικρές ποσότητες συμπίεσης JPEG μπορούν να επηρεάσουν σημαντικά το μέγεθος του αρχείου και αυτό καθιστά την JPEG πολύ χρήσιμη για τη συμπίεση εικόνων σε ιστότοπους. Οι περισσότερες εικόνες που βλέπετε online είναι συμπιεσμένες για να αποθηκεύσετε τους χρόνους λήψης, ειδικά για χρήστες κινητής τηλεφωνίας με κακές συνδέσεις δεδομένων. Στην πραγματικότητα, όλες οι εικόνες στο How-To Geek έχουν συμπιεστεί για να κάνουν τη φόρτωση σελίδων γρηγορότερη και πιθανότατα δεν έχετε παρατηρήσει ποτέ.

Συμπίεση βίντεο

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

Χρησιμοποιούμε κάτι που ονομάζεται "συμπίεση μεταξύ πλαισίων", το οποίο υπολογίζει τις αλλαγές μεταξύ κάθε πλαισίου και αποθηκεύει μόνο αυτές. Έτσι, για παράδειγμα, εάν έχετε ένα σχετικά πυροβολισμό που διαρκεί μερικά δευτερόλεπτα σε ένα βίντεο, αποθηκεύεται πολύς χώρος επειδή ο αλγόριθμος συμπίεσης δεν χρειάζεται να αποθηκεύει όλα τα στοιχεία στη σκηνή που δεν αλλάζει. Η συμπίεση μεταξύ καρέ είναι ο κύριος λόγος για τον οποίο έχουμε ψηφιακή τηλεόραση και βίντεο στο διαδίκτυο καθόλου. Χωρίς αυτό, τα βίντεο θα ήταν εκατοντάδες gigabytes, περισσότερο από το μέσο μέγεθος του σκληρού δίσκου το 2005, όταν κυκλοφόρησε το YouTube.

Επίσης, επειδή η συμπίεση μεταξύ των πλαισίων λειτουργεί καλύτερα με το περισσότερο στατικό βίντεο, αυτός είναι ο λόγος για τον οποίο τα confetti καταστρέφουν την ποιότητα του βίντεο.

Σημείωση: Το GIF δεν το κάνει αυτό, γι 'αυτό και τα κινούμενα GIF είναι συχνά πολύ μικρά και μικρά, αλλά εξακολουθούν να έχουν αρκετά μεγάλο μέγεθος αρχείου.

Ένα άλλο πράγμα που πρέπει να θυμάστε για το βίντεο είναι το bitrate του - το ποσό των δεδομένων που επιτρέπεται σε κάθε δευτερόλεπτο. Εάν το bitrate σας είναι 200 ​​kb / s, για παράδειγμα, το βίντεό σας θα φαίνεται πολύ κακό. Η ποιότητα αυξάνεται καθώς το bitrate ανεβαίνει, αλλά μετά από μερικά megabyte ανά δευτερόλεπτο, θα έχετε μειωμένες αποδόσεις.

Αυτό είναι ένα μεγεθυντικό πλαίσιο που τραβήξατε από ένα βίντεο από μια μέδουσα. Το ένα στα αριστερά είναι στα 3Mb / s, και το ένα στα δεξιά είναι 100Mb / s.

30x αύξηση του μεγέθους του αρχείου, αλλά όχι μεγάλη αύξηση της ποιότητας. Γενικά, τα βίντεο του YouTube κάθονται γύρω από 2-10Mb / s ανάλογα με τη σύνδεσή σας, καθώς πιθανότατα δεν θα παρατηρήσετε τίποτα περισσότερο.

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

Συμπίεση ήχου

Η συμπίεση ήχου λειτουργεί πολύ παρόμοια με τη συμπίεση κειμένου και εικόνας. Όπου η JPEG καταργεί τις λεπτομέρειες από μια εικόνα που δεν θα δείτε, η συμπίεση ήχου κάνει το ίδιο για τους ήχους. Ίσως να μην χρειαστεί να ακούσετε τη σκασίματα της επιλογής κιθάρας στη συμβολοσειρά, αν η πραγματική κιθάρα είναι πολύ, πολύ πιο δυνατά.

Το MP3 χρησιμοποιεί επίσης bitrate, που κυμαίνεται από το χαμηλό τέλος των 48 και 96 kbps (χαμηλό τέλος) σε 128 και 240kbps (αρκετά καλό) έως 320kbps (high-end ήχου), και πιθανότατα θα ακούσετε μόνο τη διαφορά με εξαιρετικά καλά ακουστικά και αυτιά).

Υπάρχουν επίσης κωδικοποιητές συμπίεσης χωρίς απώλειες για τον ήχο -τον κύριο είναι ο FLAC-ο οποίος χρησιμοποιεί την κωδικοποίηση LZ77 για να παρέχει ήχο χωρίς απώλειες. Μερικοί άνθρωποι ορκίζονται από την τέλεια ποιότητα ήχου του FLAC, αλλά με την επικράτηση του MP3, φαίνεται ότι οι περισσότεροι άνθρωποι είτε δεν μπορούν να πουν ή να μη νοιάζονται για τη διαφορά.