O liman (linux + huffman) é um programa capaz de reduzir o tamanho total em bytes de arquivos (ex: .txt, .png , .jpg, .gif e outros), aplicando compressão sem perda de dados baseada no algoritmo de Huffman.

• clonar esse repositorio

    git clone https://github.com/paisdegales/winrar.git

• ir até a pasta onde o projeto foi salvo

    cd path/to/project

• gerar os executaveis

    make

• compactar um arquivo contido na pasta input

    make compress input="nome_do_arquivo.txt"

• descompactar um arquivo contido na pasta output

    make decompress input="nome_do_arquivo.txt"

• limpar todos os objetos/compactados/executaveis

    make clean

.
├── input
├── lib
│   ├── data-structures
│   └── utils
└── src
    ├── data-structures
    └── utils

O algoritmo de Huffman funciona recodificando códigos comumente usados para codificar caracteres.

A exemplo da representação ASCII estendida, essa codifica 256 caracteres usando 8 bits por caracter. Portanto, se um arquivo de texto chamado senha.txt contém 4 caracteres, ao todo seu tamanho é 32 bits.

O algoritmo de Huffman atua na redução do número de bits por caracter, de forma a criar códigos que utilizam menos bits do que o usual para codificar caracteres.

Assim, em vez dos usuais 8 bits por caracter, por vezes o algoritmo de Huffmann permite que sejam utilizados apenas 4 bits, 5 bits ou 6 bits para armazenar 1 caracter, o que reduz consideravelmente o tamanho total de alguns tipos de arquivo.

Quanto aos arquivos .comp gerados pelo programa, esses são arquivos binários, sendo que o formato com que são escritos é o seguinte:

<tabela de huffman em formato de árvore> <mensagem codificada segundo tabela de huffman>

A descompressão dos arquivos .comp basicamente segue 2 passos:

1. remontar a tabela de huffman
2. ler a mensagem em binário e trocar o código de huffman pelo seu correspondente ASCII estendido

tabela de huffman: um estrutura em arvore que dispõe uma correspondência 1:1 entre os códigos de huffman e os codigos da tabela ASCII

A compactação via algoritmo de Huffman, ainda que sem perda, não é tão eficiente quanto outras existentes.

tl;dr: em geral, quanto mais vezes alguns dos caracteres de uma codificação de caracteres se repetem em um texto, mais eficiente se torna o algoritmo de Huffmann.

O projeto contem alguns arquivos na pasta input, que foram usados para testar o desempenho da compactação para diferentes tipos de arquivo.

A estratégia de compactação proposta pelo algoritmo de Hufmann nem sempre é eficiente. Pela forma como funciona, essa se torna mais proveitosa para textos/arquivos que utilizam caracteres que se repetem com muita frequência e que utilizam um número restrito de letras de um alfabeto.

A exemplo dos textos escritos em ingles/portugues, esses em geral utilizam apenas 26 (letras) + 10 (números) caracteres, totalizando 36 caracteres. Nesse sentido, apenas 36 dos 256 caracteres previstos pela representação ASCII estendida são em geral usados, sendo esse o cenário predileto para a aplicação do algoritmo de Huffman (salvo algumas exceções). Essa percepção se confirma pelas boas taxas de compactação dos arquivos .txt testados.

É notório, ainda, que alguns arquivos de extensões como .png, .jpg, .gif não apresentam taxas de compressão consideráveis e, algumas vezes, na verdade sofrem um efeito contrário àquele esperado de uma compressão de arquivos.

Isso ocorre porque esses arquivos utilizam praticamente todos os caracteres da tabela ASCII estendida na codificação da informação ali presente. Para esses arquivos, outros tipos de compactadores são necessários para armazenar a informação de forma eficiente e sem perdas.