Desenvolvimento de um utilitário de compressão de dados baseado em código Huffman com Haskell

Implementação de um programa de compressão de dados com codificação Huffman

• O que é código Huffman?
  • Realiza compressão de dados mapeando cada caractere para uma sequência única de bits
  • Caracteres que aparecem com frequência são mapeados para sequências de bits curtas, enquanto caracteres raros são mapeados para sequências mais longas
  • Exemplo: para a string aaab, a é mapeado para 1 e b para 0, resultando na compressão 1110

Código sem prefixo

• O que é um código sem prefixo?
  • Garante que nenhuma palavra-código seja prefixo de outra palavra-código
  • Exemplo: no caso de aaabc, a é mapeado para 1, b para 00 e c para 01, resultando na compressão 1110001

Geração de código sem prefixo

• Como gerar um código sem prefixo
  • Colocar todos os caracteres como folhas de uma árvore binária completa
  • Rotular o ramo esquerdo com 1 e o ramo direito com 0
  • O caminho da raiz até a folha descreve a palavra-código de cada caractere

Escrevendo o codificador

• Definições de tipos

  • Definição dos tipos Bit, Code, FreqMap, CodeMap, Weight e HTree
  • HTree é composto por Leaf e Fork

• Função de codificação

  • Função que converte uma string em bits
  • Usa FreqMap para calcular a frequência de cada caractere e, com base nisso, gera a árvore de Huffman
  • Gera a palavra-código de cada caractere a partir da árvore de Huffman

• Função de decodificação

  • Função que converte bits de volta para a string original
  • Usa a árvore de Huffman para decodificar os bits sequencialmente

Integração com arquivos binários

• Codificação de dados binários
  • Usa o módulo Data.ByteString.Char8 para ler bytes como caracteres
  • Usa o codificador de texto para codificar os dados binários

Serialização

• Função de serialização
  • Converte FreqMap e bits em bytes reais para salvar no arquivo
  • Usa a monad Put para gerar ByteString de forma eficiente

Desserialização

• Função de desserialização
  • Converte os dados lidos do arquivo em FreqMap e bits
  • Usa a monad Get para desserializar FreqMap

Integração do código completo

• Funções de compressão e descompressão de arquivos
  • Função compress: lê o arquivo, gera o mapa de frequências, codifica os dados e salva o arquivo compactado
  • Função decompress: lê o arquivo compactado, decodifica os dados e salva o arquivo original

Melhorias

• Multithreading

  • Decodifica seções do arquivo em paralelo
  • Adiciona uma tabela com limites de seções e tamanho esperado da decodificação para permitir processamento paralelo

• Codificação em passagem única

  • Gera o mapa de frequências em tempo real enquanto codifica
  • Elimina a necessidade de incluir o mapa de frequências no início do arquivo

• Código Huffman canônico

  • Decodifica em complexidade O(1) indexando um vetor em vez de percorrer a árvore

• Geração de código mais rápida

  • Se tentar codificação em passagem única, é necessário acelerar a geração do mapa de códigos

Opinião do GN⁺

• Vantagens da codificação Huffman

  • Permite compressão eficiente de dados ao mapear caracteres frequentes para sequências de bits curtas
  • Pode lidar com grandes volumes de dados minimizando o uso de memória

• Vantagens do Haskell

  • Permite escrever código modular aproveitando os benefícios da programação funcional
  • Pode otimizar o uso de memória por meio de avaliação preguiçosa

• Projetos com funcionalidade semelhante

  • Existem várias ferramentas de compressão de dados, como gzip e bzip2
  • É importante comparar vantagens e desvantagens de cada ferramenta para escolher a mais adequada

• Pontos a considerar ao adotar novas tecnologias

  • É preciso escolher o algoritmo adequado considerando desempenho e uso de memória
  • Técnicas de otimização, como codificação em passagem única, podem aumentar a eficiência

[GN⁺]

Comentários no Hacker News

• Existem algoritmos in-place baseados em arrays, o que reduz a necessidade de alocar árvores e seguir ponteiros

  • Quando aprendi a abordagem baseada em árvores na faculdade, eu não sabia que existiam outros métodos
  • A abordagem com árvores é intuitiva e útil, mas quando é preciso processar muitos dados rapidamente, faz mais sentido usar arrays in-place
  • Referência: "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

• Não é tecnicamente correto dizer que uma palavra-código não pode ser prefixo de outra palavra-código

  • A classe de códigos decodificáveis de forma única é um superconjunto dos códigos de prefixo
  • Por exemplo, o reverso de um código de prefixo ainda pode ser decodificado sem ambiguidade
  • Exemplo de código:

    a 1
    b 00
    c 10
    

  • O código de 'a' é prefixo do código de 'c', mas se for processado ao contrário, ainda pode ser decodificado sem ambiguidade

• Fiquei curioso se existe algum tutorial semelhante que cubra recursos mais avançados de escrita de programas em Haskell, como monad transformers, lenses etc.

• O curso de programação funcional da Coursera (Scala) oferece uma tarefa semelhante de codificação Huffman

  • Link: Coursera Scala Functional Programming

• Usei códigos Huffman para executar programas de macro do processador MICMAC com o mínimo de microciclos e microinstruções

  • Fiz um histograma das macroinstruções e, com base nele, escrevi um programa de microcódigo com decodificação progressiva
  • Na prática, isso provavelmente teria sido lento e inconveniente
  • A vantagem dos códigos Huffman é que eles permitem ajustar a profundidade do prefixo de acordo com a distribuição dos valores
  • Tive que lidar com predição de desvios em um modelo de processador sem pipeline superescalar

• Mais informações sobre codificação Huffman: Rosetta Code Huffman Coding

• Pergunta para programadores Haskell: como é o desempenho de Haskell para quem quer escrever código otimizado?

  • Tenho interesse especialmente no desempenho de computação numérica com operações matriciais e uso de SIMD

• Um comentário agradecendo por compartilhar

• Há um erro de digitação na tabela da seção "Creating prefix-free codes"

  • D deveria ser '0010' (no momento está incorretamente como '0110')
  • Fora isso, foi uma ótima leitura

• Codificação aritmética é melhor em quase todos os aspectos

  • Pode ser implementada com menos RAM e menos código
  • Oferece melhores taxas de compressão e descompressão
  • É mais fácil atualizar dinamicamente a probabilidade de aparecimento de outros símbolos ao longo do fluxo
  • Os códigos Huffman foram usados porque foram inventados primeiro e a codificação aritmética tinha patentes
  • Agora que as patentes expiraram, deveríamos usar o projeto melhor