O algoritmo de Huffman é usado para compactar ou codificar dados. Normalmente, cada caractere em um arquivo de texto é armazenado como oito bits (dígitos, 0 ou 1) que mapeiam para aquele caractere usando uma codificação chamada ASCII. Um arquivo codificado por Huffman divide a estrutura rígida de 8 bits para que os caracteres mais comumente usados sejam armazenados em apenas alguns bits ('a' pode ser "10" ou "1000" em vez de ASCII, que é "01100001") Os caracteres menos comuns, então, geralmente ocupam muito mais do que 8 bits ('z' pode ser "00100011010"), mas como ocorrem tão raramente, a codificação Huffman, em geral, cria um arquivo muito menor do que o original.
Passos
Parte 1 de 2: codificação
Etapa 1. Conte a freqüência de cada caractere no arquivo a ser codificado
Inclua um caractere fictício para marcar o final do arquivo - isso será importante mais tarde. Por enquanto, chame-o de EOF (fim do arquivo) e marque-o como tendo uma frequência de 1.
Por exemplo, se você quiser codificar um arquivo de texto com a leitura "ab ab cab", terá 'a' com frequência 3, 'b' com frequência 3, '' (espaço) com frequência 2, 'c' com frequência 1 e EOF com frequência 1
Etapa 2. Armazene os personagens como nós da árvore e coloque-os em uma fila de prioridade
Você estará construindo uma grande árvore binária com cada personagem como uma folha, então você deve armazenar os personagens em um formato de forma que eles possam se tornar nós da árvore. Coloque esses nós em uma fila de prioridade com a frequência de cada personagem como a prioridade de seu nó.
- Uma árvore binária é um formato de dados em que cada parte dos dados é um nó que pode ter até um pai e dois filhos. Geralmente é desenhado como uma árvore ramificada, daí o nome.
- Uma fila é uma coleção de dados apropriadamente nomeada em que a primeira coisa a entrar na fila é também a primeira coisa a sair (como esperar na fila). Em uma fila de prioridade, os dados são armazenados em ordem de prioridade, de forma que a primeira coisa a sair é a coisa mais urgente, a coisa com a menor prioridade, ao invés da primeira coisa enfileirada.
- No exemplo "ab ab cab", sua fila de prioridade seria assim: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Etapa 3. Comece a construir sua árvore
Remova (ou desenfileire) as duas coisas mais urgentes da fila de prioridade. Crie um novo nó da árvore para ser o pai desses dois nós, armazenando o primeiro nó como seu filho esquerdo e o segundo como seu filho direito. A prioridade do novo nó deve ser a soma das prioridades de seu filho. Em seguida, coloque esse novo nó na fila de prioridade.
A fila de prioridade agora se parece com isto: {'': 2, novo nó: 2, 'a': 3, 'b': 3}
Etapa 4. Conclua a construção de sua árvore:
repita a etapa acima até que haja apenas um nó na fila. Observe que, além dos nós que você criou para os personagens e suas frequências, você também irá desenfileirar, se transformar em árvores e reenfilar os nós pais, nós que já são árvores.
- Quando terminar, o último nó da fila será a raiz da árvore de codificação, com todos os outros nós ramificando a partir dela.
- Os caracteres usados com mais frequência serão as folhas mais próximas do topo da árvore, enquanto os caracteres raramente usados serão posicionados na parte inferior da árvore, mais longe da raiz.
Etapa 5. Crie um mapa de codificação. Ande pela árvore para alcançar cada personagem. Cada vez que você visita o filho esquerdo de um nó, é um '0'. Cada vez que você visita o filho certo de um nó, é um '1'. Quando você chegar a um caractere, armazene o caractere com a sequência de 0s e 1s necessária para chegar lá. Essa sequência é como o caractere será codificado no arquivo compactado. Armazene os personagens e suas sequências em um mapa.
- Por exemplo, comece na raiz. Visite o filho esquerdo da raiz e, em seguida, visite o filho esquerdo desse nó. Como o nó em que você está agora não tem filhos, você alcançou um personagem. Isto é ' '. Como você caminhou para a esquerda duas vezes para chegar aqui, a codificação para '' é "00".
- Para esta árvore, o mapa terá a seguinte aparência: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Etapa 6. No arquivo de saída, inclua o mapa de codificação como um cabeçalho
Isso permitirá que o arquivo seja decodificado.
Etapa 7. Codificar o arquivo
Para cada caractere no arquivo a ser codificado, escreva a sequência binária que você armazenou no mapa. Depois de terminar de codificar o arquivo, certifique-se de adicionar o EOF ao final.
- Para o arquivo "ab ab cab", o arquivo codificado terá a seguinte aparência: "1011001011000101011011".
- Os arquivos são armazenados como bytes (8 bits ou 8 dígitos binários). Como o algoritmo de codificação de Huffman não usa o formato de 8 bits, os arquivos codificados geralmente não têm comprimentos múltiplos de 8. Os dígitos restantes serão preenchidos com 0s. Nesse caso, dois 0s seriam adicionados ao final do arquivo, que se parece com outro espaço. Isso pode ser um problema: como o decodificador saberia quando parar de ler? No entanto, como incluímos um caractere de fim de arquivo, o decodificador fará isso e parará, ignorando tudo o que foi adicionado depois.
Parte 2 de 2: decodificação
Etapa 1. Leia um arquivo codificado por Huffman
Primeiro, leia o cabeçalho, que deve ser o mapa de codificação. Use isso para construir uma árvore de decodificação da mesma forma que você construiu a árvore que usou para codificar o arquivo. As duas árvores devem ser idênticas.
Etapa 2. Leia no binário um dígito de cada vez
Percorra a árvore enquanto lê: se você ler em um '0', vá para o filho à esquerda do nodo em que você está, e se você ler em um '1', vá para o filho certo. Quando você alcança uma folha (um nó sem filhos), você chega a um personagem. Escreva o caractere no arquivo decodificado.
Devido à forma como os caracteres são armazenados na árvore, os códigos de cada caractere têm uma propriedade de prefixo, de modo que nenhuma codificação binária de caractere pode ocorrer no início da codificação de outro caractere. A codificação de cada personagem é totalmente única. Isso torna a decodificação muito mais fácil
Etapa 3. Repita até chegar ao EOF
Parabéns! Você decodificou o arquivo.
