Πώς λειτουργεί η συμπίεση δεδομένων χωρίς απώλειες | Περιοδικό Quanta

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

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

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

Σκεφτείτε ένα μήνυμα που αποτελείται από γράμματα, αριθμούς και σημεία στίξης. Ένας απλός τρόπος για να κωδικοποιήσετε ένα τέτοιο μήνυμα θα ήταν να εκχωρήσετε σε κάθε χαρακτήρα έναν μοναδικό δυαδικό αριθμό. Για παράδειγμα, ένας υπολογιστής μπορεί να αντιπροσωπεύει το γράμμα A ως 01000001 και ένα θαυμαστικό ως 00100001. Αυτό έχει ως αποτέλεσμα κωδικούς που είναι εύκολο να αναλυθούν - κάθε οκτώ ψηφία ή bit, αντιστοιχούν σε έναν μοναδικό χαρακτήρα - αλλά τρομερά αναποτελεσματικό, επειδή ο ίδιος αριθμός δυαδικών ψηφίων χρησιμοποιείται τόσο για κοινές όσο και για ασυνήθιστες καταχωρήσεις. Μια καλύτερη προσέγγιση θα ήταν κάτι σαν τον κώδικα Μορς, όπου το συχνό γράμμα Ε αντιπροσωπεύεται από μία μόνο τελεία, ενώ το λιγότερο κοινό Q απαιτεί τη μεγαλύτερη και πιο επίπονη παύλα-παύλα-κουκκίδα-παύλα.

Ωστόσο, ο κώδικας Μορς είναι επίσης αναποτελεσματικός. Σίγουρα, κάποιοι κωδικοί είναι σύντομοι και άλλοι είναι μεγάλοι. Επειδή όμως τα μήκη κωδικών ποικίλλουν, τα μηνύματα στον κώδικα Μορς δεν μπορούν να γίνουν κατανοητά εκτός εάν περιλαμβάνουν σύντομες περιόδους σιωπής μεταξύ κάθε μετάδοσης χαρακτήρων. Πράγματι, χωρίς αυτές τις δαπανηρές παύσεις, οι παραλήπτες δεν θα είχαν κανέναν τρόπο να διακρίνουν το μήνυμα Μορς παύλα τελεία-παύλα-κουκκίδα-κουκκίδα παύλα («τετριμμένη») από παύλα τελεία-παύλα-κουκκίδα τελεία-παύλα («αληθές» ).

Ο Φάνο είχε λύσει αυτό το μέρος του προβλήματος. Συνειδητοποίησε ότι μπορούσε να χρησιμοποιήσει κωδικούς διαφορετικού μήκους χωρίς να χρειάζεται δαπανηρούς χώρους, αρκεί να μην χρησιμοποιούσε ποτέ το ίδιο μοτίβο ψηφίων τόσο ως πλήρη κωδικό όσο και ως αρχή άλλου κωδικού. Για παράδειγμα, εάν το γράμμα S ήταν τόσο συνηθισμένο σε ένα συγκεκριμένο μήνυμα που ο Fano του εκχωρούσε τον εξαιρετικά σύντομο κωδικό 01, τότε κανένα άλλο γράμμα σε αυτό το μήνυμα δεν θα κωδικοποιηθεί με τίποτα που να ξεκινά με το 01. κωδικοί όπως 010, 011 ή 0101 θα ήταν όλοι απαγορευμένοι. Ως αποτέλεσμα, το κωδικοποιημένο μήνυμα μπορούσε να διαβαστεί από αριστερά προς τα δεξιά, χωρίς καμία ασάφεια. Για παράδειγμα, με το γράμμα S να έχει εκχωρηθεί 01, το γράμμα A να έχει εκχωρηθεί 000, το γράμμα M να έχει εκχωρηθεί 001 και το γράμμα L με 1, ξαφνικά το μήνυμα 0100100011 μπορεί να μεταφραστεί αμέσως στη λέξη "small", παρόλο που το L αντιπροσωπεύεται από ένα ψηφίο, S με δύο ψηφία και τα άλλα γράμματα κατά τρία το καθένα.

Για να προσδιορίσει πραγματικά τους κωδικούς, ο Fano κατασκεύασε δυαδικά δέντρα, τοποθετώντας κάθε απαραίτητο γράμμα στο τέλος ενός οπτικού κλάδου. Στη συνέχεια, ο κωδικός κάθε γράμματος ορίστηκε από τη διαδρομή από πάνω προς τα κάτω. Εάν η διαδρομή διακλαδώθηκε προς τα αριστερά, ο Fano πρόσθεσε ένα 0. Τα δεξιά κλαδιά πήραν 1. Η δομή του δέντρου διευκόλυνε τον Fano να αποφύγει αυτές τις ανεπιθύμητες επικαλύψεις: Μόλις ο Fano τοποθετούσε ένα γράμμα στο δέντρο, αυτό το κλαδί θα τελείωνε, πράγμα που σημαίνει ότι κανένας μελλοντικός κώδικας δεν θα μπορούσε να ξεκινήσει με τον ίδιο τρόπο.

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

Το αποτέλεσμα ήταν εξαιρετικά αποτελεσματική συμπίεση. Αλλά ήταν μόνο μια προσέγγιση. έπρεπε να υπάρξει μια καλύτερη στρατηγική συμπίεσης. Ο Φάνο λοιπόν προκάλεσε τους μαθητές του να το βρουν.

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

Σκεφτείτε ένα μήνυμα όπου η προσέγγιση Fano παραπαίει. Στη "σχολική αίθουσα", το O εμφανίζεται τέσσερις φορές και το S/C/H/L/R/M εμφανίζεται το καθένα μία φορά. Η προσέγγιση εξισορρόπησης του Fano ξεκινά με την αντιστοίχιση του Ο και ενός άλλου γράμματος στον αριστερό κλάδο, με τις πέντε συνολικές χρήσεις αυτών των γραμμάτων να εξισορροπούν τις πέντε εμφανίσεις των υπόλοιπων γραμμάτων. Το μήνυμα που προκύπτει απαιτεί 27 bit.

Ο Huffman, αντίθετα, ξεκινά με δύο από τα ασυνήθιστα γράμματα - ας πούμε, R και M - και τα ομαδοποιεί, αντιμετωπίζοντας το ζευγάρι σαν ένα μόνο γράμμα.

Το ενημερωμένο διάγραμμα συχνοτήτων του προσφέρει στη συνέχεια τέσσερις επιλογές: το O που εμφανίζεται τέσσερις φορές, τον νέο συνδυασμένο κόμβο RM που χρησιμοποιείται λειτουργικά δύο φορές και τα μεμονωμένα γράμματα S, C, H και L. Ο Huffman επιλέγει και πάλι τις δύο λιγότερο κοινές επιλογές, ταιριάζουν (λέμε) H με L.

Το διάγραμμα ενημερώνεται ξανά: Το O εξακολουθεί να έχει βάρος 4, το RM και το HL τώρα έχουν βάρος 2 και τα γράμματα S και C είναι μόνα τους. Ο Huffman συνεχίζει από εκεί, σε κάθε βήμα ομαδοποιώντας τις δύο λιγότερο συχνές επιλογές και στη συνέχεια ενημερώνοντας τόσο το δέντρο όσο και το διάγραμμα συχνοτήτων.

Τελικά, η "σχολική αίθουσα" γίνεται 11101111110000110110000101, αφαιρώντας ένα κομμάτι από την προσέγγιση Fano από πάνω προς τα κάτω.

Ένα bit μπορεί να μην ακούγεται πολύ, αλλά ακόμη και οι μικρές οικονομίες αυξάνονται εξαιρετικά όταν κλιμακώνονται κατά δισεκατομμύρια gigabyte.

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

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