Como comprimir dados usando codificação de huffman

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 mapear para esse caractere usando uma codificação chamada ASCII. Um arquivo codificado pelo Huffman quebra a estrutura rígida de 8 bits para que os caracteres mais usados ​​sejam armazenados em apenas alguns bits (`A` pode ser "10" ou "1000" em vez do ASCII, que é "01100001"). Os caracteres menos comuns, então, muitas vezes ocuparão muito mais de 8 bits (`Z` pode ser "00100011010"), mas porque eles ocorrem tão raramente, o Huffman codificando, no geral, cria um arquivo muito menor do que o original.

Passos

Parte 1 de 2:
Codificação
  1. Imagem intitulada Compactar dados usando Huffman Coding Step 1
1. Conte a frequência de cada caractere no arquivo a ser codificado. Inclua um personagem manequim para marcar o final do arquivo - isso será importante mais tarde. Por enquanto, ligue para o Eof (final do arquivo) e marque-o como tendo uma frequência de 1.
  • Por exemplo, se você quiser codificar uma leitura de arquivo de texto "ab abb táxi," Você teria `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.
  • Imagem intitulada Compactar dados usando Huffman Coding Step 2
    2. Loja personagens como nós de árvore e colocá-los em uma fila prioritária. Você estará construindo uma grande árvore binária com cada personagem como uma folha, então você deve armazenar os personagens em um formato que eles podem se tornar nós da árvore. Coloque esses nós em uma fila prioritária com a frequência de cada personagem quanto a prioridade do nó.
  • Uma árvore binária é um formato de dados em que cada pedaço de dados é um nó que pode ter até um pai e dois filhos. Muitas vezes é desenhada como uma árvore ramificadora, daí o nome.
  • Uma fila é uma coleção de dados apropriadamente chamada, onde a primeira coisa a entrar na fila também é a primeira coisa a sair (como espera na linha). Em um prioridade Fila, os dados são armazenados em ordem de sua prioridade, de modo que a primeira coisa a sair é a coisa mais urgente, a coisa com a menor prioridade, em vez da primeira coisa fechada.
  • No "ab abb táxi" Exemplo, sua fila prioritária ficaria assim: {`C`: 1, EOF: 1 `: 2,` A `: 3,` B `: 3}
  • Imagem intitulada Compactar dados usando Huffman Coding Step 3
    3. Comece a construir sua árvore. Remova (ou Dequeue) as duas coisas mais urgentes da fila prioritária. Crie um novo nó da árvore para ser pai desses dois nós, armazenando o primeiro nó como a sua criança esquerda e a segunda como sua criança certa. A prioridade do novo nó deve ser a soma das prioridades de sua criança. Em seguida, enqueue este novo nó na fila prioritária.
  • A fila prioritária agora se parece com isso: {``: 2, novo nó: 2, `A`: 3, `B`: 3}
  • Imagem intitulada Compactar dados usando Huffman Coding Step 4
    4. Termine construindo sua árvore: Repita o passo acima até que haja apenas um nó na fila. Observe que, além dos nós que você criou para os personagens e suas freqüências, você também será dequeuing, transformando-se em árvores e re-enqueuing nós, nós que já são árvores.
  • Quando terminar, o último nó na fila será o raiz da árvore codificadora, com todos os outros nós ramificando-se.
  • Os personagens mais utilizados 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.


  • Imagem intitulada Compactar dados usando Huffman Coding Step 5
    5. Criar um Mapa de codificação. Caminhe pela árvore para chegar a cada personagem. Toda vez que você visita a criança esquerda de um nó, isso é um `0`. Toda vez que você visita a criança certa de um nó, isso é um `1`. Quando você chegar a um personagem, guarde o personagem com a sequência de 0s e 1s que levou para chegar lá. Esta sequência é o que o personagem será codificado como no arquivo compactado. Armazene os personagens e suas seqüências em um mapa.
  • Por exemplo, comece na raiz. Visite a criança da raiz esquerda e visite a criança esquerda do nó. Desde o nó você está agora não tem filhos, você chegou a um personagem. Isso é ` `. Desde que você andou à esquerda duas vezes para chegar aqui, a codificação para `` é "00".
  • Para esta árvore, o mapa ficará assim: {``:"00", `uma`:"10", `B`:"11", `c`:"010", Eof:"011"}.
  • Imagem intitulada Compactar dados usando Huffman Coding Step 6
    6. No arquivo de saída, inclua o mapa de codificação como um cabeçalho. Isso permitirá que o arquivo seja decodificado.
  • Imagem intitulada Compactar dados usando Huffman Coding Step 7
    7. Codifique 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 abb táxi", O arquivo codificado ficará assim: "1011001011000101011011".
  • Arquivos são armazenados como bytes (8 bits ou 8 dígitos binários). Como o algoritmo de codificação Huffman não usa o formato de 8 bits, os arquivos codificados geralmente não têm comprimentos que são múltiplos de 8. Os dígitos restantes serão preenchidos com 0s. Neste caso, dois 0s seriam adicionados no 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, porque incluímos um caractere final de arquivo, o decodificador chegará a isso e, em seguida, parará, ignorando qualquer outra coisa que tenha sido adicionada depois.
    • Parte 2 de 2:
    Decodificação
    1. Imagem intitulada Compactar dados usando Huffman Coding Step 8
    1. Leia em um arquivo codificado com 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 maneira que você construiu a árvore usada para codificar o arquivo. As duas árvores devem ser idênticas.
  • Imagem intitulada Compactar dados usando Huffman Coding Step 9
    2. Leia no binário um dígito de cada vez. Atravessar a árvore como você leu: Se você ler em um `0`, vá para a criança esquerda do nó que você está, e se você ler em um `1`, vá para a criança certa. Quando você chegar a uma folha (um nó sem filhos), você chegou a um personagem. Escreva o personagem no arquivo decodificado.
  • Por causa da maneira como os personagens são armazenados na árvore, os códigos para cada personagem têm um Propriedade do prefixo, para que a codificação binária de nenhum personagem possa ocorrer no início da codificação de outra personagem. A codificação para cada caractere é totalmente única. Isso torna a decodificação muito mais fácil.
  • Imagem intitulada Compactar dados usando Huffman Coding Step 10
    3. Repita até chegar ao eof. Parabéns! Você decodificou o arquivo.

    • Pontas

    Compartilhe na rede social:
    Semelhante