aula08

Prévia do material em texto

8ºAula
COMPACTAÇÃO DE ARQUIVOS
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
• saber o que é uma compactação de arquivos;
• conhecer o processo de compactação run-length;
• entender o algoritmo de Huffman.
Olá,
Para fecharmos a nossa disciplina com “Chave de Ouro”, 
vamos estudar um assunto muito discutido na Ciência da 
Computação, atualmente: a Compactação de Arquivos. Nesta 
aula, vamos aprender o que ela é, e veremos alguns algoritmos 
simples que fazem dessa compactação uma forma simples.
Leiam atentamente esta aula e façam os exercícios. Se 
enfrentarem alguma dúvida, estaremos a sua disposição na área 
do aluno.
Bons estudos!
53
Estrutura de Dados II 52
1. 
Seções de estudo
Compressão de dados
2. Codificação run-length
3. Algoritmo de Huffman
1 - Compressão de dados
A compressão de dados é o processo de reduzir o 
tamanho de um arquivo ou de um dado. Ele é muito 
importante, pois graças a esses algoritmos de compactação, 
muitos gigabytes de espaço nos discos rígidos e banda de 
internet foram poupados. Ela é usada nos seguintes fins:
• Para economizar espaço de armazenamento.
• Para economizar banda durante a transmissão de 
dados, deixando a transmissão mais rápida - vide o 
exemplo do streaming.
• Para juntar vários arquivos em um só. Por exemplo, 
o Microsoft Office, desde a versão 2007, a qual usa a 
tecnologia ZIP para seus novos formatos de arquivo, 
que reúne imagens, vídeos, textos, informações 
sobre o arquivo etc.
• Entre outros.
• Para desempenhar essa tarefa, foram desenvolvidos 
vários algoritmos e técnicas de compressão de 
arquivos. Esses algoritmos e técnicas podem ser 
divididos em dois grandes grupos:
• Compressão sem perda: São os algoritmos que 
compactam arquivos sem perda alguma no conteúdo 
e na integridade dos dados. Nesse grupo, um dado 
que é submetido a um processo de compressão e 
descompressão é idêntico ao original. Os dados 
redundantes são removidos na compressão e 
acrescentados na descompressão. Algoritmos 
desse grupo são usados quando nenhuma perda é 
admitida nos dados, como arquivos de texto. São 
exemplos: A codificação run-length, codificação de 
Huffman (tema desta aula), codificação Lempel-Ziv, 
compactação ZIP etc.
• Compressão com perda: São algoritmos que geram 
perdas no conteúdo e na integridade nos dados. 
Mas são perdas imperceptíveis. Esses algoritmos 
são usados quando a perda (de forma moderada) 
é algo aceitável e benéfico, como imagens, áudios e 
vídeos. São exemplos disso: a tecnologia JPEG, MP3 
e MPEG.
Nesta aula, vamos estudar os algoritmos de compactação 
de dados sem perda mais simples, que são o run-length e o 
algoritmo de Huffman.
2 - Codi cação run-length
A codificação run-length é uma das mais simples que 
existe. Ela consiste em ler todos os caracteres de um texto, e 
condensar as sequências repetidas de uma letra pela sua letra e 
o respectivo número de aparições seguidas. Assim, 
suponhamos a seguinte sequência:
Para compactar usando a codificação run-length 
precisamos ler a cadeia de caracteres do texto, para verificar 
quantas vezes repete uma letra no texto. Primeiramente, 
lemos a sequência de letras “a”. Contamos quantas vezes 
seguidas aparece a letra “a” no texto. No caso, verificamos 
que ela repete 8 vezes. Assim, colocamos a letra “a” e depois 
o número 8, para indicar que ela repete 8 vezes no texto.
O próximo caractere a ser lido é “b”. Constatamos que 
ela aparece 6 vezes seguidas. Assim, inserimos a letra “b” e 
o número 6. O mesmo acontece com a letra “c”, que repete 
duas vezes.
Feito isso, basta apenas inserir no novo texto a letra e o 
seu respectivo número de caracteres seguidos:
Para descompactar basta ler a letra e a sua quantidade de 
vezes. Feito isso, basta inserir no texto a quantidade de vezes 
desse caractere.
A seguir, veremos o pseudocódigo desta operação:
procedimento compactar(texto: caractere)
declare
 qtd: inteiro
 anterior, atual: caractere
inicio
 anterior <- leia_proximo_caracter(texto)
 qtd <- 1
 enquanto (ha_caracteres(texto)) faca
 atual <- leia_proximo_caracter(texto)
 se (atual = anterior) faca
 qtd <- qtd + 1
 senao
 escreva(anterior)
 escreva(qtd)
 qtd <- 1
 fimse
 anterior <- atual
 fimenquanto
fimprocedimento 
Esse algoritmo pode ser bom. Mas em um texto real, 
onde é difícil duas letras seguidas estarem em uma mesma 
palavra, a codificação run-length mais atrapalha do que ajuda, 
pois insere mais caracteres do que é pedido em uma situação 
de texto real.
Para isso, foram desenvolvidos outros tipos de 
algoritmos. A seguir mostraremos como funciona o algoritmo 
de Huffman.
3 - Algoritmo de Hu man
Outra forma de compactar dados em um arquivo é o 
algoritmo de Huffman. Esse algoritmo permite uma 
economia de 20 a 90% no tamanho do arquivo a ser salvo. 
54
53
Para cumprir o seu papel, o código de Huffman faz uma 
contagem de quantas vezes uma letra ou uma palavra 
aparece no texto, e classifica em ordem da quantidade de 
aparições.
Depois, as letras ou palavras são agrupadas em forma 
de uma árvore, privilegiando os símbolos mais frequentes, 
colocando eles em posições de profundidade menor na 
árvore. Após isso, temos os códigos para cada símbolo 
nessa árvore, que representam o caminho da raiz até o 
símbolo. O 0 representa a subárvore esquerda, enquanto 
que o 1 representa a subárvore direita.
A seguir, mostramos uma tabela de frequências de 
caracteres oriundos de um texto hipotético. Em seguida, 
mostraremos como ficaria à disposição dos caracteres em 
uma árvore de comprimento fixo (onde cada caractere 
recebe uma sequência de um mesmo número de caracteres), 
e em uma árvore gerada pelo algoritmo de Huffman, que 
privilegia os caracteres mais frequentes. Observe que para 
chegarmos a letra “a”, que é a mais frequente, precisaríamos 
percorrer 3 nós antes de chegarmos ao nó final em um 
código de comprimento fixo, enquanto em que uma árvore 
gerada pelo algoritmo de Huffman precisamos percorrer 
apenas 1 nó para chegar ao valor desejado. 
a b c d e f
Frequência (em 
milhares)
45 13 12 16 9 5
Palavra de código em 
comprimento o
000 001 010 011 100 101
Palavra de código de 
comprimento variável
0 101 100 111 1101 1100
Fonte: (CORMEN et. al., 2012, p. 313).
É claro que em uma árvore gerada pelo algoritmo 
de Huffman alguns símbolos serão mais difíceis de ser 
encontrados e, portanto, terão um código maior, mas isso 
é compensado pela facilidade de encontrar os caracteres 
mais frequentes e também pela economia gerada por esses 
códigos.
Mas, como gerar essa árvore? Primeiramente, lemos 
todo o arquivo texto fazendo uma contagem de quantas 
vezes cada caractere aparece no texto. Armazenamos essa 
tabela de frequências em uma lista de registros, onde cada 
registro possui duas informações: o caractere e a quantidade 
de vezes que ele apareceu. 
Como o algoritmo precisa da leitura prévia de todos os 
dados, chamamos esse algoritmo de algoritmo guloso.
Essa lista é submetida ao algoritmo de Huffman. Nesse 
algoritmo extraímos a quantidade de nós e colocamos na 
variável n. O loop percorre de 1 até n-1. A cada interação, 
extraímos os nós com as menores frequências. Depois, 
criamos um novo nó, que terá a soma das frequências dos 
dois nós extraídos, e terá como filhos os dois nós extraídos.
No final, esse novo nó é inserido na lista de maneira 
ordenada. O processo se repete até quando tivermos apenas 
um nó na lista, formando toda a árvore.
procedimento Huffman(C: *Lista)
declare
 n : inteiro
 Q : *//
 x, y, z : *TArvore
inicio
 n <- c.quantidade
 Q <- C
 para i de 1 ate n-1 faca
 z <- novoNo()
 z.esq <- x <- extrair_minimo(Q)
 z.dir <- y <- extrair_minimo(Q)
 z.freq <- x.freq + y.freq
 inserir_ordenado(Q, z)
 fimpara
 retorne extrair_minimo(Q) // Retorna a 
raiz da árvore
fimprocedimento
Depois, precisamos “traduzir” as letraspelas sequências 
correspondentes. Para isso, lemos cada letra do arquivo e 
trocamos pela sequência de bits correspondente a essa letra.
Assim, uma string contendo as seguintes letras:
fabaca
Deve ser traduzida para código binário da seguinte 
forma:
1100010101000
A princípio, não vemos uma melhora grandiosa no 
resultado, pois gerou mais caracteres. Mas, devemos lembrar 
que 1 caractere é armazenado em 1 byte, que equivale a 8 
bits. A string tem seis caracteres, logo são 6 bytes e 48 bytes. 
Em um código binário, todo 0 ou 1 pode ser armazenado 
em 1 bit. A cadeia gerada pelo compactador gerou uma 
cadeia de 13 bits. Ou seja, são 35 bits a menos.
Para facilitar a descompactação podemos salvar no 
arquivo a tabela de símbolos no seu início. Assim, para 
descompactar basta o programa ler essa tabela e ler bit 
por bit do arquivo até achar alguma correspondência. Se 
achar, escreve no arquivo resultante a letra correspondente 
e repete o processo.
A figura a seguir mostra a execução desse algoritmo no 
nosso texto de exemplo:
55
Estrutura de Dados II 54
E com isso, finalizamos a nossa aula e a nossa disciplina. 
Foi muito bom estar com vocês nesta jornada. Muito 
obrigado e até a próxima!
Retomando a aula
Chegamos ao m da nossa oitava aula. Vamos 
relembrar os pontos principais?
1 - Compressão de dados
Nesta seção, vimos que compressão de dados é o 
processo de reduzir o tamanho de um arquivo ou de um 
dado. Ela é usada nos seguintes fins: para economizar 
espaço de armazenamento; para economizar banda durante 
a transmissão de dados, deixando a transmissão mais rápida 
- vide o exemplo do streaming; para juntar vários arquivos em 
um só; entre outros. Existe dois tipos: a compressão com 
perda e a compressão sem perda.
2 - Codificação run-length
Nesta seção, vimos que a codificação run-length é uma 
das mais simples que existe. Ela consiste em ler todos os 
caracteres de um texto, e condensar as sequências repetidas 
de uma letra pela sua letra e o respectivo número de aparições 
seguidas.
3 - Algoritmo de Huffman
Nesta seção, vimos que outra forma de compactar dados 
em um arquivo é o algoritmo de Huffman. Esse algoritmo 
permite uma economia de 20 a 90% no tamanho do arquivo 
a ser salvo. Para cumprir o seu papel, o código de Huffman 
faz uma contagem de quantas vezes uma letra ou uma palavra 
aparece no texto, e classifica em ordem da quantidade de 
aparições. Depois, as letras ou palavras são agrupadas 
em forma de uma árvore, privilegiando os símbolos mais 
frequentes, colocando eles em posições de profundidade 
menor na árvore. Após isso, temos os códigos para cada 
símbolo nessa árvore, que representam o caminho da raiz até 
o símbolo. O 0 representa a subárvore esquerda, enquanto 
que o 1 representa a subárvore direita.
56
55
CORMEN, Thomas H.; et. al.. Algoritmos: teoria e 
prática. Rio de Janeiro: Campus, 2012.
FOROUZAN, Behrouz; MOSHARRAF, Firouz. 
Fundamentos de Ciência da Computação: Tradução da 2ª edição 
americana. São Paulo: Cengage, 2011.
KNUTH, Donald Ervin. The art of computer programming. 
3. ed. Amsterdam: Addison-Wesley, 1998.
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. 
Estruturas de dados e seus algoritmos. 2. ed. Rio de Janeiro: LTC, 
1994.
TENENBAUM, Aaron M.; AUGENSTEIN, Moshe 
J.; LANGSAN, Yedidyah. et al. Estruturas de dados usando 
C. São Paulo: Pearson Makron Books; São Paulo: Makron 
Books do Brasil; São Paulo: McGraw-Hill, 2013.
ZIVIANI, Nivio. Projeto de algoritmos: com 
implementação em PASCAL e C. 3. ed. São Paulo: Cengage 
Learning, 2011.
Vale a pena ler
Vale a pena
Referências
BARANAUSKAS. José Augusto. Árvores AVL Árvores 
AVL. USP, s.d. Disponível em: <http://dcm.ffclrp.usp.
br/~augusto/teaching/aedi/AED-I-Arvores-AVL.pdf>. 
Acesso em: 17 set. 2018.
CORMEN, Thomas H.; et. al.. Algoritmos: teoria e 
prática. Rio de Janeiro: Campus, 2012.
FEOFILOFF, Paulo. Hashing. São Paulo: USP, 2017. 
Disponível em: <https://www.ime.usp.br/~pf/estruturas-
de-dados/aulas/st-hash.html>. Acesso em: 07 ago. 2018.
FEOFILOFF, Paulo. Listas encadeadas. São Paulo : 
USP, 2017. Disponível em: <https://www.ime.usp.br/~pf/
algoritmos/aulas/lista.html>. Acesso em: 30 jul. 2018.
FEOFLIOFF, Paulo. Árvores binárias de busca. USP, 
2018. Disponível em: <https://www.ime.usp.br/~pf/
algoritmos/aulas/binst.html>. Acesso em: 15 set. 2018. 
FEOFILOFF, Paulo. Árvores B (B-trees). USP, 2018. 
Disponível em: <https://www.ime.usp.br/~pf/estruturas-
de-dados/aulas/B-trees.html>. Acesso em: 23 set. 2018.
FOROUZAN, Behrouz; MOSHARRAF, Firouz. 
Fundamentos de Ciência da Computação: Tradução da 2ª 
edição americana. São Paulo: Cengage, 2011.
HARGROVE, John. The AVL Tree Rotations Tutorial. 
2007. Disponível em: <https://www.cise.ufl.edu/~nemo/
cop3530/AVL-Tree-Rotations.pdf>. Acesso em: 19 set. 
2018. 
KNUTH, Donald Ervin. The art of computer 
programming. 3. ed. Amsterdam: Addison-Wesley, 1998.
MAFFEO, Bruno. Tipos Abstratos de Dados - Definição 
e Exemplos. PUC, s.d. Disponível em: <http://www.inf.puc-
rio.br/~coordicc/icc/TAD.pdf>. Acesso em: 25 jul. 2018.
MENA-CHALCO, Jesús P. Árvores Adelson-Velskii e 
Landis. UFABC, 2014. Disponível em: <http://professor.
ufabc.edu.br/~jesus.mena/courses/mc3305-2q-2015/
AED2-10.pdf>. Acesso em: 17 set. 2018.
NONATO, Luis Gustavo. Método da Dobra. USP, 2003. 
Disponível em: <http://www.lcad.icmc.usp.br/~nonato/
ED/Hashing/node36-b.html>. Acesso em: 08 ago. 2018.
RICARTE, Ivan L. M. Tabelas Hash. UNICAMP, 2003. 
Disponível em: <http://www.dca.fee.unicamp.br/cursos/
EA876/apostila/HTML/node26.html>. Acesso em: 07 ago. 
2018.
SILVA, Fernando. Listas, Pilhas e Filas. DCC-FCUP, 
s.d. Disponível em: <https://www.dcc.fc.up.pt/~fds/aulas/
EDados/1314/Apontamentos/listas-1x2.pdf>. Acesso em: 
02 ago. 2018.
SONG, Siang Wun. Listas Lineares. USP, 2008. 
Disponível em: <https://www.ime.usp.br/~song/mac5710/
slides/02linear.pdf>. Acesso em: 30 jul. 2018.
SOUZA, Jairo Francisco de. Árvores. UFJF, 2009. 
Disponível em: <http://www.ufjf.br/jairo_souza/
files/2009/12/EDI-06.ED_.Arvores.pdf>. Acesso em: 14 
set. 2018.
SOUZA, Jairo Francisco de. Árvores AVL. UFJF, 
2009. Disponível em: <http://www.ufjf.br/jairo_souza/
files/2009/12/5-Indexa%C3%A7%C3%A3o-Arvore-AVL.
pdf>. Acesso em: 17 set. 2018.
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. 
Estruturas de dados e seus algoritmos. 2. ed. Rio de Janeiro: 
LTC, 1994.
TENENBAUM, Aaron M.; AUGENSTEIN, Moshe J.; 
LANGSAN, Yedidyah. et al. Estruturas de dados usando C. São 
Paulo: Pearson Makron Books; São Paulo: Makron Books do 
Brasil; São Paulo: McGraw-Hill, 2013.
ZIVIANI, Nivio. Projeto de algoritmos: com implementação 
em PASCAL e C. 3. ed. São Paulo: Cengage Learning, 2011.
Minhas anotações
57