Compactador e descompactador de Arquivos no formato .txt, usando o algoritmo de huffman.
O número de dados gerados pela internet em um ano chega na casa de impressionantes 350 zetabyttes de informação. O armazenamento dessa quantidade de dados não é barata. Por isso, programas de compactação de arquivos são extremamente necessários e utilizados no dia-a-dia.
Existem dois tipos de compactação possíveis para arquivos. A primeira alternativa seria a compactação com perda. Apesar de ser amplamente usada para arquivos de vídeo, áudio e imagem, não é recomendada para a compactação de documentos de textos. Para esse tipo de arquivo, onde a perda de um único bit de informação já faria diferença, foram criados algoritmos que mudam a representação de cada caractere de acordo com a sua frequência. O mais famoso desses algoritmos é o de Huffman. A codificação de Huffman é um método de compressão que usa as probabilidades de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo.
Uma árvore binária completa, chamada de árvore de Huffman é construída recursivamente a partir da junção dos dois símbolos de menor probabilidade, que são então somados em símbolos auxiliares e estes símbolos auxiliares colocados no conjunto de símbolos. O processo termina quando todos os símbolos forem unidos em símbolos auxiliares, formando uma árvore binária. A árvore é então percorrida, atribuindo-se valores binários de 1 ou 0 para cada aresta, e os códigos são gerados a partir desse percurso.
A codificação gerada tem também a garantia de não ser ambígua, pois nenhum código pode ser o prefixo de outro código.
O resultado do algoritmo de Huffman pode ser visto como uma tabela de códigos de tamanho variável para codificar um símbolo da fonte. Assim como em outros métodos de codificação, os símbolos mais comuns são geralmente representados usando-se menos dígitos que os símbolos que aparecem com menos frequência.
Basta baixar o repositório e compilar o arquivo zip.cpp na versão mais recente do C++
- execute o programa
- escolha uma opção
- Digite 1 para compactar um arquivo
.txt - Digite 2 para descompactar um arquivo
.compact
- Digite 1 para compactar um arquivo
- Apenas digite o caminho para o arquivo que será compactado que o programa criará um arquivo de saida do tipo
.compactnapasta compactados. Esta pasta é criada na pasta onde o usuario salvou o programa.
- Apenas digite o caminho para o arquivo que será descompactado que o programa criará um arquivo de saida do tipo
.txtnapasta descompactados. Esta pasta é criada na pasta onde o usuario salvou o programa.
| Texto | Tamanho original | Tamanho compactado | Taxa de compactação |
|---|---|---|---|
| Martin Luther King, Jr.I Have a Dream | 9.04 kb | 6.66 kb | aproximadamente 26% |
| We shall fight on the beaches | 20,8 kb | 14,6 kb | aproximadamente 29% |
| Lincoln's Gettysburg Address | 1,46 kb | 1,30 kb | aproximadamente 10% |
| Book 1 Genesis | 196 kb | 139 kb | aproximadamente 29% |
Matheus Souza Rozendo –– [email protected]
Distribuído sob a licença MIT. Veja LICENSE para mais informações.