compressao_dados

Prévia do material em texto

1	
  
Alexandre	
  Souza	
  
Francisco	
  Mesqui5a	
  
Simoni	
  Krüger	
  
Carla	
  Pires	
  
Fabrício	
  Ferreira	
  	
  
Algoritmos e Estruturas de Dados!
Definição	
  
	
  
•  Representação	
  de	
  uma	
  fonte	
  de	
  dados	
  da	
  maneira	
  mais	
  precisa	
  
possível	
  uElizando	
  um	
  menor	
  número	
  de	
  bits;	
  
•  Fazer	
  com	
  que	
  a	
  mesma	
  quanEdade	
  de	
  informação	
  caiba	
  em	
  um	
  
espaço	
  menor;	
  
•  Eliminar	
  as	
  redundâncias:	
  recorrências	
  de	
  letras,	
  dígitos	
  ou	
  pixels;	
  
•  Receptor	
  deve	
  ser	
  capaz	
  de	
  decodificar	
  os	
  dados	
  para	
  acessar	
  a	
  
informação;	
  
•  Exemplos:	
  
²  EBCDIC	
  de	
  8	
  bits	
  para	
  o	
  formato	
  ASCII	
  de	
  7	
  bits;	
  
²  ‘AAAAAA’,	
  que	
  ocupa	
  6	
  bytes,	
  poderia	
  ser	
  comprimida	
  para	
  ‘6A’,	
  que	
  ocupa	
  2	
  
bytes	
  );	
  
²  AATTTT	
  representa-­‐se	
  por:	
  *4T	
  (decodifica	
  por	
  meio	
  de	
  uma	
  tabela).	
  
2	
  
Histórico	
  
	
  
•  A	
  compressão	
  é	
  oriunda	
  da	
  criptografia:	
  algoritmo	
  de	
  
compressão	
  é	
  um	
  codificador	
  e	
  um	
  decodificador;	
  
•  Relatos	
  de	
  encriptação	
  por	
  volta	
  de	
  1500	
  a.C.	
  (escrita	
  cifrada	
  
para	
  guardar	
  segredos);	
  
•  Gregos	
  e	
  espartanos	
  usavam	
  códigos	
  em	
  movimentos	
  bélicos	
  
durante	
  as	
  guerras	
  (475	
  a.C);	
  
•  No	
  século	
  XIX	
  a	
  invenção	
  do	
  telégrafo	
  e	
  do	
  Código	
  Morse	
  abriu	
  
espaço	
  para	
  a	
  criptografia	
  moderna	
  que	
  deixou	
  de	
  ser	
  processos	
  
altamente	
  manuais;	
  
3	
  
Histórico	
  
	
  
•  1a	
  Guerra	
  Mundial	
  (1914	
  a	
  1918):	
  máquinas	
  de	
  codificação	
  
mecânicas	
  usadas	
  para	
  codificar	
  e	
  decodificar	
  textos	
  usando	
  
encriptações	
  sofisEcadas	
  e	
  complexas;	
  
•  2a	
  Guerra	
  Mundial	
  (1939	
  a	
  1945):	
  codificação	
  da	
  mensagem	
  para	
  
esconder	
  a	
  informação	
  do	
  inimigo	
  e	
  reduzir	
  a	
  quanEdade	
  de	
  
informações	
  que	
  eram	
  passadas	
  através	
  dos	
  rádios	
  (surge	
  a	
  
compactação	
  de	
  dados);	
  
•  Advento	
  dos	
  computadores	
  digitais:	
  	
  
–  necessidade	
  da	
  criação	
  de	
  códigos	
  seguros	
  e	
  inquebráveis;	
  
–  necessidade	
  de	
  reduzir	
  espaço	
  nos	
  meios	
  de	
  armazenamento	
  e	
  
transmissão	
  de	
  dados,	
  reduzindo	
  custos	
  e	
  viabilizando	
  projetos.	
  
4	
  
Por	
  que	
  comprimir?	
  
	
  
•  Velocidade	
  de	
  processamento	
  dos	
  computadores	
  
aumentou;	
  
Tempo	
  de	
  acesso	
  a	
  discos	
  magnéEcos	
  tem	
  se	
  manEdo	
  
praEcamente	
  constante;	
  
•  É	
  mais	
  vantajoso	
  invesEr	
  em	
  poder	
  de	
  computação	
  em	
  
compressão	
  de	
  dados	
  em	
  troca	
  de	
  menos	
  espaço	
  para	
  
armazenamento	
  de	
  dados	
  em	
  disco	
  ou	
  em	
  menor	
  tempo	
  
transmissão	
  de	
  dados	
  pela	
  rede;	
  
•  Reduz	
  custos	
  operacionais:	
  
–  OEmização	
  do	
  espaço	
  em	
  disco	
  para	
  armazenamento;	
  
–  Redução	
  do	
  tráfico	
  da	
  rede;	
  
5	
  
Por	
  que	
  comprimir?	
  
•  Internet	
  e	
  o	
  uso	
  intensivo	
  de	
  sistemas	
  computacionais	
  criaram	
  
uma	
  necessidade	
  incremental	
  de	
  armazenar	
  e	
  transferir	
  grande	
  
volume	
  dados	
  sobre	
  uma	
  infraestrutura	
  existente	
  (redes	
  de	
  
computadores);	
  
•  Aumento	
  da	
  autonomia	
  da	
  bateria	
  de	
  disposiEvos	
  portáteis	
  devido	
  
a	
  redução	
  da	
  quanEdade	
  de	
  dados	
  a	
  serem	
  transmiEdos;	
  
•  Tecnologias	
  como	
  telefonia	
  3G,	
  fotos	
  geradas	
  por	
  câmeras	
  digitais,	
  
música	
  digital,	
  TV	
  digital,	
  bibliotecas	
  digitais;	
  
•  EsEma-­‐se	
  que	
  em	
  uma	
  biblioteca	
  digital	
  é	
  possível	
  uma	
  economia	
  
de	
  50	
  a	
  60%	
  de	
  espaço	
  uElizando	
  compressão	
  de	
  dados;	
  
•  Tornou	
  viável	
  a	
  aplicações	
  de	
  videoconferência;	
  
•  Redução	
  do	
  espaço	
  necessário	
  para	
  backups;	
  
•  Emails	
  e	
  downloads	
  da	
  internet.	
  
6	
  
Desvantagens	
  
•  Custo	
  de	
  processamento	
  na	
  compressão	
  e	
  na	
  
descompressão;	
  
•  Custo	
  para	
  armazenar	
  a	
  tabela	
  de	
  símbolos	
  ou	
  
dicionário;	
  
•  Ganhos	
  expressivos	
  são	
  obEdos	
  apenas	
  com	
  
métodos	
  de	
  compressão	
  que	
  não	
  permitem	
  
reconstruir	
  os	
  dados	
  exatamente	
  da	
  maneira	
  
como	
  eram	
  antes	
  da	
  compressão.	
  
7	
  
Técnicas	
  Lossless	
  	
  
	
  
•  Sem	
  perda	
  de	
  dados;	
  
•  Permite	
  a	
  reconstrução	
  exata	
  do	
  conteúdo	
  original	
  a	
  
parEr	
  da	
  fonte	
  comprimida;	
  
•  Explora	
  a	
  redundância	
  dos	
  dados;	
  
•  Aplicável	
  à	
  maioria	
  das	
  fontes	
  de	
  informação:	
  
–  Imagens	
  médicas	
  digitais;	
  
–  Transmissão	
  de	
  textos;	
  
–  Programas	
  executáveis;	
  
–  Banco	
  de	
  dados;	
  
–  Informações	
  bancárias.	
  
•  Ex.:	
  transformação	
  de	
  Burrows-­‐Wheeler,	
  codificação	
  de	
  
Huffman,	
  LZ77,	
  LZ78,	
  LZW,	
  ZIP,	
  RAR,	
  ARJ,	
  PNG,	
  GIF,	
  
PNG.	
  
8	
  
Técnicas	
  Lossless	
  	
  
	
  
•  Classificação:	
  
– Codificação	
  estáDca:	
  o	
  mapeamento	
  entre	
  as	
  
mensagens	
  e	
  o	
  conjunto	
  de	
  palavras-­‐código	
  é	
  
determinado	
  antes	
  do	
  início	
  da	
  transmissão	
  
(requer	
  duas	
  passagens	
  pela	
  fonte	
  de	
  dados);	
  
– Codificação	
  adaptaDva:	
  o	
  mapeamento	
  entre	
  
as	
  mensagens	
  e	
  o	
  conjunto	
  das	
  palavras	
  código	
  
muda	
  com	
  o	
  tempo	
  (uma	
  única	
  passagem	
  sobre	
  
a	
  fonte	
  de	
  dados);	
  
– Codificação	
  híbrida:	
  usa	
  conceitos	
  tanto	
  da	
  
codificação	
  estáEca	
  quanto	
  da	
  adaptaEva.	
  	
  
9	
  
Técnicas	
  Lossy	
  	
  
	
  
•  Com	
  perda	
  de	
  dados	
  (a	
  informação	
  descomprimida	
  é	
  diferente	
  da	
  
original);	
  
•  Comprime	
  os	
  dados	
  eliminando	
  definiEvamente	
  certas	
  redundâncias;	
  
•  Perdem-­‐se	
  dados	
  sucessivamente,	
  à	
  medida	
  em	
  que	
  se	
  aplica	
  o	
  algoritmo	
  
várias	
  vezes;	
  
•  Explora	
  redundâncias	
  temporais	
  e	
  espaciais	
  presentes	
  nas	
  fontes	
  de	
  
dados;	
  
•  Leva	
  em	
  consideração	
  a	
  percepção	
  humana,	
  que	
  é	
  incapaz	
  de	
  perceber	
  
certas	
  perdas	
  em	
  imagens,	
  áudio	
  e	
  vídeo:	
  
–  Sons	
  de	
  frequências	
  muito	
  altas	
  ou	
  muito	
  baixas	
  que	
  os	
  humanos	
  não	
  ouvem;	
  
–  Detalhes	
  muito	
  suEs	
  como	
  a	
  diferença	
  de	
  cores;	
  
–  Movimentos	
  muito	
  rápidos	
  que	
  não	
  conseguimos	
  acompanhar	
  em	
  um	
  filme;	
  
•  Taxas	
  de	
  compressão	
  melhores	
  que	
  das	
  técnicas	
  lossless	
  (50:1	
  a	
  10000:1);	
  
•  Exemplos:	
  JPEG,	
  MPEG,	
  DIVx,	
  MP3.	
  
10	
  
Técnicas	
  Lossy	
  	
  
	
  
•  Classificação:	
  
–  Métodos	
  de	
  transformação:	
  amostras	
  de	
  figuras	
  ou	
  sons	
  são	
  
transformados	
  em	
  pequenos	
  segmentos,	
  os	
  quais	
  são	
  
transformados	
  em	
  um	
  novo	
  espaço	
  base	
  e	
  quanEdades	
  
(limitação	
  de	
  possíveis	
  valores).	
  Os	
  valores	
  quanEzados	
  são	
  
codificados	
  para	
  entropia	
  (trata	
  de	
  cadeias	
  de	
  bits	
  sem	
  levar	
  
em	
  conta	
  seu	
  significado);	
  
–  Métodos	
  prediDvos:	
  informações	
  decodificadas	
  são	
  usadas	
  
para	
  prever	
  qual	
  será	
  o	
  próximo	
  pacote.	
  O	
  erro	
  entre	
  o	
  dado	
  
previsto	
  e	
  o	
  dado	
  real,	
  junto	
  com	
  qualquer	
  informação	
  extra	
  
necessária	
  para	
  reproduzir	
  a	
  previsão,	
  são	
  quanEzados	
  ecodificados.	
  	
  Ex.:	
  próximo	
  frame	
  de	
  imagem;	
  
–  Métodos	
  híbridos:	
  uso	
  de	
  ambas	
  técnicas.	
  
11	
  
1	
  
Algoritmos e Estruturas de Dados!
Histórico	
  
2	
  
David	
  Albert	
  Huffman	
  
(09-­‐08-­‐1925	
  –	
  07-­‐10-­‐1999)	
  
Codificação	
  de	
  Huffman	
  
O	
  que	
  é?	
  
	
  
É	
   um	
   método	
   de	
   compactação	
   que	
   usa	
   as	
  
probabilidades	
   de	
   ocorrência	
   dos	
   símbolos	
   no	
  
conjunto	
   de	
   dados	
   a	
   ser	
   compactado	
   para	
  
determinar	
   códigos	
   de	
   tamanho	
   variável	
   para	
  
cada	
  símbolo.	
  	
  
3	
  
Codificação	
  de	
  Huffman	
  
4	
  
ObjeJvo	
  
	
  
Tem	
   por	
   objeDvo	
   a	
   construção	
   de	
   uma	
   árvore	
  
binária	
   	
  baseada	
  na	
  frequência	
  de	
  uso	
  das	
  letras	
  
do	
   a l fabeto	
   	
   de	
   modo	
   que	
   as	
   mais	
  
frequentemente	
  uDlizadas	
  apareçam	
  	
  mais	
  perto	
  
da	
  raiz.	
  
Codificação	
  de	
  Huffman	
  
5	
  
ObjeJvo	
  
	
  
Esta	
   árvore	
   binária	
   é	
   construída	
   da	
   baixo	
   para	
  
cima	
  (das	
  folhas	
  para	
  a	
  raiz)	
  ,	
  começando	
  a	
  parDr	
  
das	
  letras	
  menos	
  usadas	
  até	
  	
  aDngir	
  a	
  raiz.	
  
Codificação	
  de	
  Huffman	
  
Etapas	
  
	
  
• 	
  	
  Cálculo	
  da	
  frequência	
  de	
  cada	
  caracter	
  no	
  arquivo	
  
• 	
  	
  Execução	
  do	
  algoritmo	
  de	
  Huffman	
  para	
  construção	
  	
  	
  	
  	
  	
  
de	
  uma	
  árvore	
  binária	
  (árvore	
  de	
  Huffman)	
  
	
  
• 	
  	
  Codificação	
  Propriamente	
  dita	
  	
  
6	
  
Codificação	
  de	
  Huffman	
  
7	
  
Como	
  Funciona	
  
	
  
No	
   início	
   do	
   algorítmo,	
   cada	
   uma	
   das	
   letras	
   forma	
  	
  
uma	
   árvore	
   que	
   é	
   composta	
   apenas	
   pela	
   raiz	
   e	
   cujo	
  
conteúdo	
  é	
  a	
  frequência	
  com	
  que	
  esta	
  letra	
  	
  ocorre	
  no	
  
texto	
  em	
  questão.	
  
Em	
   seguida,	
   são	
   escolhidas	
   as	
   duas	
   árvores	
   	
   com	
   as	
  
menores	
  frequências	
  associadas	
  e	
  elas	
  são	
  unidas	
  em	
  
uma	
  só	
  árvore	
  cujo	
  valor	
   	
  da	
  raíz	
   	
  é	
  a	
  soma	
  do	
  valor	
  
destas	
  duas.	
  	
  Este	
  processo	
  é	
  repeDdo	
  até	
  a	
  existência	
  
de	
  uma	
  única	
  árvore.	
  	
  
Codificação	
  de	
  Huffman	
  	
  
(exemplo)	
  
	
  
Sequência	
  de	
  caracteres:	
  FAAFEEEAAAAEEEECCAAAAAAAAACFFCCAAAACCCBAAAB	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  BBBAAAAAAAADDDDBBBBBBDDDDAAAAAADDDDDDAAA	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  AEE	
  
Caracteres:	
  FECBDA	
  
	
   	
  	
  
Frequência:	
  5	
  9	
  12	
  13	
  16	
  45	
  (respecDvamente)	
  
	
  
	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  Dados	
  iniciais	
  ordenados	
  por	
  frequencia	
  de	
  ocorrência	
  
	
  
	
  
	
  
	
  
8	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  
Codificação	
  de	
  Huffman	
  	
  
(exemplo)	
  
9	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  14	
  
Codificação	
  de	
  Huffman	
  	
  
(exemplo)	
  
10	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  14	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  14	
  25	
  
Codificação	
  de	
  Huffman	
  	
  
(exemplo)	
  
11	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  14	
   25	
  
Codificação	
  de	
  Huffman	
  	
  
(exemplo)	
  
12	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  
14	
  
25	
  30	
  
Codificação	
  de	
  Huffman	
  	
  
(exemplo)	
  
13	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  
14	
  
25	
   30	
  
55	
  
13	
  
Codificação	
  de	
  Huffman	
  	
  
(exemplo)	
  
14	
  
F	
  
5	
  
E	
  
9	
  
C	
  
12	
  
B	
  
13	
  
D	
  
16	
  
A	
  
45	
  
14	
  
25	
   30	
  
55	
  
100	
  
0! 1!
0! 1!
1!
1!
0!
0!
0!1!
Codificação	
  de	
  Huffman	
  	
  
(Codificação)	
  
15	
  
	
  
A	
  tabela	
  de	
  codificação	
  resultante	
  
	
  	
  
	
  
	
  
	
  
Caracter	
  	
   Huffman	
  
A	
   0	
  
C	
   100	
  
B	
   101	
  
D	
   111	
  
F	
   1100	
  
E	
   1101	
  
Codificação	
  de	
  Huffman	
  	
  
(Codificação)	
  
16	
  
	
  
A	
  tabela	
  de	
  codificação	
  resultante	
  
	
  	
  
	
  
	
  
	
  
Caracter	
  	
   Huffman	
   ASCII	
  
A	
   0	
   0100	
  0001	
  
C	
   100	
   0100	
  0011	
  
B	
   101	
   0100	
  0010	
  
D	
   111	
   0100	
  0100	
  
F	
   1100	
   0100	
  0110	
  
E	
   1101	
   0100	
  0101	
  
Codificação	
  de	
  Huffman	
  	
  
17	
  
Comparação	
  entre	
  a	
  sequência	
  de	
  caracteres	
  propostas	
  uJlizando	
  a	
  codificação	
  	
  
ASCII	
  (8	
  bits)	
  e	
  uJlizando	
  a	
  codificação	
  de	
  Huffman.	
  
	
  
Sem	
  compactação	
  (ASCII)	
  
	
  
	
  
010001100100000101000001010001100100010101000101010001010100000101000001010000010100000
101000101010001010100010101000101010000110100001101000001010000010100000101000001010000
010100000101000001010000010100000101000011010001100100011001000011010000110100000101000
001010000010100000101000011010000110100001101000010010000010100000101000001010000100100
001001000010010001001000001010000010100000101000001010000010100000101000001010000010100
100010001000100010001000100010000100100001001000010010000100100001001000010010001000100
010001000100010001000100000101000001010000010100000101000001010000010100010001000100010
00100010001000100010001000100010000010100000101000001010000010100010101000101	
  
	
  
Com	
  compactação	
  
	
  
1100001100110111011101000011011101110111011001000000000001001100110010010000001001001001
0100010110110110100000000111111111111101101101101101101111111111111000000111111111111111
111000011011101	
  	
  
	
  
	
  
	
  
Codificação	
  de	
  Huffman	
  	
  
18	
  
	
  
	
  Decodificação	
  
	
  
Para	
   decodificar	
   uma	
   mensagem	
   obDda,	
   basta	
   ir	
  
uDlizando	
   cada	
   bit	
   da	
   mensagem	
   para	
   percorrer	
   a	
  
arvore	
   de	
   Huffman	
   desde	
   a	
   raiz	
   até	
   alguma	
   folha,	
  
quando	
  se	
  obtém	
  o	
  símbolo	
  decodificado.	
  Volte	
  então	
  
para	
   a	
   raiz	
   e	
   conDnue	
   a	
   percorrer	
   a	
   árvore	
   para	
  
decodificar	
  o	
  próximo	
  símbolo.	
  	
  
	
  
1	
  
Algoritmos e Estruturas de Dados!
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
	
  
2	
  
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
	
  
3	
  
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
	
  
4	
  
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
5	
  
 !
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
6	
  
 !
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
7	
  
 !
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
8	
  
 !
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
9	
  
 !
	
  	
  	
  	
  	
  	
  Codificação	
  Shannon-­‐Fano	
  
10	
  
 !
11	
  
Algoritmos e Estruturas de Dados!
Família LZ - Compressão por Substituição
Introdução
Jacob Ziv e Abraham Lempel desenvolveram algoritmos
para compressão de dados na década de 70;
Os algoritmos Lempel-Ziv baseiam-se no princípio decompressão por substituição;
Esses algoritmos usam duas estruturas:
1 Dicionário
2 Área de Pesquisa
A idéia é que sempre que uma frase é repetida, na área de
pesquisa, substituir a ocorrência original da frase por uma
referência armazenada no dicionário.
Compressão - LZW (Lempel-Ziv-Welch)
Família LZ - Exploram Redundância de dados
LZ77
LZSS e LZH - Variação do LZ77
LZ78
LZC, LZT e LZW - Variação do LZ78
LZW - Lempel-Ziv-Welch
Desenvolvida por Terry Welch em 1984;
Usa a compactação baseada em dicionário;
É baseado na construção de um dicionário de símbolos a
partir do fluxo de entrada;
A variação introduzida foi iniciar o dicionário com todas as
frases que contém apenas um símbolo no alfabeto que está
sendo usado.
Compressão LZW
LZW - Lempel-Ziv-Welch
Para se obter a codificação através do método LZW devem
ser seguidos os seguintes passos:
1 Inicialize o dicionário com todos os símbolos;
2 Procure, no código a ser comprimido, pelo bloco mais longo
que tenha registro no dicionário;
3 Codifique o bloco com o índice que consta no dicionário,
4 Adicione o bloco, seguido pelo próximo caractere da
sequência, ao dicionário, e volte ao passo 2;
5 Parada.
Para decodificar o código gerado, basta trocar os índices pelas
frases a eles associadas.
M. Soares, P. Martins, R. Pereira e D. Coutinho..
Funcionamento
Exemplo:
codificação do texto: BABABABABABAB, a partir de três
símbolos (A, B, C)
a tabela de sequências é inicializada com os três símbolos:
A, B e C.
Funcionamento
Exemplo: BABABABABABAB
A tabela e a informação codificada obtidas após a aplicação
do algoritmo são:
Aplicações que usam LZ ou variantes
Notas:
Unix Compression
O algoritmo LZC é utilizado pelo utilitário do UNIX;
GIF (Graphics Interchange Format)
Muito similar ao compress do UNIX também usa LZC;
Protocolo V42bis
Usa uma variante do LZW (LZT);
Zip e gzip usam uma variante do LZ77 combinada com
Huffman;
ARJ usa a codificação de Huffman e o algoritmo LZSS;
Winrar usa o LZ77 e o Hufman;
Winzip entre outros algoritimo usa o LZW;
o LZ77 é usado no PKZIP, GZIP e no formato de imagens
PNG;
Notas finais
Notas:
LZ77 não tem patente, razão pela qual é usado em, muitos
compactadores.
LZ78 e LZW possuem patente;
O problema básico dos algoritmos que usam dicionário é a
memória usada para guardar o dicionário;
Atualmente existem algoritmos com taxas de compressão
significantemente melhores que os Lempel-Ziv’s, porém
devido a vantajosa simplicidade computacional, este tipo de
codificador ainda é largamente usado.
Referências
Literatura consultada
M. Pasin. Uma Breve Introdução à Compressão de Dados,
2007
M. Camara. Criptografia e Compressão de Dados. 2004.
M. Soares, P. Martins, R. Pereira e D. Coutinho.
Compressão de Dados com o Algoritmo Lempel-Ziv: Um
caso Estudado. 2002.
A. L Brasil. O Algoritmo LZW
1	
  
Algoritmos e Estruturas de Dados!
Algoritmos	
   de	
   codificação	
   (LZSS)	
   baseada	
   em	
  
dicionário	
  sem	
  perda	
  de	
  dados;	
  
	
  
	
  
Codificação	
   de	
   sequências	
   vs	
   codificação	
   de	
  
símbolos;	
  
	
  	
  	
  	
  
2	
  
Algoritmos	
  Adaptados	
  
1977	
  
•  LZ77	
  :	
  Jacob	
  Ziv	
  e	
  Abraham	
  Lempel;	
  
1978	
  
•  LZ78	
  :	
  por	
  Jacob	
  Ziv	
  e	
  Abraham	
  
Lempel;	
  
1982	
  
•  LZSS:	
  Storer	
  e	
  Szymanski;	
  
1984	
  
•  LSW	
  :	
  Terry	
  Welch;	
  
	
  	
  	
  	
  
3	
  
Algoritmos	
  Adaptados	
  
4	
  
LZ77	
  
•  O Dicionário contém os símbolos já codificados; 
•  O look-ahead contém os símbolos a serem 
codificados, “janela futura”; 
•  “Janela deslizante” de dimensão fixa. 
	
   	
   	
   	
   Procura-­‐se	
   uma	
   cadeia	
   a	
   parSr	
   do	
   primeiro	
   caracter	
   da	
  
janela	
   futura	
   que	
   também	
   esteja	
   presente	
   na	
   janela	
   de	
  
texto.	
  
	
  	
  
	
  	
  	
  	
  Sendo	
  encontrada	
  alguma	
  coincidência,	
  a	
  cadeia	
  passa	
  a	
  ser	
  
codificada	
  em	
  um	
  bloco	
  de	
  três	
  parâmetros	
  (i,	
  n,	
  p).	
  
	
  
	
  	
  	
  	
  i	
  -­‐	
  Posição	
  do	
  inicio	
  da	
  cadeia	
  na	
  janela	
  de	
  texto;	
  
	
  	
  	
  	
  n-­‐	
  O	
  comprimento	
  da	
  cadeia;	
  
	
  	
  	
  	
  p-­‐	
  Primeiro	
  caracter	
  da	
  janela	
  futura	
  após	
  o	
  fim	
  da	
  cadeia.	
  
5	
  
LZ77	
  
•  A	
   dimensão	
   do	
   dicionário	
   condiciona	
   até	
   onde	
   se	
   pode	
  
pesquisar;	
  
•  A	
   dimensão	
   do	
   look-­‐ahead,	
   janela	
   futura,	
   condiciona	
   a	
  
máxima	
  dimensão	
  da	
  sequência	
  a	
  codificar;	
  	
  
•  Se	
  aumentar	
  o	
  tamanho	
  da	
  janela	
  futura,	
  maior	
  compressão	
  
"vantagem",	
   por	
   exemplo,	
   de	
   128	
   caracteres	
   para	
   1024,	
  
torna-­‐se	
  oito	
  vezes	
  mais	
  lento.	
  
•  É	
   ineficiente	
  pesquisar	
  com	
  frases	
  de	
  2	
  ou	
  menos	
  símbolos	
  
(devido	
  aos	
  bits	
  gastos	
  para	
  o	
  índice	
  e	
  dimensão	
  da	
  frase);	
  
	
  	
  	
  	
  	
  	
  	
  
6	
  
	
  Deficiências	
  do	
  Algoritmo	
  LZ77	
  
	
  	
  	
  	
  	
  
	
  	
  	
  	
   	
  Abraham	
  Lempel	
  e	
  Jacob	
  Ziv	
  evoluíram	
  LZ77.	
  
	
   	
   	
   	
  Novo	
  algoritmo	
  LZ78,	
  criando	
  uma	
  estrutura	
  
em	
   árvore,	
   onde	
   cada	
   nó	
   pode	
   possuir	
   um	
  
número	
  de	
  ramificações	
  igual	
  ao	
  comprimento	
  
do	
  alfabeto	
  uSlizado.	
  
7	
  
LZ78	
  
8	
  
Compressão	
  LZSS	
  
Variante do LZ77 e LZ78 proposta por Storer e Szymanski em 1982.!
 !
 Na codificação!
!
ü  Não inclui o símbolo que se segue à frase na área 
!de look-ahead, janela futura.!
!
ü  Usa dois formatos:!
! ! !- Um token com (n, i), ou!
 !- Só um símbolo.!
!
ü  Usa um bit extra para distinguir os dois formatos.!
ü  Sempre que a frase a codificar já existir no dicionário e o 
!número de elementos coincidentes for pelo menos 3 é 
!usado o primeiro formato, senão é!usado o segundo. !
9	
  
Descompressão	
  
O processo de decodificação.!
!
•  !Reverso do processo de codificação, usa uma tabela buscando o 
!apontador do dicionário da palavra-código entrada.!
•  !Ao mesmo tempo, o dicionário cresce de forma idêntica àquele 
!do codificador. !
•  !Descodificação sem perda em virtude da propriedade do prefixo 
!do dicionário garantir.!
•  !São limitado o número de caracteres que podem ser enviados 
!para o decodificador em um código.!
•  !Decodificador pode ser determinístico, predizer o dicionário do 
!codificador conforme as palavras-código entradas.!
10	
  
Aplicação	
  
!
!
!
O Zip e o gzip usam uma variante do LZ77 combinada com 
Huffman estático.!
!
!
O ARJ usa a codificação de Huffman e o algoritmo LZSS.!
!
!
!
O WINRAR usa o LZ77 e Huffman.!
!
!
!
11	
  
Burrows-­‐Wheeler	
  
O método de compressão de Burrows-Wheeler foi descrito em 1994.!
!
Ele é baseado em uma pesquisa (não publicada) de Wheeler em 1983. !
!
Sendo uma combinação de três algoritmos: !
!
•  !Uma função de transformação BWT, que reordena os bytes 
!originais, tornando-os bastante propícios para compressão. !
•  Aplica uma função heurística MTF. Faz com que os !dados de 
!saída contenham muitos zeros e grande tendência para !números 
positivos pequenos. !
•  Por fim submete os dados resultantes a algum método de 
!compressão que atue sobre estatísticas dos dados !(por 
!exemplo, código de Huffman).!
"
  !
!
12	
  
Burrows-­‐Wheeler	
  
!
 Descrição do algoritmo "Burrows-Wheeler Transform“!
!
•  !Diferente dos algoritmos da família "LZ", o BWT opera em blocos 
!de dados.!
•  !Quanto maior o tamanho dos blocos, maior a taxa de 
!compressão atingida.!
!
Ideia básica: dada uma sequência S de n símbolos, reordenar os 
símbolos formando outra sequência L, que verifica duas condições:!
!
•  A probabilidade de um símbolo ser igual ao anterior é muito 
elevada;!
•  É possível reconstruirS a partir de L.!
!
!
!
13	
  
Aplicação	
  
!
!
!
!
!
O método de Burrows-Wheeler foi difundido principalmente pelo 
utilitário de compactação de dados bzip2.!
!
É utilizado em:!
!
•  Imagens;!
•  Sons;!
•  Texto.!
!
Conclusões	
  
	
  
•  A	
  compressão	
  de	
  dados	
  surgiu	
  das	
  pesquisas	
  de	
  criptografia;	
  
•  A	
  compressão	
  sem	
  perdas	
  permite	
  a	
  recuperação	
  total	
  dos	
  
dados	
  originais,	
  contudo	
  apresenta	
  baixa	
  taxa	
  de	
  compressão	
  se	
  
comparada	
  aos	
  métodos	
  com	
  perdas;	
  
•  Para	
  que	
  comprimir?	
  
–  Para	
  redução	
  do	
  espaço	
  =sico	
  u>lizado;	
  
–  Para	
  agilização	
  na	
  transmissão	
  de	
  dados.	
  
•  Com	
  o	
  advento	
  dos	
  computadores	
  digitais,	
  a	
  compactação	
  de	
  
dados	
  passou	
  a	
  ser	
  obrigatória;	
  
•  Compressão	
  baseada	
  em	
  dicionário	
  possuem	
  as	
  técnicas	
  mais	
  
eficientes.	
  
1	
  
OBRIGADO!	
  
	
  
PERGUNTAS?	
  
	
  
2