HUFFMAN BREVE ANALISE DO ALGORITMO

SÃO LUCAS JI-PARANÁ

SISTEMAS DE INFORMAÇÃO

ESTRUTURA DE DADOS

VICTOR LUCA DE MELLO RODRIGUES

ALGORITMO DE HUFFMAN

JI-PARANÁ

2020

SUMÁRIO

1 INTRODUÇÃO        3

2 DESENVOLVIMENTO        4

2.1 ÁRVORES        4

2.1.1 ÁRVORES BINÁRIAS        4

2.2 CODIFICAÇÃO DE HUFFMAN        5

3 CONSIDERAÇÕES FINAIS        7

REFERÊNCIAS        8

        

1 INTRODUÇÃO

          Este estudo refere-se ao tema do Algoritmo de Huffman dentro dos conceitos de Estrutura de Dados, onde é necessário primeiro vermos sobre arvores binárias e seus conceitos atrelados, pois as mesmas são a base para a solução de compactação criada por Huffman.

---

2 DESENVOLVIMENTO

O Algoritmo de Huffman tem como base as arvores binarias, onde coloca nos últimos nós da arvore as letras com menor frequências, pois considera que os mesmos podem possuir maior codificação final, devido ao seu baixo uso e repetição durante o processamento final.

 

2.1 ÁRVORES

Porém primeiro devemos entender o que é uma arvore, uma arvore, é uma estrutura de dados não linear, onde os dados estão dispostos de forma hierárquica, onde seus elementos podem estar acima ou abaixo de outros elementos.

É eficiente e simples, além de ser uma boa demonstração para inúmeros problemas da vida real, pois tem a mesma topologia hierárquica.

Uma árvore é formada por elementos que contem informação, chamados de Nodos ou Nós, que estão ligados diretamente a um Nó raiz, sendo o nó superior que não possui outro acima dele na hierarquia, os nós finais são chamados então de Nós folhas, por serem os mais distantes da raiz.

Por definição formal, se uma árvore tiver numero total de nós igual a Zero, ela é uma árvore vazia, mas se o numero total for maior do que Zero, um desses nós será raiz, do qual saem as subárvores.

As principais aplicações de Árvores são em áreas relacionadas a dados, como Banco de Dados, Estruturas de Pastas e Arquivos, Interfaces Gráficas, entre outros.

2.1.1 Árvores Binárias

Árvores Binárias, são derivadas da ideia original de árvores, porém com algumas diferenças especificas para a área da computação, como a limitação do numero de nós filhos que um nó qualquer pode ter, sendo 0, 1 e 2, se ele tiver 0, é um nó folha.

Outro conceito útil que se apresenta na árvore binária é o de profundidade, que é a distância entre o nó e a raiz, conceito de grande importância para o Algoritmo de Huffman, pois se coloca os dados com maior frequência dentro dos nós com menor profundidade para que tenhamos menor custo de memória.

2.2 Codificação de Huffman

Em 1951, David Huffman, aluno de Teoria da Informação no MIT, teve como opção o desenvolvimento de uma monografia para conclusão de seu curso, seu professor designou a ele a tarefa de encontrar uma codificação binária mais eficiente.

A ideia de Huffman, se dá na quantificação da frequência relativa de cada dado, dessa maneira salva os dados com maior frequência com maior eficiência.

Caráter	Frequência	Código	Total
A	15	000	45
B	8	010	24
C	3	101	9
D	20	011	60
Total			138 Bits

A Tabela anterior mostra um exemplo hipotético de uma mensagem armazenada sem a Codificação de Huffman.

Caráter	Frequência	Código	Total
A	15	00	30
B	8	010	24
C	3	011	9
D	20	1	20
Total			83 Bits

[pic 1]

A tabela anterior e a imagem anterior representam o mesmo texto codificado pela codificação de Huffman, que trouxe uma redução de 138 Bits para 83, redução de quase 40% do tamanho total.

O Algoritmo consegue isso através da ordem que monta a árvore, começando de baixo, para cima, primeiro o algoritmo faz a tabela de frequência de cada item, onde determina o numero de ocorrências de cada, pegando as duas menores ocorrências e colocando elas como os nós folhas, após isso ele realiza a soma de suas frequências e atribui esse valor ao nó pai dos nós anteriores, e compara seu valor com o próximo valor de menor frequência, caso ele seja maior que a soma das duas frequências, ele será somado com a próxima maior frequência, criando outros dois nós folha, e a soma de suas frequências será somada com a soma anterior, criando uma estrutura repetitiva que agrega dados de maneira estruturada até chegar ao item mais comum, que deve possuir a menor profundidade possível, pois a sua profundidade será a que terá o maior impacto no tamanho final.