Αφού παρακολούθησα το δράμα του HBO "Silicon Valley", πάντα με ενδιέφεραν οι αλγόριθμοι συμπίεσης. Ο Richard Hendricks και ο αλγόριθμος συμπίεσης του middle out σε αυτό είναι φυσικά ψεύτικοι, αλλά μετά το Google hard, διαπίστωσα ότι υπάρχει μια τέτοια ιδιοφυΐα αλγορίθμου συμπίεσης στην πραγματική ζωή.
Ο Yann Collet εφηύρε τον αλγόριθμο συμπίεσης LZ4 το 2011. Φυσικά, ο αλγόριθμος LZ4 δεν είναι τόσο φοβερός όσο το middle out, αλλά είναι γνωστός για την ανίκητη ταχύτητα συμπίεσης και τη μεγαλύτερη ταχύτητα αποσυμπίεσης όταν μπορεί να εγγυηθεί ένας συγκεκριμένος ρυθμός συμπίεσης.
Δεν θα υπεισέλθω σε λεπτομέρειες εδώ σχετικά με την αξιολόγηση της ταχύτητας συμπίεσής του, αν σας ενδιαφέρει, μπορείτε να διαβάσετε αυτό το άρθρο σύγκρισης:Η σύνδεση με υπερσύνδεσμο είναι ορατή.
Επισυνάπτεται επίσης η διεύθυνση github του LZ4:Η σύνδεση με υπερσύνδεσμο είναι ορατή.
Αυτό το άρθρο εστιάζει στην εξήγηση της αρχής του αλγορίθμου συμπίεσης LZ4. Ένας μεγάλος θεός έγραψε μια εξήγηση του αλγορίθμου LZ4 πριν:Η σύνδεση με υπερσύνδεσμο είναι ορατή.Αλλά όταν σπούδαζα πριν, ένιωσα ότι αυτό το άρθρο δεν ήταν πολύ φιλικό προς τους αρχάριους, οπότε ξεκίνησα ένα άλλο άρθρο για αρχάριους σαν εμένα.
Αν το συνοψίσετε σε μία πρόταση, το LZ4 είναι ένα LZ77 που αποθηκεύει ένα λεξικό με πίνακα κατακερματισμού μεγέθους 16k και απλοποιεί την ανάκτηση.
Ο LZ4 είναι ένας αλγόριθμος συμπίεσης χωρίς απώλειες που προσφέρει ταχύτητα συμπίεσης > 500 MB/s ανά πυρήνα, η οποία μπορεί να κλιμακωθεί με επεξεργαστές πολλαπλών πυρήνων. Διαθέτει εξαιρετικά γρήγορους αποκωδικοποιητές με ταχύτητες αρκετών GB/s ανά πυρήνα, φτάνοντας συχνά τα όρια ταχύτητας RAM σε συστήματα πολλαπλών πυρήνων.
Η ταχύτητα μπορεί να ρυθμιστεί δυναμικά, επιλέγοντας έναν συντελεστή «επιτάχυνσης» που ανταλλάσσει την αναλογία συμπίεσης για μεγαλύτερη ταχύτητα. Από την άλλη, παρέχεται επίσης ένα παράγωγο υψηλής συμπίεσης LZ4_HC για την αύξηση της συμπίεσης σε βάρος του χρόνου της CPU. Όλες οι εκδόσεις έχουν την ίδια ταχύτητα αποσυμπίεσης.
Τι είναι λοιπόν το LZ77;
Συμπίεση και αρχή LZ77
Ο LZ77 είναι ένας αλγόριθμος που εφαρμόζει ένα λεξικό για συμπίεση. Με απλούς όρους, είναι να αφήσουμε το πρόγραμμα να παρατηρήσει (κοιτάξτε το λεξικό) εάν τα δεδομένα που εμφανίζονται αυτήν τη στιγμή είναι διπλά με τα προηγούμενα, και αν ναι, αποθηκεύουμε την απόσταση (μετατόπιση) και το μήκος των διπλών πεδίων για να αντικαταστήσουμε τα διπλά πεδία και να συμπιέσουμε τα δεδομένα.
αναφοράΗ σύνδεση με υπερσύνδεσμο είναι ορατή.
Για μια σειρά γραμμάτων A A B C B B A B C, όταν διαβάζεται το δεύτερο Α, το πρόγραμμα αποθηκεύει (1,1) (1 ψηφίο από το προηγούμενο, μήκος 1) και ομοίως, όταν διαβάζεται το δεύτερο Β, το πρόγραμμα αποθηκεύει (2,1) (απόσταση 2, μήκος 1).
Αλλά αν η συμβολοσειρά είναι μεγαλύτερη και το πρόγραμμα καταγράφει τα δεδομένα στο λεξικό όλη την ώρα, η αναζήτηση διπλότυπων πεδίων γίνεται εξαιρετικά χρονοβόρα, επειδή στη χειρότερη περίπτωση το πρόγραμμα περνά από ολόκληρο το λεξικό με κάθε νέο γράμμα που διαβάζεται. Το LZ77 χρησιμοποιεί μια μέθοδο συρόμενου παραθύρου για να λύσει αυτό το πρόβλημα.
Παρόμοια με το σημείο εκκίνησης του TCP χρησιμοποιώντας ένα συρόμενο παράθυρο, ένα συρόμενο παράθυρο μπορεί να συρρικνώσει την περιοχή της προσωρινής μνήμης για να αποφύγει την ταυτόχρονη επεξεργασία πάρα πολλών αποθηκευμένων δεδομένων στο cache. Στο LZ77, το λεξικό δεν αυξάνεται συνεχώς, αλλά απορρίπτει τους πρώτους χαρακτήρες που προστίθενται στο λεξικό όταν υπερβαίνει το μέγιστο μέγεθος που καθορίζεται από το λεξικό, έτσι ώστε να διασφαλίζεται ότι το μέγεθος του λεξικού διατηρείται πάντα στο καθορισμένο μέγιστο μέγεθος.
Ας υποθέσουμε ότι το μήκος του λεξικού είναι 3
| λεξικό |
| Α | Α Β Γ Β Β Α Β Γ
Έξοδος (0,0,A)
| Α Α | Β Γ Β Β Α Β Γ
Παραγωγή(1,1)
| Α Α Β | Γ Β Β Α Β Γ
Έξοδος (0,0,B)
Α | Α Β Γ | Β Β Α Β Γ
Έξοδος (0,0,C)
Α Α | Β Γ Β | Β Α Β Γ
Παραγωγή(2,1)
Το άλλο μέρος του συρόμενου παραθύρου είναι η κρυφή μνήμη προς αναζήτηση (το buffer look ahead δεν έχει επίσημη μετάφραση). Η κρυφή μνήμη προς αναζήτηση είναι το ασυμπίεστο τμήμα του μήκους που βρίσκεται πιο κοντά στο λεξικό. Ο αλγόριθμος LZ77 θα ταιριάζει με τη μεγαλύτερη συμβολοσειρά σε αυτό το τμήμα του χαρακτήρα που είναι ίδια με το λεξικό. Το προηγούμενο παράδειγμα μπορεί να θεωρηθεί ως ένα buffer προοπτικής του 1.
Ας υποθέσουμε ότι το μήκος του λεξικού είναι 5 και το μέγεθος της κρυφής μνήμης που θα αναζητηθεί είναι 3
| λεξικό | Κοιτάξτε μπροστά buffer |
Α | Α Β Γ Β Β | Α Β Γ |
Παραγωγή(5,3)
Η μεγαλύτερη συμβολοσειρά που ταιριάζει είναι το ABC
Ολοκληρωμένη διαδικασία συμπίεσης:
Ας υποθέσουμε ότι το μήκος του λεξικού είναι 5 και το μέγεθος της κρυφής μνήμης που θα αναζητηθεί είναι 3
| λεξικό | Κοιτάξτε μπροστά buffer |
| Α Α Β | Γ Β Β Α Β Γ
Έξοδος (0,0,A)
| Α | Α Β Γ | Β Β Α Β Γ
Παραγωγή(1,1)
| Α Α | Β Γ Β | Β Α Β Γ
Έξοδος (0,0,B)
| Α Α Β | Γ Β Β | Α Β Γ
Έξοδος (0,0,C)
| Α Α Β Γ | Β Β Α | Β Γ
Παραγωγή(2,1)
| Α Α Β Γ Β | Β Α Β | C
Παραγωγή(1,1)
Α | Α Β Γ Β Β | Α Β Γ |
Παραγωγή(5,3)
Α Α Β Γ | Β Β Α Β Γ | 。。。 |
Δεν χρειάζεται να αποθηκεύσετε το λεξικό στο αρχείο εξόδου του συμπιεστή, επειδή το πρόγραμμα αποσυμπίεσης επαναφέρει το λεξικό ταιριάζοντας τις μονάδες εξόδου.
Διαδικασία αποσυμπίεσης
Ένα από τα μεγάλα πλεονεκτήματα του αλγορίθμου LZ77 είναι ότι αποσυμπιέζεται πολύ γρήγορα.
Εάν η πρώτη μονάδα αντιστοίχισης είναι (0,0,A), τότε εξάγεται το A.
Η δεύτερη μονάδα αντιστοίχισης είναι η (1,1), η οποία αντιγράφει το προηγούμενο bit στη συμβολοσειρά εξόδου και εξάγει το A εάν το μήκος του αντιγράφου είναι 1.
。。。
Εάν η τελευταία μονάδα που ταιριάζει είναι (5,3), τότε κοιτάξτε πίσω 5 bit στη συμβολοσειρά εξόδου του αντιγράφου και εάν το μήκος του αντιγράφου είναι 3, τότε εξάγετε τα A, B, C.
Το πιο χρονοβόρο μέρος της συμπίεσης του αλγορίθμου LZ77 είναι η εύρεση του μεγαλύτερου χαρακτήρα που ταιριάζει στην κρυφή μνήμη που θα αναζητηθεί στο λεξικό. Εάν το λεξικό και η κρυφή μνήμη προς αναζήτηση είναι πολύ μικρά, οι πιθανότητες να βρεθεί ένα ταίριασμα είναι ελάχιστες. Επομένως, το LZ4 άλλαξε τον αλγόριθμο αντιστοίχισης για το LZ77.
Πρώτον, το λεξικό του αλγορίθμου LZ4 είναι ένας πίνακας κατακερματισμού. Το κλειδί στο λεξικό είναι μια συμβολοσειρά 4 byte, κάθε κλειδί αντιστοιχεί μόνο σε μία υποδοχή και η τιμή στην υποδοχή είναι η θέση αυτής της συμβολοσειράς.
Αντί να κάνει αναζήτηση στην κρυφή μνήμη, το LZ4 διαβάζει τέσσερα byte κάθε φορά από το αρχείο εισόδου και, στη συνέχεια, αναζητά την υποδοχή που αντιστοιχεί στη συμβολοσειρά στον πίνακα κατακερματισμού, η οποία στο εξής αναφέρεται ως η παρούσα συμβολοσειρά.
Εάν έχετε φτάσει τους τελευταίους 12 χαρακτήρες, τοποθετήστε τους απευθείας στο αρχείο εξόδου.
Εάν δεν έχει εκχωρηθεί τιμή στην υποδοχή, σημαίνει ότι τα τέσσερα byte εμφανίζονται για πρώτη φορά, προσθέστε αυτά τα τέσσερα byte και θέσεις στον πίνακα κατακερματισμού και συνεχίστε την αναζήτηση.
Εάν υπάρχει ανάθεση στην υποδοχή, σημαίνει ότι βρήκαμε μια αντίστοιχη τιμή.
Εάν η τιμή στην υποδοχή συν το μέγεθος του παραθύρου του ρυθμιστικού < τη θέση του τρέχοντος χαρακτήρα, τότε η θέση αντιστοίχισης υπερβαίνει το μέγεθος του μπλοκ και το πρόγραμμα ενημερώνει την τιμή στην υποδοχή κατακερματισμού στη θέση της τρέχουσας συμβολοσειράς.
Το LZ4 θα ελέγξει εάν υπήρξε διένεξη κατακερματισμού. Εάν τα 4 byte στην υποδοχή δεν είναι ίδια με την τρέχουσα συμβολοσειρά, πρέπει να υπάρχει διένεξη κατακερματισμού. Το xxhash του ίδιου του συγγραφέα είναι επίσης γνωστό για την αποτελεσματικότητά του, αλλά οι συγκρούσεις είναι αναπόφευκτες. Σε περίπτωση διένεξης, το πρόγραμμα ενημερώνει επίσης την τιμή στην υποδοχή κατακερματισμού στην τρέχουσα θέση της συμβολοσειράς
Τέλος, μπορούμε να επιβεβαιώσουμε ότι η αντιστοίχιση είναι έγκυρη και το πρόγραμμα θα συνεχίσει να βλέπει εάν οι επόμενοι χαρακτήρες στην αντίστοιχη συμβολοσειρά είναι ίδιοι. Τέλος, αντιγράψτε όλους τους χαρακτήρες από το τέλος της προηγούμενης έγκυρης αντιστοίχισης στην αρχή αυτής της έγκυρης αντιστοίχισης στο συμπιεσμένο αρχείο και προσθέστε την ακολουθία αντιστοίχισης αυτής της έγκυρης αντιστοίχισης.
Το Collet καλεί τις αντίστοιχες μονάδες που εξάγονται από ακολουθίες LZ4 και αποτελούν το συμπιεσμένο αρχείο LZ4. Οι λεπτομέρειες έχουν ως εξής:
Το διακριτικό έχει μήκος 1 byte, με τις πρώτες 4 λέξεις να είναι το κυριολεκτικό μήκος και οι τελευταίες 4 λέξεις να είναι το μήκος αντιστοίχισης. Όπως αναφέρθηκε προηγουμένως, όλοι οι χαρακτήρες από το τέλος της προηγούμενης έγκυρης αντιστοίχισης έως την αρχή αυτής της έγκυρης αντιστοίχισης θα αντιγραφούν σε ένα συμπιεσμένο αρχείο, αυτά τα ασυμπίεστα αρχεία είναι κυριολεκτικά και το μήκος τους είναι κυριολεκτικό μήκος.
Κυριολεκτικά ακολουθείται από απόκλιση. Όπως και στο LZ77, η απόκλιση και το μήκος αντιστοίχισης αναφέρονται στο μήκος της τρέχουσας συμβολοσειράς από την αντιστοίχιση της και το μήκος αντιστοίχισης αναφέρεται στο μήκος του μήκους αντιστοίχισης της παρούσας συμβολοσειράς στην ίδια συμβολοσειρά στο λεξικό. Στην αποσυμπίεση είναι να το περάσετε για να βρείτε τη συμβολοσειρά που θα αντιγραφεί και το μήκος που θα αντιγράψετε. Το μέγεθος της απόκλισης είναι σταθερό.
Στο σχήμα, το κυριολεκτικό μήκος+ και το μήκος αντιστοίχισης+ είναι εάν οι κυριολεκτικές λέξεις ή το μήκος αντιστοίχισης 4 λέξεων στο διακριτικό δεν είναι αρκετές, θα συνεχίσουν να αυξάνονται στις αντίστοιχες θέσεις. 4 λέξεις μπορούν να αντιπροσωπεύουν 0-15 και αν υπάρχουν περισσότερες, προσθέστε ένα byte, δηλαδή προσθέστε 255 στο μέγεθος έως ότου το byte είναι μικρότερο από 255. Στο μήκος αντιστοίχισης, το 0 αντιπροσωπεύει 4 byte.
Τα τελευταία 12 byte τελειώνουν κυριολεκτικά επειδή αντιγράφηκαν απευθείας.
Ας δούμε τον κώδικα (η python είναι πιο αφηρημένη)
Περίληψη Έχοντας πει όλα αυτά, ακόμα δεν έχω συνοψίσει γιατί το LZ4 είναι τόσο γρήγορο. Ας συγκρίνουμε πρώτα την αναζήτηση λεξικού μεταξύ LZ77 και LZ4. Το εγγενές LZ77 αναζητά λεξικά αναζητώντας τη μεγαλύτερη αντιστοίχιση στην κρυφή μνήμη προς αναζήτηση και στο λεξικό. Αυτό είναι ένα πρόβλημα εύρεσης της μεγαλύτερης πανομοιότυπης συμβολοσειράς σε δύο συμβολοσειρές. Εάν δεν χρησιμοποιούμε δυναμικό προγραμματισμό, τότε στη χειρότερη περίπτωση πρέπει να εξετάσουμε όλες τις υποσυμβολοσειρές μιας συμβολοσειράς και στη συνέχεια να τις ταιριάξουμε σε μια άλλη συμβολοσειρά. Εάν ×χρησιμοποιήσουμε δυναμικό προγραμματισμό, θα χρησιμοποιήσουμε έναν πίνακα για να κρατήσουμε τη μεγαλύτερη αντιστοίχιση στη δυναμική, η οποία θα μας επιτρέψει να ολοκληρώσουμε την αντιστοίχιση μόνο στην περίπτωση του O(m*n). Και, αυτό είναι μόνο για ένα ζευγάρι κρυφές μνήμες αναζήτησης και λεξικά. Στη χειρότερη περίπτωση, εάν δεν υπάρχουν αντιστοιχίσεις, τότε το LZ77 θα πρέπει να μετρήσει (το μήκος ολόκληρου του αρχείου - το μήκος της προσωρινής μνήμης που θα αναζητηθεί) ως πολλά τέτοια προβλήματα αντιστοίχισης. Το LZ4 χρησιμοποιεί στην πραγματικότητα ένα μεγαλύτερο επίπεδο δυναμικού προγραμματισμού: αποθηκεύει 4 byte και τις θέσεις τους σε έναν πίνακα κατακερματισμού και, στη συνέχεια, αντιστοιχίζει νέα 4 byte δεδομένων κάθε φορά μόνο για να δει εάν οι τιμές στον πίνακα κατακερματισμού είναι έγκυρες. Αφού βρείτε μια έγκυρη τιμή αντιστοίχισης, αν κοιτάξετε τα δεδομένα παρακολούθησης των δύο συνόλων τιμών που ταιριάζουν, μπορείτε επίσης να βρείτε τη μεγαλύτερη αντιστοιχία. Δεδομένου ότι κάθε κλειδί του πίνακα κατακερματισμού LZ4 αντιστοιχεί μόνο σε 1 υποδοχή, η εργασία εύρεσης, προσθήκης και τροποποίησης του πίνακα κατακερματισμού απαιτεί μόνο O(1). Εάν βρεθούν περισσότερες αντιστοιχίσεις μετά την αντιστοίχιση, χρειάζονται περισσότερες συγκρίσεις ομάδων, αλλά στο συνολικό χρόνο, αυτές οι συγκρίσεις θα αντικαταστήσουν περισσότερο χρόνο για την αναζήτηση του πίνακα κατακερματισμού, επομένως ο συνολικός χρόνος του αλγορίθμου LZ4 είναι μόνο O(n). Πρέπει να θαυμάσω την ομορφιά του αλγορίθμου του Collet! Για να κάνει τον αλγόριθμο ακόμα πιο γρήγορο, ο Collet ορίζει το προεπιλεγμένο μέγεθος του πίνακα κατακερματισμού στα 16k, το οποίο συνιστάται να μην υπερβαίνει τα 32k, ώστε να μπορεί να τοποθετηθεί στην κρυφή μνήμη L1 σχεδόν όλων των CPU (Intel). Όλοι γνωρίζουν ότι η ταχύτητα και η αναλογία μνήμης της κρυφής μνήμης CPU L1 είναι πολύ διαφορετικές, επομένως δεν προκαλεί έκπληξη το γεγονός ότι το LZ4 πετάει γρήγορα, για να μην αναφέρουμε ότι η εξίσωση κατακερματισμού που χρησιμοποιείται στον πίνακα κατακερματισμού του LZ4 εξακολουθεί να είναι το ταχύτερο xxhash. Φυσικά, ένα τέτοιο σχέδιο έχει τα μειονεκτήματά του. Όσο μικρότερος είναι ο πίνακας κατακερματισμού, τόσο λιγότερα κλειδιά έχει. Αυτό σημαίνει ότι θα προκύψουν περισσότερες συγκρούσεις κατακερματισμού, κάτι που είναι αναπόφευκτο. Και περισσότερες συγκρούσεις κατακερματισμού σημαίνουν λιγότερους αγώνες. Και ένας μικρότερος πίνακας κατακερματισμού σημαίνει επίσης μικρότερο συρόμενο παράθυρο, πράγμα που σημαίνει ότι περισσότερες αντιστοιχίσεις θα απορριφθούν επειδή είναι πολύ μακριά. Λιγότερες αντιστοιχίσεις αντιπροσωπεύουν μικρότερο λόγο συμπίεσης, γι' αυτό το LZ4 έχει λιγότερο εμφανή λόγο συμπίεσης. Κοιτάζοντας μπροστά, το LZ4 έχει ένα ευρύ φάσμα σεναρίων εφαρμογής. Ακριβώς όπως το middle out χρησιμοποιήθηκε στο VR στη Silicon Valley, το LZ4 μπορεί να αυξήσει τη χρήση του εύρους ζώνης φέρνοντας λιγότερα IO με κόστος πολύ χαμηλής καθυστέρησης λόγω της πολύ γρήγορης ταχύτητας συμπίεσης. Υπάρχει επίσης μια μικρή εικασία, εάν υπάρχει CPU με μεγαλύτερη κρυφή μνήμη στο επίπεδο 1, μπορεί το LZ4 να αυξήσει την αναλογία συμπίεσης χωρίς συμβιβασμούς στην ταχύτητα;
Αρχικός:Η σύνδεση με υπερσύνδεσμο είναι ορατή. |
Δημοσιεύτηκε στις 3/1/2022 1:54:23 μ.μ.
|
|
|
|
