# Compressão de Dados (Data Compression)

### 📌 Visão Geral

**Compressão de dados** é o processo de codificar informações usando menos bits do que a representação original. É fundamental para reduzir tamanho de arquivos, economizar banda e armazenamento.

```
Dados Originais (100 MB)
        ↓
    Compressor
        ↓
Dados Comprimidos (30 MB) → Transmissão/Armazenamento → Descompressor → Dados Originais
```

#### Analogia

> *"Compressão é como dobrar roupas para caberem em uma mala menor: você reorganiza o espaço para que mais coisas caibam, mas precisa desdobrar para usar novamente."*

***

### 🏷️ Tipos de Compressão

| Tipo                     | Descrição                                                 | Perda de Informação | Exemplos        |
| ------------------------ | --------------------------------------------------------- | ------------------- | --------------- |
| **Lossless (Sem perda)** | Dados originais são recuperados integralmente             | ❌ Nenhuma           | ZIP, PNG, FLAC  |
| **Lossy (Com perda)**    | Dados são aproximados (descartam detalhes imperceptíveis) | ✅ Sim               | JPEG, MP3, MPEG |

#### Quando usar cada tipo

| Cenário                  | Tipo     | Por que                                |
| ------------------------ | -------- | -------------------------------------- |
| Texto, código, planilhas | Lossless | Qualquer erro invalida o dado          |
| Arquivos executáveis     | Lossless | Erro de 1 bit pode quebrar o programa  |
| Fotos (uso geral)        | Lossy    | Pequenas diferenças são imperceptíveis |
| Música (streaming)       | Lossy    | 320kbps é indistinguível do original   |
| Vídeo                    | Lossy    | Compressão massiva é necessária        |
| Backup de dados          | Lossless | Precisa ser exato                      |

***

### 📋 Algoritmos por Categoria

#### 📝 Compressão Lossless

| Algoritmo     | Ano  | Tipo               | Aplicação Principal      | Taxa        |
| ------------- | ---- | ------------------ | ------------------------ | ----------- |
| **RLE**       | 1967 | Run-length         | BMP, PCX, fax            | 2:1 a 10:1  |
| **Huffman**   | 1952 | Entropia           | ZIP, JPEG, MP3           | 1.5:1 a 3:1 |
| **LZ77**      | 1977 | Dicionário         | ZIP, gzip, PNG           | 2:1 a 5:1   |
| **LZ78**      | 1978 | Dicionário         | Compressão teórica       | 2:1 a 5:1   |
| **LZW**       | 1984 | Dicionário         | GIF, TIFF, Unix compress | 2:1 a 4:1   |
| **Deflate**   | 1993 | Híbrido            | ZIP, gzip, PNG, HTTP     | 2:1 a 8:1   |
| **LZMA**      | 1998 | Dicionário + range | 7z, xz                   | 3:1 a 10:1  |
| **Brotli**    | 2013 | LZ77 + Huffman     | WOFF, HTTP (Google)      | 3:1 a 12:1  |
| **Zstandard** | 2016 | Entropia + rep     | Moderno (Facebook)       | 2:1 a 10:1  |

#### 🖼️ Compressão Lossy (Imagem)

| Algoritmo      | Ano  | Aplicação   | Taxa Típica                          |
| -------------- | ---- | ----------- | ------------------------------------ |
| **DCT (JPEG)** | 1992 | Fotografias | 10:1 (boa qualidade) a 100:1 (baixa) |

#### 🎵 Compressão Lossy (Áudio)

| Algoritmo         | Ano   | Aplicação                 | Taxa Típica                     |
| ----------------- | ----- | ------------------------- | ------------------------------- |
| **Psicoacústica** | 1990s | MP3, AAC                  | 10:1 (320kbps) a 100:1 (64kbps) |
| **DCT**           | 1990s | Transformada usada no MP3 | -                               |

#### 🎬 Compressão Lossy (Vídeo)

| Algoritmo        | Ano  | Aplicação          | Taxa Típica    |
| ---------------- | ---- | ------------------ | -------------- |
| **H.264 (AVC)**  | 2003 | Blu-ray, streaming | 100:1 a 1000:1 |
| **H.265 (HEVC)** | 2013 | 4K, HDR            | 200:1 a 2000:1 |
| **AV1**          | 2018 | YouTube, Netflix   | 300:1 a 3000:1 |

***

### 🔢 Algoritmos em Detalhe

#### 1. RLE (Run-Length Encoding)

**Como funciona:** Substitui sequências repetidas por (valor, contagem).

```
Original:  AAAAABBBBBCCCCC
RLE:      (A,5)(B,5)(C,5)
Tamanho:  15 bytes → 6 bytes (60% de redução)
```

**Melhor para:** Imagens simples (ícones), dados com muitas repetições.

```python
def rle_encode(data):
    encoded = []
    count = 1
    for i in range(1, len(data)):
        if data[i] == data[i-1]:
            count += 1
        else:
            encoded.append((data[i-1], count))
            count = 1
    encoded.append((data[-1], count))
    return encoded

# Exemplo
rle_encode("AAAABBBCCDAA")  # [('A',4), ('B',3), ('C',2), ('D',1), ('A',2)]
```

***

#### 2. Huffman Coding

**Como funciona:** Caracteres mais frequentes recebem códigos menores.

```
Original:  "AAAAABBBCC" (10 bytes)
Frequência: A:5, B:3, C:2
Códigos:   A→0, B→10, C→11
Comprimido: 000001010101111 (15 bits ≈ 2 bytes)
Redução: 80%!
```

**Melhor para:** Texto, dados com distribuição desigual.

```python
from heapq import heappush, heappop

class NoHuffman:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

def huffman_encode(dados):
    # Contar frequências
    freq = {}
    for c in dados:
        freq[c] = freq.get(c, 0) + 1
    
    # Criar heap
    heap = []
    for char, f in freq.items():
        heappush(heap, (f, NoHuffman(char, f)))
    
    # Construir árvore
    while len(heap) > 1:
        f1, n1 = heappop(heap)
        f2, n2 = heappop(heap)
        pai = NoHuffman(None, f1 + f2)
        pai.left = n1
        pai.right = n2
        heappush(heap, (f1 + f2, pai))
    
    # Gerar códigos (recursivamente)
    # ...
```

***

#### 3. LZ77 (Lempel-Ziv 1977)

**Como funciona:** Substitui sequências repetidas por referências a ocorrências anteriores.

```
Original:  "ABABABA"
          "AB" (pos 0) → "AB" (pos 2, len 2) → "AB" (pos 4, len 2)
Comprimido: Literal A, Literal B, Ref(0,2), Ref(2,2)
```

**Melhor para:** Texto, código-fonte, dados com padrões repetidos.

***

#### 4. Deflate (ZIP, gzip)

**Como funciona:** Combina LZ77 + Huffman.

```
Dados → LZ77 (encontra repetições) → Huffman (codifica literais/distâncias) → Comprimido
```

**Onde é usado:**

* ZIP (.zip)
* gzip (.gz)
* PNG (compressão de imagens)
* HTTP compression (Content-Encoding: deflate)

```bash
# Exemplos de uso
gzip arquivo.txt        # Cria arquivo.txt.gz
gunzip arquivo.txt.gz   # Descomprime
zip arquivo.zip arquivo.txt
```

***

#### 5. LZMA (7-Zip)

**Como funciona:** Similar ao LZ77, mas com dicionário maior e range coding.

**Características:**

* Dicionário de até 4 GB
* Maior taxa de compressão
* Mais lento que Deflate

```bash
# 7-Zip (melhor compressão)
7z a arquivo.7z arquivo.txt -mx=9  # Máxima compressão

# Comparação de tamanhos (texto de 100 MB)
# original: 100 MB
# gzip:     35 MB
# bzip2:    28 MB
# LZMA:     22 MB
```

***

#### 6. Brotli (Google)

**Como funciona:** LZ77 + Huffman, otimizado para texto (HTML, CSS, JS).

**Características:**

* Criado pelo Google (2013)
* Melhor compressão que gzip para texto
* Usado em HTTPS (Content-Encoding: br)

```bash
# Comparação de taxas (HTML, CSS, JS)
# gzip:   redução de ~70%
# Brotli: redução de ~75-80%
```

***

#### 7. Zstandard (Facebook)

**Como funciona:** Combinação de técnicas modernas, extremamente rápido.

**Características:**

* Criado pelo Facebook (2016)
* Velocidade comparável ao lz4
* Taxa comparável ao zlib (gzip)
* Suporte a dicionários treinados

```bash
# Comparação de velocidade (MB/s)
# lz4:    500 MB/s (compressão) / 2000 MB/s (descompressão)
# zstd:   400 MB/s / 1000 MB/s
# gzip:    50 MB/s / 200 MB/s
# xz:      10 MB/s / 50 MB/s
```

***

#### 8. DCT (JPEG, MP3)

**Como funciona:** Transforma imagem do domínio espacial para frequências.

```
Imagem (espaço) → DCT → Frequências → Quantização (perda) → Huffman
```

**Onde é usado:**

* JPEG (imagem)
* MP3 (áudio)
* MPEG (vídeo)

```python
import numpy as np
from scipy.fftpack import dct

# DCT em uma imagem (bloco 8x8)
bloco = np.random.rand(8, 8)
dct_coeffs = dct(dct(bloco.T, norm='ortho').T, norm='ortho')
```

***

#### 9. Psicoacústica (MP3, AAC)

**Como funciona:** Remove sons que o ouvido humano não percebe.

```
Áudio → Análise espectral → Mascaramento (frequências inaudíveis) → Compressão
```

**Princípios:**

* **Mascaramento temporal:** Som alto esconde som baixo próximo
* **Mascaramento de frequência:** Frequência forte esconde vizinhas fracas

**Bitrates comuns:**

* 320 kbps: "indistinguível" do original
* 192 kbps: boa qualidade para música
* 128 kbps: qualidade de streaming
* 64 kbps: voz, podcasts

***

#### 10. Compressão de Vídeo (H.264, H.265, AV1)

**Como funciona:** Predição de quadros + DCT + compensação de movimento.

```
Quadros:
I-frame (Intra)  → Quadro completo (como JPEG)
P-frame (Predicted) → Diferenças do quadro anterior
B-frame (Bidirectional) → Diferenças de ambos os lados
```

**Comparação de eficiência:**

| Codec     | Taxa de compressão   | Uso                    |
| --------- | -------------------- | ---------------------- |
| **H.264** | Linha base           | Blu-ray, YouTube, Zoom |
| **H.265** | 50% melhor que H.264 | 4K, HDR                |
| **AV1**   | 30% melhor que H.265 | YouTube, Netflix       |

***

### 📊 Comparação de Algoritmos

#### Lossless - Taxa de Compressão (Texto Inglês)

| Algoritmo          | Tamanho (%) | Velocidade (MB/s) | Memória |
| ------------------ | ----------- | ----------------- | ------- |
| **Original**       | 100%        | -                 | -       |
| **RLE**            | 80-90%      | 500               | Baixa   |
| **Huffman**        | 60-70%      | 100               | Baixa   |
| **LZ77**           | 50-60%      | 200               | Média   |
| **Deflate (gzip)** | 35-45%      | 50                | Média   |
| **Brotli (q11)**   | 30-40%      | 20                | Média   |
| **Zstandard (19)** | 30-40%      | 100               | Média   |
| **LZMA (7z)**      | 20-30%      | 5                 | Alta    |

#### Lossy - Qualidade vs Tamanho

| Tipo              | Taxa       | Qualidade Percebida        |
| ----------------- | ---------- | -------------------------- |
| **JPEG (90%)**    | 10:1       | Excelente                  |
| **JPEG (75%)**    | 20:1       | Boa                        |
| **JPEG (50%)**    | 50:1       | Aceitável                  |
| **JPEG (25%)**    | 100:1      | Baixa (artefatos visíveis) |
| **MP3 (320kbps)** | 10:1       | Indistinguível             |
| **MP3 (192kbps)** | 17:1       | Muito boa                  |
| **MP3 (128kbps)** | 26:1       | Boa (streaming)            |
| **H.264**         | 100-1000:1 | Excelente                  |

***

### 🎯 Guia de Seleção

#### "Preciso comprimir texto..."

| Cenário            | Escolha        |
| ------------------ | -------------- |
| Máxima compressão  | LZMA (7z)      |
| Bom equilíbrio     | Deflate (gzip) |
| Velocidade extrema | Zstandard      |
| Compressão web     | Brotli         |

#### "Preciso comprimir imagens..."

| Tipo de imagem           | Escolha           |
| ------------------------ | ----------------- |
| Fotos                    | JPEG (lossy)      |
| Ícones, logos, diagramas | PNG (lossless)    |
| Necessita transparência  | PNG               |
| Animação                 | GIF (LZW) ou WebP |

#### "Preciso comprimir áudio..."

| Cenário              | Escolha           |
| -------------------- | ----------------- |
| Streaming, uso geral | MP3 (192-320kbps) |
| Alta qualidade       | FLAC (lossless)   |
| Compacto             | AAC ou Opus       |

#### "Preciso comprimir vídeo..."

| Cenário                   | Escolha      |
| ------------------------- | ------------ |
| Compatibilidade universal | H.264        |
| 4K/HDR                    | H.265 (HEVC) |
| Moderno (YouTube)         | AV1          |

***

### 🔗 Links Úteis

* [Compression Wiki](https://compression.wiki/)
* [LZbench (Benchmark de compressão)](https://github.com/inikep/lzbench)
* [Lossless Compression Benchmark](https://www.maximumcompression.com/)
* [JPEG vs PNG vs WebP](https://www.smashingmagazine.com/2021/09/modern-image-formats-webp-avif/)

***

### 📊 Tabela de Extensões

| Extensão | Algoritmo                | Tipo     |
| -------- | ------------------------ | -------- |
| `.zip`   | Deflate                  | Lossless |
| `.gz`    | Deflate (gzip)           | Lossless |
| `.7z`    | LZMA                     | Lossless |
| `.xz`    | LZMA2                    | Lossless |
| `.zst`   | Zstandard                | Lossless |
| `.br`    | Brotli                   | Lossless |
| `.jpg`   | DCT (JPEG)               | Lossy    |
| `.png`   | Deflate                  | Lossless |
| `.gif`   | LZW                      | Lossless |
| `.mp3`   | Psicoacústica + DCT      | Lossy    |
| `.flac`  | FLAC (Linear prediction) | Lossless |
| `.mp4`   | H.264/H.265              | Lossy    |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/algoritmos/compressao-de-dados-data-compression.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.