Os algoritmos de compressão binária funcionam identificando e explorando padrões, redundâncias e probabilidades estatísticas dentro dos dados binários de um arquivo. Eles conseguem isso através de uma variedade de técnicas, amplamente categorizadas como compressão sem perdas e com perdas. Vamos nos concentrar na compactação sem perdas, pois é usada para preservar os dados originais exatos.

Aqui está um detalhamento dos métodos comuns de compressão binária sem perdas:

1. Identificando redundância e padrões:

* Repetição: A forma mais simples. Se o mesmo byte ou sequência de bytes se repetir várias vezes, o algoritmo os substituir por um marcador indicando a sequência repetida e o número de repetições. Isso é frequentemente chamado de codificação run-comprimento (rle) . Por exemplo:
* Original:`aaaaabbbbcccdd`
* Rle comprimido:`5a3b3c2d` (5 a, 3 b's, 3 c's, 2 d'S)
* O RLE é mais eficaz quando há longas execuções dos mesmos dados.
* Compressão baseada no dicionário: Este método constrói um dicionário (ou tabela) de sequências de bytes que ocorrem frequentemente. Em vez de armazenar a sequência completa a cada vez, o algoritmo armazena o índice (ou código) representando essa sequência no dicionário.
* lz77 e lz78 (e suas variantes lzw, deflate): Estes são algoritmos baseados no dicionário da Cornerstone. Eles trabalham mantendo uma janela deslizante de dados vistos recentemente.
* lz77: Procura sequências correspondentes * dentro * da janela deslizante. Quando encontra uma correspondência, armazena um par `(distância, comprimento)`, onde:
* `distance`:quão longe a janela inicia a partida.
* `comprimento`:quanto tempo é a sequência correspondente.
* lz78: Construa um dicionário de * novas * frases enquanto as encontra. Ele codifica cada nova frase como `(índice, caractere)`, onde:
* `index`:o índice do prefixo * mais longo * da frase já no dicionário.
* `personagem`:o personagem que estende o prefixo para criar a nova frase.
* lzw (lempel-ziv-welch): Uma melhoria do LZ78. Começa com um dicionário pré-inicializado contendo todos os caracteres únicos. Ele constrói o dicionário dinamicamente à medida que processa os dados. A LZW é famosa por ser usada no formato da imagem do GIF (embora as patentes na LZW tenham causado problemas por um tempo).
* deflatar: Combina LZ77 com a codificação Huffman (explicada abaixo) para uma compressão ainda melhor. É usado em gzip, zlib e png. É muito comum.

2. Codificação estatística (codificação de entropia):

* Esses métodos analisam a frequência de diferentes símbolos (bytes) nos dados e atribuem códigos mais curtos a símbolos mais frequentes e códigos mais longos a outros menos frequentes. Isso se baseia na teoria da informação, onde eventos mais prováveis ​​exigem menos informações para transmitir.
* Codificação de Huffman: Um esquema de codificação de comprimento de variável. Ele constrói uma árvore binária com base nas frequências dos símbolos. Os símbolos mais frequentes são colocados mais perto da raiz da árvore, resultando em comprimentos de código mais curtos.
* O algoritmo gera um código de prefixo, o que significa que nenhum código é um prefixo de outro código, impedindo a ambiguidade durante a decodificação.
* codificação aritmética: Representa todo o fluxo de dados como um único número fracionário entre 0 e 1. O comprimento da fração é determinado pelas probabilidades dos símbolos. A codificação aritmética geralmente atinge melhor compressão do que a codificação de Huffman, especialmente ao lidar com símbolos com probabilidades muito diferentes. É mais intensivo computacional, no entanto.

Exemplo ilustrativo (simplificado):

Imagine que temos os seguintes dados:`AABBBCCCAADDDEEFFFF`

1. rle: Pode comprimir para `2a3b3c2a3d3e4f` (reduz, mas não drasticamente).

2. Codificação de Huffman:
* Análise de frequência:
* A:5
* B:3
* C:3
* D:3
* E:3
* F:4
* Huffman Tree Construction (exemplo):
* Combine menos frequente:B (3) e C (3) -> Nó BC (6)
* Combine d (3) e e (3) -> nó de (6)
* Combine BC (6) e DE (6) -> Nó BCDE (12)
* Combine F (4) e A (5) -> Nó AF (9)
* Combine AF (9) e BCDE (12) -> Raiz (21)
* Atribuir códigos (0 para a esquerda, 1 para atravessar a direita na árvore) - * Isso pode variar com base na implementação! *
* A:00
* B:100
* C:101
* D:110
* E:111
* F:01
* Dados compactados:`0000100100100101101101101111111111101010101` (muito mais curto que o original, especialmente para grandes conjuntos de dados!)

Considerações importantes:

* Complexidade: Diferentes algoritmos têm diferentes complexidades computacionais. Alguns são mais rápidos para codificar/decodificar, mas alcançam taxas de compressão mais baixas. Outros são mais lentos, mas alcançam maior compressão.
* Taxa de compressão : A proporção do tamanho do arquivo original e o tamanho do arquivo compactado. Uma proporção mais alta indica melhor compressão.
* Uso da memória: Os algoritmos requerem memória para buffers, dicionários e estruturas de árvores. O uso da memória pode ser um fator limitante, especialmente ao compactar arquivos grandes.
* Tipo de dados: Alguns algoritmos são mais adequados para tipos específicos de dados (por exemplo, texto, imagens, áudio). Por exemplo, algoritmos que exploram a localidade espacial são bons para imagens.

Em resumo, os algoritmos de compressão binária funcionam por:

1. Analisando os dados: Identificando padrões, repetições e frequências estatísticas.
2. representando os dados com mais eficiência: Usando códigos mais curtos para elementos comuns e códigos mais longos para elementos raros.
3. armazenando metadados: Armazenamento de informações necessárias para descomprimir os dados (por exemplo, dicionários, árvores de Huffman).

A escolha do algoritmo depende dos requisitos específicos do aplicativo, incluindo a taxa de compressão desejada, os recursos computacionais disponíveis e o tipo de dados que está sendo compactado. Freqüentemente, as abordagens híbridas (como o deflate) são usadas para combinar os pontos fortes de diferentes técnicas.