---
title: "Compressor de Arquivos LZ77 em Rust"
url: "https://rustlang.com.br/projetos/compressor-lz/"
markdown_url: "https://rustlang.com.br/projetos/compressor-lz.MD"
description: "Construa um compressor de arquivos com o algoritmo LZ77 em Rust: janela deslizante, busca de correspondências, codificação e decodificação."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Compressor de Arquivos LZ77 em Rust

Construa um compressor de arquivos com o algoritmo LZ77 em Rust: janela deslizante, busca de correspondências, codificação e decodificação.


Neste projeto vamos construir um **compressor e descompressor de arquivos** implementando o algoritmo LZ77 do zero em Rust. O LZ77 (Lempel-Ziv 1977) é um dos algoritmos de compressão mais influentes da história da computação -- ele é a base de formatos populares como gzip, DEFLATE e PNG. A ideia central é substituir sequências repetidas por referências a ocorrências anteriores, usando uma janela deslizante como dicionário.

Este projeto é uma excelente oportunidade para praticar manipulação de bytes, leitura e escrita eficiente com buffers, gerenciamento de slices e otimização de performance em Rust. Ao final, você terá um compressor funcional capaz de reduzir significativamente o tamanho de arquivos de texto.

## O Que Vamos Construir

Um compressor de arquivos LZ77 com as seguintes funcionalidades:

- Algoritmo LZ77 com janela deslizante de tamanho configurável
- Busca de correspondências (match finding) eficiente
- Codificação de tokens (offset, comprimento, literal) em formato binário
- Decodificação que reconstrói os dados originais perfeitamente
- Leitura e escrita com buffers para performance
- Cabeçalho de arquivo com metadados de compressão
- Estatísticas de compressão (razão, tamanho antes/depois)
- Interface de linha de comando para comprimir e descomprimir

## Estrutura do Projeto

```
compressor-lz/
├── Cargo.toml
└── src/
    └── main.rs
```

## Configurando o Projeto

Crie o projeto com o Cargo:

```bash
cargo new compressor-lz
cd compressor-lz
```

Edite o `Cargo.toml`:

```toml
[package]
name = "compressor-lz"
version = "0.1.0"
edition = "2021"
```

Este projeto usa apenas a biblioteca padrão do Rust -- nenhuma dependência externa é necessária. Toda a lógica de compressão é implementada do zero.

## Passo 1: Definindo os Tokens LZ77

O algoritmo LZ77 codifica os dados como uma sequência de tokens. Cada token pode ser uma **referência** a dados já vistos (offset + comprimento) ou um **literal** (um byte que não encontrou correspondência). Vamos definir essas estruturas e as constantes do algoritmo.

```rust
use std::env;
use std::fs::File;
use std::io::{self, BufReader, BufWriter, Read, Write};

/// Tamanho da janela deslizante (quantos bytes anteriores são pesquisados)
const TAMANHO_JANELA: usize = 4096;

/// Tamanho máximo do buffer de lookahead (correspondência máxima)
const TAMANHO_LOOKAHEAD: usize = 255;

/// Comprimento mínimo para considerar uma correspondência
/// (referências menores que isso ocupam mais espaço que o literal)
const COMPRIMENTO_MINIMO: usize = 3;

/// Byte mágico que identifica nosso formato de arquivo comprimido
const MAGIC_BYTES: [u8; 4] = [b'L', b'Z', b'7', b'7'];

/// Token produzido pelo algoritmo LZ77
#[derive(Debug, Clone)]
enum Token {
    /// Referência a dados anteriores: (distância para trás, comprimento)
    Referencia { offset: u16, comprimento: u8 },
    /// Byte literal que não encontrou correspondência
    Literal(u8),
}
```

Os parâmetros são cuidadosamente escolhidos: a janela de 4096 bytes permite offsets representáveis em 12 bits, e o lookahead de 255 bytes cabe em um `u8`. O comprimento mínimo de 3 garante que uma referência (3 bytes: flag + offset + comprimento) economize espaço em vez de desperdiçar.

## Passo 2: O Compressor -- Busca de Correspondências

O coração do LZ77 é a busca de correspondências na janela deslizante. Para cada posição no buffer de entrada, procuramos a maior sequência que já apareceu anteriormente dentro da janela.

```rust
/// Encontra a maior correspondência dentro da janela deslizante.
/// Retorna (offset, comprimento) ou None se não encontrar correspondência
/// suficientemente longa.
fn encontrar_correspondencia(
    dados: &[u8],
    posicao: usize,
) -> Option<(u16, u8)> {
    // Início da janela de busca
    let inicio_janela = posicao.saturating_sub(TAMANHO_JANELA);
    // Bytes restantes disponíveis para correspondência
    let max_comprimento = TAMANHO_LOOKAHEAD.min(dados.len() - posicao);

    if max_comprimento < COMPRIMENTO_MINIMO {
        return None;
    }

    let mut melhor_offset: u16 = 0;
    let mut melhor_comprimento: usize = 0;

    // Percorre todas as posições possíveis na janela
    for candidato in inicio_janela..posicao {
        let mut comprimento = 0;

        // Conta quantos bytes consecutivos são iguais
        while comprimento < max_comprimento
            && dados[candidato + comprimento] == dados[posicao + comprimento]
        {
            comprimento += 1;
        }

        // Atualiza a melhor correspondência encontrada
        if comprimento >= COMPRIMENTO_MINIMO && comprimento > melhor_comprimento {
            melhor_offset = (posicao - candidato) as u16;
            melhor_comprimento = comprimento;
        }
    }

    if melhor_comprimento >= COMPRIMENTO_MINIMO {
        Some((melhor_offset, melhor_comprimento as u8))
    } else {
        None
    }
}

/// Comprime os dados usando o algoritmo LZ77, retornando uma lista de tokens
fn comprimir_lz77(dados: &[u8]) -> Vec<Token> {
    let mut tokens = Vec::new();
    let mut posicao: usize = 0;

    while posicao < dados.len() {
        if let Some((offset, comprimento)) = encontrar_correspondencia(dados, posicao) {
            // Encontrou correspondência: emite uma referência
            tokens.push(Token::Referencia { offset, comprimento });
            posicao += comprimento as usize;
        } else {
            // Sem correspondência: emite o byte literal
            tokens.push(Token::Literal(dados[posicao]));
            posicao += 1;
        }
    }

    tokens
}
```

A busca percorre todas as posições dentro da janela, comparando byte a byte com os dados na posição atual. Para cada candidato, conta quantos bytes consecutivos são idênticos. Mantém registro da melhor correspondência encontrada e, se ela for maior que o comprimento mínimo, emite uma referência. Caso contrário, emite um literal.

## Passo 3: Codificação e Decodificação Binária

Precisamos serializar os tokens em um formato binário compacto para salvar no arquivo, e depois conseguir lê-los de volta para descomprimir. Usamos um esquema simples: um byte de flag indica se o próximo token é um literal (0x00) ou uma referência (0x01).

```rust
/// Codifica os tokens em formato binário e escreve no escritor
fn codificar_tokens<W: Write>(
    tokens: &[Token],
    escritor: &mut W,
) -> io::Result<()> {
    for token in tokens {
        match token {
            Token::Literal(byte) => {
                // Flag 0x00 seguido do byte literal
                escritor.write_all(&[0x00, *byte])?;
            }
            Token::Referencia { offset, comprimento } => {
                // Flag 0x01 seguido de offset (2 bytes, big-endian) e comprimento (1 byte)
                escritor.write_all(&[0x01])?;
                escritor.write_all(&offset.to_be_bytes())?;
                escritor.write_all(&[*comprimento])?;
            }
        }
    }
    Ok(())
}

/// Decodifica os tokens do formato binário lido do leitor
fn decodificar_tokens<R: Read>(leitor: &mut R) -> io::Result<Vec<Token>> {
    let mut tokens = Vec::new();
    let mut flag = [0u8; 1];

    loop {
        // Lê o byte de flag
        match leitor.read_exact(&mut flag) {
            Ok(()) => {}
            Err(e) if e.kind() == io::ErrorKind::UnexpectedEof => break,
            Err(e) => return Err(e),
        }

        match flag[0] {
            0x00 => {
                // Token literal: lê o próximo byte
                let mut byte = [0u8; 1];
                leitor.read_exact(&mut byte)?;
                tokens.push(Token::Literal(byte[0]));
            }
            0x01 => {
                // Token de referência: lê offset (2 bytes) e comprimento (1 byte)
                let mut buf_offset = [0u8; 2];
                let mut buf_comprimento = [0u8; 1];
                leitor.read_exact(&mut buf_offset)?;
                leitor.read_exact(&mut buf_comprimento)?;
                let offset = u16::from_be_bytes(buf_offset);
                let comprimento = buf_comprimento[0];
                tokens.push(Token::Referencia { offset, comprimento });
            }
            outro => {
                return Err(io::Error::new(
                    io::ErrorKind::InvalidData,
                    format!("Flag inválido no arquivo comprimido: 0x{:02X}", outro),
                ));
            }
        }
    }

    Ok(tokens)
}

/// Reconstrói os dados originais a partir dos tokens decodificados
fn descomprimir_lz77(tokens: &[Token]) -> Vec<u8> {
    let mut saida: Vec<u8> = Vec::new();

    for token in tokens {
        match token {
            Token::Literal(byte) => {
                saida.push(*byte);
            }
            Token::Referencia { offset, comprimento } => {
                // Copia bytes da própria saída, um por vez
                // (necessário porque a referência pode sobrepor a região copiada)
                let inicio = saida.len() - *offset as usize;
                for i in 0..*comprimento as usize {
                    let byte = saida[inicio + i];
                    saida.push(byte);
                }
            }
        }
    }

    saida
}
```

Na descompressão, a cópia byte a byte é intencional: uma referência pode apontar para dados que se sobrepõem à região sendo escrita (por exemplo, offset=1, comprimento=10 repete o último byte 10 vezes). Copiar um a um garante que cada byte copiado considere os bytes já inseridos.

## Passo 4: Interface de Arquivo e Função main

Agora montamos as funções de alto nível para comprimir e descomprimir arquivos, incluindo o cabeçalho com bytes mágicos e o tamanho original, além da interface de linha de comando.

```rust
/// Comprime um arquivo e salva o resultado
fn comprimir_arquivo(caminho_entrada: &str, caminho_saida: &str) -> io::Result<()> {
    // Lê todo o arquivo de entrada
    let arquivo_entrada = File::open(caminho_entrada)?;
    let mut leitor = BufReader::new(arquivo_entrada);
    let mut dados = Vec::new();
    leitor.read_to_end(&mut dados)?;

    let tamanho_original = dados.len();
    println!("Comprimindo '{}' ({} bytes)...", caminho_entrada, tamanho_original);

    // Comprime os dados
    let tokens = comprimir_lz77(&dados);

    // Conta estatísticas dos tokens
    let num_literais = tokens.iter().filter(|t| matches!(t, Token::Literal(_))).count();
    let num_referencias = tokens.iter().filter(|t| matches!(t, Token::Referencia { .. })).count();
    println!(
        "  Tokens gerados: {} literais, {} referências",
        num_literais, num_referencias
    );

    // Escreve o arquivo comprimido
    let arquivo_saida = File::create(caminho_saida)?;
    let mut escritor = BufWriter::new(arquivo_saida);

    // Cabeçalho: bytes mágicos + tamanho original (4 bytes, big-endian)
    escritor.write_all(&MAGIC_BYTES)?;
    escritor.write_all(&(tamanho_original as u32).to_be_bytes())?;

    // Dados comprimidos
    codificar_tokens(&tokens, &mut escritor)?;
    escritor.flush()?;

    // Calcula e exibe as estatísticas
    let tamanho_comprimido = std::fs::metadata(caminho_saida)?.len() as usize;
    let razao = tamanho_comprimido as f64 / tamanho_original as f64 * 100.0;
    let economia = tamanho_original as i64 - tamanho_comprimido as i64;

    println!("  Tamanho comprimido: {} bytes", tamanho_comprimido);
    println!("  Razão de compressão: {:.1}%", razao);
    if economia > 0 {
        println!("  Economia: {} bytes ({:.1}%)", economia, 100.0 - razao);
    } else {
        println!("  Aviso: arquivo comprimido ficou maior que o original!");
    }
    println!("  Salvo em '{}'", caminho_saida);

    Ok(())
}

/// Descomprime um arquivo e salva o resultado
fn descomprimir_arquivo(caminho_entrada: &str, caminho_saida: &str) -> io::Result<()> {
    let arquivo_entrada = File::open(caminho_entrada)?;
    let mut leitor = BufReader::new(arquivo_entrada);

    // Verifica os bytes mágicos
    let mut magic = [0u8; 4];
    leitor.read_exact(&mut magic)?;
    if magic != MAGIC_BYTES {
        return Err(io::Error::new(
            io::ErrorKind::InvalidData,
            "Arquivo não é um arquivo LZ77 válido (bytes mágicos incorretos)",
        ));
    }

    // Lê o tamanho original
    let mut buf_tamanho = [0u8; 4];
    leitor.read_exact(&mut buf_tamanho)?;
    let tamanho_original = u32::from_be_bytes(buf_tamanho) as usize;

    println!(
        "Descomprimindo '{}' (tamanho original: {} bytes)...",
        caminho_entrada, tamanho_original
    );

    // Decodifica os tokens
    let tokens = decodificar_tokens(&mut leitor)?;
    println!("  Tokens lidos: {}", tokens.len());

    // Reconstrói os dados originais
    let dados = descomprimir_lz77(&tokens);

    // Verifica integridade
    if dados.len() != tamanho_original {
        return Err(io::Error::new(
            io::ErrorKind::InvalidData,
            format!(
                "Tamanho descomprimido ({}) difere do esperado ({})",
                dados.len(),
                tamanho_original
            ),
        ));
    }

    // Escreve o arquivo descomprimido
    let arquivo_saida = File::create(caminho_saida)?;
    let mut escritor = BufWriter::new(arquivo_saida);
    escritor.write_all(&dados)?;
    escritor.flush()?;

    println!("  Descomprimido com sucesso em '{}'", caminho_saida);

    Ok(())
}

/// Exibe as instruções de uso do programa
fn exibir_uso() {
    eprintln!("Compressor de Arquivos LZ77");
    eprintln!();
    eprintln!("Uso:");
    eprintln!("  compressor-lz comprimir   <entrada> <saida.lz>");
    eprintln!("  compressor-lz descomprimir <entrada.lz> <saida>");
    eprintln!();
    eprintln!("Exemplos:");
    eprintln!("  compressor-lz comprimir   texto.txt texto.txt.lz");
    eprintln!("  compressor-lz descomprimir texto.txt.lz texto_recuperado.txt");
}

fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() != 4 {
        exibir_uso();
        std::process::exit(1);
    }

    let comando = args[1].as_str();
    let entrada = &args[2];
    let saida = &args[3];

    let resultado = match comando {
        "comprimir" | "c" => comprimir_arquivo(entrada, saida),
        "descomprimir" | "d" => descomprimir_arquivo(entrada, saida),
        _ => {
            eprintln!("Comando desconhecido: '{}'\n", comando);
            exibir_uso();
            std::process::exit(1);
        }
    };

    if let Err(e) = resultado {
        eprintln!("Erro: {}", e);
        std::process::exit(1);
    }
}
```

O cabeçalho do arquivo comprimido contém os bytes mágicos `LZ77` para identificação e o tamanho original em 4 bytes (big-endian), permitindo verificação de integridade na descompressão. As funções de alto nível usam `BufReader` e `BufWriter` para evitar chamadas de sistema excessivas, melhorando a performance especialmente em arquivos grandes.

## Como Executar

Compile o projeto em modo otimizado:

```bash
cargo build --release
```

Crie um arquivo de teste e comprima:

```bash
# Cria um arquivo de texto com conteúdo repetitivo (ideal para LZ77)
echo "Rust é uma linguagem de programação. Rust é rápida. Rust é segura. Rust é incrível. Programação em Rust é produtiva. A linguagem Rust cresce cada dia mais." > teste.txt

# Comprime o arquivo
cargo run --release -- comprimir teste.txt teste.txt.lz

# Saída esperada:
# Comprimindo 'teste.txt' (178 bytes)...
#   Tokens gerados: 92 literais, 22 referências
#   Tamanho comprimido: 202 bytes
#   Razão de compressão: ...%
#   Salvo em 'teste.txt.lz'

# Descomprime o arquivo
cargo run --release -- descomprimir teste.txt.lz teste_recuperado.txt

# Verifica que o conteúdo é idêntico
diff teste.txt teste_recuperado.txt && echo "Arquivos idênticos!"
```

Para testar com arquivos maiores onde a compressão é mais efetiva:

```bash
# Baixe um arquivo de texto grande (ex: livro em domínio público)
# ou use um log do sistema
cargo run --release -- comprimir /var/log/syslog syslog.lz
cargo run --release -- descomprimir syslog.lz syslog_recuperado
```

Arquivos de texto com muita repetição (logs, código-fonte, HTML) geralmente atingem razões de compressão entre 40-70% com esta implementação.

## Desafios para Expandir

1. **Busca com hash** -- Substitua a busca linear por uma tabela hash que mapeia trigramas (sequências de 3 bytes) para posições na janela. Isso reduz a complexidade de O(n * janela) para O(n) na média, acelerando enormemente a compressão.

2. **Codificação por bits** -- Implemente codificação Huffman ou codificação aritmética sobre os tokens LZ77 para comprimir ainda mais a saída, aproximando-se do que o DEFLATE (gzip) faz na prática.

3. **Compressão em streaming** -- Modifique o compressor para processar dados em blocos fixos em vez de carregar o arquivo inteiro na memória, permitindo comprimir arquivos maiores que a RAM disponível.

4. **Suporte a múltiplos arquivos** -- Adicione a capacidade de comprimir vários arquivos em um único arquivo comprimido (como tar + gzip), armazenando nomes e metadados junto com os dados comprimidos.

5. **Benchmarks comparativos** -- Implemente também o LZ78 e compare as razões de compressão e velocidade entre LZ77 e LZ78 para diferentes tipos de arquivos (texto, binário, imagens).

## Veja Também

- [Vec: Vetores Dinâmicos](/stdlib/vec/) -- Estrutura principal para armazenar bytes e tokens
- [Módulo IO](/stdlib/io-module/) -- Leitura e escrita de arquivos com tratamento de erros
- [BufReader e BufWriter](/stdlib/bufreader-bufwriter/) -- Buffers para I/O eficiente
- [Slices em Rust](/stdlib/slice/) -- Manipulação de fatias de bytes na janela deslizante
- [Otimização de Performance](/artigos/otimizacao-performance/) -- Técnicas para acelerar a busca de correspondências