Compressão de Dados
Elisa M. Pivetta Cantarelli
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compressão de Dados
zCompressão de dados é uma forma de
codificar um certo conjunto de
informações de maneira que o código
gerado seja menor que o fonte.
zPara que comprimir?
yPara redução do espaço físico utilizado
yPara agilização na transmissão de
dados.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compressão de Dados
zA redução do espaço físico permite um
significativo ganho em termos de
ocupação em disco e velocidade de
acesso.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compressão
zA compressão é aquela realizada sobre
dados, a partir dos quais é verificada a
repetição de caracteres para efetivar a
redução do número de elementos de
dados.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Técnica de Compressão sem
perda
zSe a informação, após sua compressão, pode
ser exatamente reconstruída a técnica de
compressão é dita sem perdas.
zEstas técnicas exploram estatísticas de dados
(redundância de dados)
zComo exemplo de técnicas sem perda temos:
codificaçãoRun-length e codificação Huffman.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação run-length
zQuando temos um arquivo onde ocorre
uma repetição contínua de determinado
caracter, por exemplo AAAAAAAAAAAA, é
possível sua representação através da
codificação run-length , da seguinte
forma:
zCe 12 A
yonde A é o caracter repetido 12 vezes, e é
indicado pelo caracter especial Ce .
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação run-length
zO que fazer quando não for possível a
colocação de caracteres especiais?
zHá determinados casos que os
caracteres especiais utilizados conflitam
com outros aplicativos, de transmissão
de dados, por exemplo.
zDesta forma, utiliza-se um caracter
convencional
como
indicador
de
compressão.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação run-length
zComo na língua portuguesa utiliza-se
muito pouco as letras W, Y,#,$,|, podese, por exemplo, indicar a compressão
de um arquivo de texto na forma:
z# 12 A
PDF created with pdfFactory Pro trial version www.pdffactory.com
zAs técnicas de compressão orientadas a
caracter não são as mais eficientes ou as mais
sofisticadas.
zPelo contrário, em geral elas são utilizadas num
primeiro nível de compressão multinível, onde
os demais níveis podem ser técnicas
estatísticas de compressão.
zAqui serão analisados 8 técnicas de
compressão orientada a caracter, de modo a
dar uma noção das possíveis aplicações deste
tipo de compressão.
PDF created with pdfFactory Pro trial version www.pdffactory.com
1)Supressão de Caracteres
Nulos
zNesta técnica, temos como objetivo
comprimir apenas os caracteres nulos ou
brancos. Em geral, são comprimidos
caracteres correspondentes ao espaço em
branco.
zPara a compressão, utiliza-se a seguinte
seleção de caracteres indicadores:
yCe N
PDF created with pdfFactory Pro trial version www.pdffactory.com
Supressão de Caracteres
Nulos
zonde Ce é um caracter especial e N é o
número de caracteres brancos repetidos
seqüencialmente.
zEntão, por exemplo, uma seqüência do
tipo:
... vazio.
Exatamente o que...
pode ser comprimida como sendo:
... vazio. Ce8 Exatamente o que...
PDF created with pdfFactory Pro trial version www.pdffactory.com
O algoritmo para a técnica
apresentada
z 1. inicializa-se um contador para o cálculo do número de
repetições de brancos;
z 2.
lê-se o caracter do arquivo a comprimir;
z 3.
verifica-se se o caracter é um branco;
z 4. se for, incrementa-se o contador - verifica-se se o contador é
maior que 2, valendo a pena comprimir - verifica-se se o número
de caracteres ultrapassou a 255 (limite binário); se verdadeiro,
colocam-se os caracteres indicadores no arquivo comprimido e
volta-se ao passo 1, caso contrário, volta-se ao passo 2;
PDF created with pdfFactory Pro trial version www.pdffactory.com
2- Mapeamento de Bit
z Quando é sabida a existência de múltiplas ocorrências não
consecutivas de determinado caracter no arquivo a comprimir,
utiliza-se a compressão por mapeamento de bit.
z Esta técnica utiliza-se de um byte no arquivo comprimido para
indicar, através dos bits, a ocorrência do caractere repetido.
z Desta forma, caso desejarmos comprimir todos os caracteres
a de um texto, devemos indicá-lo no mapa de bits. Cada
mapa descreve 8 bytes, um por bit do arquivo manipulado.
Portanto, para letra encontrada a cada trecho de 8 bytes, será
assinalada no mapa de bits.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Mapeamento de Bit
z. Por exemplo:
... abacate ...
será descrito como:
... Mbbcte...
zonde Mb é o mapa de bits correspondente à
compressão do caracter a .
PDF created with pdfFactory Pro trial version www.pdffactory.com
Mapeamento de Bit
zEste mapa é composto,
zpara o exemplo, dos bits:
zonde o primeiro zero indica a presença de
um caracter a na primeira posição, valor um
em seguida indica um caracter diferente, e
assim por diante, até completar o mapa.
zConvenciona-se, portanto, que o bit 0
indica a presença do caracter a comprimir e
o bit 1 a sua ausência.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Algoritmo
z 1. inicializa-se o mapa de bits colocando todos os bits em
zero;
z 2. inicializa-se o contador;
z 3. realiza-se a leitura do caracter no arquivo a comprimir;
z 4. compara-se o caracter lido com o caracter procurado-se
for o mesmo
z 5. troca-se para 1 o bit da posição atual;
z 6. incrementa-se o contador;
z verifica-se se o contador chegou a 8; se verdadeiro, então
grava-se o mapa de bits e os caracteres diferentes do
comprimido, e volta-se para o passo 1; senão, volta-se ao
passo 3.
PDF created with pdfFactory Pro trial version www.pdffactory.com
3-Comprimento de Fileira
zEsta técnica aplica a indicação semelhante à
run-length de compressão.
zO formato permite
caracter repetido:
a
determinação
yCe C N
yonde Ce é o caracter especial, C é o
caracter repetido e N é o número binário
de repetições. Como podemos perceber,
esta técnica também permite apenas a
compressão de um caracter por vez.
PDF created with pdfFactory Pro trial version www.pdffactory.com
do
4- Compactação de Meio
Byte
z Este tipo de compactação é utilizado quando encontramos uma
seqüência de bits em comum nos caracteres de determinado
arquivo. Um tipo de repetição de bits de grande ocorrência é a
que acontece em caracteres numéricos.
z Por exemplo, se observarmos o conjunto binário da tabela
ASCII para os caracteres numéricos, teremos:
•se isolarmos os primeiros 4 bits de cada byte
de caracter numérico, veremos que há uma
constância de valores.
•Estes valores constantes são um exemplo de
objetos de compactação de meio byte.
•A compactação de meio byte propriamente
dita consiste na seguinte seqüência de
caracteres indicadores:
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compactação de Meio
Byte
z onde Ce é o caracter especial,
z N é o número binário dos caracteres comprimidos e Cn é a
metade do caracter comprimido.
z Na seqüência de caracteres indicadores apresentada são
apresentados 5 caracteres (Cn=c1c2c3c4c5) porque este é o
mínimo para que a compressão seja válida, uma vez que até
4 caracteres ela necessita um número de byte igual ou
maior.
z Cada Cn é a ocorrência de 4bits
yCe 0011 0000 0001 0010 0011 0100
PDF created with pdfFactory Pro trial version www.pdffactory.com
5 -Codificação Diatômica
z Esta técnica de compressão permite a representação de
um par de caracteres em apenas um caracter especial.
z Normalmente utilizam-se tabelas com pares de
caracteres e sua freqüência de ocorrência em
determinado tipo de arquivo.
z Obviamente procura-se substituir os caracteres de maior
freqüência, associando a cada dupla um caracter
especial.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Diatômica
z Em texto da língua portuguesa, por exemplo, duplas de ocorrência
freqüente são a letra a acentuada com til seguido da letra o (ão) e
a letra e com acento agudo seguido de um espaço em branco (é ).
A cada uma dessas seqüência deve-se atribuir um caracter especial
para nos permitir a compactação através da codificação diatômica.
z Obviamente, estes são apenas dois exemplos de duplas de
caracteres, numa tabela normal para compactação utilizam-se mais
de 20 duplas para que seja obtida uma compressão razoável.
PDF created with pdfFactory Pro trial version www.pdffactory.com
6 -Substituição de Padrões
z A substituição de padrões é semelhante à codificação diatômica, pois também
ocorre a substituição de um conjunto de caracteres por um caracter especial.
y PALAVRA => Ce
z O processamento desta técnica é semelhante ao da substituição de padrões, com
a diferença de que são avaliados um número maior de caracteres.
z Desta forma, são estabelecidas tabelas de palavras de maior freqüência de
ocorrência para substituição com o caracter especial.
z com a diferença de que são avaliados um número maior de caracteres. Desta
forma, são estabelecidas tabelas de palavras de maior freqüência de ocorrência
para substituição com o caracter especial.
z A utilização mais comum para este tipo de compressão é a de arquivos de
programas de linguagens de programação. Uma vez que as linguagens contém
diversas palavras que se repetem freqüentemente em programas, utiliza-se esta
característica para a sua compressão.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Substituição de Padrões
z Uma variante da substituição de padrões para permitir a
codificação de um maior número de palavras é a
utilização de dois caracteres para indicação da
ocorrência de determinada palavra:
zC N
yonde C é um caracter escolhido para indicar a
compressão
yN é o número (binário) da palavra a substituir. Isso
permite a codificação de até 256 palavras reservadas,
o que anteriormente era limitado ao número de
caracteres especiais que poderíamos utilizar.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Substituição de Padrões
zPor exemplo, as palavras reservadas begin e end
da linguagem Pascal poderiam ser, por exemplo,
substituídas pelos códigos $1 e $2 .
zAs demais palavras reservadas da linguagem
também poderiam ser codificadas desta maneira,
permitindo uma compressão considerável de um
arquivo de programa.
PDF created with pdfFactory Pro trial version www.pdffactory.com
7 -Codificação Relativa
z Esta técnica de compressão é realizável quando existe a
transmissão de seqüências de caracteres numéricos.
z Estas seqüências podem ser valores dentro de intervalos
definidos ou valores binários.
z A transmissão de valores intervalares pode ser exemplificada
por transmissões de dados provenientes de sinais de sensores.
z Um exemplo de transmissão binária é o fax. Nestes dois casos,
suas transmissões podem ser comprimidas através da
codificação relativa.
z Para cada um dos casos existe um processamento adequado
aos tipos de valores envolvidos, por isso, veremos como é o
processamento para a codificação de valores intervalares e
para valores binários.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Relativa
Valores Intervalares
z A compressão somente é válida se existe um intervalo definido de
valores, caso contrário não ocorre uma compressão satisfatória. Isso
porque este tipo de compressão baseia-se na colocação da variação
numérica de um valor a outro, desta forma:
y Val Var1 Var2...
z onde Val é o primeiro valor da seqüência, VarN é a variação do valor
anterior para o atual. Exemplificando de forma numérica, seja a seguinte
seqüência de caracteres numéricos:
y 10.3 10.1 10.8 10.4 10.4 10.9 10.2
z pode ser compactada através da codificação relativa, ficando os
caracteres na forma:
y 10.3 -.2 .7 -.4 0 .5 -.7
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Relativa
Valores Binários
z o fax utiliza-se desta forma de compressão, portanto a comparação
existente não será mais entre um valor e outro, mas entre uma linha e a
seguinte.
z Cada linha é um vetor de valores binários, que representam o mapa de
bits do desenho da página. O que ser quer é transmitir apenas a variação
de uma linha para outra, evitando-se a transmissão de toda a linha.
z Então, um trecho de linha binária poderia ser:
x... 01001011100010101...
z e a sua seguinte:
x... 01001011111100001...
z a diferença seria em 5 bits:
y .. _________MMMM_M__...
PDF created with pdfFactory Pro trial version www.pdffactory.com
8 - Compressão Estatística
zA idéia da compressão estatística é
realizar uma representação otimizada de
caracteres ou grupos de caracteres.
zCaracteres de maior freqüência de
utilização são representados por códigos
binários pequenos, e os de menor
freqüência são representados por códigos
proporcionalmente maiores.
PDF created with pdfFactory Pro trial version www.pdffactory.com
8 - Compressão Estatística
zNeste tipo de compressão portanto, não
necessitamos saber qual caracter vai ser
comprimido, mas é necessário, porém, ter o
conhecimento da probabilidade de ocorrência de
todos os caracteres sujeitos à compressão.
zCaso não seja possível a tabulação de todos os
caracteres sujeitos à compressão, utiliza-se uma
técnica adequada para levantamento estatístico
dos dados a comprimir, formando tabelas de
probabilidades.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
z Esta técnica de compressão foi criada por D. A.
Huffman em 1950
z No envio de uma mensagem de um dispositivo
origem a um dispositivo destino os caracteres da
mensagem são enviados um a um modificados
através de alguma tabela de codificação.
z Em geral, este código forma um número binário.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
z Como a velocidade de transmissão é importante, é
interessante tornar a mensagem tão curta quanto
possível sem, é claro, perder a capacidade de
decodificar o texto enviado.
z Um algoritmo de determinação de códigos binários
para caracteres baseado na freqüência de uso destes
caracteres foi sugerida por Huffman.
z A idéia é associar números binários com menos bits
aos caracteres mais usados nos textos.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zNeste método de compressão, é atribuído menos bits
a símbolos que aparecem mais freqüentemente e
mais bits para símbolos que aparecem menos.
zCodificação de Huffman é um exemplo de técnica de
codificação estatística, que diz respeito ao uso de um
código curto para representar símbolos comuns, e
códigos longos para representar símbolos pouco
freqüentes.
zEsse é o princípio do código Morse, onde:
yE = ?
yQ = --?PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zSabemos que todo caracter é formado por
sequencia de 8 bits (1 byte). A idéia para a
compressão é criar seqüências de bits de
tamanhos variáveis, onde os caracteres que
tiverem mais freqüência no arquivo usarão uma
seqüência de bits menor e os caracteres que
tiverem mais freqüência no arquivo usarão uma
seqüência de bits maior.
zAssim para um arquivo grande ocorrerá uma
diminuição no seu tamanho.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zUma aplicação interessante de
árvores binárias em codificação de
dados a serem transmitidos e
compactação de arquivos são os
códigos de Huffman.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zExemplo:
ysuponha que uma mensagem seja composta
pelos caracteres A,B,C,D,E, R e que a
freqüência de uso destas letras na mensagem
seja 22, 8, 10, 12, 18, 7.
zA técnica de Huffman consiste em construir uma
árvore binária baseada na freqüência de uso das
letras de tal forma que as mais freqüentemente
usadas (A, E) apareçam mais perto da raiz que as
menos freqüentemente usadas (B, R).
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zA construção desta árvore binária será
feita de baixo para cima, começando a
partir das letras menos usadas até
atingir a raiz.
zNesta árvore binária, as letras serão
representadas nas folhas e o seus
vértices internos conterão um número
correspondente
à
soma
das
freqüências dos seus descendentes.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
z Em cada passo do algoritmo teremos uma coleção
de árvores de Hoffman da qual tomaremos as duas
com menor valor associado e as transformaremos
num só, cujo valor é a soma dos valores dos
descendentes.
z Inicialmente, cada uma das letras será uma árvore
composta apenas pela raiz e cujo conteúdo é o
valor da freqüência de uso.
A
B
C
D
E
R
22
8
10
12
18
7
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zSelecionamos, então, as duas raízes
de menor valor (7 e 8) e as juntamos
em uma nova árvore,
que
fará
parte da nossa coleção.
15
R
B
C
D
E
A
10
12
18
22
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zRepetindo o processo, escolhemos as
árvores com raízes 10 e 12, obtendo
uma 22 na raiz. Neste ponto, nossa
coleção de árvores tem a forma:
22
15
R
B
C
PDF created with pdfFactory Pro trial version www.pdffactory.com
D
E
A
18
22
Codificação Huffman
zContinuando o mesmo processo
escolhemos 18 e 15, formando:
33
15
R
22
E
B
C
D
A
22
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zDepois, 22 e 22
33
44
A
15
R
22
E
B
PDF created with pdfFactory Pro trial version www.pdffactory.com
C
D
Codificação Huffman
zE, finalmente:
77
1
0
33
44
0
1
15
E
0
0
1
A
22
1
0
R
1
B
C
PDF created with pdfFactory Pro trial version www.pdffactory.com
D
Temos, então, a árvore de
Huffman completamente
construída.
Associamos 0 às arestas
que ligam um vértice com
seu filho esquerdo e 1 às
arestas que ligam um
vértice com seu filho à
direito.
O código correspondente a
cada letra será formado
pelo número binário
associado ao caminho da
raiz até a folha
correspondente.
Codificação Huffman
77
1
0
33
44
0
1
15
0
A
E
0
1
22
1
0
R
1
B
C
D
Com isso,
tabela:
A
10
B
001
PDF created with pdfFactory Pro trial version www.pdffactory.com
C
110
D
111
obtemos
E
01
R
000
a
Codificação Huffman
Para decodificar uma mensagem obtida através da
tabela acima por exemplo:
10 001 000 10 110 10 111 10 001 000 10
•basta ir utilizando cada bit da seqüência para
percorrer a árvore de Huffman desde a raiz até se
atingir uma folha, quando se obtém o caracter
correspondente. Devemos, então voltar à raiz e
continuar a percorrer a árvore para continuar a
decodificação.
•No exemplo da string de bits acima temos a
mensagem
ABRACADABRA.
Veja
como
esta
mensagem foi compactada: de 11 bytes (88 bits)
para 28 bits.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Huffman
zAssim acontece com os demais
caracteres, em ordem crescente do
número de bits, conforme a prioridade.
zA codificação Huffman manteve a
propriedade de permitir a decodificação
direta, não permitindo que os bits da
codificação de um caracter confundisse
com a de outro.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Shannon-Fano
zA forma desta técnica tem muitas semelhanças
com a de Huffman.
z Necessita-se de uma tabela com a probabilidade
de ocorrência de cada caracter, e de um
procedimento para a codificação em binário.
zO procedimento para a codificação, baseia-se na
divisão de conjuntos de probabilidades para a
obtenção do código binário
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Shannon-Fano
z Para a codificação, devemos ter os caracteres com suas
probabilidades de ocorrência:
• O passo seguinte é ordenar colocando os
caracteres de maior probabilidade no topo da
tabela, até o menor, na base:
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Shannon-Fano
z Uma vez feito isso, divide-se a tabela em dois grupos cuja
soma de probabilidades seja igual ou semelhante.
z No caso da tabela, serão obtidos dois grupos, um
composto pelo caracter C1 e outro pelos demais.
z O primeiro grupo recebe como primeiro valor de código o
binário 0 e o segundo recebe 1:
PDF created with pdfFactory Pro trial version www.pdffactory.com
z Como para o primeiro grupo não há ambigüidade em
termos apenas um bit,Shannon-Fano
vamos resolver o problema do
Codificação
segundo grupo.
z Para isso, repetimos o procedimento anterior, dividindo
em dois subgrupos de probabilidades equivalentes.
z O caracter C2 forma o primeiro subgrupo e os demais
formam o segundo.
z Mais uma vez vamos colocar 0 para distinguir o primeiro e
1 para o segundo
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Shannon-Fano
zFinalmente, para resolução da última
duplicidade, repete-se o processo, inserindo o
binário 0 na seqüência do código de C1 e 1
para C3
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compressão Fixa x
Compressão Auto-adaptável
zAs técnicas de compressão estatística de
Huffman e Shannon-Fano permitem apenas a
criação de uma tabela fixa de códigos
associados a cada caracter tabelado.
zCaso as probabilidades nas quais foram
concebidos os códigos da tabela forem distintos
para determinado arquivo a comprimir, este
será prejudicado na compressão.
zPara resolver este caso utiliza-se uma tabela
adaptável.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compressão Fixa x
Compressão Auto-adaptável
z A tabela adaptável consiste na mesma tabela que
conhecemos, contendo o caracter e seu código,
acrescida de mais uma coluna contendo a contagem de
ocorrência do caracter no arquivo a comprimir.
z Efetua-se, portanto, uma contagem de quantos
caracteres ocorrem no arquivo, e ordena-se a coluna
dos caracteres em ordem crescente a partir desta coluna
da contagem, mantendo a coluna de código inalterada.
z Como resultado, obtém-se uma tabela com os
caracteres de ocorrência mais freqüente sendo
codificados com menos bits.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compressão Fixa x
Compressão Auto-adaptável
zSeja, então, a tabela, contendo o caracter o código
e a contagem:
zCaso o caracter C3 ocorra 21 vezes, o C2 18 vezes,
C1 10 vezes, o C5 3 vezes e o C4 2 vezes, a tabela
agora será a seguinte:
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compressão Fixa x
Compressão Auto-adaptável
zA codificação continuou a mesma, mas a
correspondência foi alterada para a situação
específica do arquivo comprimido em questão.
z Observamos, portanto, a necessidade de
realizarmos um processamento de leitura e cálculo
anterior à compressão propriamente dita, o que
implica em maior tempo gasto do que com a
utilização da tabela fixa.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Compressão Fixa x
Compressão Auto-adaptável
zCom a compressão auto-adaptável ganha-se,
obviamente, uma compressão mais eficiente.
zPor outro lado, há um problema pela própria
variabilidade da tabela: para a descompressão, há a
necessidade de se anexar a tabela ao arquivo
comprimido, para que os códigos correspondentes
possam ser devidamente decodificados.
zIsso pode significar, em alguns casos, perda da
compressão eficientemente obtida.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação de
Lempel-Ziv-Welch (LZW)
z Criada em 1977 por Abraham Lempel e Jacob Ziv, a
compressão LZW é encontrada na compressão de texto
e de programas. Os algoritmos de compressão LZ78
são usados na compressão de dados binários, como os
bitmaps.
z Em 1984, Terry Welch modificou o compressor LZ78
para a sua implementação em controladores de discos
de elevado desempenho.
z O resultado foi o algoritmo LZW que é encontrado e
usado nos nossos dias (como o ARJ e o
PKZIP/WinZip)
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação de
Lempel-Ziv-Welch (LZW)
z Criada em 1977 por Abraham Lempel e Jacob Ziv, a
compressão LZW é encontrada na compressão de texto e
de programas. Os algoritmos de compressão LZ78 são
usados na compressão de dados binários, como os
bitmaps.
z Em 1984, Terry Welch modificou o compressor LZ78 para
a sua implementação em controladores de discos de
elevado desempenho.
z O resultado foi o algoritmo LZW que é encontrado e
usado nos nossos dias (como o ARJ, Gunzip,
PKZIP/WinZip e o formato imagem GIF)
z Inicialmente o algoritmo era de domínio público,
atualmente a patente é propriedade da Unisys.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação de
Lempel-Ziv-Welch (LZW)
z O LZW é um algoritmo que constrói um dicionário dos dados
(normalmente chamado de tabela de tradução) originais.
z Os padrões dos dados são identificados e registrados no
dicionário.
z Se o padrão não está presente no dicionário, é codificado e
registrado no mesmo.
z O LZW é um dos algoritmos de compressão mais utilizados
nos nossos dias.
z Este método de compressão de dados sem perdas é
encontrado em vários formatos de imagem, como o GIF, TIFF
e PDF.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação de
Lempel-Ziv-Welch (LZW)
zCodificação LZW é baseada na construção de
um dicionário de palavras (grupos de um ou
mais caracteres) a partir do fluxo de entrada.
zQuando uma nova palavra é encontrada, a
máquina de compressão adicionada ao
dicionário e um valor que identifica a posição da
frase no dicionário substitui a frase.
zSe a frase já foi registrada, ela é substituída
pelo valor de posição no dicionário.
PDF created with pdfFactory Pro trial version www.pdffactory.com
zExemplo:String ABACABA
ytabela de códigos : 0=A, 1=B, 2=C, 3=D
yPrimeiro caractere da string é A, e está na nossa
tabela. Analisar o caracter seguinte que é o B,
junta-se AB que não está na tabela. Neste caso
enviamos o código 0 e adicionamos a nova string
na tabela fazendo 4=AB
yTomamos para prefixo o caracter B, buscando o
próximo caracter, obtem-se BA, que não está na
tabela, repetindo o anterior, enviar o código 1 e
adicionamos nova string na tabela fazendo 5=BA
yNovo prefixo é o A, concatenada com próximo
caracter, obtemos a string AC, enviamos 0 e
fazemos 6=AC
PDF created with pdfFactory Pro trial version www.pdffactory.com
zString ABACABA
yNovo prefixo é o C, concatenado com próximo caracter,
string CA. Enviamos o código 2, e fazemos 7=CA
yNovo prefixo é o A, concatenado com próximo caracter,
string AB, a qual se encontra na tabela, não enviamos
nenhum código e tomamos para novo prefixo AB
yEste prefixo concatenado com próximo caractere forma ABA,
que não se encontra na tabela. Enviamos o código 4, e
fazemos 8=ABA
yO novo prefixo passa a ser A e como não tem mais caracter,
enviamos o código 0.
yDesta forma obtemos a seguinte seqüência codificada:
0 1 0 2 4 0.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Tipos de Compactações
z ARJ: criado pelo programa de compactação homônimo, batizado
em homenagem ao inventor, Robert Jung (ARJ = Archive Tobert
Jules). Foi o principal concorrente do ZIP no tempo do DOS, mas
caiu em desuso com a popularização do Windows.
CAB: usado pela Microsoft na distribuição de seus software e
descompactado na instalação. CAB é a abreviatura de Cabinet.
GIF: muito usado para imagens, foi criado pelo serviço on-line
CompuServe no tempos pré-Internet. Por usar compressão LZW,
o Gharphics Interchange Format é protegido por patentes da
Unisys, cuja autorização é necessaria para o desenvolvimento de
produtos nele baseados.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Tipos de Compactações
z GZ ou GZIP: o nome vem de GNU Zip, por fazer parte do Projeto
GNU (que originou o Linux). Seu grande beneficio é ser livre, de
código aberto.
JAR: dos mesmos criadores do ARJ, atinge maiores níveis de
compressão e é mais rápido que a maioria dos rivais. Não
confudir com o formato de distribuição de applets Java.
JPG: criado a partir dos padrões definidos pelo JoinPhoto-graphic
Experts Group (JPEG), é o mais usado para imagens,
principalmente fotos. Permite vários níveis de compactação.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Tipos de Compactações
z
MP3: o vilão do mercado fonográfico caiu nas graças dos
internautas ao permitir a compressão de áudio em até 12 vezes.
Tecnicamente, é parte do padrão MPEG-2. MP3 vem do MPEG-2,
layer 3.
MPG: criado pelo Moving Picture Experts Group (semelhante ao
JPEG, mas dedicado ao vídeo), usado até nos DVD´s.
PNG: foi desemvolvido para substituir o GIF, evitando problemas
de licenciamento, além de ter algumas vantagens técnicas. A
sigla vem de Portable Network Graphics.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Tipos de Compactações
z
RAR: formato usado pelo compactador WinRAR, que emprega
diferentes métodos de compressão de acordo com o tipo de
arquivo.
TAR: criado pelo comando de Unix com o mesmo nome, derivado
de Tape Archive, ele apenas agrupa vários arquiivos, sem
compressão.
ZIP: provavelment o formato mais popular, surgiu com o
compactador PKZip, criado por Phillip Katz, em 1986. Chegou ao
Windows com o WinZip e já é descompactado automaticamente
pelas versões mais novas do sistema operacional da Microsoft.
Apesar do nome, não tem relação com os ZIP drives da Iomega.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
z A codificação Lempel-Ziv é um tipo de compressão de cadeia
que forma strings de caracteres a partir de sua ocorrência,
criando tabelas de strings conforme vão acontecendo.
z Dada a interessante abordagem utilizada nesse tipo de
compressão, a codificação Lempel-Ziv foi aprimorada e tornada
padrão para a compressão de dados transmitidos via modem.
z Esta técnica padrão baseada na Lempel-Ziv é a recomendação
V. 42 bis do CCITT (Consultative Committee for International
Telephone and Telegraph).
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zAs técnicas de Huffman e Shannon-Fano
estudadas anteriormente eram de compressão
estatística baseada em caracteres, uma vez que
utilizavam a probabilidade de ocorrência de
cada caracter.
zA codificação Lempel-Ziv utiliza probabilidades
de cadeias de caracteres ao invés de apenas
um caracter. Qual a vantagem disso?
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zEm primeiro lugar, vamos analisar qual é a influência
da probabilidade sobre o número teórico de bits para
representação de determinado conjunto de caracteres.
zPara tanto, vamos pegar os caracteres C1 e C2 para
verificar a relação entre probabilidade e número
teórico de bits.
zPara sabermos este número teórico de bits precisamos
calcular a harmonia, que nos dá o número de bits por
intervalo de símbolo.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zAssim, se C1 tiver probabilidade 0,8 e C2 tiver
0,2, sua entropia será 0,72, e assim
sucessivamente, conforme a tabela a seguir:
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
z Isso indica que quanto mais distinta é a porcentagem,
maior é o aproveitamento de bits.
z Para aproveitarmos isso como forma de compressão,
basta criarmos conjuntos de caracteres de forma a
acumular porcentagens.
z Assim, podemos acumular os caracteres em cadeias do
tipo C1C1, C1C2, etc.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
z Para verificarmos se há ganho no comprimento médio
de bits, vamos iniciar analisando as probabilidades de
cadeias de 2 caracteres na tabela a seguir, onde foi
estabelecido C1 com probabilidade 0,7 e C2 com 0,3:
z A probabilidade de ocorrência da cadeia C1C1 é de
0,7*0,7 = 0,49, ou melhor, 49%.
z O mesmo raciocínio aplica-se às demais combinações.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zUtilizando a codificação Huffman, podemos
estabelecer o tamanho médio ocupado pelo grupo de
cadeias da tabela anterior.
zObtendo-se os códigos binários, que podem ser
observados na tabela a seguir, pode-se calcular o
tamanho médio de bits ocupado:
T = 0,49*1 + 0,21*2 + 0,21*3 + 0,09*3 = 1,81 bits
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
z O valor de 1,81 bits para representação da cadeia pode
parecer grande, mas se dividirmos por 2, teremos 0.905
bit por caracter, menor que 1 bit por caracter no caso de
codificarmos o bit 0 para C1 e bit 1 para C2.
z Seguindo este raciocínio, podemos ampliar a idéia para um
número maior de caracteres e chegaremos à conclusão de
que, quanto maior a cadeia, mais caracteres serão
passíveis de compressão.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
z Desta forma, a codificação Lempel-Ziv utiliza um conjunto
de regras para analisar as cadeias de um conjunto de
caracteres pré-definido.
z As cadeias são montadas e codificadas à medida em que
são lidos os caracteres a codificar.
z A forma de composição destas cadeias está descrita na
técnica V. 42 bis.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zA codificação Lempel-Ziv foi melhorada e é
utilizada como uma técnica padrão para
transmissão através de modens.
zEsta técnica possui um tamanho máximo de
cadeia que pode variar de 6 a 250 caracteres
para formação de cadeia.
zExiste um dicionário com 512 cadeias básicas
codificadas.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zO dicionário de cadeias é dinâmico e pode ter
cadeias acrescentadas e retiradas em tempo de
compressão.
zA formação de novas cadeias é baseada na
comparação das cadeias lidas com as
existentes no dicionário.
zSe a cadeia lida não existe, ela é acrescentada
e recebe um código que a representa como
cadeia comprimida.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zComo o modem transmissor é o que faz a
compressão e o dicionário é dinâmico, como o
modem receptor irá decifrar os códigos para
descomprimi-los?
zA cada nova cadeia formada no transmissor
são enviados os caracteres ou a primeira
subcadeia que a compõe e o código
correspondente à nova cadeia, para que exista
uma réplica do dicionário no receptor.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zÉ utilizada uma estrutura de dados em árvore para
implementação do dicionário de cadeias.
zA partir de uma cadeia pré-definida é formada uma
árvore para processamento das cadeias.
zSeja a cadeia pré-definida DA , a partir da qual
derivam-se as cadeias DATA e DADO. Para esta
seqüência a estrutura seria:
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zOs valores ao lado de cada caracter é o código
correspondente à cadeia composta até aquele
nó da árvore.
zOu seja, a cadeia DA possui código 300, a
cadeia DAT possui código 342 e assim por
diante.
zDesta forma, amplia-se o dicionário sem
prejudicar as codificações existentes e permite,
ao mesmo tempo, a verificação de variações
destes códigos.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zExiste, ainda, a possibilidade de substituição de
códigos pouco utilizados.
zUma vez definida um número N de códigos
possíveis, ao atingir este número, procura-se
um código que corresponda a um nó folha que
não esteja sendo utilizado na compressão em
curso.
zCaso exista, a nova cadeia utiliza o código da
cadeia antiga não utilizada. Ocorre, portanto,
eliminação de códigos do dicionário.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Codificação Lempel-Ziv e
CCITT V.42 bis
zEsta é a técnica padrão V. 42 bis utilizada para
compressão na transmissão de dados via
modem.
zEla baseia-se na codificação em cadeia de
Lempel-Ziv, utilizando-se da multiplicação das
probabilidades de ocorrência de caracteres,
para, em cima das estatísticas de cadeias,
permitir a compressão de bits utilizados na
transmissão de dados.
PDF created with pdfFactory Pro trial version www.pdffactory.com