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

 (lazamar.github.io)
1 pontos por GN⁺ 2024-07-06 | 1 comentários | Compartilhar no WhatsApp
  • Ao implementar um compressor com codificação de Huffman em cerca de 150 linhas de Haskell, o texto mostra uma estrutura que processa a codificação e a decodificação de arquivos binários arbitrários com memória constante
  • O código de Huffman atribui sequências de bits curtas aos valores mais frequentes e, com a condição de prefix-free code, permite que o decodificador interprete as sequências de bits sem ambiguidade
  • A implementação usa FreqMap, HTree e CodeMap para construir uma árvore a partir da tabela de frequências e gera o resultado gradualmente com a avaliação preguiçosa de concatMap e de um decodificador recursivo
  • Arquivos binários são tratados com Data.ByteString.Char8, manipulando bytes como se fossem Char; no início do resultado comprimido, a tabela de frequências é serializada, e a sequência de bits é armazenada com padding por byte
  • Nos testes, War and Peace caiu de 3.2M para 1.9M, e o binário ghcup de 106M foi reduzido para 84M; o máximo de resident set size observado ficou abaixo de 300KB

Ideia básica da compressão com código de Huffman

  • O objetivo é implementar um utilitário de compressão de dados usando Huffman coding em cerca de 150 linhas de Haskell
  • O código completo está disponível em um repositório no GitHub
  • O código de Huffman atribui uma sequência de bits única a cada caractere ou valor
    • Valores que aparecem com frequência usam sequências de bits curtas
    • Valores raros usam sequências de bits longas
    • O efeito de compressão surge quando valores comuns passam a ser representados com menos bits do que na representação original
  • No exemplo aaab, se definirmos a = 1 e b = 0, o resultado será 1110
    • É um exemplo em que uma string que exigiria 4 bytes em UTF-8 passa a ser representada em meio byte

Prefix-free code e árvore de Huffman

  • Para que a decodificação não seja ambígua, nenhum codeword pode ser prefixo de outro
    • Por exemplo, em aaabc, se atribuirmos a = 1, b = 10 e c = 01, 101 pode se tornar ambíguo entre ac e ba
  • Um prefix-free code pode ser construído como uma árvore binária completa
    • Todos os valores são colocados nas folhas
    • A aresta à esquerda recebe o rótulo 1, e a aresta à direita recebe 0
    • O caminho da raiz até a folha se torna o codeword correspondente àquele valor
  • A árvore de Huffman é gerada agrupando de baixo para cima os valores menos frequentes
    • Cada caractere vira um nó com seu weight, que é a contagem de ocorrências
    • Os dois nós com menor weight são agrupados em uma árvore
    • O weight da nova árvore é a soma dos weights dos dois nós
    • O processo se repete até restar apenas uma árvore
  • Com isso, os valores mais frequentes ficam mais próximos da raiz e passam a ter codewords mais curtos

Estrutura do codificador em Haskell

  • Os principais tipos da implementação são Bit, Code, FreqMap, CodeMap, Weight e HTree
    • Bit é One ou Zero
    • Code é [Bit]
    • FreqMap é Map Char Int e armazena a contagem de ocorrências de cada caractere
    • CodeMap é Map Char Code e armazena o codeword de cada caractere
    • HTree é Leaf Weight Char ou Fork Weight HTree HTree
  • HTree pode ser comparada com base no weight, o que simplifica a ordenação e a inserção durante a construção da árvore
  • countFrequency calcula quantas vezes cada caractere aparece em uma string
  • buildTree transforma FreqMap em uma lista de folhas, ordena essa lista e combina repetidamente os dois menores nós para formar a árvore de Huffman
  • buildCodes percorre a árvore e gera o codeword de cada caractere, adicionando One à esquerda e Zero à direita
  • encode :: FreqMap -> String -> [Bit] constrói a árvore e o mapa de códigos a partir de FreqMap e troca cada caractere da string de entrada por seu codeword, produzindo uma lista de bits

Processamento gradual com avaliação preguiçosa

  • A transformação central da codificação é concatMap codeFor str
    • Conceitualmente, isso transforma [Char] em [[Bit]] e depois achata tudo de volta em [Bit]
    • Graças à avaliação preguiçosa do Haskell, isso não funciona como um processo que primeiro codifica toda a entrada para só depois concatenar tudo
  • As pequenas listas avançam da esquerda para a direita e são achatadas dentro de uma grande lista de resultado
    • A cauda da lista de resultado permanece como um thunk ainda não avaliado
    • Quando um valor é solicitado, a próxima parte é calculada
  • O decodificador gera o resultado gradualmente da mesma forma
    • decode :: FreqMap -> [Bit] -> String se move para a esquerda ou para a direita na árvore conforme os bits
    • Ao chegar a uma folha, emite o caractere e reinicia a partir da raiz
    • Isso se repete até que o número total de caracteres decodificados seja igual ao weight da árvore de Huffman
  • O decodificador para com base na quantidade de caracteres, e não no fim da lista de bits de entrada
    • Isso acontece porque bits de padding são adicionados ao final na etapa de serialização para alinhar aos bytes
  • A função go, ao alcançar uma folha, retorna uma lista com head conhecido e uma chamada recursiva na tail, então o resultado pode ser avaliado antes de toda a recursão terminar

Processamento de arquivos binários e serialização

  • Dados binários podem ser vistos como repetições de um entre 256 bytes possíveis
  • Data.ByteString.Char8 permite tratar ByteString com operações de Char, e todo Char é truncado para 8 bits
    • Graças a essa propriedade, o codificador voltado a texto pode ser aplicado a dados binários sem grandes mudanças
  • O arquivo comprimido começa com o FreqMap necessário para a decodificação, seguido pela sequência de bits codificada
  • serializeFreqMap grava a tabela de frequências no seguinte formato
    • O tamanho do mapa é armazenado como Word8, mas salvando o valor com 1 a menos para ajustar o intervalo representável
    • Cada item grava a chave como Word8 e o valor de frequência como inteiro big-endian de 64 bits
  • serialize gera um ByteString com a mônada Put do pacote binary
    • Lê os bits um a um até completar um byte
    • Quando 8 bits são preenchidos, grava com putWord8
    • O último byte recebe padding com Zero no espaço restante

Desserialização e estratégia de memória constante

  • deserializeFreqMap lê a tabela de frequências serializada com Data.Binary.Get
    • Primeiro lê o tamanho e soma 1 para recuperar o número real de itens
    • Depois lê, em cada item, a chave Word8 e o valor de frequência de 64 bits para reconstruir o FreqMap
  • O restante da entrada não é processado inteiro com Get; em vez disso, pega-se do ByteString a parte após o offset e ela é convertida em uma lista de bits
  • deserialize retorna (FreqMap, [Bit]), e [Bit] é uma lista preguiçosa que não é totalmente calculada de imediato
    • Exigir o comprimento dessa lista forçaria a avaliação completa, então isso deve ser evitado
  • O motivo para não usar Get em toda a entrada é que o bind da mônada impõe ordem de avaliação
    • Isso leva a uma estrutura em que a lista só poderia ser retornada depois de processar toda a entrada
  • A estratégia de memória constante consiste em avaliar apenas o próximo pequeno trecho da entrada cada vez que um bit de saída precisa ser escrito
    • Parte do ByteString é avaliada, e o fragmento correspondente do arquivo é lido
    • A saída processada é gravada no arquivo
    • Fragmentos de entrada e listas de bits que já não são mais referenciados podem ser recuperados pelo garbage collector
  • Como FreqMap tem no máximo 256 itens no caso de bytes, o overhead permanece de tamanho constante

CLI para compressão e descompressão de arquivos

  • compress lê o arquivo de entrada duas vezes
    • Na primeira passagem, constrói o FreqMap
    • Na segunda, codifica os dados usando esse FreqMap
  • Se o arquivo fosse lido só uma vez e a mesma referência fosse passada a encode, a referência ao arquivo inteiro precisaria ser mantida em memória mesmo depois da criação da tabela de frequências
  • A abordagem de duas leituras permite liberar a memória já processada tanto na criação da tabela quanto na codificação
  • decompress lê o arquivo comprimido, obtém FreqMap e a lista de bits com deserialize e grava no arquivo o resultado de decode
  • A CLI aceita os seguintes argumentos
    • compress FILE FILE
    • decompress FILE FILE
  • Como só usa pacotes incluídos no GHC, é possível compilar com ghc -O2 Main.hs -o main sem cabal

Resultado da execução e uso de memória

  • No teste com o arquivo de texto War and Peace de Tolstói, o resultado após compressão e descompressão foi idêntico no diff
    • Original WarAndPeace.txt: 3.2M
    • Arquivo comprimido: 1.9M
    • Arquivo descomprimido: 3.2M
    • O tamanho foi reduzido em cerca de 40%
  • A compressão e a descompressão também funcionaram com o arquivo binário maior ghcup
    • Original ghcup: 106M
    • Arquivo comprimido: 84M
    • Arquivo descomprimido: 106M
    • O tempo de compressão foi de cerca de 15.173 segundos, e o de descompressão de cerca de 14.555 segundos
  • Segundo +RTS -s, o maximum resident set size durante o processamento de ghcup ficou abaixo de 300KB
  • Os dois processos usaram menos de 10MB de memória para executar
  • Onde o tempo é gasto pode ser visto em um profile separado

Pontos que ainda podem ser melhorados

  • O objetivo da implementação era ser um utilitário de compressão o mais simples e claro possível; para ganhar eficiência, seria necessária uma implementação mais complexa
  • Algumas melhorias possíveis são as seguintes
    • Multithreading: decodificar trechos do arquivo em paralelo, adicionando ao início do arquivo comprimido uma tabela com limites de blocos e tamanho esperado da decodificação, já que não é possível saber os limites dos codewords em posições arbitrárias
    • Codificação em passagem única: começar com uma tabela de frequências inicial em que todos os bytes têm frequência 1 e, a cada byte observado, codificá-lo primeiro e depois atualizar a tabela
    • Canonical Huffman codes: em vez de percorrer a árvore em O(log n) na decodificação, usar o código como índice de vetor para buscar O(1); mais detalhes em Canonical Huffman code
    • Geração de códigos mais rápida: na codificação em passagem única, a criação de CodeMap precisaria ser muito mais rápida, e há maneiras mais rápidas de gerar codewords sem construir a árvore
  • No futuro, usando LZ77, uma abordagem de dicionário adaptativo, seria possível implementar gzip em conjunto com códigos de Huffman

Leituras relacionadas

1 comentários

 
GN⁺ 2024-07-06
Comentários do Hacker News

  • Existe um algoritmo in-place baseado em array para esse trabalho, que reduz a necessidade de alocar árvores e seguir ponteiros
    Quando aprendi a abordagem baseada em árvore na faculdade, eu não sabia que existia outra forma, e fico curioso se com outras pessoas foi igual
    A abordagem com árvore é intuitiva e ajuda no entendimento, mas as situações em que compressão mais importa normalmente são aquelas em que há muitos dados e se quer executar rápido, então pode fazer mais sentido trabalhar com arrays in-place
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • Em geral, também vale consultar On the Implementation of Minimum Redundancy Prefix Codes, de Moffat e Turpin
      Charles Bloom recomendou fortemente e depois acrescentou uma explicação
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • O padrão JPEG ITU T.81 (1992) descreve esse algoritmo em um fluxograma, então esse conhecimento sobre Huffman baseado em array aparentemente já era conhecido em algum nível nos anos 80
    • Isso é mencionado no fim do texto e deixado como exercício para o leitor
    • A frase “fico curioso quantos de vocês também se encaixam nisso” soa como uma list comprehension

  • A afirmação de que “nenhuma palavra-código deve ser prefixo de outra palavra-código para que não haja ambiguidade” não é estritamente correta
    Os chamados códigos unicamente decodificáveis não são ambíguos e formam um superconjunto dos códigos de prefixo
    Um exemplo simples é inverter um código de prefixo. No exemplo do texto, isso daria a 1, b 00, c 10
    O código de a é prefixo do código de c, mas, se você processar a sequência de códigos ao contrário, ainda será possível decodificar sem ambiguidade. Seria interessante ver um código unicamente decodificável que não seja nem de prefixo nem o seu reverso

    • Compondo um código de prefixo com um código de sufixo, dá para construir esse tipo de código sem ficar desnecessariamente ineficiente
      Se A 0, B 01, C 11, e depois a A 0, b BA 010, c BB 0101, d BC 0111, e C 11, então obtemos {a=0,b=010,c=0101,d=0111,e=11}
      Como é possível decodificar de forma única de trás para frente com algo como 0->A, e depois novamente da frente para trás com algo como A->a, ele é claramente unicamente decodificável
      Em termos de comprimento, ele é igual ao código de prefixo ótimo {a=0,b=110,c=1110,d=1111,e=10}, então é um dos vários códigos ótimos para a mesma distribuição de probabilidades
      Ao mesmo tempo, por causa de a=0 e b=010, ele não é nem um código de prefixo nem um código de sufixo. Na verdade, em geral não é possível fazer decodificação progressiva em nenhuma direção, e para distinguir cee...ee? de bee...ee?, ou ?cc...cca de ?cc...ccb, pode ser necessário um lookahead infinito mesmo para identificar um único símbolo
      Não sei se a otimalidade sempre se preserva ao compor um código de prefixo independentemente ótimo com um código de sufixo independentemente ótimo, mas nos casos mais simples em que pensei, excluindo códigos degenerados 1:1, pareceu funcionar
    • É um problema mais interessante do que parece. Para começar com uma resposta adversarial, dá para usar algo como a 101, b 1
      Mas é um código ruim, porque sempre seria melhor usar a=1, b=0
      A desigualdade de Kraft informa quais conjuntos de comprimentos de código podem ser unicamente decodificáveis, e a codificação de Huffman consegue atingir todos esses conjuntos. Então, se você está fazendo codificação de símbolos, não há motivo para usar um código sem prefixo, a menos que vá mudar para outro esquema, como ANS ou codificação aritmética
      Ainda assim, não sei se existe um código unicamente decodificável com o mesmo conjunto de comprimentos de um código de Huffman ótimo, mas que não seja nem um código de prefixo nem seu inverso, um código de sufixo
      Se eu fosse gastar tempo nisso, olharia o https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm e tentaria achar um contraexemplo por força bruta ou tirar uma prova do funcionamento do algoritmo
    • É um exemplo estranho, mas e a 1, b 101?
      Não é livre de prefixo nem livre de sufixo, mas cada ocorrência de 0 corresponde a uma ocorrência de b
      Claro, isso é obviamente ineficiente, então no fim a pergunta é se existe algum código ótimo que não seja nem livre de prefixo nem livre de sufixo
      Pesquisando, encontrei https://blog.plover.com/CS/udcodes.html dando o exemplo de código unicamente decodificável a 0011, b 011, c 11, d 1110
      A única relação de prefixo é c ser prefixo de d, então ele está “quase” livre de prefixo. Se a mensagem começa com 1, parece que basta encontrar o primeiro 0 e ver se a quantidade de 1s antes dele é ímpar ou par, então dá para entender por que é unicamente decodificável
      Mas não lembro como mostrar para qual distribuição de probabilidades isso seria ótimo; meu conhecimento de criptografia está enferrujado demais
    • Interessante, mas imagino que normalmente não se use isso porque talvez seja preciso ler uma sequência de bits muito longa até aparecer o bit que resolve a ambiguidade
      Por exemplo, em algo como 100000000000000001, para saber se o primeiro código é a ou c, seria preciso ler até o fim da sequência de zeros

  • Queria saber se existe algum tutorial parecido com este, de ir construindo um programa em Haskell, mas cobrindo recursos mais avançados como transformadores de mônadas ou lenses

    • Recomendo o livro Haskell in Depth. Ele cobre transformadores de mônadas no capítulo 6 e lenses nos capítulos 3 e 14
      Também aborda outros recursos avançados, como Template Haskell e concorrência, e há até um capítulo sobre trabalhar com bancos de dados SQL em Haskell
    • Vale a pena ver https://github.com/turion/rhine-koans
      É um tutorial da biblioteca de FRP Rhine, com bons comentários e testes

  • No curso de programação funcional com Scala da Coursera também há uma tarefa de codificação de Huffman bem parecida, e como existe correção automática, é ótimo para quem quer tentar resolver por conta própria
    https://www.coursera.org/learn/scala-functional-programming?...

  • A última vez que usei código de Huffman foi no macroprograma do processador MICMAC, ou seja, para executar texto em assembly com o mínimo de microciclos e o mínimo de microinstruções
    Comecei com o histograma das macroinstruções executadas e, se bem me lembro, primeiro escrevi um interpretador em C para contar quantas vezes cada instrução era executada
    Depois disso, criei um programa de microcódigo de decodificação progressiva que implementava todas as macro-operações ISA necessárias. Acho que a ISA de macroinstruções que criei não era orientada a bytes, e sim em nível de bits
    No mundo real, isso teria sido lento e inconveniente, mas a vantagem do código de Huffman é que ele permite ajustar a profundidade do prefixo de acordo com a distribuição dos valores, então não é necessário criar um código enviesado para um lado por causa de um prefixo de 1 bit
    Além disso, o microprograma era um modelo de processador com pipeline não superescalar, então também era preciso lidar com previsão de desvio. Se um desvio fosse previsto incorretamente, ciclos seriam desperdiçados com a paralisação do pipeline enquanto o desvio correto se propagava adiante

  • https://rosettacode.org/wiki/Huffman_coding

  • Como parece que há programadores Haskell por aqui, queria perguntar: hoje em dia, quão rápido é Haskell quando usado por alguém que se preocupa com otimização?
    Em especial, tenho curiosidade sobre o desempenho em tarefas de computação numérica e que se beneficiam de SIMD, como operações com matrizes

    • A velocidade de Haskell pode competir com linguagens de sistema, mas é preciso ter em mente que a principal vantagem está na facilidade de abstração
      O ponto central é que é fácil montar várias partes em um programa coerente e bem organizado. Isso é importante para o programa inteiro, não apenas para loops apertados
      Haskell tem uma FFI boa, então partes que essencialmente exigem otimização imperativa podem ser levadas para uma linguagem sem garbage collector. Se você encapsular essas partes em uma biblioteca com bons tipos, qualquer código Haskell com os tipos corretos pode aproveitar esse desempenho bruto
      Foi assim que fizeram aplicações Haskell de alto desempenho na Meta. Escreviam programas Haskell bonitos, grandes e rápidos, mas colocavam componentes em C++ em algumas partes especializadas. Gastavam 99% do tempo montando aplicações mais úteis do lado Haskell
    • No trabalho cotidiano de backend, web e CLI, gosto do desempenho de Haskell. Mas, quando preciso escrever código focado em performance, desço para Rust
      Ainda assim, Haskell não é exatamente lento. Dá para usar como exemplo um pequeno programa que conta o número de bits 1 em um arquivo
      Quando compilado com -msse4.2, ele usa corretamente a instrução de hardware popcount e processa um arquivo de entrada de 1GB em 0m0,090s. Arredondando em unidades de MB, o heap usado é 0
      Quando compilado sem -msse4.2, leva 0m0,293s
      Nunca fiz cálculo de matrizes diretamente, mas como ponto de partida eu daria uma olhada em repa, accelerate e massiv
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • Encontrei Sam Derbyshire na ZuriHac e ouvi dizer que todo o trabalho difícil de arquitetura para suporte a SIMD já foi concluído
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      Pode entrar no GHC 9.12. Mas, por enquanto, mira apenas vetores de 128 bits e, a menos que outras pessoas contribuam, provavelmente será focado principalmente em operações de ponto flutuante
      O patch está aqui
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • Na prática, em qualquer linguagem, incluindo C, código otimizado pelo compilador não consegue ser tão rápido quanto código otimizado manualmente em bibliotecas como BLAS
      Em certo nível, a escolha da linguagem hospedeira não importa tanto. Se você realmente leva velocidade a sério, de qualquer forma vai delegar os cálculos para algo externo
      Essa é a mesma razão pela qual código de IA, que provavelmente é uma das maiores fontes de uso de recursos computacionais no mundo, pode ser escrito em Python fora das bibliotecas de computação de baixo nível
      Respondendo diretamente: o compilador GHC é muito bom. Código de alto nível funciona muito bem, e na maioria das aplicações reais o gargalo de desempenho não é algo como operações de largura única versus SIMD, mas sim questões de arquitetura. A “assintótica arquitetural” de Haskell é bastante favorável
      Acho que o GHC já tem ou está ganhando suporte a SIMD, mas eu não focaria nisso ao avaliar desempenho
      Eu não escreveria um algoritmo de multiplicação de matrizes diretamente em Haskell, mas, se estivesse levando velocidade realmente a sério, também não o escreveria diretamente em Rust ou C
      Computação numérica é frequentemente usada como métrica de desempenho, mas quase ninguém de fato tem gargalo nisso e, se tiver, a linguagem de alto nível usada importa pouco
    • Haskell realmente brilha quando você quer escrever código declarativo de alto nível
      O desempenho desse estilo normalmente é suficiente para trabalho de CLI ou backend web. Há ferramentas para escrever código de baixo nível bem rápido, mas elas são meio desajeitadas, então talvez não sejam a melhor opção se isso for tudo o que você quer fazer
      Ainda assim, quando há alguns hotspots concentrados que precisam de otimização, funciona bastante bem
      As ferramentas de profiling de CPU são boas, então encontrar e otimizar hotspots de CPU é relativamente agradável. Por outro lado, rastrear vazamentos de memória estranhos, que podem surgir mais facilmente por causa da avaliação preguiçosa, pode ser extremamente frustrante
      Pelos resultados do benchmarks game, as implementações Haskell mais rápidas costumam ser de 2 a 5 vezes mais lentas que as versões C mais rápidas e são escritas em um estilo bem imperativo
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • Acho que há um erro de digitação na tabela da seção “Creating prefix-free codes”. D deveria ser 0010, não 0110

    • Fiquei um tempão quebrando a cabeça tentando entender como 0110 poderia não ser ambíguo, mas agora faz sentido

  • Fiquei curioso sobre o que está na camiseta da mulher na imagem
    Link direto: https://lazamar.github.io/images/data-compressor.svg