A25a-INF01124_CPD

Prévia do material em texto

1
Classificação e Pesquisa de 
Dados
Aula 25a
Exercícios sobre Compressão de Arquivos
UFRGS INF01124
Exercício 1
Com base no método de compressão de Pike (códigos compostos) 
decodificar as seqüências abaixo e calcular o percentual de redução 
obtido em relação a uma representação de códigos de tamanho fixo 
de 8 bits:
n A) 0001 0011 0000 1101 1011
n B) 0000 1110 0000 1010 0001 0001 0111 0001 1010 0101
Exercício 1 - Resolução
(A) 0001 0011 0000 0010 1011
(B) 0000 1110 0000 1010 0001 0001 0111 0001 1010 0101
n
with
8 bit word
m
8 bit char
8 bit char 8 bit char8 bit word 8 bit word
he was p i k e
Pike=>20 bits
8 bits=>48 bits
Percentual de Redução=>58,33%
Pike=>40 bits 8 bits=>72 bits Percentual de Redução=>44,44%
Exercício 2
Uma palavra foi codificada usando o código de Huffman, tendo-se 
obtido a sequência binária 
1 0 1 1 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 
O alfabeto original era constituído pelas letras 
A, B, C, D, E, I, L, R e T e a letra I foi codificada como "00".
Supondo que estas letras ocorriam com as probabilidades
P(A) = 0.26 P(D) = 0.01 P(L) = 0.01 
P(B) = 0.09 P(E) = 0.07 P(R) = 0.23 
P(C) = 0.08 P(I) = 0.22 P(T) = 0.03 
A) Qual terá sido a palavra codificada?
B) Calcule o número médio de bits por caracter obtido pelo uso da 
codificação de Huffman e compare com a utilização de um código 
binário de tamanho fixo para representação do mesmo alfabeto.
C) Apresente o esboço de um algoritmo para criar uma árvore de Huffman.
Exercício 2 - Resolução
I R A D L T E C B
(0.22) (0.23) (0.26) (0.01) (0.01) (0.03) (0.07) (0.08) (0.09)
(0.02)
(0.12) (0.17)
(0.29)(0.45)
(0.55)
(1.00)
0
0
(0.05)1
1
1
1
1
0
0
1
1
10
0
0
0
Exercício 2 - Resolução
Ch Freqüência (f) Código Comprimento (l) l * f
A 0.26 10 2 0.52
B 0.09 1111 4 0.36
C 0.08 1110 4 0.32
D 0.01 110000 6 0.06
E 0.07 1101 4 0.28
I 0.22 00 2 0.44
L 0.01 110001 6 0.06
R 0.23 01 2 0.46
T 0.03 11001 5 0.15
Nro. médio de bits por caracter = 2.65
2
Exercício 2 - Resolução
(A) 
1 0 1 1 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0
A C E R T E I
(B)
n 9 caracteres (A, B, C, D, E, I, L, R, T) 
n 4 bits por caracter (2^4=16)
n Huffman --> 33,75% Redução
Exercício 2 - Resolução
(C) 
Huffman(c) 
n = |c| 
Q = c 
for i = 1 to n-1 
z = Allocate-Node() 
x = Extract-Min(Q) 
y = Extract-Min(Q) 
left(z) = x 
right(z) = y 
f(z) = f(x) + f(y) 
Insert(Q,z) 
return Extract-Min(Q) 
Onde:
n Q é uma lista de espera ordenada pela frequência de cada caracter. 
n left(z) e right(z) são os filhos esquerdo e direito, respectivamente, do nodo z. 
n Extract-Min retorna o primeiro elemento da lista (excluindo-o). 
n Insert(Q,z) insere o novo elemento z na lista Q. 
Exercício 3
Utilizar o método de compressão de seqüências ordenadas 
(explorando prefixos comuns), que foi apresentado em aula, 
para comprimir a seqüência dada:
VENDA
VENDADO
VENDEDOR
VENDEDORA
VENDENDO
VENDIDO
VENDIDA
Faça o algoritmo para tal método de compressão. 
Considerar que a seqüência ordenada é representada em 
um vetor de strings. Por ex.: 
n Entrada à sequencia[0]=“SEPARAR”; sequencia[1]=“SEPARATA”;
n Saída à sdecodif[0]=“0,SEPARAR”; sdecodif[1]=“6,TA”;
VENDA 0, VENDA
VENDADO 5, DO
VENDEDOR 4, EDOR
VENDEDORA 8, A
VENDENDO 5, NDO
VENDIDO 4, IDO
VENDIDA 6, A
Seqüência Comprimida
Seqüência original
Exercício 3 - Resolução
Exercício 3 - Resolução
Decodifica(string sequencia[n])
sdecodif[0]=“0,”+sequencia[0];
for (x=1; x<n; x++)
cont=0;
while((sequencia[x-1][cont]==sequencia[x][cont])|| 
(cont!=strlen(sequencia[x-1]))
cont++;
sdecodif[x]=cont+’,’;
for (y=cont;y<strlen(sequencia[x]);y++)
sdecodif[x]=sdecodif[x]+sequencia[x][y];