Depois de assistir ao drama da HBO "Vale do Silício", sempre tive interesse em algoritmos de compressão. Richard Hendricks e seu algoritmo de compressão middle out são, claro, falsos, mas depois do Google Hard, descobri que existe esse tipo de gênio do algoritmo de compressão na vida real.
Yann Collet inventou o algoritmo de compressão LZ4 em 2011. Claro, o algoritmo LZ4 não é tão incrível quanto o middle out, mas é conhecido por sua velocidade de compressão invencível e velocidade de descompressão mais rápida quando uma certa taxa de compressão pode ser garantida.
Não vou entrar em detalhes aqui sobre a avaliação da velocidade de compressão; se você tiver interesse, pode ler este artigo comparativo:O login do hiperlink está visível.
Também está anexado o endereço do github do LZ4:O login do hiperlink está visível.
Este artigo foca em explicar o princípio do algoritmo de compressão LZ4. Um grande deus escreveu uma explicação do algoritmo LZ4 antes:O login do hiperlink está visível.Mas quando eu estudava antes, sentia que este artigo não era muito amigável para iniciantes, então comecei outro artigo para iniciantes como eu.
Se você resumir em uma frase, LZ4 é um LZ77 que armazena um dicionário com uma tabela hash de tamanho 16k e simplifica a recuperação.
LZ4 é um algoritmo de compressão sem perdas que oferece uma velocidade de compressão de > 500 MB/s por núcleo, que pode ser escalada com CPUs multi-core. Possui decodificadores extremamente rápidos com velocidades de vários GB/s por núcleo, frequentemente atingindo os limites de velocidade da RAM em sistemas multi-core.
A velocidade pode ser ajustada dinamicamente, selecionando um fator de "aceleração" que troca a taxa de compressão por uma velocidade maior. Por outro lado, também é fornecido um LZ4_HC derivado de alta compressão para aumentar a compressão em detrimento do tempo da CPU. Todas as versões têm a mesma velocidade de descompressão.
Então, o que é o LZ77?
Compressão e princípio do LZ77
LZ77 é um algoritmo que aplica um dicionário para compressão. Em termos simples, é permitir que o programa observe (veja o dicionário) se os dados atualmente vistos estão duplicados com os anteriores e, se sim, salvamos a distância (deslocamento) e o comprimento dos campos duplicados para substituir os campos duplicados e comprimir os dados.
referênciaO login do hiperlink está visível.
Para uma sequência de letras A A B B A B C, quando o segundo A é lido, o programa salva (1,1) (1 dígito do anterior, comprimento 1), e da mesma forma, quando o segundo B é lido, o programa salva (2,1) (distância 2, comprimento 1).
Mas se a string for mais longa e o programa registrar os dados no dicionário o tempo todo, a busca por campos duplicados se torna extremamente demorada, porque no pior dos casos o programa percorre todo o dicionário a cada nova letra lida. O LZ77 utiliza um método de janela deslizante para resolver esse problema.
Semelhante ao ponto de partida do TCP usando uma janela deslizante, uma janela deslizante pode reduzir a área do cache para evitar processar muitos dados armazenados em cache ao mesmo tempo. No LZ77, o dicionário não aumenta o tempo todo, mas descarta os primeiros caracteres adicionados ao dicionário quando ultrapassa o tamanho máximo especificado pelo dicionário, para garantir que o tamanho do dicionário seja sempre mantido no tamanho máximo especificado.
Suponha que o comprimento do dicionário seja 3
| Dicionário |
| A | A B C B B A B C
Saída (0,0,A)
| A A | B C B B A B C
Saída(1,1)
| A A B | C B B A B C
Saída (0,0,B)
A | A B C | B B A B C
Saída (0,0,C)
A A | B C B | B A B C
Saída(2,1)
A outra parte da janela deslizante é o cache a ser buscado (o buffer de antecipação não tem tradução oficial). O cache a ser buscado é a parte não comprimida do comprimento mais próxima do dicionário. O algoritmo LZ77 irá corresponder à string mais longa dessa parte do caractere que é igual ao dicionário. O exemplo anterior pode ser considerado como um buffer de antecipação de 1.
Suponha que o comprimento do dicionário seja 5 e o tamanho do cache a ser buscado seja 3
| Dicionário | Buffer de antecipação |
A | A B C B B | A B C |
Saída(5,3)
A sequência mais longa que combina é ABC
Processo completo de compressão:
Suponha que o comprimento do dicionário seja 5 e o tamanho do cache a ser buscado seja 3
| Dicionário | Buffer de antecipação |
| A A B | C B B A B C
Saída (0,0,A)
| A | A B C | B B A B C
Saída(1,1)
| A A | B C B | B A B C
Saída (0,0,B)
| A A B | C B | A B C
Saída (0,0,C)
| A A B C | B B A | B C
Saída(2,1)
| A A B C B | B A B | C
Saída(1,1)
A | A B C B B | A B C |
Saída(5,3)
A A B C | B B A B C | 。。。 |
Não há necessidade de salvar o dicionário no arquivo de saída do compressor, pois o programa de descompressão restaura o dicionário ao corresponder as unidades de saída.
Processo de descompressão
Uma das grandes vantagens do algoritmo LZ77 é que ele é muito rápido para descomprimir.
Se a primeira unidade correspondente for (0,0,A), então A é saída.
A segunda unidade correspondente é (1,1), que copia o bit anterior na cadeia de saída, e gera A se o comprimento da cópia for 1.
。。。
Se a última unidade correspondente for (5,3), então olhe 5 bits para trás na string de saída da cópia, e se o comprimento da cópia for 3, então saia A, B, C.
A parte mais demorada da compressão do algoritmo LZ77 é encontrar o caractere correspondente mais longo no cache a ser pesquisado no dicionário. Se o dicionário e o cache a ser buscado forem muito curtos, as chances de encontrar uma correspondência são pequenas. Portanto, o LZ4 alterou o algoritmo de correspondência para o LZ77.
Primeiro, o dicionário do algoritmo LZ4 é uma tabela hash. A chave no dicionário é uma string de 4 bytes, cada tecla corresponde a apenas um slot, e o valor no slot é a posição dessa string.
Em vez de buscar no cache, o LZ4 lê quatro bytes por vez do arquivo de entrada e então procura o slot correspondente à string na tabela hash, que daqui em diante será chamada de string atual.
Se você chegou aos últimos 12 caracteres, coloque-os diretamente no arquivo de saída.
Se não houver valor atribuído no slot, significa que os quatro bytes aparecem pela primeira vez, adicionam esses quatro bytes e posições à tabela de hash e continuam a busca.
Se houver uma atribuição no slot, significa que encontramos um valor correspondente.
Se o valor no slot mais o tamanho da janela deslizante < a posição do caractere atual, então a posição de correspondência excede o tamanho do bloco, e o programa atualiza o valor no slot de hash para a posição da string atual.
O LZ4 vai verificar se houve um conflito de hash. Se os 4 bytes no slot não forem iguais à string atual, deve haver um conflito de hash. O próprio xxhash do autor também é conhecido por sua eficiência, mas conflitos são inevitáveis. Em caso de conflito, o programa também atualiza o valor no slot de hash para a posição atual da string
Finalmente, podemos confirmar que a correspondência é válida, e o programa continuará para verificar se os caracteres seguintes na sequência correspondente são os mesmos. Por fim, copie todos os caracteres do final da correspondência válida anterior para o início dessa correspondência válida no arquivo comprimido e adicione a sequência correspondente dessa correspondência válida.
Collet chama as unidades correspondentes de saída por sequências LZ4, que compõem o arquivo comprimido LZ4. Os detalhes são os seguintes:
O token tem 1 byte de comprimento, sendo as primeiras 4 palavras o comprimento literal e as últimas 4 palavras o comprimento da correspondência. Como mencionado anteriormente, todos os caracteres do final da correspondência válida anterior até o início dessa correspondência válida serão copiados para um arquivo comprimido, esses arquivos não comprimidos são literais, e seu comprimento é o comprimento literal.
Literalmente seguido por desvio. Assim como no LZ77, desvio e comprimento de correspondência referem-se ao comprimento da string atual em relação à sua correspondência, e o comprimento da correspondência refere-se ao comprimento do comprimento da correspondência da string atual com a mesma string no dicionário. Na descompressão, é passar por ela para encontrar a corda a ser copiada e o comprimento a ser copiado. A magnitude do desvio é fixa.
Na figura, comprimento+ literal+ e comprimento de correspondência+ são que, se as palavras literais ou de comprimento de correspondência 4 no token não forem suficientes, elas continuarão a aumentar nas posições correspondentes. 4 palavras podem representar de 0 a 15, e se houver mais, adiciona um byte, ou seja, adiciona 255 ao tamanho até que o byte seja menor que 255. No comprimento correspondente, 0 representa 4 bytes.
Os últimos 12 bytes terminam literalmente porque foram copiados diretamente.
Vamos olhar para o código (python é mais abstrato)
Resumo Dito tudo isso, ainda não resumi por que o LZ4 é tão rápido. Vamos primeiro comparar a busca no dicionário entre LZ77 e LZ4. O LZ77 nativo busca dicionários procurando a maior correspondência no cache a ser pesquisado e no dicionário. Esse é um problema de encontrar a maior cadeia idêntica em duas cadeias. Se não usarmos programação dinâmica, no pior dos casos temos que considerar todas as substrings de uma string e então combiná-las em outra. Se ×usarmos programação dinâmica, usaremos uma tabela para manter a correspondência mais longa na dinâmica, o que só nos permitirá completar a correspondência no caso de O(m*n). E isso é só para um par de caches de busca e dicionários. No pior caso, se não houver correspondências, o LZ77 terá que contar (o comprimento de todo o arquivo - o comprimento do cache a ser buscado) como muitos desses problemas de correspondência. O LZ4 na verdade usa um nível maior de programação dinâmica: ele armazena 4 bytes e suas posições em uma tabela hash, e depois corresponde a 4 novos bytes de dados a cada vez apenas para verificar se os valores na tabela hash são válidos. Após encontrar um valor de correspondência válido, se você olhar os dados de acompanhamento dos dois conjuntos de valores correspondentes, também pode encontrar a correspondência mais longa. Como cada chave da tabela hash do LZ4 corresponde a apenas 1 slot, o trabalho de encontrar, adicionar e modificar a tabela de hash requer apenas O(1). Se mais correspondências forem encontradas após o matching, mais comparações de grupos são necessárias, mas no tempo total, essas comparações substituirão mais tempo para consultar a tabela hash, então o tempo total do algoritmo LZ4 é apenas O(n). Tenho que admirar a beleza do algoritmo de Collet! Para tornar o algoritmo ainda mais rápido, o Collet define o tamanho padrão da tabela de hash em 16k, o que é recomendado não exceder 32k, para que possa ser colocado no cache L1 de quase todas as CPUs (Intel). Todo mundo sabe que a velocidade e a razão de memória do cache L1 da CPU são muito diferentes, então não é surpresa que o LZ4 esteja voando rápido, sem contar que a equação de hash usada na tabela de hash do LZ4 ainda é a xxhash mais rápida. Claro, esse tipo de design tem suas desvanências. Quanto menor a tabela de hash, menos chaves ela tem. Isso significa que mais conflitos de hash vão ocorrer, o que é inevitável. E mais colisões de hash significam menos correspondências. E uma tabela de hash menor também significa uma janela deslizante menor, o que significa que mais matches serão descartados porque estão muito longe. Menos correspondências representam uma taxa de compressão menor, por isso o LZ4 tem uma taxa de compressão menos proeminente. O Looking Future LZ4 oferece uma ampla variedade de cenários de aplicação. Assim como o middle out foi usado em VR no Vale do Silício, o LZ4 pode aumentar a utilização da largura de banda ao trazer menos IOs, ao custo de uma latência muito baixa devido à sua velocidade de compressão muito rápida. Também há uma pequena conjectura: se houver um processador com cache maior no nível 1, o LZ4 pode aumentar a taxa de compressão sem comprometer a velocidade?
Original:O login do hiperlink está visível. |
Publicado em 03/01/2022 13:54:23
|
|
|
|
