Codificação de Huffman: comprimindo com árvores binárias

A = 01000001  (8 bits)
B = 01000010  (8 bits)
C = 01000011  (8 bits)
Z = 01011010  (8 bits)

A → aparece 50% das vezes
B → aparece 25% das vezes
C → aparece 12.5% das vezes
D → aparece 12.5% das vezes

A = 00  (2 bits)
B = 01  (2 bits)
C = 10  (2 bits)
D = 11  (2 bits)

A = 0     (1 bit)   ← aparece mais, código mais curto
B = 10    (2 bits)
C = 110   (3 bits)  ← aparece menos, código mais longo
D = 111   (3 bits)  ← aparece menos, código mais longo

500 vezes A × 1 bit  = 500 bits
250 vezes B × 2 bits = 500 bits
125 vezes C × 3 bits = 375 bits
125 vezes D × 3 bits = 375 bits
                Total: 1750 bits

01001110

01 | 00 | 11 | 10  →  B A D C

0 | 10 | 0 | 111 | 0   →  A B A D A     (5 símbolos)
0 | 10 | 0 | 11 | 10   →  Ops, "11" não é código válido...
0 | 100 | 1110         →  "100" não existe...

A = 0
B = 10
C = 110
D = 111

Lê "0"     → É código de A!  → A
Lê "1"     → Não é nenhum código ainda, continua...
Lê "10"    → É código de B!  → B
Lê "0"     → É código de A!  → A
Lê "1"     → Continua...
Lê "11"    → Continua...
Lê "110"   → É código de C!  → C

Resultado: A B A C

A: frequência 50%   (0.50)
B: frequência 25%   (0.25)
C: frequência 12.5% (0.125)
D: frequência 12.5% (0.125)

[A: 0.50]    [B: 0.25]    [C: 0.125]    [D: 0.125]

[A: 0.50]    [B: 0.25]    [CD: 0.25]
                            /       \
                        [C: 0.125] [D: 0.125]

[A: 0.50]          [BCD: 0.50]
                    /         \
              [B: 0.25]    [CD: 0.25]
                            /       \
                        [C: 0.125] [D: 0.125]

               [RAIZ: 1.00]
              /            \
        [A: 0.50]     [BCD: 0.50]
                       /         \
                 [B: 0.25]    [CD: 0.25]
                               /       \
                           [C: 0.125] [D: 0.125]

              [RAIZ]
           0 /      \ 1
        [A]       [BCD]
               0 /      \ 1
            [B]        [CD]
                    0 /    \ 1
                  [C]      [D]

A: esquerda                       → 0
B: direita, esquerda              → 10
C: direita, direita, esquerda     → 110
D: direita, direita, direita      → 111

A → 5 vezes (45.5%)
B → 2 vezes (18.2%)
R → 2 vezes (18.2%)
C → 1 vez   (9.1%)
D → 1 vez   (9.1%)

[A: 5]    [B: 2]    [R: 2]    [C: 1]    [D: 1]

[A: 5]    [B: 2]    [R: 2]      [CD: 2]
                                /     \
                            [C: 1]  [D: 1]

[A: 5]     [BR: 4]    [CD: 2]
           /     \
       [B: 2]  [R: 2]

[A: 5]      [BRCD: 6]
            /       \
       [BR: 4]    [CD: 2]
        /    \     /    \
    [B: 2] [R: 2] [C: 1] [D: 1]

               [RAIZ: 11]
             /           \
         [A: 5]      [BRCD: 6]
                      /       \
                 [BR: 4]    [CD: 2]
                  /    \     /    \
              [B: 2] [R: 2] [C: 1] [D: 1]

A: 0          (1 bit)
B: 100        (3 bits)
R: 101        (3 bits)
C: 110        (3 bits)
D: 111        (3 bits)

A   B   R   A   C   A   D   A   B   R   A
0   100 101 0   110 0   111 0   100 101 0

Juntando: 0 100 101 0 110 0 111 0 100 101 0
Total: 23 bits

11 caracteres × 3 bits = 33 bits

12, 0, 0, 0, -3, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0...

'E', 'u', ' ', 'g', 'o', 's', 't', 'a', 'r', 'i', 'a', ' ', 'd', 'e', ' ', 's', 'a', 'b', 'e', 'r'...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// ============================================================
// ESTRUTURAS DE DADOS
// ============================================================

// Cada nó da árvore de Huffman pode ser uma FOLHA (com um símbolo)
// ou um NÓ INTERNO (com dois filhos).

typedef struct NoHuffman {
    unsigned char simbolo;       // O byte que este nó representa (só pra folhas)
    int frequencia;              // Quantas vezes esse símbolo aparece
    struct NoHuffman *esquerda;  // Filho esquerdo (bit 0)
    struct NoHuffman *direita;   // Filho direito (bit 1)
} NoHuffman;

// Estrutura pra armazenar o código binário de cada símbolo
// (como string de '0's e '1's pra facilitar a visualização)
typedef struct {
    char bits[256];   // O código em si (ex: "110")
    int tamanho;      // Quantos bits tem o código
} CodigoHuffman;

// ============================================================
// FUNÇÕES AUXILIARES
// ============================================================

// Cria um novo nó folha (com símbolo)
NoHuffman *criar_folha(unsigned char simbolo, int frequencia) {
    NoHuffman *no = (NoHuffman *) malloc(sizeof(NoHuffman));
    no->simbolo = simbolo;
    no->frequencia = frequencia;
    no->esquerda = NULL;
    no->direita = NULL;
    return no;
}

// Cria um novo nó interno (com dois filhos)
NoHuffman *criar_no_interno(NoHuffman *esq, NoHuffman *dir) {
    NoHuffman *no = (NoHuffman *) malloc(sizeof(NoHuffman));
    no->simbolo = 0;  // Nós internos não têm símbolo
    no->frequencia = esq->frequencia + dir->frequencia;
    no->esquerda = esq;
    no->direita = dir;
    return no;
}

// Verifica se um nó é folha (não tem filhos)
int eh_folha(NoHuffman *no) {
    return (no->esquerda == NULL && no->direita == NULL);
}

// Libera toda a memória da árvore recursivamente
void liberar_arvore(NoHuffman *no) {
    if (no == NULL) return;
    liberar_arvore(no->esquerda);
    liberar_arvore(no->direita);
    free(no);
}

// ============================================================
// PASSO 1: CONTAR FREQUÊNCIAS
// ============================================================
//
// Percorre todos os bytes de entrada e conta quantas vezes
// cada valor (0 a 255) aparece.

void contar_frequencias(unsigned char *dados, int tamanho, int *freq) {
    // Inicializa todas as frequências com zero
    for (int i = 0; i < 256; i++) {
        freq[i] = 0;
    }

    // Conta cada byte
    for (int i = 0; i < tamanho; i++) {
        freq[dados[i]]++;
    }
}

// ============================================================
// PASSO 2: CONSTRUIR A ÁRVORE DE HUFFMAN
// ============================================================
//
// Usa o algoritmo clássico:
// 1. Cria uma folha pra cada símbolo com freq > 0
// 2. Repetidamente pega os 2 nós com menor frequência
//    e junta num nó pai
// 3. Para quando sobra 1 nó (a raiz)
//
// NOTA: pra simplificar, estou usando um array como
// "fila de prioridade" ingênua. Em produção, usaria
// uma min-heap, mas pra fins didáticos o array é mais
// fácil de entender.

NoHuffman *construir_arvore(int *freq) {
    // Array de ponteiros pros nós (nossa "fila de prioridade" simples)
    NoHuffman *nos[256];
    int num_nos = 0;

    // Cria uma folha pra cada símbolo que aparece pelo menos 1 vez
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            nos[num_nos] = criar_folha((unsigned char) i, freq[i]);
            num_nos++;
        }
    }

    // Caso especial: se só tem 1 símbolo, cria um nó pai artificial
    // (uma árvore precisa de pelo menos 2 folhas pra gerar códigos)
    if (num_nos == 1) {
        NoHuffman *filho = nos[0];
        NoHuffman *raiz = criar_no_interno(filho, criar_folha(0, 0));
        return raiz;
    }

    // Repetidamente junta os 2 nós de menor frequência
    while (num_nos > 1) {
        // Encontra o nó com MENOR frequência
        int idx_min1 = 0;
        for (int i = 1; i < num_nos; i++) {
            if (nos[i]->frequencia < nos[idx_min1]->frequencia) {
                idx_min1 = i;
            }
        }

        // Remove o menor do array (troca com o último e diminui o tamanho)
        NoHuffman *min1 = nos[idx_min1];
        nos[idx_min1] = nos[num_nos - 1];
        num_nos--;

        // Encontra o SEGUNDO menor
        int idx_min2 = 0;
        for (int i = 1; i < num_nos; i++) {
            if (nos[i]->frequencia < nos[idx_min2]->frequencia) {
                idx_min2 = i;
            }
        }

        // Remove o segundo menor
        NoHuffman *min2 = nos[idx_min2];
        nos[idx_min2] = nos[num_nos - 1];
        num_nos--;

        // Cria um nó pai que junta os dois
        NoHuffman *pai = criar_no_interno(min1, min2);

        // Adiciona o pai de volta no array
        nos[num_nos] = pai;
        num_nos++;
    }

    // Sobrou 1 nó: é a raiz da árvore
    return nos[0];
}

// ============================================================
// PASSO 3: GERAR OS CÓDIGOS A PARTIR DA ÁRVORE
// ============================================================
//
// Percorre a árvore recursivamente. Cada vez que desce
// pra esquerda, adiciona '0' ao código. Cada vez que
// desce pra direita, adiciona '1'. Quando chega numa
// folha, o caminho percorrido é o código daquele símbolo.

void gerar_codigos(NoHuffman *no, char *caminho, int profundidade,
                   CodigoHuffman *tabela) {
    if (no == NULL) return;

    // Se é folha, salva o código na tabela
    if (eh_folha(no)) {
        caminho[profundidade] = '\0';  // termina a string
        strcpy(tabela[no->simbolo].bits, caminho);
        tabela[no->simbolo].tamanho = profundidade;
        return;
    }

    // Desce pra esquerda (bit 0)
    caminho[profundidade] = '0';
    gerar_codigos(no->esquerda, caminho, profundidade + 1, tabela);

    // Desce pra direita (bit 1)
    caminho[profundidade] = '1';
    gerar_codigos(no->direita, caminho, profundidade + 1, tabela);
}

// ============================================================
// PASSO 4: CODIFICAR (comprimir)
// ============================================================
//
// Substitui cada byte de entrada pelo seu código de Huffman.
// O resultado é uma sequência de bits empacotados em bytes.

int huffman_encode(unsigned char *entrada, int tamanho_entrada,
                   unsigned char *saida, CodigoHuffman *tabela) {
    int bit_pos = 0;  // posição atual em bits no array de saída

    // Inicializa a saída com zeros
    // (o tamanho máximo possível é difícil de prever, mas
    //  nunca será maior que o dobro da entrada)
    memset(saida, 0, tamanho_entrada * 2);

    for (int i = 0; i < tamanho_entrada; i++) {
        unsigned char simbolo = entrada[i];
        CodigoHuffman *codigo = &tabela[simbolo];

        // Escreve cada bit do código na saída
        for (int j = 0; j < codigo->tamanho; j++) {
            if (codigo->bits[j] == '1') {
                // Liga o bit na posição correta
                // byte_idx = em qual byte estamos
                // bit_idx  = qual bit dentro desse byte (7=mais significativo)
                int byte_idx = bit_pos / 8;
                int bit_idx  = 7 - (bit_pos % 8);
                saida[byte_idx] |= (1 << bit_idx);
            }
            bit_pos++;
        }
    }

    // Retorna o tamanho em bytes (arredondando pra cima)
    return (bit_pos + 7) / 8;
}

// ============================================================
// PASSO 5: DECODIFICAR (descomprimir)
// ============================================================
//
// Percorre a sequência de bits e navega pela árvore:
// - bit 0 → vai pra esquerda
// - bit 1 → vai pra direita
// - chegou numa folha → emite o símbolo e volta pra raiz

int huffman_decode(unsigned char *entrada, int total_bits,
                   NoHuffman *raiz, unsigned char *saida) {
    int out_pos = 0;
    NoHuffman *atual = raiz;

    for (int bit_pos = 0; bit_pos < total_bits; bit_pos++) {
        // Lê o bit na posição bit_pos
        int byte_idx = bit_pos / 8;
        int bit_idx  = 7 - (bit_pos % 8);
        int bit = (entrada[byte_idx] >> bit_idx) & 1;

        // Navega pela árvore
        if (bit == 0) {
            atual = atual->esquerda;
        } else {
            atual = atual->direita;
        }

        // Se chegou numa folha, emite o símbolo
        if (eh_folha(atual)) {
            saida[out_pos] = atual->simbolo;
            out_pos++;
            atual = raiz;  // volta pra raiz pra decodificar o próximo
        }
    }

    return out_pos;
}

// ============================================================
// MAIN — Testa tudo com exemplos concretos
// ============================================================

int main() {
    printf("=== Codificação de Huffman ===\n\n");

    // ----- Teste 1: ABRACADABRA -----
    printf("--- Teste 1: ABRACADABRA ---\n\n");

    char *texto1 = "ABRACADABRA";
    int tamanho1 = strlen(texto1);

    // Passo 1: Contar frequências
    int freq1[256];
    contar_frequencias((unsigned char *)texto1, tamanho1, freq1);

    printf("Frequências:\n");
    for (int i = 0; i < 256; i++) {
        if (freq1[i] > 0) {
            printf("  '%c' → %d vezes (%.1f%%)\n",
                   (char)i, freq1[i], (freq1[i] * 100.0) / tamanho1);
        }
    }
    printf("\n");

    // Passo 2: Construir a árvore
    NoHuffman *raiz1 = construir_arvore(freq1);

    // Passo 3: Gerar os códigos
    CodigoHuffman tabela1[256];
    memset(tabela1, 0, sizeof(tabela1));
    char caminho1[256];
    gerar_codigos(raiz1, caminho1, 0, tabela1);

    printf("Códigos de Huffman:\n");
    for (int i = 0; i < 256; i++) {
        if (tabela1[i].tamanho > 0) {
            printf("  '%c' → %s (%d bits)\n",
                   (char)i, tabela1[i].bits, tabela1[i].tamanho);
        }
    }
    printf("\n");

    // Passo 4: Codificar
    unsigned char saida1[100];
    int tam_codificado1 = huffman_encode(
        (unsigned char *)texto1, tamanho1, saida1, tabela1);

    // Calcula total de bits usado
    int total_bits1 = 0;
    for (int i = 0; i < tamanho1; i++) {
        total_bits1 += tabela1[(unsigned char)texto1[i]].tamanho;
    }

    printf("Original:   \"%s\" (%d caracteres × 8 bits = %d bits)\n",
           texto1, tamanho1, tamanho1 * 8);
    printf("Huffman:    %d bits (%d bytes)\n", total_bits1, tam_codificado1);
    printf("Compressão: %.1f%% (vs ASCII 8-bit)\n\n",
           (1.0 - (double)total_bits1 / (tamanho1 * 8)) * 100.0);

    // Passo 5: Decodificar e verificar
    unsigned char decodificado1[100];
    int tam_decodificado1 = huffman_decode(saida1, total_bits1, raiz1, decodificado1);
    decodificado1[tam_decodificado1] = '\0';

    int ok1 = (tam_decodificado1 == tamanho1)
           && (memcmp(texto1, decodificado1, tamanho1) == 0);
    printf("Decodificado: \"%s\"\n", decodificado1);
    printf("Lossless:     %s\n\n",
           ok1 ? "SIM (idêntico ao original)" : "NÃO (ERRO!)");

    liberar_arvore(raiz1);

    // ----- Teste 2: Texto com distribuição mais desigual -----
    printf("--- Teste 2: Texto com muita repetição ---\n\n");

    char *texto2 = "AAAAAAAAAAAAAAAAABBBBCCD";
    int tamanho2 = strlen(texto2);

    int freq2[256];
    contar_frequencias((unsigned char *)texto2, tamanho2, freq2);

    printf("Frequências:\n");
    for (int i = 0; i < 256; i++) {
        if (freq2[i] > 0) {
            printf("  '%c' → %d vezes (%.1f%%)\n",
                   (char)i, freq2[i], (freq2[i] * 100.0) / tamanho2);
        }
    }
    printf("\n");

    NoHuffman *raiz2 = construir_arvore(freq2);
    CodigoHuffman tabela2[256];
    memset(tabela2, 0, sizeof(tabela2));
    char caminho2[256];
    gerar_codigos(raiz2, caminho2, 0, tabela2);

    printf("Códigos de Huffman:\n");
    for (int i = 0; i < 256; i++) {
        if (tabela2[i].tamanho > 0) {
            printf("  '%c' → %s (%d bits)\n",
                   (char)i, tabela2[i].bits, tabela2[i].tamanho);
        }
    }
    printf("\n");

    unsigned char saida2[100];
    int tam_codificado2 = huffman_encode(
        (unsigned char *)texto2, tamanho2, saida2, tabela2);

    int total_bits2 = 0;
    for (int i = 0; i < tamanho2; i++) {
        total_bits2 += tabela2[(unsigned char)texto2[i]].tamanho;
    }

    printf("Original:   \"%s\" (%d chars × 8 bits = %d bits)\n",
           texto2, tamanho2, tamanho2 * 8);
    printf("Huffman:    %d bits (%d bytes)\n", total_bits2, tam_codificado2);
    printf("Compressão: %.1f%% (vs ASCII 8-bit)\n\n",
           (1.0 - (double)total_bits2 / (tamanho2 * 8)) * 100.0);

    unsigned char decodificado2[100];
    int tam_decodificado2 = huffman_decode(saida2, total_bits2, raiz2, decodificado2);
    decodificado2[tam_decodificado2] = '\0';

    int ok2 = (tam_decodificado2 == tamanho2)
           && (memcmp(texto2, decodificado2, tamanho2) == 0);
    printf("Decodificado: \"%s\"\n", decodificado2);
    printf("Lossless:     %s\n\n",
           ok2 ? "SIM (idêntico ao original)" : "NÃO (ERRO!)");

    liberar_arvore(raiz2);

    // ----- Teste 3: Simulando dados de imagem (canal Y pós-quantização) -----
    printf("--- Teste 3: Simulando coeficientes DCT quantizados ---\n\n");

    // Depois da DCT + quantização, a maioria dos valores são 0,
    // com alguns valores pequenos e raros valores grandes.
    // Vamos simular isso:
    unsigned char dados3[100];
    // 60 zeros (simula coeficientes zerados pela quantização)
    memset(dados3, 0, 60);
    // 20 valores pequenos (1, 2, 3)
    for (int i = 60; i < 70; i++) dados3[i] = 1;
    for (int i = 70; i < 78; i++) dados3[i] = 2;
    for (int i = 78; i < 80; i++) dados3[i] = 3;
    // 15 valores médios
    for (int i = 80; i < 90; i++) dados3[i] = 10;
    for (int i = 90; i < 95; i++) dados3[i] = 20;
    // 5 valores grandes (raros)
    dados3[95] = 100; dados3[96] = 150;
    dados3[97] = 200; dados3[98] = 220; dados3[99] = 255;
    int tamanho3 = 100;

    int freq3[256];
    contar_frequencias(dados3, tamanho3, freq3);

    NoHuffman *raiz3 = construir_arvore(freq3);
    CodigoHuffman tabela3[256];
    memset(tabela3, 0, sizeof(tabela3));
    char caminho3[256];
    gerar_codigos(raiz3, caminho3, 0, tabela3);

    printf("Frequências dos valores mais comuns:\n");
    printf("  0   → %d vezes (60%%)\n", freq3[0]);
    printf("  1   → %d vezes (10%%)\n", freq3[1]);
    printf("  2   → %d vezes (8%%)\n", freq3[2]);
    printf("  ... valores raros: 3%% a 1%% cada\n\n");

    printf("Códigos de Huffman (seleção):\n");
    printf("  0   → %s (%d bits)  ← mais comum, código mais curto!\n",
           tabela3[0].bits, tabela3[0].tamanho);
    printf("  1   → %s (%d bits)\n", tabela3[1].bits, tabela3[1].tamanho);
    printf("  2   → %s (%d bits)\n", tabela3[2].bits, tabela3[2].tamanho);
    printf("  255 → %s (%d bits)  ← mais raro, código mais longo\n\n",
           tabela3[255].bits, tabela3[255].tamanho);

    unsigned char saida3[200];
    int tam_codificado3 = huffman_encode(dados3, tamanho3, saida3, tabela3);

    int total_bits3 = 0;
    for (int i = 0; i < tamanho3; i++) {
        total_bits3 += tabela3[dados3[i]].tamanho;
    }

    printf("Original:   %d bytes (= %d bits com tamanho fixo de 8 bits)\n",
           tamanho3, tamanho3 * 8);
    printf("Huffman:    %d bits (%d bytes)\n", total_bits3, tam_codificado3);
    printf("Compressão: %.1f%%\n\n",
           (1.0 - (double)total_bits3 / (tamanho3 * 8)) * 100.0);

    // Verificação lossless
    unsigned char decodificado3[200];
    int tam_decodificado3 = huffman_decode(saida3, total_bits3, raiz3, decodificado3);

    int ok3 = (tam_decodificado3 == tamanho3)
           && (memcmp(dados3, decodificado3, tamanho3) == 0);
    printf("Lossless:   %s\n\n",
           ok3 ? "SIM (idêntico ao original)" : "NÃO (ERRO!)");

    liberar_arvore(raiz3);

    // ----- Resumo -----
    printf("=== Resumo ===\n");
    printf("Teste 1 (ABRACADABRA):    %d bits → %d bits (%.1f%% economia)\n",
           tamanho1*8, total_bits1, (1.0-(double)total_bits1/(tamanho1*8))*100.0);
    printf("Teste 2 (muita repetição): %d bits → %d bits (%.1f%% economia)\n",
           tamanho2*8, total_bits2, (1.0-(double)total_bits2/(tamanho2*8))*100.0);
    printf("Teste 3 (coeficientes DCT): %d bits → %d bits (%.1f%% economia)\n",
           tamanho3*8, total_bits3, (1.0-(double)total_bits3/(tamanho3*8))*100.0);

    return 0;
}

cd ~/huffman-c
gcc main.c -o huffman
./huffman