579931 3 Compressao

Prévia do material em texto

Compressão	
  de	
  Dados	
  
	
  
IFCe	
  –	
  Ins)tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá)ca	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
  
	
  
1	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  de	
  Educação,	
  Ciência	
  e	
  Tecnologia	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  Código	
  -­‐	
  
•  Um	
   código	
   fonte	
  C	
   para	
   uma	
   variável	
   aleatória	
  X	
   é	
   o	
  mapeamento	
   dos	
  
possíveis	
  valores	
  de	
  X	
  para	
  o	
  conjunto	
  D*	
  (dicionário)	
  de	
  palavras	
  código	
  
de	
  comprimento	
  finito	
  cons2tuídas	
  com	
  símbolos	
  do	
  alfabeto	
  D.	
  
•  Se	
   x	
   é	
   uma	
   observação,	
   então	
  C(x)	
   é	
   seu	
   código	
   e	
   l(x)	
   o	
   comprimento	
  
deste	
  código.	
  
Exemplo:	
   C(vermelho)=00	
   e	
   C(azul)=11	
   é	
   a	
   codificação	
   do	
   espaço	
   amostral	
  
S={vermelho,	
  azul}	
  u2lizando	
  o	
  alfabeto	
  D={0,1}.	
  
	
  
•  Comprimento	
  Esperado	
  ou	
  Médio.	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   2	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
L(C) = p(x)l(x)
x∈S
∑
-­‐	
  Informação	
  -­‐	
  
•  Exemplos:	
  calcule	
  a	
  entropia	
  de	
  X	
  e	
  o	
  comprimento	
  médio	
  do	
  código	
  
usado.	
  
	
  
1.	
  	
  
P(X=1)=1/2	
  è	
  C(1)=0	
  
P(X=2)=1/4	
  è	
  C(2)=10	
  
P(X=3)=1/8	
  è	
  C(3)=110	
  
P(X=4)=1/8	
  è	
  C(4)=111	
  
	
  
2.	
  Repita	
  para:	
  
P(X=1)=1/3	
  è	
  C(1)=0	
  
P(X=2)=1/3	
  è	
  C(2)=10	
  
P(X=3)=1/3	
  è	
  C(3)=11	
  
	
  	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   3	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  Código	
  -­‐	
  
•  Um	
  código	
  C	
  é	
  dito	
  não	
  singular	
  se	
  todo	
  valor	
  de X é	
  mapeado	
  em	
  uma	
  
palavra	
  código	
  diferente	
  de	
  D*,	
  isto	
  é:	
  	
  
x ≠ x’à C(x) ≠ C(x’)
•  A	
   não	
   singularidade	
   é	
   suficiente	
   para	
   uma	
   descrição	
   não	
   ambígua	
  
individual	
  dos	
  valores	
  de	
  X.	
  Porém,	
  quando	
  pensamos	
  na	
  transmissão	
  de	
  
vários	
   símbolos	
   torna-­‐se	
   necessário	
   o	
   uso	
   de	
   um	
   símbolo	
   extra	
   para	
  
separar	
   as	
   palavras	
   código,	
   o	
   que	
   não	
   é	
   uma	
   abordagem	
   eficiente.	
   A	
  
solução	
  é	
  o	
  uso	
  de	
  códigos	
  unicamente	
  decodificáveis.	
  
•  A	
  extensão	
  C*	
  de	
  um	
  código	
  C	
  é	
  o	
  mapeamento	
  definido	
  por:	
  
C(x1x2x3... xn) = C(x1)C(x2)C(x3)... (xn)
Um	
  código	
  é	
  dito	
  unicamente	
  decodificavel	
  se	
  sua	
  extensão	
  é	
  não	
  singular. 
Um	
   código	
   é	
   dito	
   instantâneo	
   se	
   uma	
   palavra	
   não	
   é	
   prefixo	
   de	
   qualquer	
  
outra.	
  	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   4	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  Código	
  -­‐	
  
•  Em	
  um	
  código	
   instantâneo	
  cada	
   símbolo	
  pode	
   ser	
  decodificado	
   tão	
   logo	
  
sua	
  palavra	
  código	
  é	
  recebida.	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   5	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  Inequação	
  de	
  Krae	
  -­‐	
  
•  Ao	
  construir	
  um	
  código	
  desejamos	
  que	
  ele	
  seja	
  instantâneo	
  e	
  de	
  mínimo	
  
comprimento	
   médio.	
   Porém	
   existe	
   uma	
   limitação	
   quanto	
   a	
   u2lizar	
  
palavras	
  código	
  curtas	
  e	
  manter	
  o	
  código	
  instantâneo.	
  
O	
   comprimento	
   possível	
   das	
   palavras	
   para	
   um	
   código	
   instantâneo	
   deve	
  
obedecer	
  a	
  seguinte	
  inequação:	
  
	
  
	
  
	
  
em	
   que	
   D	
   é	
   o	
   tamanho	
   do	
   alfabeto	
   e	
   li	
   o	
   comprimento	
   de	
   cada	
   palavra	
  
código	
  u2lizada.	
  
	
  
	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   6	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
D−li
i
∑ ≤1
-­‐	
  Código	
  Ó2mo-­‐	
  
•  O	
  código	
  ó2mo	
  busca	
  atender	
  a	
  dois	
  critérios:	
  
1.  Mínimo	
  comprimento	
  médio	
  de	
  código	
  
2.  Ser	
  instantâneo	
  (atender	
  a	
  inequação	
  de	
  Krae)	
  
Sendo	
   assim,	
   a	
   condição	
   para	
   que	
   um	
   código	
   seja	
   ó2mo	
   pode	
   ser	
  
estabelecida	
  minimizando	
  o	
  critério	
  abaixo:	
  
	
  
	
  
	
  
Em	
  que	
  λ	
  é	
  uma	
  constante	
  de	
  lagrange.	
  Queremos	
  encontrar	
  o	
  comprimento	
  	
  
li*	
   que	
  minimize	
   simultaneamente	
  os	
   dois	
   critérios,	
   logo	
  devemos	
  derivar	
  J	
  
em	
  relação	
  a	
  li.	
  
	
  
	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   7	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
J = pili
i
∑ +λ D−li
i
∑
-­‐	
  Código	
  Ó2mo-­‐	
  
Minimizar	
  os	
  somatórios	
  consiste	
  de	
  minimizar	
  cada	
  termo	
  individualmente,	
  
logo	
  podemos	
  simplificar	
  a	
  análise:	
  
	
  
	
  
	
  
	
  
	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   8	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
∂J
∂li
= 0
∂J
∂li
≡
∂
∂li
pili +λD−li( )
∂
∂li
pili +λD−li( ) = pi −λD−li ln(D)
pi −λD−li ln(D) = 0
-­‐	
  Código	
  Ó2mo-­‐	
  
	
  
Se 	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  ,	
  então	
  
	
  
	
  
	
  
Com	
  base	
  neste	
  resultado	
  podemos	
  derivar	
  a	
  comprimento	
  médio	
  do	
  código	
  
ó2mo:	
  
	
  
	
  
	
  
	
  
	
  
O	
   Comprimento	
  médio	
   do	
   código	
   ó2mo	
   com	
   dicionário	
   de	
  D	
   símbolos	
   é	
   a	
  
entropia	
  D-­‐nária	
  desta	
  fonte.	
  
	
  
	
  
	
  
	
  
	
  
	
  
	
  
	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   9	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
λ =
1
ln(D)
D−li = pi → li* = − logD (pi )
L* = E li*{ }= E − logD (pi ){ }
L* = − pi logD (pi )
i
∑
L* = HD (X)
-­‐	
  Código	
  Ó2mo-­‐	
  
Temos	
  que	
  o	
  comprimento	
  médio	
  do	
  código	
  ó2mo	
  é	
  exatamente	
  a	
  entropia	
  
da	
   fonte	
   X,	
   computada	
   na	
   base	
   do	
   alfabeto.	
   No	
   caso	
   de	
   D=2,	
   temos	
   a	
  
entropia	
  da	
  Shannon	
  que	
  é	
  limite	
  da	
  codificação	
  de	
  fonte.	
  	
  
	
  
No	
   Exemplo	
   1	
   do	
   Slide	
   3	
   encontramos	
   um	
   código	
   ó2mo,	
   como	
   se	
   pode	
  	
  
verificarP(X=1)=1/2	
  è	
  C(1)=0	
  	
  
P(X=2)=1/4	
  è	
  C(2)=10	
  
P(X=3)=1/8	
  è	
  C(3)=110 	
  	
  	
  	
  	
  	
  è	
  
P(X=4)=1/8	
  è	
  C(4)=111	
  
	
  
	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   10	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
l1* = − log2(1 / 2) =1
l2* = − log2(1 / 4) = 2
l3* = − log2(1 / 8) = 3
l4* = − log2(1 / 8) = 3
-­‐	
  Código	
  Ó2mo-­‐	
  
Uma	
  restrição	
  do	
   resultado	
  encontrado	
  é	
  que	
   li	
  dever	
   ser	
   inteiro,	
   logo	
  nem	
  
sempre	
  é	
  possível	
  encontrar	
  o	
  conjunto	
  de	
  códigos	
  que	
  atendam	
  ao	
  critério:	
  
	
  
	
  
Ficamos	
   assim,	
   normalmente,	
   limitados	
   a	
   um	
  que	
   se	
   aproxima	
  do	
   conjunto	
  
ó2mo,	
  de	
  tal	
  forma	
  que	
  na	
  prá2ca	
  temos:	
  
	
  
	
  
Alcançamos	
  a	
   igualdade	
  na	
  expressão	
  acima	
   se	
   somente	
   se	
  a	
  probabilidade	
  
da	
   dos	
   símbolos	
  pi	
   é	
  D-­‐adica,	
   ou	
   seja,	
   se	
   cada	
   probabilidade	
   é	
   igual	
   a	
  D-n.	
  
Como	
   no	
   exemplo	
   do	
   slide	
   anterior.	
   Neste	
   caso	
   -­‐logD(pi)	
   fornece	
   valores	
  
inteiros.	
  Caso	
  contrário,	
  ficamos	
  restritos	
  a	
  condição	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   11	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
L ≥ HD (X)
li* = − logD (pi )
HD (X) ≤ L < HD (X)+1
-­‐	
  Código	
  Ó2mo-­‐	
  
Exemplo:	
  calcule	
  L(C)	
  e	
  H(X)	
  considerando	
  as	
  novas	
  probabilidades.	
  
	
  
P(X=1)=0.54	
  è	
  C(1)=0	
  	
  
P(X=2)=0.26	
  è	
  C(2)=10	
  
P(X=3)=0.1	
  è	
  C(3)=110 	
  	
  	
  	
  	
  
P(X=4)=0.1	
  è	
  C(4)=111	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   12	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
Código	
  de	
  Huffman	
  
13	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  de	
  Educação,	
  Ciência	
  e	
  Tecnologia	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  Código	
  de	
  Huffman	
  -­‐	
  
Huffman	
   propôs	
   o	
   método	
   de	
   obtenção	
   do	
   código	
   “ó2mo”,	
   com	
   o	
   menor	
  
comprimento	
   médio	
   L.	
   É	
   comprovado	
   que	
   nenhum	
   código,	
   u2lizando	
   o	
  
mesmo	
   alfabeto,	
   fornece	
   comprimento	
   médio	
   menor	
   que	
   o	
   código	
   de	
  
Huffman.	
  	
  
	
  
Assim,	
   o	
   código	
   de	
   Huffman	
   estabelece	
   o	
   limite	
  mínimo	
   prá2co	
   de	
  L	
   para	
  
codificação	
  de	
  uma	
  fonte,	
  dada	
  qualquer	
  distribuição	
  de	
  probabilidade.	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   14	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  Código	
  de	
  Huffman	
  -­‐	
  
	
  
A	
   implementação	
   do	
   código	
   consiste	
   em	
   listar	
   os	
   símbolos	
   em	
   ordem	
  
decrescente	
   de	
   probabilidade	
   e	
   combinar	
   os	
   dois	
   símbolos	
   de	
   menor	
  
probabilidade.	
  	
  
	
  
Estes	
   símbolos	
   são	
   recolocados	
   na	
   lista	
   como	
   um	
   novo	
   símbolo	
   cuja	
  
probabilidade	
   é	
   a	
   soma	
   das	
   anteriores.	
   Uma	
   nova	
   lista	
   é	
   formada	
   e	
   o	
  
processo	
  é	
  repe2do	
  até	
  que	
  se	
  tenha	
  um	
  único	
  símbolo.	
  
	
  
Percorrendo	
  esta	
  estrutura	
  no	
  sen2do	
  contrário	
  teremos	
  uma	
  árvore	
  binária	
  
que	
  formará	
  a	
  palavra	
  código	
  de	
  cada	
  símbolo.	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   15	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  Código	
  de	
  Huffman	
  -­‐	
  
	
  	
  
	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   16	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
(4;5)=0.3	
  
(2;3)=0.45	
  
(1;4;5)=0.55	
  
(1)=0.25	
  
(2)=0.25	
  
(3)=0.20	
  
(4)=0.15	
  
(5)=0.15	
  
(1…5)=1.00	
  
0
0
1
1
1
1
0
0
Códigos	
  Universais	
  
17	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  de	
  Educação,	
  Ciência	
  e	
  Tecnologia	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  Lempel-­‐Ziv	
  -­‐	
  
Código	
  de	
  Lempel-­‐Ziv	
  pode	
  ser	
  implementado	
  seguindo	
  dois	
  modelos:	
  
•  LZ-­‐77:	
  implementação	
  por	
  janela	
  deslizante	
  
•  LZ-­‐78:	
  implementação	
  por	
  árvore	
  
O	
  princípio	
  de	
  codificação	
  do	
  LZ	
  é	
  o	
  de	
  dicionário	
  dinâmico,	
  ou	
  seja,	
  os	
  dados	
  
são	
  codificados	
  a	
  medida	
  que	
  são	
  lidos	
  e	
  novas	
  entradas	
  são	
  adicionadas	
  ao	
  
dicionário.	
  
	
  
O	
  Algoritmo	
  LZ	
  não	
  tem	
  o	
  desempenho	
  do	
  código	
  de	
  Huffman,	
  porém	
  ele	
  é	
  
u2lizado	
  devido	
  a	
  sua	
  simplicidade	
  	
  e	
  velocidade.	
  Alguns	
  formatos	
  como	
  ZIP	
  e	
  
GIF	
   u2lizam	
   o	
   LZ	
   em	
   estratégias	
   de	
   compactação,	
   como	
   por	
   exemplo,	
  
combinado	
  com	
  o	
  código	
  de	
  Huffman.	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   18	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  LZ-­‐77	
  -­‐	
  
Seja	
  a	
  sequência	
  x1	
  x2	
  x3	
  x4	
  x5	
  x6	
  ...	
  xi	
  xi+1	
  xi+2	
  xi+3	
  ...	
  xj....	
  xn	
  
No	
   esquema	
   de	
   janela	
   deslizante,	
   escolhe-­‐se	
   previamente	
   um	
   tamanho	
   de	
  
janela	
  w.	
  	
  
	
  
1.	
   Com	
   a	
   janela	
   posicionada	
   em	
   xi-­‐w	
   …	
   xi,	
   busca-­‐se	
   dentro	
   da	
   janela	
   a	
  
sequência	
   xi+1…xi+1+k.	
   O	
   procedimento	
   começa	
   com	
   k=w	
   e	
   o	
   valor	
   de	
   k	
   é	
  
decrescido	
  até	
  que	
  a	
  sequência	
  xi+1…xi+1+k	
  seja	
  encontrada.	
  	
  
	
  
2.	
   Se	
   a	
   sequência	
   é	
   encontrada,	
   armazena-­‐se	
   o	
   par	
   (comprimento	
   da	
  
sequência,	
  posição	
  na	
  janela).	
  	
  
	
  
3.	
  Se	
  k=0	
  e	
  a	
  sequência	
  não	
  foi	
  encontrada,	
  armazena-­‐se	
  o	
  par	
  (0,xi).	
  	
  
	
  
4.	
  A	
  janela	
  é	
  deslocada	
  para	
  o	
  caracter	
  xi+k+1.	
  O	
  procedimento	
  é	
  reiniciado.	
  	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   19	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  LZ-­‐77	
  -­‐	
  
Ex:	
  seja	
  a	
  sequência	
  abaixo	
  e	
  w	
  =	
  4321	
  
	
   	
   	
   	
   	
  Código	
  gerado	
  
	
  ABBABBABBBAABABA 	
   	
  è	
  (0,A)	
  
	
  ABBABBABBBAABABA 	
   	
  è	
  (0,B)	
  
	
  ABBABBABBBAABABAè	
  (1,1)	
  
	
  ABBABBABBBAABABA 	
   	
  è	
  (3,3)	
  
	
  ABBABBABBBAABABA 	
   	
  è	
  (3,3)	
  
	
  ABBABBABBBAABABA 	
   	
  è	
  (2,4)	
  
	
  ABBABBABBBAABABA 	
   	
  è	
  (1,1)	
  
	
  ABBABBABBBAABABA 	
   	
  è	
  (2,3)	
  
	
  ABBABBABBBAABABA 	
   	
  è	
  (2,2)	
  
	
  
	
  
	
  
	
   Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   20	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  LZ-­‐78	
  -­‐	
  
Seja	
  a	
  sequência	
  x1	
  x2	
  x3	
  x4	
  x5	
  x6	
  ...	
  xi	
  xi+1	
  xi+2	
  xi+3	
  ...	
  xj....	
  xn	
  
No	
   esquema	
  de	
   árvore	
   a	
   sequência	
   é	
   previamente	
   dividida	
   em	
  palavras	
   de	
  
maneira	
  que:	
  i)	
  cada	
  palavra	
  seja	
  única	
  e	
  ii)	
  de	
  menor	
  comprimento	
  possível.	
  	
  
	
  	
  
Assim,	
  cada	
  palavra	
  Pj	
  terá	
  kj	
  caracteres	
  consecu2vos	
  da	
  sequência.	
  	
  
	
  
Uma	
  caracterís2ca	
  deste	
  procedimento	
  é	
  que	
  se	
  Pj	
  é	
  composta	
  por	
  mais	
  de	
  
uma	
  caractere,	
  ou	
  seja	
  kj>1,	
  exis2rá	
  uma	
  palavra	
  Pi	
  anterior	
  (i<j)	
  tal	
  que	
  Pj={Pi	
  	
  
xkj}.	
  Esta	
  é	
  exatamente	
  a	
   informação	
  u2lizada	
  para	
  codificar	
  cada	
  palavra	
  da	
  
sequência	
  na	
  forma:	
  (i,	
  xki)	
  (índice	
  da	
  palavra	
  prévia	
  Pi,	
  úl2mo	
  caracter	
  de	
  Pj).	
  
	
  
Se	
  kj=1,	
  ou	
  seja,	
  a	
  palavra	
  Pj	
  é	
  composta	
  de	
  apenas	
  um	
  caractere,	
  essa	
  será	
  
codificada	
  como	
  (0,xkj)	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   21	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca	
  
-­‐	
  LZ-­‐77	
  -­‐	
  
Ex:	
  seja	
  a	
  sequência:	
  ABBABBABBBAABABA	
  
	
   	
   	
   	
   	
  Código	
  gerado	
  
	
  P1,	
  P2,	
  	
  P3	
  ,	
  P4	
  ,	
  	
  P5	
  ,	
  	
  P6	
  	
  	
  	
  	
  ,	
  	
  P7	
  	
  	
  ,	
  P8 	
  	
  
	
  A,	
  	
  B	
  	
  ,	
  BA,	
  BB,	
  AB,	
  BBA,	
  ABA,	
  BA	
  
	
  
	
  P1={A} 	
   	
   	
   	
  è	
  (0,A)	
  
	
  P2={B} 	
   	
   	
   	
  è	
  (0,B)	
  
	
  P3={P2	
  A} 	
   	
   	
  è	
  (2,A)	
  
	
  P4={P2	
  B} 	
   	
   	
  è	
  (2,B)	
  
	
  P5={P1	
  B} 	
   	
   	
  è	
  (1,B)	
  
	
  P6={P4	
  A} 	
   	
   	
  è	
  (4,A)	
  
	
  P7={P5	
  A} 	
   	
   	
  è	
  (5,A)	
  
	
  P8={P3	
  EOF} 	
   	
   	
  è	
  (3,EOF)	
  
	
  
	
  
	
  
	
  
Prof.	
  Dr.	
  Regis	
  C.	
  P.	
  Marques	
  
regismarques@ifce.edu.br	
   22	
  
IFCe	
  –	
  Ins2tuto	
  Federal	
  do	
  Ceará	
  
Departamento	
  de	
  Telemá2ca