15 Algoritmos de Compressão de Dados Mais Populares

Algoritmos de Compressão de Dados podem ser definidos como o processo de redução de tamanhos de arquivos no momento de reter o mesmo ou similar em alguma extensão de dados. Isto é feito através da eliminação de dados desnecessários ou fazendo os dados novamente para maior eficiência.

No momento da compressão, você tem a opção de escolher entre métodos com ou sem perdas. Se falarmos do método com perdas, ele apaga os dados permanentemente. Por outro lado, sem perdas, cuide dos seus dados originais. O tipo que você escolhe depende da qualidade que você precisa que seus arquivos sejam.
Neste artigo, você encontrará uma mistura de algoritmos de compressão de dados sem perdas e algoritmos de compressão de imagem e vídeo baseados em aprendizagem profunda.

Gloritmos de compressão de dados sem perdas são normalmente seres usados para executar a função de arquivo ou qualquer outra função de alta qualidade. Estes algoritmos de compressão de dados permitem executar uma redução do tamanho do arquivo. Ele também garante que os arquivos podem ser restaurados completamente se eles precisarem ser restaurados.

LZ77

LZ77 foi anunciado em 1977 e denominado como a base de tantos outros algoritmos de compressão sem perdas. Normalmente usa o método de “Janela deslizante”. Nesta metodologia, ele cuida de um dicionário que faz uso de triplos para representar:

• Offset- Pode ser denominado como o início real da frase e o início do arquivo.
• Run-length- É definido como a quantidade de caracteres que o ajudam a fazer uma frase.
• Deviating characters- Estes são os comercializadores que indicam uma nova frase.

Inclui uma indicação de que a frase utilizada é completamente igual à frase original e também define se há algum caractere diferente.

Como você vai analisar um arquivo, o dicionário é atualizado dinamicamente para a reflexão do conteúdo e tamanho dos dados comprimidos também.

LZR

LZR foi desenvolvido e anunciado no ano de 1981. Michael Rodeh anunciou-o, e modificou-o mais tarde. Ele pode ser usado como uma alternativa primária para o algoritmo de compressão de dados LZ77, mas você também tem a opção de usá-lo para qualquer offset dentro do arquivo. Se você não o estiver usando linearmente, então ele precisa de uma quantidade significativa de armazenamento de memória. Esta condição faz do LZ77 uma opção melhor para o uso. Este algoritmo de compressão de dados é simples de implementar e tem o potencial para um desempenho muito alto quando implementado em hardware.

É o algoritmo que é amplamente utilizado como utilitário de compressão de dados Unix e é utilizado no formato de imagem GIF. Ele se tornou o primeiro algoritmo de compressão de dados que foi amplamente utilizado em computadores. Um grande arquivo de texto em inglês pode tipicamente ser comprimido de LZW para cerca de metade do seu tamanho original.

LZSS

LZSS significa Lempel Ziv Storer Szymanski e foi desenvolvido e anunciado no ano de 1982. Este é um algoritmo de compressão de dados que melhora o LZ77. Este processo de compressão é feito através da inclusão de um método que irá manter um olho em se uma substituição diminui o tamanho do arquivo. Se não diminuir, então a entrada será deixada na sua forma original. Ele também não prefere o uso de caracteres desviantes, e apenas prefere usar pares de comprimento de offset.

Este algoritmo é usado principalmente para arquivar os arquivos em diferentes formatos como RAR ou ZIP, ou para a compressão de dados de rede.

Pode ser denominado como uma técnica de codificação de dicionário. LZSS tenta substituir uma string de símbolos por uma referência a uma localização de dicionário da mesma string. A diferença chave entre LZ77 e LZSS, na qual em LZ77, a referência do dicionário poderia ser mais longa do que a cadeia de caracteres que estava substituindo. Em LZSS, tais referências são omitidas se o comprimento for menor que o ponto de “break-even”.

Deflate

Deflate é um formato de arquivo com algoritmo de compressão de dados sem perdas que faz uso de uma combinação de codificação LZSS e Huffman. Ele foi projetado por Phil Katz no ano de 1993. A codificação Huffman é também um algoritmo que foi desenvolvido no ano de 1952. Pode ser definido como um algoritmo de codificação de entropia que o ajuda na atribuição do seu código com base na frequência do caractere.

Katz também projetou o algoritmo original que é usado para construir fluxos Deflate. Como foi dito no documento da RFC, um algoritmo que produz arquivos Deflate foi amplamente considerado implementável de uma forma que não foi coberta por patentes. Isto levou à sua utilização generalizada, além do formato de arquivo ZIP que foi o principal objetivo do Katz para desenhá-lo. A patente não está mais disponível.

LZMA

LZMA significa o algoritmo de cadeia Lempel Ziv Markov e foi projetado e lançado no ano de 1998. Também pode ser dito como uma modificação do LZ77. Esta modificação foi feita para o arquivador -Zip com o formato .7z. O método de compressão em cadeia está sendo usado que implementa o LZ77 modificado em um nível de bit e não de byte. A saída que aparece será processada posteriormente usando codificação aritmética para executar mais compressão.

A performance de outros passos de compressão depende da implementação exata. Este algoritmo de compressão de dados usa um esquema de compressão de dicionário algo muito similar ao algoritmo LZ77 que foi publicado por Abraham Lempel e Jacob Ziv no ano de 1977. Ele também apresenta uma alta taxa de compressão e um tamanho variável do dicionário de compressão. Embora ainda mantenha a velocidade de descompressão muito semelhante a outros algoritmos de compressão comumente usados.

LZMA2

LZMA2 foi projetado e lançado no ano de 2009. Também pode ser definido como a modificação do LZMA. Ele torna o LZMA melhor, melhorando seu desempenho com maior capacidade de multithreading. O LZMA2 também lhe proporciona um melhor manuseio de dados incompressíveis. É um formato de contentor simples que pode incluir tanto dados não comprimidos como dados LZMA e que também com vários parâmetros de codificação LZMA diferentes.

LZMA2 suporta arbitrariamente a compressão e descompressão multithreaded escalável e a compressão eficiente de dados que são parcialmente incompressíveis. No entanto, pode ter alguns problemas de segurança e pode ser inseguro e menos eficiente do que o LZMA. Em palavras simples, isto pode ser útil para você, mas sim não é tão seguro em comparação com o LZMA.

Multi-Layer Perceptron (MLP)- Based Compression

MLP pode ser definido como uma tecnologia que usa múltiplas camadas de neurônios para entrada, processamento e fornecimento de dados de saída. Ela pode ser implementada para a redução de tarefas de dimensão e também compressão de dados. O algoritmo baseado no MLP foi desenvolvido pela primeira vez no ano de 1988 e une os processos já existentes de:

• Codificação binária – codificação padrão de dois símbolos.
• Quantificação – problemas de entrada de um conjunto contínuo para um conjunto discreto.
• Transformação do domínio espacial – mudança pixel a pixel para dados.

Para a determinação do código binário ótimo, o algoritmo MLP usa saídas dos processos acima para uma rede neural de decomposição.

Outras, este algoritmo foi modificado com técnicas intuitivas que permitiram uma aproximação precisa dos dados completamente baseada em dados vizinhos através da retropropagação. Ele pode ser muito útil para você na compressão de dados de imagem e vídeo.

Dee Coder- Deep Neural Network Based Video Compression

Deep Coder é definido como uma estrutura baseada em Convolutional Neural Network (CNN). Isso torna a representação de uma alternativa àquelas técnicas de compressão de vídeo que temos usado há tanto tempo. Para sinais preditivos e residuais, diferentes Redes Neurais Convolucionais (CNNs) são trazidas por este modelo.

Realiza a codificação de mapas de características no fluxo binário com o uso de quantização escalar e um algoritmo de compressão de arquivos muito antigo e tradicional chamado Huffman encoding. É afirmado que este modelo é capaz de fornecer um desempenho superior em comparação com o conhecido padrão de codificação de vídeo H.264/AVC.

Convolutional Neural Network (CNN) – Compressão Baseada

CNN’s são definidos como redes neurais de diferentes camadas. Isto é usado principalmente para o reconhecimento de imagens e detecção do recurso. No momento em que você a aplica à compressão, essas redes fazem uso da convolução para calcular a conexão entre os pixels vizinhos. Se compararmos com algoritmos baseados em MLP, as CNNs mostram melhores resultados de compressão do que elas.

Isso também fornece a você melhor desempenho de super-resolução e redução de artefatos. Além disso, os algoritmos de compressão de dados baseados em CNN melhoram a qualidade das imagens JPEG. Isto é feito através da redução da relação sinal/ruído de pico e da similaridade estrutural.

compressão baseada na CNN também pode se juntar ao desempenho do padrão de Codificação de Vídeo de Alta Eficiência. Isto é feito com o uso de estimativa de entropia. Também pode ser muito útil para você na execução da compressão de arquivos.

Generative Adversarial Network (GAN) – Compressão Baseada em GAN

GANs podem ser definidas como uma alternativa de redes neurais que fazem uso de duas redes que competem. Isto é feito para a produção de análises e previsões mais precisas. No ano 2017 foram desenvolvidos os primeiros algoritmos baseados em GAN. Estes algoritmos de compressão de dados podem comprimir os arquivos mais de duas vezes e meia menor em comparação aos métodos tradicionais comumente usados, como JPEG ou WebP.

GAN baseado em algoritmos podem ser usados para compressão em tempo real com processamento paralelo sendo usado em conjunto. Este algoritmo funciona como uma compressão completa das imagens com base nas características mais correspondentes.

Quando a descodificação é executada, com base nas previsões que foram feitas por estas características as imagens são reconstruídas. Se compararmos com a compressão baseada na CNN, a compressão baseada no GAN irá produzir imagens de alta qualidade para você pela eliminação da perda adversa.

Previsão por correspondência parcial (PPM)

PPM é uma técnica adaptativa de compressão de dados estatísticos baseada em modelagem de contexto e previsão. Estes modelos utilizam um conjunto de símbolos anteriores no fluxo de símbolos não comprimidos para prever o próximo símbolo no fluxo. Os algoritmos PPM também podem ser usados para agrupar dados em grupos de previsão na análise de agrupamento.
O número de símbolos anteriores, n, determina a ordem do modelo PPM que é denotado como PPM(n).

Variantes não vinculadas onde o contexto não tem limitações de comprimento também existem e são denotados como PPM. Se nenhuma previsão pode ser feita com base em todos os n símbolos de contexto, uma previsão é tentada com n – 1 símbolo. Este processo é repetido até que uma correspondência seja encontrada ou até que nenhum outro símbolo permaneça no contexto. Nesse ponto, uma previsão fixa é feita.
PPM as implementações de compressão variam muito em outros detalhes. A seleção real do símbolo é geralmente registrada usando codificação aritmética, embora também seja possível usar codificação Huffman ou mesmo algum tipo de técnica de codificação de dicionário.

Codificação por run-length (RLE)

RLW é uma forma de compressão de dados sem perdas na qual execuções de dados (seqüências nas quais o mesmo valor de dados ocorre em muitos elementos de dados consecutivos) são armazenadas como um único valor de dados e contagem, ao invés da execução original. Isto é mais útil em dados que contenham muitas execuções desse tipo.

Por exemplo, imagens gráficas simples como ícones, desenhos de linhas, o Jogo da Vida da Conway, e animações. Não é útil com arquivos que não têm muitas execuções, pois poderia aumentar muito o tamanho do arquivo.

RLE também pode ser usado para se referir a um formato de arquivo gráfico inicial suportado pelo CompuServe para compressão de imagens em preto e branco, mas foi amplamente suplantado pelo seu posterior Graphics Interchange Format (GIF). RLE também se refere a um formato de imagem pouco utilizado no Windows 3.x, com a regra de extensão, que é um Bitmap codificado Run Length, usado para comprimir a tela de inicialização do Windows 3.x.

bzip2

bzip2 é um programa de compressão de dados livre e de código aberto que usa o algoritmo Burrows-Wheeler. Ele só comprime arquivos individuais e não é um arquivador de arquivos. Ele é desenvolvido por Julian Seward e mantido por Federico Mena. Seward fez o primeiro lançamento público do bzip2, versão 0.15, em julho de 1996. A estabilidade e popularidade do compressor cresceu nos anos seguintes, e a Seward lançou a versão 1.0 no final de 2000.

Seguindo um hiato de nove anos de atualizações para o projeto desde 2010. Em 4 de junho de 2019, Federico Mena aceitou a manutenção do projeto bzip2. bzip2 comprime dados em blocos de tamanho entre 100 e 900 kB.

Usa a transformação Burrows-Wheeler para converter sequências de caracteres frequentemente recorrentes em cadeias de letras idênticas. Aplica então a transformação move-to-front e codificação Huffman. bzip2 bzip ancestral usou a codificação aritmética em vez de Huffman. A alteração foi feita devido a uma restrição de patente de software.

codificação Huffman

Código Huffman é um tipo particular de código de prefixo ideal que é comumente usado para compressão de dados sem perdas. O processo de encontrar ou usar tal código procede para utilizar a codificação de Huffman, um algoritmo desenvolvido por David A. Huffman enquanto ele era um estudante de Sc.D. no MIT, e publicado no artigo 1952 “A Method for the Construction of Minimum-Redundancy Codes.

The output from Huffman’s algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). O algoritmo deriva esta tabela da probabilidade estimada ou frequência de ocorrência (peso) para cada valor possível do símbolo da fonte.

Como em outros métodos de codificação de entropia, mais símbolos comuns são geralmente representados usando menos bits do que símbolos menos comuns. O método de Huffman pode ser implementado eficientemente. Encontrar um código no tempo linear ao número de pesos de entrada se esses pesos forem ordenados.

ZStandard

Zstandard (ou zstd) é um algoritmo de compressão de dados sem perdas desenvolvido por Yann Collet no Facebook. Zstd é a implementação de referência em C. A versão 1 desta implementação foi lançada como software livre em 31 de agosto de 2016.
Zstandard foi projetado para dar uma taxa de compressão comparável à do algoritmo DEFLATE (desenvolvido em 1991 e usado nos programas ZIP e gzip originais), mas mais rápido, especialmente para descompressão. É sintonizável com níveis de compressão que variam de 5 negativos (mais rápido) a 22 (mais lento na velocidade de compressão, mas com a melhor taxa de compressão).

Zstd no seu nível máximo de compressão dá uma taxa de compressão próxima a LZMA, LZAHM, e PPM. Tem um melhor desempenho que o LZA, ou bzip2. O Zstandard atinge a fronteira atual de Pareto, pois se descomprime mais rápido do que qualquer outro algoritmo atualmente disponível com uma taxa de compressão similar ou melhor

Dicionários podem ter um grande impacto na taxa de compressão de arquivos pequenos, portanto o Zstandard pode usar um dicionário de compressão fornecido pelo usuário. Ele também oferece um modo de treinamento, capaz de gerar um dicionário a partir de um conjunto de amostras.

Conclusão

Estes algoritmos de compressão de dados irão ajudá-lo a otimizar o tamanho do arquivo. Diferentes tipos de algoritmos de compressão de dados lhe fornecerão resultados diferentes. Entretanto, se você não conseguir encontrar o algoritmo certo aqui, você pode dar uma olhada neste guia e refinar sua pesquisa. Não há falta de algoritmos, mas você precisa ser específico ao procurar o algoritmo certo para o seu projeto.

Eu espero que este artigo tenha sido útil para você escolher o melhor algoritmo de compressão de dados de acordo com as suas necessidades. Obrigado por ler este artigo. Você também pode conferir os algoritmos de Melhor Criptografia e Hashing.

Stay Tuned