Organização de Arquivos - Organizando Arquivos para Desempenho (Parte 1)

Prévia do material em texto

Introduc¸a˜o a` Organizac¸a˜o de Arquivos: Aula 9
Departamento de Cieˆncia da Computac¸a˜o
Instituto de Cieˆncias Exatas
Universidade de Bras´ılia
1 / 51
Suma´rio
Organizando Arquivos para Desempenho
1 To´picos em Teoria da Informac¸a˜o
2 Compressa˜o de dados
3 Recuperando espac¸o em disco
4 Uma introduc¸a˜o a ordenac¸a˜o interna e busca bina´ria.
5 Ordenac¸a˜o de chaves (Keysorting ou Tag Sort).
6 Ordenac¸a˜o de arquivos grandes.
2 / 51
Introduc¸a˜o
Sistema Operacional
O Sistema Operacional e´ um programa resposa´vel pelo gerenciamento dos recursos
de um sistema de computac¸a˜o para seus mu´ltiplos usua´rios.
Uma das func¸o˜es e´ formar uma interface entre os usua´rios e os dispositivos de
memo´ria secunda´ria.
Ele deve facilitar o mapeamento da visa˜o lo´gica do usua´rio na visa˜o f´ısica dos
dispositivos de armazenamento.
Com relac¸a˜o aos meios de armazenamento, as func¸o˜es do SO podem ser de baixo
n´ıvel ou de alto n´ıvel.
3 / 51
Introduc¸a˜o
Sistema Operacional
As func¸o˜es de baixo n´ıvel referem-se a` transfereˆncia de blocos de bytes entre a memo´ria
principal e a secunda´ria, compreendendo:
Gerenciamento da memo´ria cache;
Programac¸a˜o de Transfereˆncia de dados;
Codificac¸a˜o e Decodificac¸a˜o dos dados;
Codificac¸a˜o/Decodificac¸a˜o envolvem: Detecc¸a˜o e correc¸a˜o de erros, criptografia,
compressa˜o de dados.
4 / 51
Introduc¸a˜o
Sistema Operacional: Func¸o˜es de Alto N´ıvel
As func¸o˜es de alto n´ıvel incluem:
Estrutura do sistema de arquivos;
Seguranc¸a (gerenciamento de usua´rios);
Integridade;
Alocac¸a˜o de espac¸o.
5 / 51
Introduc¸a˜o
Motivac¸a˜o
Vamos estudar algumas func¸o˜es do SO relacionas ao acesso a` memo´ria secunda´ria.
Pore´m, nosso objetivo na˜o e´ analisar o problema desde o ponto de vista de um SO e
sim da organizac¸a˜o de arquivos.
Logo, alguns conceitos sera˜o somente introduzidos rapidamente, e outros sera˜o mais
detalhados. Veremos formas de organizar ou mesmo reorganizar arquivos, visando
melhorar desempenho, usando as te´cnicas de:
Compressa˜o de dados (como tornar arquivos menores);
Recuperac¸a˜o de espac¸os na˜o usados : gerados no processo de eliminar ou atualizar
registros no arquivo;
Reorganizac¸a˜o de arquivos:
Introduc¸a˜o a “Internal Sorting” e busca bina´ria,
Criando estruturas externas (´ındices) atrave´s das quais podemos acessar um arquivo.
Um me´todo melhor de ordenac¸a˜o: KeySorting (Tag Sort)
6 / 51
Func¸o˜es de Baixo N´ıvel
Caching
Historicamente os processadores sa˜o mais ra´pidos que a memo´ria. Logo, um
processador pode ficar ocioso por alguns ciclos enquanto o dado e´ lido da memo´ria.
Na verdade e´ poss´ıvel fazer memo´rias mais ra´pidas, pore´m isso significa um maior
custo de fabricac¸a˜o e venda.
Uma soluc¸a˜o adotada pelos fabricantes e combinar memo´ria mais barata (lenta) com
memo´ria mais cara (ra´pida). Normalmente, voceˆ tem uma maior quantidade de
memo´ria lenta do que ra´pida.
A RAM e´ feita com a tecnologia mais barata, enquanto o memo´ria cache do
computador e´ feita com a memo´ria mais cara
7 / 51
Func¸o˜es de Baixo N´ıvel
Caching
A ideia geral e´ que, quando uma palavra e´ referenciada, ela e´ trazida da RAM para a
cache, de modo que, da pro´xima vez que for utilizada pode ser acessada diretamente
da cache.
Logo, se a palavra e´ requerida k vezes, seria acessada uma vez da RAM e k − 1
vezes da cache.
Se ‘c’ e´ o tempo me´dio de acesso a cache, ‘m’ e´ o tempo me´dio de acesso a RAM, e
‘h’ e´ a taxa de acerto (no exemplo anterior seria k−1
k
). Enta˜o o tempo de acesso a
memo´ria e´:
Tempo me´dio de acesso := c+ (1− h) ·m
8 / 51
Func¸o˜es de Baixo N´ıvel
Programac¸a˜o de Transfereˆncia
Nas operac¸o˜es de leitura e gravac¸a˜o, observa-se que o movimento do brac¸o das
cabec¸as representa a parcela de tempo mais significativa.
Um controlador de dispositivos inteligente organiza uma se´rie de transfereˆncias de tal
forma de minimizar a perda de tempo recorrente ao movimento do brac¸o (seeking).
9 / 51
Func¸o˜es de Baixo N´ıvel
Codificac¸a˜o de Dados
Transformac¸a˜o de um certo conjunto de s´ımbolos em um outro conjunto de s´ımbolos.
10 / 51
Codificac¸a˜o de Dados
Codificac¸a˜o de Dados
A transformac¸a˜o (codificac¸a˜o) e´ feita para atingir um certo objetivo:
Compressa˜o
Representac¸a˜o Eficiente, tambe´m chamado de Codificac¸a˜o de Fonte
Tambe´m chamada como: Codificac¸a˜o de Fonte
Seguranc¸a dos aˆmbitos de Protec¸a˜o e Autenticac¸a˜o, tambe´m chamado de
Criptografia
Robustez
Canal na˜o ideal (erro de transmissa˜o), tambe´m chamado de Codificac¸a˜o de Canal
11 / 51
Codificac¸a˜o de Dados
Observac¸a˜o
E´ importante notar que cada um deste objetivos normalmente envolve requisitos
contra´rios aos outros:
O principal objetivo dos algoritmos de compressa˜o e´ a reduc¸a˜o do comprimento da
mensagem (codificac¸a˜o de fonte).
Por outro lado, os co´digos de controle de erros implicam muitas vezes o aumento do
comprimento das mensagens (codificac¸a˜o de canal).
Dados que tenham sido previamente cifrados sa˜o geralmente muito dif´ıceis de
comprimir.
12 / 51
Codificac¸a˜o de Dados: Robustez
Robustez
Detecc¸a˜o e Correc¸a˜o de Erros
A natureza f´ısica do armazenamento pode ocasionar corrupc¸a˜o de dados.
Para detecc¸a˜o de erro, deve-se incluir redundaˆncia na informac¸a˜o.
A ideia principal e´ utilizar uma certa quantidade de bits de controle para um
determinado bloco de informac¸a˜o. Os bits de controle devem ser gerados a partir
dos bits que representam a informac¸a˜o e gravados junto com o bloco
Ao ler a informac¸a˜o gera-se novamente os bits de controle, se na˜o conferem com os
bits gravados, enta˜o a informac¸a˜o foi corrompida.
Os bits de controle podem ajudar tambe´m na correc¸a˜o de erros.
13 / 51
Codificac¸a˜o de Dados: Criptografia
Criptografia
A criptografia e´ utilizada para transformar a informac¸a˜o de forma que se torne
ileg´ıvel aos usua´rios na˜o autorizados.
Existem diversas formas de criptografar uma mensagem. A maioria e´ baseada no uso
de uma chave criptogra´fica.
14 / 51
Codificac¸a˜o de Dados: Compressa˜o
Compressa˜o
Compressa˜o de dados e´ o processo de codificar uma determinada informac¸a˜o utilizando
uma menor representac¸a˜o. Os dois principais benef´ıcios trazidos pela compressa˜o de
dados sa˜o:
Capacidade de armazenamento de informac¸o˜es crescente: o uso de compressa˜o de
dados pode aumentar significativamente a capacidade de armazenamento do
sistema. “Um sinal comprimido ocupa menos espac¸o”.
Transmissa˜o de dados crescente: informac¸o˜es digitais podem ser comprimidas antes
de serem transmitidas de um mo´dulo para outro. “Um sinal comprimido requer
menor largura de banda”.
15 / 51
Codificac¸a˜o de Dados: Conceitos Ba´sicos
Entropia
Na Termodinaˆmica: Medida da desorganizac¸a˜o de um sistema.
Na Mecaˆnica Estat´ıstica: Medida da quantidade de incerteza que esta presente num
sistema.
Na Teoria da Informac¸a˜o: Medida da incerteza associada a uma varia´vel aleato´ria.
Entropia de Shannon
Quantifica a informac¸a˜o contida numa mensagem, normalmente na unidade de Bits.
16 / 51
Codificac¸a˜o de Dados: Conceitos Ba´sicos
Entropia
A entropia de uma varia´vel aleato´ria X com valores poss´ıveis {x1, . . . , xn} e´ definida
como:
H(X) := E(I(X))
Onde E() e´ o valor esperado e I() e´ a informac¸a˜o contida em X, ou
auto-informac¸a˜o.
Se I(X) e´ tambe´m uma varia´vel aleato´ria e´ p representa a func¸a˜o de massa de
probabilidade, podemos escrever H(X) como:
H(X) :=
n∑
i=1
p(xi)I(xi) = −
n∑
i=1
p(xi) logb p(xi)
Onde b e´ normalmente 2 (base bina´ria)
17 / 51
Codificac¸a˜o de Dados: Conceitos Ba´sicos
Exemplo
Consideremoso lanc¸amento de Moeda (Cara ou Coroa).
Se a Moeda e´ justa enta˜o a probabilidade de cada um dos dois eventos acontecer e´
1
2
.
Portanto a entropia e´ H(X) = 1.
E´ necessa´rio um bit para transmitir a informac¸a˜o a cada lanc¸amento.
Figura: Probabilidade Vs Entropia
18 / 51
Compressa˜o de Dados
Compressa˜o de Dados
Existem dois tipos de compressa˜o:
Sem perdas (Lossless)
Com perdas (Lossy)
A compressa˜o sem perdas, e´ aquela que destina-se a retirar somente a redundaˆncia
nos dados.
Em 1948 o pesquisador Claude E. Shannon publicou um artigo: “A Mathematical
Theory of Communication”, que demostrava que a compressa˜o sem perdas tem um
limite (denotada por H e´ definida como Entropia)
Teorema (Teorema de Codificac¸a˜o de Fonte)
E´ poss´ıvel comprimir um sinal sem perdas numa taxa NA˜O inferior a entropia do sinal.
19 / 51
Compressa˜o de Dados
Lossless Vs Lossy
A compressa˜o com perdas, e aquele que destina-se a retirar a redundaˆncia nos
dados, e a irrelevaˆncia para um determinada aplicac¸a˜o.
Shannon tambe´m desenvolveu a teoria da compressa˜o com perdas. Conhecida como
a teoria da Taxa-Distorc¸a˜o (rate-distortion)
Na compressa˜o com perdas, o sinal reconstru´ıdo na˜o e´ exatamente igual ao sinal
original. Existe uma distorc¸a˜o, D, que e´ tolerada para um determinada aplicac¸a˜o.
Vamos estudar somente algumas te´cnicas de compressa˜o de dados SEM PERDAS,
ja´ que dentro da organizac¸a˜o de arquivos o objetivo e poder recuperar a informac¸a˜o
dos dados completamente.
20 / 51
Compressa˜o de Dados
Compressa˜o de Dados por Notac¸a˜o Diferente
Considere o registro constitu´ıdo dos campos abaixo, relativos a aluno:
< matr´ıcula >< nome >< enderec¸o >< uf >< curso >< opc¸a˜o >< departamento >
< uf > e´ usualmente representado por uma sigla.
Ao inve´s de usar dois bytes: DF, GO, MG, RJ, etc, pode-se usar um byte para
representar os 26 Estados da Federac¸a˜o na forma bina´ria.
< curso >< opc¸a˜o >< departamento >
Pode-se usar co´digos correspondentes a essas entidades, em bina´rio (mais
econoˆmico) ou uma string nume´rica.
Reduc¸a˜o de Redundaˆncia
Essa notac¸a˜o mais compacta, economiza bytes que eram redundantes para representar a
mesma informac¸a˜o.
21 / 51
Compressa˜o de Dados
Tabela: Tabela Geral
Matr´ıcula Nome Curso Departamento
02/35879 Maria Vito´ria Bacharelado em Matema´tica 117-0 Departamento de Matema´tica
MAT
03/01329 Pascual Monton Bacharelado em F´ısica 116-8 Departamento de F´ısica FIS
04/02556 Platina Constru-
tiva
Engenharia Ele´trica 115-3 Departamento de Engenharia
Ele´trica ENE
04/03714 Gertrudes Sina-
goga
Bacharelado em Matema´tica 117-0 Departamento de Matema´tica
MAT
04/03881 Miracema de Deus Engenharia Ele´trica 115-3 Departamento de Engenharia
Ele´trica ENE
Tabela: Tabela dos Departamentos
ENE Dept de Engenharia Ele´trica
FIS Dept de F´ısica
MAT Dept de Matema´tica
Tabela: Tabela de Cursos
115-3 Engenharia Ele´trica
116-8 Bacharelado em F´ısica
117-0 Bacharelado em Matema´tica
22 / 51
Compressa˜o de Dados
Desvantagens
Uso de co´digos bina´rios torna o arquivo menos leg´ıvel para humanos.
Ha´ um custo associado a codificac¸a˜o e decodificac¸a˜o das entidades:
Aumenta a Complexidade do Software.
Devem ser programados mo´dulos para codificac¸a˜o e decodificac¸a˜o de cada entidade
codificada:
Criando arquivos e tabelas em memo´ria para tais entidades.
Inserindo tais mo´dulos nos programas que cotizam os arquivos com entidades
codificadas.
Existe o tempo de codificar e decodificar
Torna o processo mais lento
23 / 51
Compressa˜o de Dados
Vale a pena usar esta te´cnica?
Depende da aplicac¸a˜o!
Quando na˜o usar compressa˜o
Em arquivos pequenos (em certos casos);
Arquivos com muitos programas diferentes tendo acesso a ele;
Aplicac¸o˜es sem capacidade de lidar com bina´rios (ex. editor de texto);
Quando usar compressa˜o
Em arquivos grandes (milhares de registros);
Em arquivos cujo poucos programas tenham acesso;
Se a conversa˜o (codificac¸a˜o/decoficac¸a˜o) nestas compresso˜es for simples.
Nestes casos, a economia de acesso compensa os custos de compressa˜o.
24 / 51
Compressa˜o de Dados
Custo Vs Benef´ıcio
Devemos considerar:
Tempo de codificac¸a˜o e decodificac¸a˜o;
Ganho de compressa˜o;
Nu´mero de acesso ao arquivo;
Exemplo
Se um arquivo for pequeno e acessado frequ¨entemente, o custo sera´ maior que o
benef´ıcio.
25 / 51
Compressa˜o de Dados
Supressa˜o de Sequeˆncias Repetidas — Run Length Coding
Indicada para arquivos nos quais sequeˆncias do mesmo byte sa˜o frequentes.
O procedimento normalmente e´ utilizar um co´digo de escape:
Supondo-se a ocorreˆncia de N repetic¸o˜es do caractere k, pode-se substituir essa
ocorrencia por 3 bytes:
< Co´gido de escape >< N >< k >
Exemplo: Utilizac¸a˜o em um Arquivo de Texto
GOOOOOOOL → G$7OL
26 / 51
Compressa˜o de Dados
Supressa˜o de Sequeˆncias Repetidas — Run Length Coding
Pode-se tambe´m definir um nu´mero minimo de repetic¸o˜es.
Exemplo: Utilizando repetic¸a˜o minima de 3 em um arquivo bina´rio:
Sequeˆncia de bytes (em hexadecimal):
22 23 24 24 24 24 24 24 24 24 24 24 25 25 26 26 26 26 26 26 26 26 24 24
Sequeˆncia compactada (em hexadecimal):
22 23 FF 0A 24 25 25 FF 08 26 24 24
24 bytes sa˜o reduzidos a 12 bytes.
Esta te´cnica so´ e´ eficiente se existe varias sequeˆncias de caracteres repetidos.
27 / 51
Compressa˜o de Dados
Co´digos de Comprimento Varia´vel
Os co´digos com comprimento varia´vel sa˜o aqueles que os s´ımbolos codificados
podem ter diferente tamanho (em bits);
Os co´digos de comprimento varia´vel podem ser utilizados na compressa˜o sem perda;
Os co´digos devem ser unicamente decodifica´veis, ou seja um conjunto de s´ımbolos
codificados deve somente poder ser interpretado de um u´nica forma. Uma forma de
garantir isso e´ que nenhum simbolo codificado seja o prefixo de outro;
Os co´digos podem ser instantaneamente codifica´veis, ou seja um simbolo pode ser
codificado assim que e´ recebido. Pore´m, os co´digos com comprimento varia´vel pode
na˜o ser instantaˆneos, ou seja, TODA a mensagem necessita ser codificada para
podermos decodificar.
28 / 51
Compressa˜o de Dados
Co´digos de Comprimento Varia´vel
Co´digos de comprimento varia´vel, em geral, sa˜o baseados no princ´ıpio de que alguns
valores ocorrem mais frequentemente do que outros, portanto, os co´digos para estes
valores devem ocupar o menor espac¸o.
Ou seja, as letras (s´ımbolos emitidos pela fonte) com maior probabilidade de
ocorreˆncia sa˜o codificadas com s´ımbolos menores e as letras com menor
probabilidade de ocorreˆncia sa˜o codificadas com s´ımbolos maiores.
29 / 51
Compressa˜o de Dados
Co´digos de Comprimento Varia´vel: Co´digo Morse
O mais antigo co´digo de comprimento varia´vel;
Utiliza apenas dois s´ımbolos no esquema de codificac¸a˜o: ponto (.) e trac¸o (-);
As duas letras mais utilizadas do alfabeto ingleˆs (“e” e “t”) sa˜o codificadas com um
ponto e um trac¸o, respectivamente.
As outras letras do alfabeto recebem dois ou mais s´ımbolos, sendo que as letras
mais utilizadas recebem menos s´ımbolos do que as menos utilizadas.
30 / 51
Compressa˜o de Dados: Co´digo Morse
International Morse Code
1. A dash is equal to three dots.
2. The space between parts of the same letter is equal to one dot.
3. The space between two letters is equal to three dots.
4. The space between two words is equal to seven dots.
UVWXYZ
ABCDEFGHIJKLMNO
QPRST
1234567890
Figura: Co´digo Morse. Figura retirada de http://en.wikipedia.org/wiki/Morse_code
31 / 51
Compressa˜o de Dados
Co´digos de Comprimento Varia´vel: Co´digo de Huffman
Te´cnica desenvolvida por David Huffman como um trabalho de aula do primeirocurso de teoria da informac¸a˜o ministrado por Robert Fano no MIT em 1951.
E´ uma das te´cnicas mais utilizada para co´digos de comprimento varia´vel.
O co´digo de Huffman e´ o´timo, ou seja, o tamanho me´dio dos s´ımbolos codificados e´
igual a entropia do sinal, se as probabilidades de ocorreˆncia das letras sa˜o potencias
de dois (2−n).
32 / 51
Compressa˜o de Dados
Co´digos de Comprimento Varia´vel: Co´digo de Huffman
Vamos criar um co´digo de Huffman para uma fonte que gera letras do alfabeto
{a, b, c, d, e} com probabilidades P (a) = P (c) = 0.2, P (b) = 0.4,
P (d) = P (e) = 0.1.
A entropia desta fonte e´ 2.122 bits por simbolo.
Para fazer o co´digo de Huffman primeiro ordenamos as letras em forma decrescente
de probabilidade.
33 / 51
Compressa˜o de Dados
Letra Probabilidade Co´digo
b 0.4 c(b)
a 0.2 c(a)
c 0.2 c(c)
d 0.1 c(d)
e 0.1 c(e)
Tabela: Distribuic¸a˜o de probabilidade dos s´ımbolos
Os dois s´ımbolos menos prova´veis sa˜o ‘d’ e ‘e’. Logo, combinamos as duas letras numa
nova α1. E colocamos o co´digo para as letras combinadas da seguinte forma:
c(d) = c(α1).0
c(e) = c(α1).1
Onde ‘.’ significa concatenac¸a˜o.
34 / 51
Compressa˜o de Dados
Letra Probabilidade Co´digo
b 0.4 c(b)
a 0.2 c(a)
c 0.2 c(c)
α1 0.2 c(α1)
Agora, os s´ımbolos menos prova´veis sa˜o ‘c’ e ‘α1’. Juntamos e criamos o co´digo:
c(c) = c(α2).0
c(α1) = c(α2).1
Letra Probabilidade Co´digo
b 0.4 c(b)
α2 0.4 c(α2)
a 0.2 c(c)
35 / 51
Compressa˜o de Dados
Fazendo o mesmo racioc´ınio temos:
c(α2) = c(α3).0
c(a) = c(α3).1
Letra Probabilidade Co´digo
α3 0.6 c(α3)
b 0.4 c(b)
Logo:
c(α3) = 0
c(b) = 1
36 / 51
Compressa˜o de Dados
Com o co´digo de α3 obtemos os co´digos restantes:
c(a) = c(α3).1 = 01
c(α2) = c(α3).0 = 00
c(c) = c(α2).0 = 000
c(α1) = c(α2).1 = 001
c(d) = c(α1).0 = 0010
c(d) = c(α1).1 = 0011
37 / 51
Compressa˜o de Dados
Logo, temos a seguinte tabela de co´digos Huffman:
Letra Probabilidade Co´digo
b 0.4 1
a 0.2 01
c 0.2 000
d 0.1 0010
e 0.1 0011
Tabela: Co´digo de Huffman
Note que:
Nenhum co´digo e´ prefixo do outro e que os dois u´ltimos s´ımbolos possuem um
co´digo do mesmo valor;
O tamanho me´dio deste co´digo e´:
l := 0.4 · 1 + 0.2 · 2 + 0.2 · 3 + 0.1 · 4 + 0.1 · 4 = 2.2 bits/s´ımbolo
Assim a redundaˆncia deste co´digo e´ 2.2–2.122 = 0.078 bits/s´ımbolo
38 / 51
Compressa˜o de Dados
Na˜o Unicidade do Co´digo de Huffman
A principio para uma mesma fonte com probabilidades conhecidas, pode ser gerado
va´rios co´digos de Huffman, isto e´, o co´digo na˜o e´ u´nico.
Por exemplo, para a fonte anterior podemos gerar o seguinte co´digo.
Letra Probabilidade Co´digo
b 0.4 00
a 0.2 10
c 0.2 11
d 0.1 010
e 0.1 011
Tabela: Co´digo de Huffman
39 / 51
Compressa˜o de Dados
Na˜o Unicidade do Co´digo de Huffman
O co´digo anterior foi gerado colando sempre as letras combinadas o mais alto
poss´ıvel na lista.
O tamanho me´dio deste novo co´digo e´:
l = 0.4 · 2 + 0.2 · 2 + 0.2 · 2 + 0.1 · 3 + 0.1 · 3 = 2.2 bits/s´ımbolo
Ambos co´digos tem o mesma taxa
Pore´m, o novo co´digo tem um variaˆncia menor.
E´ comum que durante a transmissa˜o de arquivos se utiliza um buffer de tamanho
fixo. Logo, o co´digo com a menor variaˆncia e´ melhor.
40 / 51
Compressa˜o de Dados
Construc¸a˜o do Co´digo de Huffman
Podemos Construir o co´digo de Huffman atrave´s de uma estrutura de a´rvore.
A a´rvore de Huffman possui as seguintes propriedades:
Cada no´ interno tem 2 filhos.
As frequeˆncias menores esta˜o mais longe da raiz.
As duas frequeˆncias menores sa˜o no´s irma˜os.
O nu´mero de bits necessa´rios para codificar um arquivo e´ dado por:
B(T ) :=
∑
f(c) · dT (c)
Onde:
B(T ) e´ nu´mero de bits necessa´rio para codificar o arquivo usando a a´rvore T ;
f(c) e´ frequeˆncia do caracter ‘c’;
dT (c) e´ comprimento do co´digo para o caracter ‘c’;
0
0
0
01 1
1
1
b
d e
a c
Letra Probabilidade Co´digo
b 0.4 00
a 0.2 10
c 0.2 11
d 0.1 010
e 0.1 011
41 / 51
Compressa˜o de Dados
Algoritmo 1 Construc¸a˜o da A´rvore e do Co´digo de Huffman
1: Compute a frequeˆncia relativa (fr) de cada valor no arquivo crie uma tabela valor vs
frequeˆncia (a frequeˆncia relativa sera´ considerada como a probabilidade da letra)
2: Cada valor nesta tabela sera´ um no´ folha na a´rvore
3: while Restar No´s Desconexos do
4: Defina um no´ pai unindo dois no´s filhos, cuja soma das fr seja a menor poss´ıvel
5: Calcule a fr deste pai como a soma das fr dos seus filhos
6: Atribua o bit 1 para o primeiro filho e 0 para o segundo
7: end while
8: Obtenha o co´digo de cada valor pegando a sequeˆncia de bits atribu´ıda aos no´s, indo
da raiz ate´ a folha que corresponde ao valor
9: Gere a tabela valor Vs co´digo
42 / 51
Compressa˜o de Dados
Exemplo
Suponha que o arquivo contenha os seguintes caracteres: “i am sammy”.
i:1 s:1 y:1 a:2 m:3\b:2
Figura: Suba´rvores iniciais
Unimos as duas suba´rvores de menor peso
i:1 s:1 y:1 a:2 \b:2 m:3
2
Figura: Unia˜o das suba´rvores de menor peso
43 / 51
Compressa˜o de Dados
i:1 s:1 y:1a:2 \b:2 m:3
2 3
Figura: Unia˜o das suba´rvores de menor peso
44 / 51
Compressa˜o de Dados
i:1 s:1 y:1a:2 \b:2 m:3
2 3
4
Figura: Unia˜o das suba´rvores de menor peso
i:1 s:1 y:1a:2 \b:2 m:3
2 3
4 6
Figura: Unia˜o das suba´rvores de menor peso
45 / 51
Compressa˜o de Dados
i:1 s:1 y:1a:2 \b:2 m:3
2 3
4 6
10
0
0
0 0
0
1
1
1
1
Figura: A´rvore de Huffman
Letra Frequeˆncia Co´digo
m 3 11
a 2 01
\b 1 101
y 1 100
i 1 000
s 1 001
Tabela: Co´digo de Huffman
46 / 51
Compressa˜o de Dados
Algoritmo 2 Comprimindo um arquivo
1: while ¬feof(arquivo ba´sico a ser compactado) do
2: Para cada byte lido, acesse a tabela valor Vs co´digo e recupere o co´digo dele
3: Transfira o co´digo para a sequeˆncia de bits de sa´ıda
4: Soma 1 ao contador de bytes codificados
5: Se o buffer de sa´ıda encheu grave-o no arquivo compactado de sa´ıda.
6: end while
7: Grave no cabec¸alho valor do contador de bytes codificados
8: Grave no cabec¸alho a tabela de frequeˆncia dos bytes ou a a´rvore gerada
9: Grave no cabec¸alho a tabela de valor Vs co´digo
10: Feche os arquivos
Nota
Na verdade so´ e´ necessa´rio mandar a tabela (valor Vs co´digo). Mandar a a´rvore facilita a
implementac¸a˜o do algoritmo de decodificac¸a˜o pore´m ocupa mais espac¸o!
47 / 51
Compressa˜o de Dados
Algoritmo 3 Descomprimindo um Arquivo
1: Leia o cabec¸alho do arquivo compactado
2: Defina o contador de bytes codificados
3: Defina a a´rvore de Huffman
4: while ¬feof(arquivo-compactado) ∧ Contador de bytes codificados > 0 do
5: Leia o arquivo compactado
6: Enquanto ha´ bits lidos
7: Va´ pegando os bits e percorrendo a a´rvore da raiz para as folhas, em func¸a˜o do
valor dos bits encontrados. Quando chegar ao no´ folha voceˆ tem o valor (byte)
correspondente ao co´digo
8: Transfira o byte para o arquivo descompactado
9: Decremente o contador de bytes codificados
10: end while
48 / 51
Compressa˜o de Dados
Codificac¸a˜o Aritme´tica
Os co´digos de Huffman sa˜o o´timos somente quando a probabilidade de ocorreˆncia
das letras e´ poteˆncia de dois.
Ale´m disso, quando existe uma letra com probabilidade maior que 0.5, o melhor que
o co´digo de Huffman consegue e´ representar essa letra com um bit.
A codificac¸a˜o aritme´tica e´ uma alterativa, a codificac¸a˜o de Huffman. A codificac¸a˜o
aritme´tica converte uma sequeˆncia de s´ımbolos em um u´nico co´digo, tendo o
potencial de chegar mais perto da entropia.
Possui uma implementac¸a˜o mais dif´ıcil.
Pesquisa
Pesquise sobre codificac¸a˜o aritme´tica.
49 / 51
Compressa˜o de Dados
Compressa˜o no Unix
Oscomandos pack e unpack do Unix utilizam o Co´digo de Huffman.
Atingem uma reduc¸a˜o de 25% a 40% em arquivos tipo texto.
Entretanto, na˜o se obte´m resultados ta˜o bons em arquivos do tipo bina´rio, uma vez
que estes possuem uma distribuic¸a˜o mais uniforme dos valores.
50 / 51
Pro´xima Aula
Pro´xima Aula
Organizando Arquivos para Desempenho (continuac¸a˜o).
51 / 51