Dopo aver visto il drama HBO "Silicon Valley", sono sempre stato interessato agli algoritmi di compressione. Richard Hendricks e il suo algoritmo di compressione middle out sono ovviamente finti, ma dopo aver cercato su Google, ho scoperto che esiste un genio di questo tipo di algoritmo di compressione nella vita reale.
Yann Collet ha inventato l'algoritmo di compressione LZ4 nel 2011. Certo, l'algoritmo LZ4 non è eccezionale come il middle out, ma è noto per la sua velocità di compressione invincibile e la velocità di decompressione più elevata quando è garantita una certa velocità di compressione.
Non entrerò nei dettagli qui sulla valutazione della sua velocità di compressione; se siete interessati, potete leggere questo articolo di confronto:Il login del link ipertestuale è visibile.
È allegato anche l'indirizzo github di LZ4:Il login del link ipertestuale è visibile.
Questo articolo si concentra sull'spiegazione del principio dell'algoritmo di compressione LZ4. Un grande dio scrisse una spiegazione dell'algoritmo LZ4 prima:Il login del link ipertestuale è visibile.Ma quando studiavo prima, sentivo che questo articolo non era molto amichevole per i principianti, così ho iniziato un altro articolo per principianti come me.
Se lo riassumi in una frase, LZ4 è un LZ77 che memorizza un dizionario con una tabella hash di dimensione 16k e semplifica il recupero.
LZ4 è un algoritmo di compressione senza perdita che offre una velocità di compressione di > 500 MB/s per core, scalabile con CPU multi-core. Dispone di decoder estremamente veloci con velocità di diversi GB/s per core, spesso raggiungendo i limiti di velocità della RAM su sistemi multi-core.
La velocità può essere regolata dinamicamente, selezionando un fattore di "accelerazione" che scambia il rapporto di compressione con una velocità più elevata. D'altra parte, è inoltre fornita una derivata ad alta compressione LZ4_HC per aumentare la compressione a scapito del tempo della CPU. Tutte le versioni hanno la stessa velocità di decompressione.
Quindi cos'è LZ77?
Compressione e principio del LZ77
LZ77 è un algoritmo che applica un dizionario per la compressione. In termini semplici, serve a lasciare che il programma osserva (guarda il dizionario) se i dati attualmente visualizzati sono duplicati con quelli precedenti e, in tal caso, salviamo la distanza (offset) e la lunghezza dei campi duplicati per sostituire i campi duplicati e comprimere i dati.
riferimentoIl login del link ipertestuale è visibile.
Per una sequenza di lettere A A B B C, quando viene letta la seconda A, il programma salva (1,1) (1 cifra della precedente, lunghezza 1), e allo stesso modo, quando viene letta la seconda B, il programma salva (2,1) (distanza 2, lunghezza 1).
Ma se la stringa è più lunga e il programma registra i dati nel dizionario continuamente, la ricerca di campi duplicati diventa estremamente dispendiosa in termini di tempo, perché nel peggiore dei casi il programma attraversa l'intero dizionario con ogni nuova lettera leggiata. LZ77 utilizza un metodo a finestra scorrevole per risolvere questo problema.
Similmente al punto di partenza del TCP usando una finestra scorrevole, una finestra scorrevole può ridurre l'area della cache per evitare di elaborare troppi dati memorizzati contemporaneamente. In LZ77, il dizionario non aumenta sempre, ma elimina i primi caratteri aggiunti quando supera la dimensione massima specificata, in modo da garantire che la dimensione del dizionario venga sempre mantenuta alla dimensione massima specificata.
Supponiamo che la lunghezza del dizionario sia 3
| Dizionario |
| A | A B C B B A B C
Output (0,0,A)
| A A | B C B B A B C
Output(1,1)
| A A B | C B B A B C
Produzione (0,0,B)
A | A B C | B B A B C
Output (0,0,C)
A A | B C B | B A B C
Output(2,1)
L'altra parte della finestra scorrevole è la cache da cercare (il buffer di anticipo non ha una traduzione ufficiale). La cache da cercare è la parte non compressa della lunghezza più vicina al dizionario. L'algoritmo LZ77 corrisponderà alla stringa più lunga in questa parte del carattere che è uguale al dizionario. L'esempio precedente può essere considerato come un buffer di anticipazione di 1.
Supponiamo che la lunghezza del dizionario sia 5 e la dimensione della cache da cercare sia 3
| Dizionario | buffer di anticipo |
A | A B C B B | A B C |
Output(5,3)
La stringa più lunga che corrisponde è ABC
Processo completo di compressione:
Supponiamo che la lunghezza del dizionario sia 5 e la dimensione della cache da cercare sia 3
| Dizionario | buffer di anticipo |
| A A B | C B B A B C
Output (0,0,A)
| A | A B C | B B A B C
Output(1,1)
| A A | B C B | B A B C
Produzione (0,0,B)
| A A B | C B | A B C
Output (0,0,C)
| A A B C | B B A | B C
Output(2,1)
| A A B C B | B A B | C
Output(1,1)
A | A B C B B | A B C |
Output(5,3)
A A B C | B B A B C | 。。。 |
Non è necessario salvare il dizionario nel file di uscita del compressore, perché il programma di decompressione ripristina il dizionario abbinando le unità di uscita.
Processo di decompressione
Uno dei grandi vantaggi dell'algoritmo LZ77 è che è molto veloce da decomprimere.
Se la prima unità corrispondente è (0,0,A), allora A è l'output.
La seconda unità corrispondente è (1,1), che copia il bit precedente nella stringa di output e produce A se la lunghezza di copia è 1.
。。。
Se l'ultima unità corrispondente è (5,3), allora guarda indietro 5 bit nella stringa di uscita di copia, e se la lunghezza di copia è 3, allora output A, B, C.
La parte più dispendiosa in termini di tempo della compressione dell'algoritmo LZ77 è trovare il carattere corrispondente più lungo nella cache da cercare nel dizionario. Se il dizionario e la cache da cercare sono troppo brevi, le probabilità di trovare una corrispondenza sono scarse. Pertanto, LZ4 ha modificato l'algoritmo di matching per LZ77.
Innanzitutto, il dizionario dell'algoritmo LZ4 è una tabella hash. La chiave nel dizionario è una stringa da 4 byte, ogni chiave corrisponde a un solo slot, e il valore nello slot è la posizione di questa stringa.
Invece di cercare nella cache, LZ4 legge quattro byte alla volta dal file di input, e poi cerca lo slot corrispondente alla stringa nella tabella hash, che d'ora in poi sarà chiamata stringa presente.
Se hai raggiunto gli ultimi 12 caratteri, inserili direttamente nel file di output.
Se non è assegnato un valore nello slot, significa che i quattro byte appaiono per la prima volta, si aggiungono questi quattro byte e posizioni alla tabella hash e si continua la ricerca.
Se c'è un'assegnazione nello slot, significa che abbiamo trovato un valore corrispondente.
Se il valore nello slot più la dimensione della finestra slider < la posizione del carattere corrente, allora la posizione corrispondente supera la dimensione del blocco e il programma aggiorna il valore nello slot hash alla posizione della stringa corrente.
LZ4 controllerà se c'è stato un conflitto di hash. Se i 4 byte nello slot non sono gli stessi della stringa corrente, deve esserci un conflitto di hash. Il xxhash dell'autore è anche noto per la sua efficienza, ma i conflitti sono inevitabili. In caso di conflitto, il programma aggiorna anche il valore nello slot hash alla posizione corrente della stringa
Infine, possiamo confermare che la corrispondenza è valida e il programma continuerà a verificare se i caratteri successivi nella stringa corrispondente sono gli stessi. Infine, copia tutti i caratteri dalla fine della corrispondenza valida precedente all'inizio di questa corrispondenza valida nel file compresso e aggiungi la sequenza corrispondente di questa corrispondenza valida.
Collet chiama le unità corrispondenti prodotte da sequenze LZ4, che costituiscono il file compresso LZ4. I dettagli sono i seguenti:
Il token è lungo 1 byte, con le prime 4 parole che rappresentano la lunghezza letterale e le ultime 4 parole la lunghezza della corrispondenza. Come menzionato prima, tutti i caratteri dalla fine della corrispondenza valida precedente all'inizio di questa corrispondenza valida saranno copiati in un file compresso, questi file non compressi sono letterali e la loro lunghezza è la lunghezza letterale.
Letteralmente seguita da una deviazione. Come in LZ77, deviazione e lunghezza della corrispondenza si riferiscono alla lunghezza della stringa corrente rispetto alla sua corrispondenza, e la lunghezza della corrispondenza si riferisce alla lunghezza della corrispondenza della stringa attuale con la stessa stringa nel dizionario. In decompressione si tratta di attraversarla per trovare la stringa da copiare e la lunghezza da copiare. La grandezza della deviazione è fissa.
Nella figura, la lunghezza letterale+ e la lunghezza corrispondente+ sono se le parole letterali o corrispondenti di 4 parole nel token non sono sufficienti, continueranno ad aumentare nelle posizioni corrispondenti. 4 parole possono rappresentare da 0 a 15, e se ce ne sono di più, si aggiunge un byte, cioè si aggiungono 255 alla dimensione finché il byte non è inferiore a 255. Nella lunghezza corrispondente, 0 rappresenta 4 byte.
Gli ultimi 12 byte finiscono letteralmente perché sono stati copiati direttamente.
Diamo un'occhiata al codice (python è più astratto)
Riassunto Detto tutto questo, non ho ancora riassunto perché la LZ4 è così veloce. Confrontiamo prima la ricerca nel dizionario tra LZ77 e LZ4. Il LZ77 nativo cerca dizionari cercando la corrispondenza più grande nella cache da cercare e nel dizionario. Questo è un problema nel trovare la stringa identica più grande in due stringhe. Se non usiamo la programmazione dinamica, nel peggiore dei casi dobbiamo considerare tutte le sottostringhe di una stringa e poi abbinarle in un'altra. Se ×usiamo la programmazione dinamica, useremo una tabella per contenere la corrispondenza più lunga nella dinamica, il che ci permetterà di completare la corrispondenza solo nel caso di O(m*n). E questo solo per un paio di cache di ricerca e dizionari. Nel peggiore dei casi, se non ci sono corrispondenze, LZ77 dovrà conteggiare (la lunghezza dell'intero file - la lunghezza della cache da cercare) come molti di questi problemi di corrispondenza. LZ4 utilizza in realtà un livello più ampio di programmazione dinamica: memorizza 4 byte e le loro posizioni in una tabella hash, e poi abbina ogni volta nuovi 4 byte di dati solo per verificare se i valori nella tabella hash sono validi. Dopo aver trovato un valore corrispondente valido, se guardi i dati di seguito dei due insiemi di valori corrispondenti, puoi anche trovare la corrispondenza più lunga. Poiché ogni chiave della tabella hash LZ4 corrisponde a un solo 1 slot, il lavoro di trovare, aggiungere e modificare la tabella hash richiede solo O(1). Se si trovano più corrispondenze dopo l'abbinamento, sono necessarie più confrontazioni di gruppo, ma nel tempo totale questi confronti sostituiranno il tempo necessario per consultare la tabella hash, quindi il tempo totale dell'algoritmo LZ4 è solo O(n). Devo ammirare la bellezza dell'algoritmo di Collet! Per rendere l'algoritmo ancora più veloce, Collet imposta la dimensione predefinita della tabella hash a 16k, raccomandata di non superare i 32k, così da poter essere inserita nella cache L1 di quasi tutte le CPU (Intel). Tutti sanno che la velocità e il rapporto di memoria della cache L1 della CPU sono molto diversi, quindi non sorprende che LZ4 stia volando veloce, senza contare che l'equazione hash usata nella tabella hash di LZ4 è ancora la xxhash più veloce. Naturalmente, un tale design ha i suoi svantaggi. Più piccola è la tabella hash, meno chiavi ha. Questo significa che si verificheranno più conflitti di hash, cosa inevitabile. E più collisioni di hash significano meno corrispondenti. E una tabella hash più piccola significa anche una finestra scorrevole più piccola, il che significa che più corrispondenti verranno scartate perché sono troppo lontane. Meno corrispondenze rappresentano un rapporto di compressione più piccolo, motivo per cui l'LZ4 ha un rapporto di compressione meno evidente. Looking Forward LZ4 offre una vasta gamma di scenari applicabili. Proprio come il middle out è stato usato nella VR nella Silicon Valley, LZ4 può aumentare l'utilizzo della larghezza di banda portando meno IO a scapito di una latenza molto bassa grazie alla sua velocità di compressione molto elevata. C'è anche una piccola ipotesi: se c'è una CPU con una cache più grande al livello 1, l'LZ4 può aumentare il rapporto di compressione senza compromettere la velocità?
Originale:Il login del link ipertestuale è visibile. |
Pubblicato su 03/01/2022 13:54:23
|
|
|
|
