Codificação de Huffman

Morse e a ideia de frequência

Em 1838, Samuel Morse percebeu que o 'E' (o caractere mais comum em inglês) deveria ter o código mais curto (·) e o 'Z' (raro) o mais longo (- - · ·). Cem anos depois, David Huffman formalizou essa ideia numa prova matemática e um algoritmo ótimo: a codificação de Huffman.

A ideia: conte com que frequência cada símbolo aparece. Construa uma árvore binária onde símbolos raros ficam mais fundos (códigos mais longos) e frequentes ficam próximos da raiz (códigos mais curtos). O resultado é um código de comprimento variável que minimiza o número total de bits — sem qualquer perda de informação.

Construtor de árvore de Huffman

Digite qualquer texto e veja a árvore construída em tempo real. Observe como letras mais frequentes ficam mais próximas da raiz com códigos mais curtos.

Algoritmo e construção da árvore

// Algoritmo de Huffman — construção da árvore

function buildHuffman(text) {
  // 1. Contar frequências
  const freq = {};
  for (const ch of text) freq[ch] = (freq[ch] || 0) + 1;

  // 2. Fila de prioridade (min-heap) — usamos array ordenado por simplicidade
  let heap = Object.entries(freq)
    .map(([ch, f]) => ({ ch, freq: f, left: null, right: null }));

  // 3. Construir árvore: pegue os 2 menores, combine, repita
  while (heap.length > 1) {
    heap.sort((a, b) => a.freq - b.freq);  // O(n log n) — na prática usa min-heap
    const left  = heap.shift();            // menor frequência
    const right = heap.shift();            // segunda menor
    heap.push({
      ch: null,
      freq: left.freq + right.freq,
      left, right,
    });
  }
  return heap[0];  // raiz da árvore
}

// 4. Gerar códigos (DFS na árvore)
function getCodes(node, prefix = "", codes = {}) {
  if (!node.left) { codes[node.ch] = prefix; return codes; }
  getCodes(node.left,  prefix + "0", codes);
  getCodes(node.right, prefix + "1", codes);
  return codes;
}

Entropia de Shannon — o limite teórico

// Entropia de Shannon — limite teórico da compressão
// H(X) = -Σ P(x) * log₂(P(x))

function entropy(text) {
  const freq = {};
  for (const ch of text) freq[ch] = (freq[ch] || 0) + 1;

  return Object.values(freq).reduce((H, f) => {
    const p = f / text.length;
    return H - p * Math.log2(p);     // bits por símbolo
  }, 0);
}

// Exemplos:
entropy("aaaa");             // → 0 bits (sem surpresa)
entropy("abcd");             // → 2 bits (4 símbolos equiprováveis)
entropy("abracadabra");     // → ~2.04 bits (distribuição desigual)

// Huffman garante: comprimento médio entre H e H+1 bits por símbolo
// Limite de Shannon: não existe compressor que faça melhor que H
// Compressores modernos (zstd, brotli) usam contextos para aproximar H mais

Compressor completo em JavaScript

Mini projeto: implemente a decodificação Huffman: dada uma árvore e uma string de bits, percorra a árvore bit a bit (0=esquerda, 1=direita) e emita o caractere ao chegar a uma folha. Verifique que decode(encode(text)) === text.

Projeto principal: implemente um compressor de arquivo completo: serialize a árvore de Huffman como header (para o decodificador poder reconstruí-la), seguido dos bits codificados. Calcule a taxa de compressão real em bytes (incluindo o overhead do header). Para textos curtos, o overhead da árvore pode fazer o arquivo comprimido ser maior que o original.

Desafio extra: implemente Run-Length Encoding (RLE) antes de Huffman: sequências repetidas como "aaaaaabbb" viram "6a3b". Combine RLE + Huffman e compare com Huffman puro em diferentes tipos de dados (texto, imagem PNG, arquivo binário). Em quais casos RLE ajuda?

Teste sua intuição

Onde você encontra isso