Compressão de dados

Compressão de dados

1

Conteúdo
Huffman ........................................................................................................................................ 2
Shannon Fano................................................................................................................................ 3
Família LZ ....................................................................................................................................... 4
Codificação Aritmética .................................................................................................................. 7
RLE –Run length encoding ............................................................................................................. 7

Huffman






Mais popular.
Atribuí códigos a pedaços de texto que tem freqüência alta.
Atribuí códigos mais curtos a freqüências mais baixas.
Um código único de tamanho variável é atribuído a cada símbolo.
A compressão ocorre em 2 passagens sobre o texto.
1º - Conta as freqüências
2º - Monta a árvore binária realizando a compressão (árvore canônica), depois gera código compactado.

Codificação - A árvore é percorrida emitindo bits ao longo de suas arestas.
Decodificação – Os bits de entrada são usados para selecionar as arestas.
Algoritmo:
1. Ordenar os símbolos na ordem de ocorrência.
2. Combinar sucessivamente os dois símbolos com a freqüência mais baixa para construir a árvore.
3. Descrever um caminho para cada nó.

2

Exemplo : Para cada rosa rosa, uma rosa é rosa.

Árvore Canônica

Tabela de frequencias
Símbolo Frequência
Rosa
4
Para
1
Cada
1
Uma
1 é 1
,
1

Caminho
Rosa - 1
Para - 000
Cada – 0001
Uma – 01
É – 0010
, - 0011

Código compactado: 0000 | 0001 | 1 | 1 | 0011 | 01 | 1 | 0010 | 01| 1
Descompactação: para | cada | rosa | rosa | uma | rosa | é | rosa

Shannon Fano
 Não tem árvore
 Constrói um código de prefixos baseado no conjunto de