UNIVERSIDADE VILA VELHA
CURSO DE CIÊNCIA DA COMPUTAÇÃO
LUCAS GALON ARRIGONI
COMPACTAÇÃO SEM PERDA PELO MÉTODO
DE HUFFMAN ASSOCIADO À
TRANSFORMADA DE WAVELET
VILA VELHA
Novembro/2012
LUCAS GALON ARRIGONI
COMPACTAÇÃO SEM PERDA PELO MÉTODO
DE HUFFMAN ASSOCIADO À
TRANSFORMADA DE WAVELET
Trabalho de Conclusão de Curso apresentado a Universidade Vila Velha como requisito parcial para a obtenção do grau de
Bacharel em Ciência da Computação.
Orientador: Marcello Novas de Amorim
VILA VELHA
Novembro/2012
LUCAS GALON ARRIGONI
COMPACTAÇÃO SEM PERDA PELO MÉTODO
DE HUFFMAN ASSOCIADO À
TRANSFORMADA DE WAVELET
BANCA EXAMINADORA
Prof. Msc. Marcello Novas de
Amorim
Universidade Vila Velha
Orientador
Prof. Msc. Alessandro
Universidade Vila Velha
Prof. Msc. Hudson Ramos
Universidade Vila Velha
Trabalho de Conclusão de Curso
aprovado
bro/2012.
em
27/11/Novem-
Autorizo que a UVV, sem ônus, promova a publicação de minha monografia em
página própria na Internet ou outro meio de divulgação de trabalho científico.
ASSINATURAS
Prof. Msc. Marcello Novas de
Amorim
Universidade Vila Velha
Orientador
Lucas Galon Arrigoni
Universidade Vila Velha
27/11/2012
“Onde não falta vontade existe sempre um caminho”.
J. R. R. Tolkien
LISTA DE TABELAS
1
Conjunto binário da tabela ASCII por codificação . . . . . . . . . . . . .
30
2
Codificação inicial de Shannon Fano . . . . . . . . . . . . . . . . . . . .
31
3
Codificação intermediária de Shannon Fano . . . . . . . . . . . . . . . .
31
4
Codificação final de Shannon Fano . . . . . . . . . . . . . . . . . . . . .
31
5
Frequência e o código original dos símbolo . . . . . . . . . . . . . . . .
33
6
Frequência e o código codificado dos símbolo . . . . . . . . . . . . . . .
34
7
Decomposição em coeficientes de aproximação e detalhes. . . . . . . .
38
8
Tabela de codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
9
Resuldos referêntes aos arquivos de teste . . . . . . . . . . . . . . . . .
67
LISTA DE FIGURAS
1
Lista linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2
Representação da lista contínua . . . . . . . . . . . . . . . . . . . . . .
16
3
Estrutura de um nó de uma lista encadeada, onde “Info” é o campo de
informação e “Prox” aponta para o próximo nó da lista . . . . . . . . . .
16
4
Lista simplesmente encadeada . . . . . . . . . . . . . . . . . . . . . . .
17
5
Lista duplamente encadeada . . . . . . . . . . . . . . . . . . . . . . . .
17
6
Lista simplesmente encadeada circular . . . . . . . . . . . . . . . . . .
17
7
Lista duplamente encadeada circular . . . . . . . . . . . . . . . . . . . .
18
8
Esquema completo de uma árvore . . . . . . . . . . . . . . . . . . . . .
19
9
Representação de uma árvore binária . . . . . . . . . . . . . . . . . . .
20
10
Esquema de codificação e decodificação . . . . . . . . . . . . . . . . .
23
11
Tipos de compactação . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
12
Tabela ASCII caracteres não imprimíveis . . . . . . . . . . . . . . . . .
27
13
Técnica run-length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
14
Processo de compressão Run-Length . . . . . . . . . . . . . . . . . . .
29
15
Processo de codificação de Huffman - passo a passo . . . . . . . . . .
33
16
Sequência dos processos . . . . . . . . . . . . . . . . . . . . . . . . . .
40
17
Processo da codificação da Transformada Wavelet de Haar . . . . . . .
40
18
Árvore de codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
19
Transformação dos dados . . . . . . . . . . . . . . . . . . . . . . . . . .
41
20
Processo da decodificação da Transformada Wavelet de Haar . . . . .
42
21
Fluxo do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
22
Fluxo de compactação e descompactação . . . . . . . . . . . . . . . . .
44
23
Fluxo do pré-processamento . . . . . . . . . . . . . . . . . . . . . . . .
45
24
Código do pré-processamento . . . . . . . . . . . . . . . . . . . . . . .
45
25
Fluxograma da Transformada Wavelet de Haar . . . . . . . . . . . . . .
46
26
Código da codificação da Transformada Wavelet de Haar . . . . . . . .
47
27
Estrutura do nó.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
28
Caso dos símbolos repetidos. . . . . . . . . . . . . . . . . . . . . . . . .
49
29
Caso dos símbolos diferentes. . . . . . . . . . . . . . . . . . . . . . . .
49
30
Fluxograma da criação da lista de símbolos.
. . . . . . . . . . . . . . .
49
31
Código da criação da lista de símbolos. . . . . . . . . . . . . . . . . . .
50
32
Criação da árvore. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
33
Fluxograma da criação da árvore. . . . . . . . . . . . . . . . . . . . . .
52
34
Código da criação da árvore. . . . . . . . . . . . . . . . . . . . . . . . .
53
35
Fluxograma da criação da tabela codificada. . . . . . . . . . . . . . . .
54
36
Código da criação da tabela codificada. . . . . . . . . . . . . . . . . . .
55
37
Fluxograma da codificação. . . . . . . . . . . . . . . . . . . . . . . . . .
57
38
Código da codificação. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
39
Fluxograma da reconstrução da tabela codificada. . . . . . . . . . . . .
59
40
Código da reconstrução da tabela codificada. . . . . . . . . . . . . . . .
60
41
Fluxograma da reconstrução da árvore binária de decodificação . . . .
61
42
Código da reconstrução da árvore binária de decodificação, parte 1 . .
62
43
Código da reconstrução da árvore binária de decodificação, parte 2 . .
63
44
Código de decodificação. . . . . . . . . . . . . . . . . . . . . . . . . . .
65
45
Fluxograma da decodificação da Transformada Wavelet de Haar. . . . .
66
46
Código da decodificação da Transformada Wavelet de Haar. . . . . . .
66
SUMÁRIO
RESUMO
ABSTRACT
1 INTRODUÇÃO
12
1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.2 Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.3 Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.4 Objetivos específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2 ESTRUTURA DE DADOS
15
2.1 Listas Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2 Árvore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.2.1 Árvore Binária . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3 COMPACTADORES
21
3.1 Histórico da Compactação . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.2 Compactação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.3 Tipos de Compactação . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.4 Técnicas de Compressão . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.4.1 Técnicas com Caracteres Indicadores . . . . . . . . . . . . . . .
25
3.4.2 Compressão Estatística . . . . . . . . . . . . . . . . . . . . . . .
30
4 A Transformada Wavelet
36
4.1 Surgimento das Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4.2 Transformada Wavelet de Haar . . . . . . . . . . . . . . . . . . . . . . .
37
5 ALGORITMO PROPOSTO
39
5.1 Prova de Integridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
5.2 Características do Algoritmo
. . . . . . . . . . . . . . . . . . . . . . . .
43
5.3 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
5.3.1 Compactação . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
5.3.2 Descompactação . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6 RESULTADOS, DISCUSSÃO e CONCLUSÕES
67
6.1 Resultados e Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
6.2 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
7 CONCLUSÃO
69
8 REFERÊNCIAS
70
RESUMO
A compressão de dados se revela essencial para o armazenamento e transmissão.
Há métodos que, embora atinjam altas taxas de compressão, em seu procedimento reverso (descompactação), podem fazer com que parte dos dados presentes no arquivo
original se percam. Assim o objetivo desse estudo consiste na criação de um compactador de dados sem perda, a partir da verificação da viabilidade do uso da Transformada Wavelet associadas a codificação de Huffman; possibilitando a compressão
e descompressão do arquivo, mantendo a integridade dos dados sem prejudicar a sua
utilização pelo usuário.
Palavras-Chave
Compactação de dados, Wavelet, Huffman
ABSTRACT
Data compression is essential for storage and transmission. There are methods
that, although achieve high compression ratios, in its reverse procedure (decompression) can cause part of the data present in the original file are lost. Thus objective this
study is the creation of a compactor without loss of data from the verify the feasibility of
using Wavelet Transform associated with Huffman coding, enabling compression and
decompression of the file, maintaining data integrity without impairing its use by the
user.
Keywords
Compression of data, Wavelet, Huffman
12
1
INTRODUÇÃO
Com o surgimento da internet, a evolução tecnológica cresce substancialmente, e
uma de suas características é a necessidade de obter informações em tempo hábil,
com o mínimo de espaço físico possível.
Desse modo a redução, compressão ou compactação de dados é um recurso
muito utilizado, que permite aumentar consideravelmente a quantidade de dados a
serem gravados em um mesmo espaço físico ou até mesmo reduzir o tempo de transmissão desses dados, já que a velocidade da rede ainda apresenta limitação, como
ligações telefônicas, fax e downloads.
Arquivos digitais como fotos, vídeos, livros e músicas, geram grande volume de dados, tornando-se iminentes às aplicação de técnicas para compactação de dados, que
possibilitem reduzir a quantidade de informações necessárias, tendo como garantia a
exatidão dos dados, facilitando o armazenamento, a transmissão e o processamento
dos dados.
Neste projeto será realizado uma sucinta abordagem sobre as estruturas de dados, relacionadas à codificação, além disso discorrerá uma breve evolução histórica
da codificação. Posteriormente, alguns conceitos relativos a compressão de dados
serão apresentados, especificando conceitos e definições, e incluindo demonstrações
de algumas técnicas.
A abordagem da codificação de Huffman em conjunto com um apêndice da Transformada Wavelet de Haar, terá como objetivo buscar argumentos concretos da relação
entre os mesmos.
Diante disso, estima-se o desenvolvimento de uma análise técnico-científica sobre
os métodos de compressão com a finalidade de apresentar uma proposta de compactação que correlacione os princípios utilizados nesse projeto.
13
1.1
Motivação
Várias pesquisas têm sido desenvolvidos na área de compressão de imagens utilizando métodos baseados em Wavelets1 . Todavia, poucos trabalhos utilizam a Transformada Wavelet sem perda, para arquivo do tipo texto.
Métodos que resultam em perda de informações não são aceitos para arquivos
texto, pois isso pode prejudicar a integridade dos mesmos.
O interesse nesta pesquisa surgiu pela possibilidade de associar a Transformada
Wavelet com a codificação de Huffman para propor uma nova técnica de compactação.
1.2
Justificativa
Atualmente, é fácil se deparar com pessoas, ou organizações que necessitam armazenar ou transferir em seus computadores ou redes, arquivos de grande porte. Entretanto, mesmo que a capacidade de armazenamento e o processamento computacional sejam abundantes, para os recursos já disponíveis, o tempo de transferência e
o espaço fisico requerido para o armazenamento são elevados. Assim, a redução da
associação entre o tempo de transferência e o espaço físico possibilita maior agilidade
na obtenção de informações favorecendo o desempenho técnico. Porém, a totalidade
desses recursos será atingida de maneira integral a partir da ausência de perda de
dados, que resulta na preservação da integridade das informações transmitidas. Com
isso, a implementação de um algoritmo capaz de unir esses fatores por intérmedio de
técnicas associadas, permite ampliar a visão técnica e computacional incentivando o
desenvolvimento de novas pesquisas.
1.3
Objetivo Geral
Criar um compactador de dados sem perda de dados, para compactar arquivos
do tipo texto, de modo que após o procedimento, seja possível retornar aos arquivos
originais sem que ocorream alterações não permitindo a perda de informações durante
o processo de compressão, já que, de acordo com a compactação sem perda, a falta
de um bit em um arquivo binário pode comprometer todo o seu significado.
1 Wavelet
é uma função capaz de representar uma série de dados possibilitando a análise em diferentes escalas de frequência e de tempo. [OLIVEIRA, 2007]
14
1.4
Objetivos específicos
• Promover o estudo da estrutura de dados, das técnicas, métodos e codificações
de compressão de dados.
• Desenvolver um algoritmo de compactação sem perda, que utilize a codificação
de Huffman juntamente com a Transformada de Wavelet.
• Analisar se a compactação reduziu o tamanho do arquivo.
• Verificar se houve perda de dados no processo.
15
2
ESTRUTURA DE DADOS
Este capítulo será aborda uma síntese das principais estruturas de dados que são
inerentes à codificação de Huffman ao qual será utilizada neste projeto.
2.1
Listas Lineares
De acordo com Szwarcfiter (1994), uma estrutura de lista é formada por um conjunto de elementos, os quais se relacionam entre si. Os elementos contidos em uma
lista podem forma a combinações de informações, assim, [ A, 1, C ], por exemplo
representa uma lista de 3 elementos, sendo que os elementos A, 1 e C indicam as
informações da lista. Uma estrutura de lista também pode ser formadas por um conjunto de listas e sub listas, ou seja, podemos falar que [ [ A, [ B ] ] , [ C ] ] é uma lista
com dois elementos.
Segundo Szwarcfiter (1994), as operação mais frequentes utilizadas em listas são
a inclusão, exclusão e busca de elementos na lista. Essas operações, apesar de
serem simples, mostram uma grande importância para a criação de outras operações.
Tem-se como exemplo real as filas dos caixas em um banco, onde os clientes se
organizam de forma sequencial entre o primeiro e o último da fila, criando assim uma
ordem de atendimento e a medida que os clientes são atendidos, os mesmos são
removidos da fila.
As listas lineares são constituídas pelas seguintes regra:
• Uma lista E contem n elementos (nós) tal que n >= 0
• Quando n = 0, dizemos que a lista é vazia.
• Caso E n = E n-1 dizemos que E n-1 é antecessor a E n
16
Figura 1: Lista linear
As listas podem ser armazenadas de duas formas na memória do computador,
contínua e dinâmica. A representação contínua ocorre quando cada nó da lista é
armazenado de uma forma contínuo na memória, desde que o número máximo de
elementos da lista sejá conhecido. Nessa representação a busca pela informação é
“rápida”, pois conhecendo o endereço do nó Ei pode-se determinar o endereço do nó
Ei+1 utilizando-se um índice, onde E é a lista linear e i é a posição da lista. Essas
listas, também chamadas de Vetores
1
ou Matrizes2 , segundo Veloso (1991) podem
ser representadas da seguinte forma:
Figura 2: Representação da lista contínua
A alocação encadeada conhecida também como dinâmica, tem como característica a dinamicidade de alocar os elementos na memória na medida em que houver
necessidade, visto que os nós se encontram em posições aleatórias na memória,
porem cada nó contém ponteiros que interligam uns aos outros. (Segundo Szwarcfiter
(1994)).
Figura 3: Estrutura de um nó de uma lista encadeada, onde “Info” é o campo de
informação e “Prox” aponta para o próximo nó da lista
Pode-se então representar uma lista simplesmente encadeada conforme a figura
04.
Nesta estrutura de dados podemos identificar os seguintes conceitos:
1 Em
computação Vetores são variáveis compostas homogêneas unidimensionais, não podendo ser
confundida com a definição geométrica do termo, pois sua semelhança é de difícil percepção.
2 Matrizes são variáveis compostas homogêneas multidimensionais, diferenciam de vetores pelo fato
de necessitar de mais de um índice para individualizar seus elementos.
17
Figura 4: Lista simplesmente encadeada
1. O ponteiro para o início da lista;
2. Em cada nó existem dois campos: o que contem a informação e o campo que
armazena o endereço na memória onde está alocado o próximo nó.
3. No último nó, o campo de ligação aponta para um local de informações nulas
(null) indicando o fim da lista.
Nesta lista sempre temos um ponteiro que guarda o endereço do primeiro elemento e a partir dele realizamos um percurso sequencial, sempre do início ao fim lista,
até chegarmos no último elemento, que contém um valor nulo no seu campo “prox”.
Entretanto caso houvesse a necessidade de apontar para o nó anterior, ficaríamos
impossibilitados pelo fato de que não existe nenhum ponteiro indicando o nó anterior.
Para este problema existe a lista duplamente encadeada, onde cada elemento possui dois ponteiros: um que aponta para o nó anterior e outro que aponta para o seu
próximo. Observe a figura a seguir:
Figura 5: Lista duplamente encadeada
Além dessas listas há também a lista circular, em que o seu último elemento aponta
para o primeiro. As figuras 06 e 07 representam esquematicamente a lista circular.
Figura 6: Lista simplesmente encadeada circular
Neste projeto de pesquisa a implementação de uma das técnicas empregadas
(método de Huffman - que será descrita posteriormente), utilizou a estrutura de lista
18
Figura 7: Lista duplamente encadeada circular
duplamente encadeada que conforme abordado anteriormente, possibilita a inserção
dinâmica dos elementos e a flexibilidade de obter as informações do próximo elemento
e a do anterior. A inserção dinâmica tem como vantagem, abstrair a quantidade de
elementos que serão inseridos e utilizar somente o espaço nescessário para a operação. Já a obtenção das informações tanto do próximo elemento quanto do anterior
favorece a busca pelas mesmas, agilizando o processo.
Outro fator que favorece o desemprenho das listas é a sua criação em memória
primária, a qual tem um acesso mais rápido em comparação à memória secundária
[Machado e Maia, 2007], que geralmente é preferida para o armazenamento de arquivos, por possuir uma maior capacidade de armazenamento de dados. Apesar
disso, a redução do tempo gasto foi o fator de maior relevância para a escolha da
lista, potencializado por ser do tipo duplamente encadeada.
2.2
Árvore
Os métodos os quais serão abordados posteriormente sobre os compactadores,
com particularidade em Huffman, terão uma base relevante sobre árvores.
A árvore segue a mesma idéia das listas porém, segundo Pinto (1990), "Uma
árvore é uma representação capaz de exprimir a relação de hierarquia existente entre
os dados, ou a relação de composição onde um conjunto de dados é subordinado a
outro".
Em um exemplo de árvore, pode-se pensar em um gerente de projetos que coordena uma equipe de 3 funcionários. Seus funcionários serão subordinados, ou podese ter também uma árvore genealógica. Para definir uma árvore deve-se determinar
um:
19
• nó que é pai de todos os demais denominado raiz da árvore;
• e cada nó subsequente são ao nó pai, irá formam um outro subconjunto maior
ou igual à zero (0) elementos.
O esquema de uma árvore está representado na figura 08.
Figura 8: Esquema completo de uma árvore
2.2.1
Árvore Binária
As árvores binárias são especiais porque, quando ordenadas, elas conduzem às
pesquisas, inserções e exclusões rápidas. Segundo Schildt (1997):
"Cada nó de uma árvore consiste em ter informações e que juntamente
contem um elo ao membro esquerdo e outro elo ao membro direito".
"...a árvore binária é uma forma especial de lista encadeada. Podese inserir, excluir e acessar itens em qualquer ordem. Além disso, a
operação de recuperação é não destrutiva."
20
Figura 9: Representação de uma árvore binária
A maioria das funções que usam árvores é recursiva , pois as versões não recursivas dessas funções são muito mais complexas.
Na construção de árvores de busca binária deve-se ter as seguintes observações
para que dados sejam armazenados:
1 Se a árvore for vazia, o símbolo é colocado na raiz;
2 Se o elemento for menor que o símbolo da raiz, ele é colocado na subárvore da
esquerda, se for maior, é colocado à direita.
21
3
COMPACTADORES
Esse capítulo apresenta um breve histórico das estratégias de compactação e
diversos métodos, técnicas e codificações da compactação, relevantes para o projeto.
3.1
Histórico da Compactação
Em vários momentos da história, encontramos relatos de criptográficas , Schildt
(1997) descreve que por volta de 1500 a.C. já era utilizado a escrita cifrada para
guardar segredos. Os gregos e espartanos utilizavam códigos que os ajudavam em
movimentos bélicos durante as Guerras Médicas e do Peloponeso, tendo registro escrito dessa codificação em 475 a.C. Além disso, a classe dos Patrícios Romanos utilizava a encriptação simples durante o reinado de Júlio César.
Durante a Idade Média, o interesse pela criptografia diminuiu. Mesmo porque
neste período histórico a quantidade de pessoas que sabia ler era irrisória (exceto
entre os monges que ocasionalmente faziam uso deste modo de registro).
Com o Renascimento Italiano, a arte da criptografia novamente floresceu, sendo
aplicada às mensagens governamentais para dificultar a interpretação dos inimigos.
No século XIX , a invenção do telégrafo elétrico e do Código Morse por Samuel F. B.
Morse abriu espaço para a criptografia moderna, deixando de ser um processo altamente manual. O código Morse foi a primeira representação de um sistema binário
(ponto e traços) de um alfabeto com ampla aplicabilidade. Essa representação dupla
também é chamada de bit. Para cada bit representado, pode-se considerar uma única
unidade lógica e para cada byte é considerado um conjuto de oito (8) bits, consequentimente oito (8) unidades lógicas.
Na Primeira Guerra Mundial, várias nações desenvolveram máquinas de codificação mecânica que permitiram facilmente codificar e decodificar textos usando criptografias sofisticadas e complexas. Na Segunda Guerra Mundial a codificação das
22
mensagens passa a ser utilizada não somente para esconder a informação do inimigo,
mas também para reduzir a quantidade de informações que era passada através dos
rádios. Então, surge neste momento a compactação de dados relacionanda diretamente com a criptografia, utilizada inicialmente para fins bélicos, sendo expandida
posteriormente.
Scheidcmantel (1995), evoluiu seus algoritmos e hoje eles são altamente utilizados
na proteção de informações estratégicas das empresas e organizações governamentais detentoras de tecnologia. A compressão de dados também passou a ser muito
desenvolvida, porém como uma área distinta. Grandes pesquisadores deixaram várias
contribuições que evoluíram os métodos de compactação até os dias de hoje. Não é
demais citar nomes como Claude A. Shannon, David Huffman, Abraham Lempel, Jacob Ziv e Terry Welch, dentre outros.
Neste período, Schildt (1997) relata que em vários equipamentos já se encontra a
compressão de dados, que pode ser implementada em hardware, software ou através
do uso de um dispositivo especial de hardware que incorpore uma ou mais técnicas
de compressão. Os primeiros entre estes componentes, foram os concentradores de
dados e os multiplexadores estatísticos, por volta dos anos 70 e início dos anos 80.
Aproximadamente a partir da metade dos anos 80, ocorreu uma revolução na utilização de produtos que executavam a compressão de dados nas áreas de modems
de rede chaveada, armazenamento em discos usado em microcomputadores e mainframes. Centenas de fabricantes de modem para rede chaveada incorporaram uma
variedade de algoritmos de compressão de dados em seus produtos, enquanto diversos projetistas de software comercializaram produtos que aumentavam a capacidade
de armazenamento de discos ao comprimir os dados antes de armazená-los.
3.2
Compactação
Como já descrito, a criptografia é uma ciência antiga que possibilitou o surgimento
da compactação de dados. Pode-se considerar que a compactação e a criptografia
são correlatos, sendo que em um algoritmo de compressão encontra-se um codificador e um decodificador que é aplicado sobre os dados de entrada e saída.
23
Figura 10: Esquema de codificação e decodificação
Como mostra na Figura 10, um codificador tem como entrada os dados D e que por
sua vez passa por um processo de compactação de dados, gerando em sua saída os
dados C (dados foram criptografados). O decodificador faz o trabalho inverso, recebe
como entrada os dados C e devolve como saída os dados D. O processo pode ser
feito sem perdas ou com perdas de dados. Se o processo for sem perdas o resultado
obtido será exatamente o mesmo da entrada do codificador.
Atualmente, é comum se deparar com uma situação em que se deseja armazenar
um arquivo de grande porte em algum tipo de memória, seja ela primária (memória
RAM) ou secundaria (HD). Para que se possa utilizar melhor os recursos dos dispositivos, é preciso minimizar de alguma forma, o espaço ocupado no dispositivo utilizado.
Uma maneira para que o problema acima seja resolvido, consiste em modificar (compactar) o conteúdo do arquivo de maneira apropriada, de tal forma que o tamanho do
arquivo fique menor que o original.
Se o arquivo compactado for menor do que o original, pode-se armazenar a versão
do arquivo modificado em vez do arquivo original. Isso representaria um ganho de
memória. Geralmente uma tabela de códigos também é armazenada. Essa tabela de
códigos é criada de modo que seja possível codificar ou decodificar as informações
de um arquivo, sem que haja muitos problemas com a integridade dos dados.
O problema referido é conhecido como compressão de dados. No decorrer da
história a compressão sempre teve grande importância, pois no início da computação
a economia de recursos, principalmente em memória, era crítica, devido ao seu elevado custo. Com o passar do tempo, esse problema não era mais o foco, entretanto,
muitos programas que são utilizados atualmente requerem o uso de grande parte da
memória. Tem-se como exemplo, programas que utilizam muitos recursos visuais,
virtualização, ou consultas em bancos de dados.
Com isto, o problema de economia de memória ainda persiste na atualidade. Ao
contrário do que possa parecer, compactação não é somente reduzir o tamanho de
um arquivo; há várias outras aplicações que utilizam a compactação de dados.
24
Nos últimos tempos as redes de computadores se tornaram comuns e a transferência de dados pela rede se tornou cada vez mais frequente, assim o tráfego pela rede
está ficando cada vez mais custosa, com isso a compressão de dados se encaixaria
muito bem neste quadro, pois um número menor de dados a ser transmitido, implicaria
em um custo de transmissão menor.
A compactação também é utilizada para agilizar a transmissão de dados basicamente de duas formas: alterando a taxa de transmissão e/ou permitindo o aumento
no número de computadores de uma rede. Se houver um modem que opera a 9600
bps (bits por segundo), é possível que ele transmita como se estivesse a 14400 bps;
Desde que ele permita a compressão de dados transmitidos, ampliando sua capacidade de transferência de informação. Na verdade, o modem continuará transmitindo a
uma taxa de transmissão de 9600 bps, mas a taxa de transferência de informação estará ampliada para 14400 bps. Portando, a compressão de dados permite o aumento
da taxa de transmissão de dados. [PINHEIRO, 2004]
Outra vantagem da compressão é a possibilidade de expansão de uma rede de
computadores. Com a ampliação do número de computadores em uma rede pode
ocorrer um desempenho não esperado devido ao aumento do tráfego de dados, tornandose necessária uma transmissão mais rápida desses dados. Há, portanto, duas alternativas: trocar os equipamentos que fazem essa transmissão por modelos mais
coerentes com o cenário, ou incorporar um algoritmo de compressão aos equipamentos existentes em seus chips desde que estes permitam essa atualização. Como a
primeira alternativa é mais cara, a segunda permite que se alcance o mesmo desempenho com um custo menor. A compressão de dados, neste caso, permite a ampliação
de uma rede de computadores de uma forma alternativa e mais baratas. [PINHEIRO,
2004]
3.3
Tipos de Compactação
A compressão lógica refere-se a uma estratégia para a otimização de dados. Um
exemplo é o projeto de um banco de dados utilizando sequências de bits para a representação de campos de dados. No lugar de sequências de letras ou números, utilizase bits (que são sequências de vários zeros e uns que a máquina entende), reduzindo
significativamente o espaço de utilização do banco de dados. Este tipo de compressão
é possível ser efetivada em campos projetados para representar dados constantes,
25
como datas, códigos e quaisquer outros campos formados por números. A característica lógica da compressão encontra-se no fato de os dados já serem comprimidos no
momento do armazenamento, não ocorrendo sua transformação de dados estendidos
para comprimidos; exemplo da representação de:
• “01 de Abril de 2003” : 15 bytes
• “01 Abr 2002” : 9 bytes
• “01042002” : 8 bytes
A compactação física é aquela realizada sobre dados já existentes, ao qual é verificado a repetição de elementos como letras, números ou símbolos, para efetivar a
redução dos mesmos. Na compressão física, existem dois tipos de técnicas para
sinalizar a ocorrência de caracteres repetidos: Um deles indica o caractere (ou conjunto de caracteres) repetido através da substituição por um caractere especial. Outras
técnicas indicam a frequência de repetição de caracteres e representam isto através
de sequências de bits.
Figura 11: Tipos de compactação
3.4
3.4.1
Técnicas de Compressão
Técnicas com Caracteres Indicadores
É necessário esclarecer como são codificados os caracteres indicadores (especiais) a serem substituídos pelos caracteres repetidos na compressão física como
run-length, apesar de não serem um codificação tão eficaz e não fazer parte do projeto, o entendimento pelo mesmo é importante para entender codificações que serão
abordadas posteriormente.
26
3.4.1.1
Codificação Run-length
O Run Length Encoding, também conhecido por comprimento de fileira pode ser
esclarecido por Held (1992) que:
"A codificação de comprimento de fileira é um método de compressão
de dados que reduzirá, fisicamente qualquer tipo de sequência de caracteres repetidos, desde que a sequência de caracteres alcance um
nível predefinido de ocorrência. Para a situação especial onde o caractere nulo é o caractere repetido a compressão de comprimento de
fileira pode ser vista como um processo avançado de supressão de
nulos."
A Figura 15 mostra os caracteres A, B e C sendo repetidos 5 vezes, porém os
números do texto poderiam ser confundidos com o número que indica a frequência de
repetições. Para resolver esse problema, geralmente coloca-se um caractere que não
ocorre no texto ou um daqueles caracteres não imprimíveis,como mostra na tabela
ASCII na Figura 14. Por exemplo o caractere especial STX (código 00000010 binário
na tabela ASCII) é utilizado para anunciar o início do texto do texto codificado e o
SI (código 00001111 binário na tabela ASCII) anuncia que o próximo número será a
quantidade de vezes que o caractere irá se repetir. A representação da codificação
run-length está ilustrada na Figura 13.
27
Figura 12: Tabela ASCII caracteres não imprimíveis
Figura 13: Técnica run-length
28
Considerando que um caractere ocupe um byte de memória, pode-se concluir que
a codificação abordada na Figura 13 ocupa 9 bytes, em vez de 15, visto isso podemos
calcular que a taxa de compressão seria de 40% calculado pela seguinte formula:
Taxadecompresso = (1 − TamanhoComprimido/TamanhoOriginal)x100
Além disso, deve-se ter em mente o modo de representar um inteiro como um
byte, pois estamos manipulando caracteres. Um byte pode ser armazenado em um
interlavo de valores entre zero (0) e 255, pois, como já foi dito anteriormente, um byte
tem 8 bits e o bit representado por sistema binário tem como base o número dois,
ou seja, temos 28 e com isso temos 256 ocorrências de caracteres. Visto isso, caso
ocorra mais do que isso, utiliza-se representações mais eficientes.
Utilizando o run-length estendido o problema abordado anteriormente pode ser
facilmente resolvido, pois a diferença desta técnica para a run-legth simples é que há
um caractere específico que delimita o inicio e o fim de cada sequência de codificação.
Por exemplo:
SO R A 980 SI
No exemplo acima SO (do inglês: shift out) representa um caractere especial indicador de início de uma sequência de caracteres definida pelo usuário até que SI
(do inglês: shift in) seja encontrado. Esta é uma propriedade de códigos de caracteres, como o ASCII e EBCDIC. O caractere R indica a compressão run-length, onde
o caractere A é indicado como repetido 980 vezes. Como o valor 980 ultrapassa o
limite de 256 de um byte, torna-se necessária a utilização de mais um byte para a
representação do valor.
O algoritmo da técnica run-length é simples. Consiste nos seguinte passos:
1. Inicializa-se um contador de caracteres, destinado ao controle de cada caractere,
buscando a verificação de existência de repetição;
2. Inicializa-se um contador de repetições do caractere procurado;
3. Faz-se à leitura do caractere no arquivo a comprimir;
4. Incrementa-se o contador de caracteres;
29
5. Se o contador de caracteres for igual a 1, o caractere é armazenado e volta-se
ao passo 3 para verificação de repetição;
6. Verifica-se se o caractere armazenado é o que procuramos; se for, incrementase o contador de repetições;
7. Verifica-se se o contador de repetição é maior ou igual a 4 se for menor, gravamse os caracteres lidos no arquivo comprimido e volta-se ao passo 1;
8. Realiza-se a gravação dos caracteres indicadores no arquivo comprimido e voltase ao passo 1.
A Figura 14 representa uma visualização geral do exposto acima.
Figura 14: Processo de compressão Run-Length
30
3.4.2
Compressão Estatística
A idéia é realizar uma representação otimizada de caracteres ou grupos de caracteres. Caracteres de maior frequência de utilização são representados por códigos
binários pequenos, e os de menor frequência são representados por códigos proporcionalmente maiores. Não é necessário saber qual caractere vai ser comprimido, mas
sim, conhecer a probabilidade de ocorrência de todos os caracteres sujeitos à compressão [PINHEIRO 2004].
Caso não seja possível a tabulação de todos os caracteres sujeitos à compressão,
utiliza-se uma técnica para levantamento estatístico dos dados a comprimir, formando
tabelas de probabilidades [PINHEIRO, 2004].
Os método que utilizam muito essa idéia são a codificação de Shanno-Fano e a
de Huffman que serão descritas ao decorrer deste tópico.
3.4.2.1
Codificação de Shannon-Fano
Esse método foi um dos primeiros algoritmos de compressão criado nos anos 40
por R. M. Fanno. Nessa técnica, aplica-se nos dados de entrada um algoritmo de
compressão probabilístico que representa os caracteres mais repetidos com menos
bits que os menos repetidos [SANCHES 2001].
Em um conjunto de símbolos (ou caractere), obtém-se uma tabela de probabilidade de ocorrência de cada caractere e aplica-se sobre esta tabela um procedimento
de codificação baseado na divisão de conjunto de probabilidades para a obtenção do
código binário [SANCHES, 2001]. Podemos relatar da seguinte forma:
Tabela 1: Conjunto binário da tabela ASCII por codificação
Símbolo Freq. de Ocorrência
A
0,5
B
0,3
C
0,1
D
0,1
Após obter a tabela de probabilidades acima, divide-a em dois grupos cuja soma
de probabilidades seja igual ou o mais próximo possível. O primeiro grupo recebe
como primeiro valor de código o valor zero e o segundo recebe um.
31
Tabela 2: Codificação inicial de Shannon Fano
Símbolo Freq. de Ocorrência Código
A
0,5
0
B
0,3
1
C
0,1
1
D
0,1
1
O procedimento é repetido até chegar ao fim da tabela, dividindo-a em subgrupos
de probabilidades equivalentes. Na tabela 3 o símbolo B forma o primeiro subgrupo
e os demais formam o segundo. Seguindo a regra de que o primeiro recebe zero e o
segundo recebe um.
Tabela 3: Codificação intermediária de Shannon Fano
Símbolo Freq. de Ocorrência Código
A
0,5
0
B
0,3
10
C
0,1
11
D
0,1
11
Tabela 4: Codificação final de Shannon Fano
Símbolo Freq. de Ocorrência Código
A
0,5
0
B
0,3
10
C
0,1
110
D
0,1
111
3.4.2.2
Codificação de Huffman
Uma das técnicas mais populares para resolver a redundância de codificação foi
elaborada por Huffman em 1952. Por codificar individualmente os símbolos de uma
fonte de informação, tendo como resultado o menor número possível de símboloscódigo por símbolo-fonte [GONZALEZ, 2009].
A idéia desse algoritmo parte do mesmo princípio de Shanno-Fano, codificar os
símbolos de maior frequência com menos bits e os símbolos de menor frequência
com mais. Basicamente, o algoritmo cria uma árvore binária, que apartir dela montase uma tabela de frequências em que cada caractere é representado por um conjunto
de bits de tamanho variado.
Supõe-se que um texto seja constituído de um conjunto de símbolos (ou caracteres). Assim, é conhecida a frequência de cada símbolo ao longo do texto e após isso
32
atribui-se um código a cada símbolo, de modo a compactar o texto todo. A atribuída
que se coloca é que nenhum código seja prefixo de algum outro, para que não haja
ambiguidade de código.
Para cada nó interno denominado “v”, a aresta que conduz ao filho esquerdo de
“v” é rotulada com zero, enquanto o rótulo daquela que conduz ao direito é igual a
um. Cada símbolo é associado a uma folha da árvore. Os códigos dos símbolos são
sequências binárias, tal que essas sequências são definidas dependendo do caminho
a ser tomando na árvore [SANCHES, 2004].
A codificação de Huffman pode ser abordada pelos seguintes passos:
1 Organizam-se os símbolos em ordem decrescente de probabilidade;
2 Agrupam-se os dois símbolos de menor probabilidade, dando origem a um novo
símbolo cuja probabilidade será igual à soma das probabilidades dos símbolos
que geraram. Uma "nova"fonte é criada e a esta fonte dá-se o nome de fonte
reduzida. Essa nova fonte terá um elemento a menos em relação à fonte que a
gerou. Novamente, organizam-se os símbolos em ordem decrescente de probabilidade de ocorrência;
3 Continua-se executando o passo anterior, formando novas fontes reduzidas, até
que só restem dois símbolos;
4 Com os dois símbolos restantes, faz-se uma atribuição aleatória de 1 para um
dos símbolos e zero para o outro. Não há necessidade de nenhuma regra nessa
atribuição, sendo a mesma feita a critério do codificador;
5 Procede-se com o algoritmo, voltando dos símbolos finais até os símbolos da
fonte, fazendo atribuição de zeros e uns às palavras do código;
6 Ao chegar nos símbolos da fonte, a codificação está pronta.
A tabela de frênquencias a seguir, é um exemplo de um arquivo genérico de símbolos da tabela ASCII. A partir da tabela frequência de símbolos conforme a Tabela 5
é feita a árvore de Huffman como mostra passo a passo na Figura 15.
33
Tabela 5: Frequência e o código original dos símbolo
Símbolo Freq. de Ocorrência Código ASCII
g
10
0110 0111
c
15
0110 0011
b
25
0110 0010
f
25
0110 0110
h
25
0110 1000
i
25
0110 1001
e
35
0110 0101
d
40
0110 0100
a
50
0110 0001
Figura 15: Processo de codificação de Huffman - passo a passo
34
A Tabela 6 a seguir representa a codificação referente a ávore da Figura 15. Temse como exemplo o código do símbolo “a” que é 01, pois é a sequência dos rótulos
das arestas, desde a raiz até “a”.
Tabela 6: Frequência e o código codificado dos símbolo
Símbolo Freq. de Ocorrência Código ASCII Código
g
10
0110 0111
1000
c
15
0110 0011
1001
b
25
0110 0010
1110
f
25
0110 0110
1111
h
25
0110 1000
000
i
25
0110 1001
001
e
35
0110 0101
101
d
40
0110 0100
110
a
50
0110 0001
01
Observe que na tabela anterior a sequência de código foi reduzida comparada
com a tabela ASCII. Para obter a taxa de compressão, basta calcular a somatório da
frequência de cada símbolo ( f i), multiplicado pelo tamanho da sequência de código
(pi), que seria o caminho percorrido na árvore, conforme a seguinte formula:
n
TaxaCompressao = ∑ f i × pi
i=1
Calculando a taxa, tem-se:
• Arquivo original: 10x8+15x8+...+50x8= 2000 bits
• Arquivo codificado: 50x2+40x3+...+10x4 = 775 bits
Nota-se que houve uma redução de 61,25%, uma melhoria consideravel em relação ao arquivo original.
Uma vantagem da utilização de código de prefixo é a facilidade existente para executar tarefas de codificação ou decodificar. Para decodificar um texto, basta percorrer
da esquerda para a direita, ao mesmo tempo em que a árvore é percorrida, repetidamente, da raiz para as folhas. Nesse percurso, toma-se o caminho para a esquerda
ou direita, na árvore, de acordo com o dígito correspondente encontrado no texto, zero
ou um, respectivamente. Toda vez que uma folha é atingida, um símbolo decodificado
foi encontrado. Nesse caso, retoma-se o processo reiniciando o percurso na árvore a
partir da raiz, para decodificar o próximo símbolo.
35
Por exemplo, dada uma sequência 01000, significa que se deve tomar o caminho
da esquerda da raiz, já que o primeiro digito é zero (0) O digito seguinte é um (1), o que
conduz para a direita desse último nó, a folha corresponde ao símbolo “a” é alcançada.
O texto decodificado inicia-se, por “a”. Retoma-se então a raiz da árvore. O próximo
dígito na codificação é um (1). O caminho a seguir são tês filhos à direita da raiz,
seguido pela adição por três zeros (000). Com isso, atinge-se a folha correspondente
a “g”. Assim sendo, detectou-se que o símbolo seguinte a “a” no texto é “g”.
Pode-se determinar a análise da complexidade da codificação de Huffman da
seguinte forma:
• Usa-se um Heap para armazenar o peso de cada árvore e cada iteração requer
O(log n) para determinar o peso menor e inserir o novo peso.
• Existem O(n) iterações, uma para cada ítem.
Conclui-se então que a complexidade da codificação de Huffman é O(n log n).
Além da complexidade, deve-se levar em conta o custo da busca, tal que, uma
árvore T de prefixo correspondente a um dado texto, em que cada símbolo si ocorre
f i vezes. Seja li o comprimento do código binário do símbolo si. É explicito que cada
símbolo si contribui com f i.li unidades de custo, com isso se tem:
n
sim(T ) = ∑ f i × li
i=1
Este valor corresponde ao custo do comprimento de caminho. Se todas as frequências são idênticas, então “T” é uma árvore binária completa e “c(T)” é o comprimento de caminho externo de “T”. Vale observar que a codificação de Huffman
apresenta ineficiência em arquivos com uma grande quantidade de elementos distintos, pois caso a árvore esteja totalmente completa e atinja o tamanho máximo, a taxa
de compressão é nula.
36
4
A Transformada Wavelet
A Transformada Wavelet pode ser a chave para a compressão eficiente de imagens com uma mistura de áreas de alta frequência e baixa frequência. Em contraste,
imagens com grande quantidade de informações uniforme podem responder melhor
aos outros métodos de compressão. Pode-se destacar a codificação de Huffman apresentada na sessão 3, uma das técnicas mais populares para resolver as redundâncias.
A seguir será descrito o surgimento das Wavelets e algumas abordagens como a
Transformada Wavelet de Haar.
4.1
Surgimento das Wavelets
No início de 1800, o matemático francês Joseph Fourier descobriu que qualquer
função “f” periódica pode ser expressa como uma soma (possivelmente infinita) de
senos e cossenos. Estas funções são representadas graficamente como ondas, razão
pela qual a expansão de Fourier de uma função “f” está associada com as ondas e
revela as frequências ocultas em “f”. A Expansão de Fourier tem muitas aplicações na
engenharia, principalmente na análise de sinais [SALOMON, 2008].
A desvantagem de Expansão de Fourier é que ela não diz em que ponto no tempo
cada frequência está ativa em um dado sinal. Portanto, diz-se que a Expansão de
Fourier oferece análise Wavelet, que é uma abordagem bem sucedida a analisar de um
sinal no tempo e na frequência. A idéia fundamental por trás das wavelets é analisar
uma função ou um sinal de acordo com a escala de frequência e tempo [SALOMON,
2008].
A Transformação de Wavelet Contínua ilustra a conexão entre a análise tempofrequência de funções contínuas e as ondas que se concentram em uma área pequena. Em aplicações práticas, os dados são normalmente coletados como conjuntos de números, e não como uma função contínua, e por isso é discreto. Assim, a
37
Wavelet discreta, é a ferramenta utilizada na prática, para analisar os dados digitais e
comprimi-lo [SALOMON, 2008].
Apesar de existirem várias Transformadas Wavelet a sessão a seguir irá abordar
sobre a Transformada Wavelet de Haar, sendo que o foco do projeto.
4.2
Transformada Wavelet de Haar
A transformada de Haar, surgiu pelo trabalho feito por Alfred Haar em 1910-1912,
pelos sistemas de funções ortogonais. Sua abordagem funciona da seguinte forma,
tal que dado uma vetor com N posições, dividi-se em N/2 pares de pixels consecutivos, calcula-se a média e a diferença de cada par, resultando em N/2 Médias e N/2
diferenças [SALOMON, 2008].
Em seguida, repete-se este processo nas médias (N/2 elementos) para se obter
N/4 médias e N/4 diferenças. Isto é repetido até resultar em uma média seguido por
N - 1 diferenças [SALOMON, 2008].
Uma seqüência unidimencional com uma resolução de quatro pixeis, tendo valores: [9 7 3 5]. Para entender como representar esta seqüência na base de Haar
computando sua Transformada Wavelet, calcula-se primeiro a média dos valores em
pares, obtendo os novos valores de menor resolução da imagem: [8 4].
Claramente, um pouco da informação foi perdida neste processo de cálculo da
média. Para recuperar os valores dos pixeis originais a partir dos valores de média,
precisa-se armazenar alguns coeficientes de detalhes, que capturam a informação
perdida. No exemplo abordado, o 1 será o valor de escolha para o primeiro coeficiente
de detalhe, como na média computada tem-se 1 a menos que 9 e 1 a mais que 7. Este
único número permite recuperar os primeiros dois pixeis a imagem original de quatro
pixeis. Semelhantemente, o segundo coeficiente de detalhe é “-1”, pois 4 + (−1) = 3 e
4 − (−1) = 5.
Assim, a imagem original foi decomposta em uma versão de resolução mais baixa
(dois pixeis) e um par de coeficientes de detalhes. Repetindo este processo recursivamente até a decomposição completa conforme tabela a seguir:
38
Tabela 7: Decomposição em coeficientes de aproximação e detalhes.
Resolução Média/Valores Coeficientes de
Detalhamento
4
[9 7 3 5]
2
[8 4]
[1 -1]
1
[6]
[2]
Assim definiremos a Transformada de Wavelet de Haar unidimencional (também
chamada de Decomposição de Wavelet) da imagem original de quatro pixeis com a
simples representação da média global da imagem original, seguido pelos coeficientes
de detalhe em ordem de resolução crescente. Para a base de Haar unidimensional, a
Transformada de Wavelet da nossa imagem original de quatro pixeis é dada por: [6 2
1 -1].
Pode-se observar que o resultado obtido no exemplo acima não reduz a quantidade de dados existente no arquivo, porem os valores para a representação dos
dados, são aproximados.
Computacionalmente, a Transformada Wavelet de Haar tem uma complexidade
linear, requerendo apenas O(n) operações aritméticas. Se aplicarmos uma função
para um sinal com n amostras será necessário kn operações para alguma constante
“k”, então o número total de operações para computar a Transformada Wavelet será:
n
n
n
1 1
1
kn + k + k + ... + k
<= Kn(1 + + + ... +
) <= 2kn = O(n)
2
4
log2 n
2 4
log2 n
Apesar das Wavelets terem uma grande influência na codificação de imagens, áudio e vídeos, podemos também relacioná-las a compressão de arquivos texto com os
conhecimentos adquiridos no capítulo 3. Sabe-se que cada caractere representa 8
bits, com valores de 0 a 255, conforme a tabela ASCII. Com isso, pode-se converter
facilmente letras em números e vice versa. Tendo isso em mente, tem-se uma correlação entre os valores de uma imagem 8 bits (grayscale - escala de preto, branco e
cinza) com os valores de um caractere de um arquivo texto.
39
5
ALGORITMO PROPOSTO
O algoritmo proposto neste presente projeto surgiu a partir de pesquisas sobre
o comportamento da codificação de Huffman e da Transformada Wavelet de Haar.
O interesse sobre a codificação de Huffman se deu devido ao comportamento dos
dados observado em outros estudos quando aplicada tal codificação, visto que no
final do processo a compactação sobre os dados do tipo texto se revelou eficiente e
sem perda, tal que quanto menor for a variação dos elementos distintos, maior será
sua taxa de compactação. [GONZALEZ, 2009]
Com o intuito de buscar outras alternativas de compactação sem perda, observouse que na aplicação da codificação da Transformada Wavelet de Haar, a representação do valor de cada dado tornou-se aproximado entre si. Considerando a variação
dos dados, e a representação destes através de valores, quanto maior for a proximidade entre eles menor será a variação dos elementos distintos. Assim, quando
houver uma maior proximidade entre os dados disponibilizados para a codificação de
Huffman, haverá também uma maior compactação. Visto isso, surgiu a idéia de associar a codificação de Huffman com a Transformada Wavelet de Haar, no intuito obter
uma maior eficiência sobre a taxa de compactação.
5.1
Prova de Integridade
No procedimento de compactação e descompactação dos dados sem perda, a
integridade de um arquivo é essencial, visto que uma entrada Z deve ser equivalente
a sua saida Z’, conforme ilustrado na figura 16.
40
Figura 16: Sequência dos processos
O exemplo abaixo serviu como teste para a verificação de que o algoritmo proposto
manteve a integridade dos dados.
Conforme descrito no capitulo 4, quando aplicada a codificação da Transformada
Wavelet de Haar, sobre uma entrada Z, sendo esta um conjunto de elementos “AAAAAAAA”,
serão obtidas as médias e diferenças entre os elementos. A figura abaixo ilustra o exemplo citado.
Figura 17: Processo da codificação da Transformada Wavelet de Haar
Após o processo da Transformada Wavelet de Haar, o resultado obtido pela mesma
é uma sequência de elementos contendo um “A” e sete “NULL”, sendo representados por 01000001 00000000 00000000 00000000 00000000 00000000 00000000
00000000 na forma binária. Em seguida é criada a árvore de codificação a partir das
frequências dos elementos, visto que ao final da criação da mesma, o caminho da
direita sibolizará o bit 0 e o da esquerda o bit 1, conforme descrito no capítulo 3.
Na figura 18, pode-se observar que os elementos passaram a ter uma nova representação, e a partir desta foi criada uma tabela de codificação (Tabela 8), com
o intuito reduzir a sequência obtida no processo anterior e auxiliar no retrocesso da
codificação.
41
Figura 18: Árvore de codificação
Tabela 8: Tabela de codificação
Elemento Frequência Código Original Código Codificado
A
1
01000001
0
NULL
7
00000000
1
Assim da tabela 8, o elemento “A” é representado por 0 e o ”NULL“ por 1. Desta
forma, a sequência obtida no processo de codificação da Transformada Wavelet de
Haar, é reduzida para o valor binário 01111111, que na tabela ASCII é representado
pelo elemento ”DELETE“ (Z’).
Para provar que Z’ é equivalente a Z, sabendo que aquele é o resultado obtido
na compactação, a partir da tabela codificada (Tabela 8) tem-se que a sequência
01111111 (”DELETE“), é transformada por 01000001 00000000 00000000 00000000
00000000 00000000 00000000 00000000 (”A NULL NULL NULL NULL NULL NULL
NULL“), conforme ilustra a figura 19.
Figura 19: Transformação dos dados
Com o resultado da transformação, é aplicado o processo reverso da Transformada
Wavelet de Haar também decrito no capitulo 4 deste projeto. Por fim este processo
terá um conjuto de elementos ”AAAAAAAA“, ilutrado na figura 20.
42
Figura 20: Processo da decodificação da Transformada Wavelet de Haar
Sabendo-se que Z é uma entrada ”AAAAAAAA“ e o resultado obtido por Z’ na
descompactação é um conjunto de elementos ”AAAAAAAA“, assim o conjunto dos
elementos de Z é equivalente a Z’, concluido que a premissa sobre a integridade do
algoritmo é verdadeira.
5.2
Características do Algoritmo
No algoritmo utilizou-se a Codificação e Decodificação de Huffman para obter a
compactação sem perda de dados. Também foram utilizadas técnicas do processamento digital de imagens e modelagem matemática, com base na ferramenta Wavelet
para decomposição dos dados. Apesar de existirem muitas transformadas Wavelet,
a escolha da Transformada Wavelet de Haar se deu devido a características como a
rapidez em que executa seus processos e a possibilidade de fazer a codificação sem
haver perdas de dados.
Já a Codificação de Huffman apresenta uma grande eficiência quanto a presença
de dados redundantes, tal que o resultado obitido contém o menor número possível
de símbolos com a menor representação possível de bits. O algoritmo desenvolvido
processa um arquivo texto no formato “.txt”, sendo que os símbolos dentro do arquivo
devem ser restringidos a tabela ASCII.
Inicialmente o algoritmo tem duas opções: compactação e descompactação. Para
que o algoritmo compacte um arquivo texto, o usuário terá que passar por linha de
comando em que irá determinar parâmetros, sendo, sequencialmente: o arquivo que
deseja compactar, o nome que o arquivo compactado irá receber, e por fim a letra
43
’C’ ou ’c’ para identificar que o algoritmo irá fazer uma compactação. Já na descompactação, o usuário passará pelos seguintes parâmetros: o arquivo anteriormente
compactado pelo mesmo algoritmo, a tabela codificada referente ao mesmo arquivo;
e a letra ’D’ ou ’d’, identificando que será uma descompactação.
A Figura 21 ilustra o fluxo geral do algoritmo desenvolvido.
Figura 21: Fluxo do algoritmo
5.3
Implementação
O presente tópico aborda o algoritmo criado neste projeto, subdividindo-se em dois
subitens: compactação e descompactação. Cada etapa dos subitens são interligadas,
ou seja, a saída de uma é a entrada da próxima, como mostra no fluxograma a seguir.
Figura 22: Fluxo de compactação e descompactação
44
5.3.1
Compactação
A seguir será descrito todo o processo de compactação referente ao algoritmo
proposto, desde a entrada do arquivo com dados puros até a saída do arquivo compactado, iniciando-se o processo com o pré-processamento até a codificação de Huffman. Cada subtópico terá 3 itens, entrada, saída e processo.
5.3.1.1
Pré-Processamento
• Entrada: Arquivo com dados puros a ser compactado;
• Saída: Dados processados;
• Processo: Inicialmente o arquivo de entrada é lido, posteriormente é feito todos
os tipos de conversões e adaptações necessárias sobre os dados no intuito de
que a próxima etapa consiga processá-los.
Figura 23: Fluxo do pré-processamento
No código a seguir, o pré-processamento é feito para cada dado lido no arquivo,
sendo que na leitura o mesmo é convertido implicitamente, visto que a linguagem
usada no algoritmo tem suporte a tal conversão.
45
Figura 24: Código do pré-processamento
5.3.1.2
Transformada Wavelet de Haar
• Entrada: Dados processados.
• Saída: Após esse procedimento é gerado como resultado um arquivo codificado.
• Processo: Utiliza-se funções matemáticas da Transformada Wavelet de Haar.
Inicialmente os dados são armazenados em um vetor unidimensional, onde é
aplicada a decomposição unidimensional citado no capítulo 4.
Figura 25: Fluxograma da Transformada Wavelet de Haar
46
Segue o código da codificação da Transformada Wavelet de Haar.
Figura 26: Código da codificação da Transformada Wavelet de Haar
5.3.1.3
Codificação de Huffman
A terceira etapa é a fase mais importante do algoritmo. Nela é executada várias
subetapas, que são: criação da lista de símbolos, criação da árvore binária, criação
da tabela codificada e a codificação.
A) Criação da lista de símbolos
• Entrada: Arquivo compactado.
• Saída: Lista duplamente encadeada.
• Processo: O arquivo gerado na fase anterior é lido símbolo a símbolo e a partir
de cada leitura o símbolo é armazenado em uma estrutura como mostra na figura
27:
47
Figura 27: Estrutura do nó.
• Frequência: Armazena a frequência em que o símbolo aparece no arquivo;
• Token: Armazena o símbolo;
• Dir: Referência do nó a direita;
• Esq: Referência do nó a esquerda;
• Prox: Referência do próximo nó;
• Ant: Referência do nó anterior.
Quando o primeiro elemento é lido, por sua vez é criada uma estrutura que guarda
o símbolo e sua frequência inicialmente como um (1), caso o arquivo não tenha
acabado ainda, a leitura continua sendo feita. Em seguida, o segundo símbolo é lido,
porém há dois casos para esse símbolo, caso ele seja igual ao primeiro, somente é incrementada a frequência da primeira estrutura referente ao símbolo, caso contrário, é
criada uma nova estrutura que armazene o novo símbolo, com frequência inicialmente
um (1). Entretanto, essa estrutura deve ser referenciada para que não haja perda
de elementos, com isso, a primeira estrutura utiliza o ponteiro “Prox” para referenciar
a segunda estrutura e a mesma utiliza o ponteiro “Ant” para referenciar a primeira
estrutura. Percebe-se que esse procedimento é a criação de uma lista duplamente
encadeada. As Figuras 28 e 29 demonstram o descrito acima.
48
Figura 28: Caso dos símbolos repetidos.
Figura 29: Caso dos símbolos diferentes.
A Figura 30 representa o fluxograma do processo:
Figura 30: Fluxograma da criação da lista de símbolos.
49
Segue na figura 31 a função da criação da lista de símbolos.
Figura 31: Código da criação da lista de símbolos.
50
B) Criação da Árvore
• Entrada: Lista duplamente encadeada.
• Saída: Árvore binária.
• Processo: A criação da árvore é um processo que parte inicialmente da lista
criada na subetapa anterior. Antes de começar a criação, a lista é ordenada em
ordem crescente. Após isso, inicia-se o processo da seguinte forma:
1. Verifica-se há mais de um elemento da lista, caso haja passa-se ao passo 2,
senão o processo é interrompido;
2. Cria-se um nó pai, onde seus filhos são o primeiro e segundo elemento da lista,
tal que, a frequência do nó pai é a soma do primeiro e do segundo elemento;
3. Retira-se a referência entre o primeiro e o segundo elemento da lista;
4. Atribe-se o nó pai como o primeiro elemento da lista;
5. Ordene-se a lista em ordem crescente e retorna-se ao passo 1.
Na Figura 32 exemplifica o processo de criação da arvore.
51
Figura 32: Criação da árvore.
Na Figura 33 ilustra o fluxograma do processo da criação da árvore:
Figura 33: Fluxograma da criação da árvore.
52
Segue o apêndice da criação da árvore ilustrado na figura 34.
Figura 34: Código da criação da árvore.
C) Criação da tabela de Codificação
• Entrada: Árvore binária;
• Saída: Tabela de Codificação;
• Processo: Tem como objetivo criar uma tabela de codificação a partir da árvore
biária. Para que a tabela seja preenchida, inicialmente a árvore é percorrida, e
para cada folha encontrada, é preenchida uma linha da tabela. A tabela apresenta os seguintes campos:
• Token: Símbolo encontrado na folha;
53
• Qtd-Bit: Quantidade de bits, que é representado pela quantidade de nós que
percorreu até chegar a folha;
• Freq: Frequência do símbolo encontrado na folha;
• Code-Bit: Código binário, é representado por zeros e uns, sendo que para cada
nível em que a árvore desce é atribuído um valor zero (0) caso a árvore for para
a direita e um (1) caso a árvore vá para a esquerda.
Segue abaixo o fluxograma do processo ilustrado na Figura 35:
Figura 35: Fluxograma da criação da tabela codificada.
54
O código da tabela codificada, ilustrado na figura 36, foi criado com base na recursividade, sendo que para cada recursão, o caminho da árvore é percorrido para
direita ou para a esquerda, até chegar a uma folha. Ao chegar à folha, o elemento
encontrado é preenchido na tabela com os dados obtidos no caminho da árvore.
Figura 36: Código da criação da tabela codificada
55
D) Codificação
• Entrada: Tabela Codificada e o arquivo compactado pela transformada;
• Saída: Arquivo compactado, arquivo com a tabela codificada;
• Processo: Essa é a fase em que os dados do arquivo de entrada são transformados em representações menores, a partir da tabela de codificação criada na
etapa anterior.
A codificação é feita a partir dos seguintes passos:
1. Lê-se um símbolo no arquivo de entrada, caso não tenha mais símbolos no arquivo, passa-se ao passo 5, caso contrário passa-se ao passo 2.
2. Procura-se o símbolo na tabela.
3. Atribue-se ao “buffer ” o Code-Bit, bit por bit, caso o “buffer ” chegue a seu limite
passa-se ao passo 4, Caso contrário, mantêm-se a distribuição do Code-Bit ao
“buffer”. Quando o Code-Bit acabar, retorna-se ao passo 1.
4. Escreva-se no arquivo de saída o “buffer”.
5. Armazena-se em um arquivo a tabela codificada e finalize-se o processo.
Segue abaixo o fluxograma do processo ilustrado na Figura 37:
56
Figura 37: Fluxograma da codificação.
57
Após este processo, a etapa de compactação termina por completo e tem como
saída um arquivo binário com os dados compactados e uma tabela codificada para
que seja possível a recuperação dos dados originários.
A seguir um apêndice do código da codificação:
Figura 38: Código da codificação.
58
5.3.2
Descompactação
Nos próximos subitens será abordado todo o processo de descompactação desde
a entrada do arquivo compactado até a saída do arquivo com dados puros.
5.3.2.1
Decodificação de Huffman
A decodificação de Huffman é a etapa que tem como entrada, um arquivo compactado gerado pelo algoritmo e um arquivo com a tabela de codificação referente ao
arquivo compactado. A saída desta etapa é um arquivo descompactado, porém os dados desse aquivo ainda não são os orginais, e por isso devem passar posteriormente
pela decodificação da Transformada Wavelet de Haar para obter os mesmos.
Essa etapa inicialmente tem como objetivo reconstruir a tabela de codificação e a
árvore binária, para que seja possível retroceder o processo de compactação.
A) Reconstrução da Tabela Codificada
• Entrada: Arquivo com a tabela codificada;
• Saída: Tabela codificada;
• Processo: O arquivo de entrada com a tabela codificada é lido, tal que para
cada leitura feita é inserida uma linha na tabela. Quando a leitura chega ao final
do arquivo a tabela é totalmente reconstruída na memória.
Segue abaixo o fluxograma da decodificação de Huffman:
Figura 39: Fluxograma da reconstrução da tabela codificada.
59
Segue abaixo o código da reconstrução da tabela codificada.
Figura 40: Código da reconstrução da tabela codificada.
B) Reconstrução da Arvore Binária
• Entrada: Tabela codificada;
• Saída: Árvore binária;
• Processo: Essa é uma etapa muito importante no processo da decodificação,
pois é a árvore binária que irá identificar os códigos no arquivo compactado e
transformá-los em símbolos.
Nesta etapa inicialmente processa-se os dados de cada linha da tabela, tal que
para cada linha processada é criado um caminho na árvore, onde na folha ocorre o
armazenado do símbolo e de sua frequência.
60
Fluxograma do processo acima está ilustrado na Figura 41:
Figura 41: Fluxograma da reconstrução da árvore binária de decodificação
O código da reconstrução da árvore binária de decodificação é representado pela
Figura 42 e 43.
61
Figura 42: Código da reconstrução da árvore binária de decodificação, parte 1
62
Figura 43: Código da reconstrução da árvore binária de decodificação, parte 2
63
C) Decodificação
• Entrada: Arquivo compactado e a árvore binária;
• Saída: Arquivo descompactado;
• Processo: Ao implementar este processo, foi identificado uma limitação da linguagem utilizada no projeto, pois a mesma não tem suporte para a identificação
de um único bit. Com isso houve a necessidade de buscar novas alternativas,
como a máscara variável que será descrita ao decorrer do projeto.
O processo inicia-se fazendo várias leituras no arquivo compactado até que ele
chegue ao seu fim. Para cada leitura no arquivo, um “buffer” de 8 bits é preenchido,
que por sua vez é feita uma comparação com uma máscara variável para que seja
identificado se o bit é um ou zero.
A máscara variável é uma estratégia para a identificação do bit. Ela tem um
tamanho equivalente de 8 bits, que pode representar valores de 0 (00000000 representação binária) a 255 (11111111 representação binária), porém na estratégia foram
utilizados somente valores na potência de 2, como 00000001, 00000010, 00000100,
..., 10000000 na representação binária.
A máscara é criada no momento em que é identificado qual a posição do bit que
será comparado. Inicialmente a máscara está zerada (00000000) e após a identificação da posição é feita a seguinte operação:
M = 1x2 p
para que a posição (p) referente a máscara (M) seja preenchido com um (1). Exemplificando a situação, se a posição for zero (0) a máscara seria 1000000, tendo em
vista que a posição varia de zero a sete.
Após a criação da máscara, é feito uma operação binária AND, tal que se a posição
do “buffer” e da máscara forem iguais, o retorno dessa operação será um (1), caso
contrário zero (0).
Com a identificação do bit, será possível agora percorrer a árvore até chegar a sua
folha e identificar assim o símbolo pelo qual será escrito no arquivo descompactado,
tal que se o bit for identificado o caminho será para a direita, caso contrário será para
a esquerda.
64
Segue a baixo o código de decodificação ilustrado na figura 44.
Figura 44: Código de decodificação.
5.3.2.2
Decodificação da Transformada Wavelet de Haar
• Entrada: Arquivo descompactado pela decodificação de Huffman;
• Saída: Arquivo descompactado com os dados originais ou puros;
• Processo: Inicialmente o arquivo compactado de entrada é lido, tal que cada
símbolo lido é armazenado em um vetor, visto que os símbolos desse arquivo
representa as médias e os coeficientes de detalhamento. Ao chegar no final do
arquivo, o processo de armazenamento no vetor termina e inicia-se a decodificação da transformada Wavelet de Haar que é o processo inverso da decomposição, como vimos no capitulo 4.
65
Segue abaixo o fluxograma ilustradopela Figura 45:
Figura 45: Fluxograma da decodificação da Transformada Wavelet de Haar.
O código da decodificação da Transformada Wavelet de Haar é representado pela
Figura 46.
Figura 46: Código da decodificação da Transformada Wavelet de Haar.
66
6
RESULTADOS, DISCUSSÃO e
CONCLUSÕES
6.1
Resultados e Discussão
Com objetivo de comparar o tempo e a taxa de compressão, foram utilizados 3
arquivos para a avaliação dos resultados referente ao algoritmo criado, sendo que
cada arquivo continha quantidades diferentes de elementos distintos.
A Tabela 9 ilustra os dados obtidos nos testes realizados.
Tabela 9: Resuldos referêntes aos arquivos de teste
Quantidade de Tamanho Orig- Tamanho
Tempo (s)
Taxa de Comelementos dis- inal (KBytes)
Compactado
pressão
tintos
(KBytes)
2
97.657
12.208
52.093615s
87.499%
4
97.657
24.415
55.654067s
74,999%
16
97.657
48.829
68.041140s
50.995%
A relação inversamente proporcional entre a número de elementos distintos e o
tempo gasto para a compactação, ocorreu devido ao uso da codificação de Huffman
uma vez que ela apresenta grande eficiência quando na presença de dados com
menor distinção entre si, reduzindo o tamanho do arquivo e consequentemente requerendo menor tempo de compactação.
Na codificação de Huffman, o tamanho da árvore formada irá representar o tamanho
do código formado para cada caracter. Assim, quanto maior a quatidade de símbolos
distintos, maior será sua a representação. Com isso, a busca pela determinação exata
do símbolo levará maior tempo.
O aumento da aproximidade entre os valores dos dados, possibilitado pelo uso da
Transformada Wavelet de Haar, levou ao aumento da taxa de compressão, revelando
a eficiência das técnincas quando em associação.
67
6.2
Conclusão
Conforme os resultados apresendados, o algoritmo criado apresentou uma excelente compactação dos dados, podendo atingir 87% da taxas de compressão, entretanto esse valor é diretamente proporcional ao tempo gasto e à variação da quantidade
de elementos distintos do arquivo.
68
7
CONCLUSÃO
O conhecimento de compressão de dados surgiu com as pesquisas de criptografia,
pois a compactação é um esquema de codificação aplicado a uma fonte de informação
de modo que a saída seja menor que os dados originais de entrada.
Todo esse processo, mesmo fora das aplicações computacionais, há muito tempo
faz parte do cotidiano. Mas com o advento dos computadores digitais, a compactação
de dados passou a ser obrigatória, pois houve a necessidade de se otimizar o espaço
em disco e reduzir o tempo de transmissão dos dados.
Embora atualmente, os meios de armazenamento e de transmissão de dados dos
computadores contemporâneos seja bastante alto, ainda faz-se necessário o desenvolvimento de algoritmos de compressão cada vez mais eficientes, pois o software
atual é muito robusto, ocupando mais espaço em disco, e as informações por ele manipuladas demasiadamente volumosas, exigindo muito dos meio de armazenamento
e de transmissão.
A Transformada Wavelet de Haar apesar de ser eficiente na compressão de imagem, áudio e vídeo, apresenta correlação também com os arquivos texto, entretanto
a decomposição dos coeficientes utilizado pela mesma, tem como objetivo tornar a
representação dos valores referêntes aos símbolos mais próximos. Já a codificação
de Huffman revela-se muito eficiente para dados com uma menor quantidade de elementos ditintos, obtendo altas taxas de compressão.
Conclui-se que as técnicas utilizadas se mostraram eficiente quando associadas,
uma vez que uma complementou a outra favorecendo o desfecho pretendido nesse
projeto.
69
8
REFERÊNCIAS
[1] SALOMON, David. A Concise Introdution to Data Compression. Undergraduate
Topics in Computer Science. 2008.
[2] GONZALEZ, Rafael C. WOODS, Richard E. Processamento digital de imagens.
Edição 3a . São Paulo - SP. Editora Pearson Prentice Hall. 2009
[3] PINTO, Wilson Silva. Introdução ao desenvolvimento de algoritmos e estrutura
de dados. São Paulo-SP. Edição 6a. Editora Érica Ltda. 1990 152p.
[4] SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de dados e seus
Algoritmos. Editora LTC - Livros Técnicos e Científicos. Rio de Janeiro - RJ. 1994.2079p.
[5] INTERNET, GRAPS, Amara, Historical Perspective [online] 1995 - 2004 [Disponível
na Internet] htt p : //www.amara.com/IEEEwave/IWh istory.html
[6] SCHILDT, Herbert. Borland C++ Completo e Total. Trad Jeremias René Descartes
Pereira dos Santos. Editora Makron Boocks. São Paulo-SP. 1997. 1114p.
[7] INTERNET, PINHEIRO, José Mauricio Santos, Técnicas de Compactação e
Compressão [online] 2004 [Disponível na Internet]
[8] INTERNET, SANCHES, Ademir Martinez. Um estudo de compactação de dados, com a implementação do método de LZW [online] 2001 [Disponível na Internet]
www.comp.uems.br/trab/p f c/downloads/2001 − 1.pd f
[9] MULLER, Daniel Nehme. Compressão de dados, [on line] 2000 [citado em 18
06 01] Disponível na Internet:< http://www.ulbra.tche.br/ danielnm/ed/E/polE.html >
[10] TENENBAUM, Aeron M.; LANGSAM, Yedidyah; AUGENSTEIN ,Moshe J.; Estruturas de Dados Usando C. Trad Teresa Cristina Félix de Souza. Edição 1. Editora
Makron Books do Brasil Editora Ltda. São Paulo-SP 1995 884p.
[11] Internet, Wikipédia [Diponível na Internet] htt p : //pt.wikipedia.org/wiki/ASCII
70
[12] VELLOSO, Paulo. Estruturas de Dados. Rio de Janeiro: Ed. Campus, 1991
[13] OLIVEIRA, Hélio Magalhães. ANALISE DE FOURIER E WAVELETS: sinais
estacionários e não estacionários. 1 ed. [S.l.]: Editora universitária UFPE, 2007. 342
p.