Compactação, Compressão de Dados e Estudo dos Algoritmos

de Huffman e Lempel-Ziv-Welch (LZW)

André Hack1

, Daniel Rossi

1

1Universidade Regional do Noroeste do Estado do Rio Grande do Sul (UNIJUI)

Rod RS 344, Km 39 - CEP 98900-000 – Santa Rosa – RS – Brasil

hack_lco@yahoo.com.br, danielrossi88@gmail.com

Resumo. A crescente utilização de sistemas conectados em redes e a

necessidade de transmitir cada vez mais informações através delas nos levam

ao estudo de métodos para diminuição do espaço dos arquivos em memória.

Através destes, existe a possibilidade de pesquisar diretamente o texto

comprimido, sem necessidade de descomprimir todo o texto, gerando maior

economia de tempo e espaço, além de melhorar as taxas na transferência de

dados, especialmente em aplicações distribuídas. Este artigo visa explicar e

exemplificar os conceitos de Compactação e Compressão de Dados, além de

fornecer detalhes acerca dos algoritmos de Huffman e LZW, ambos muito

utilizados para estes fins.

Palavras-chave. Compactação, Compressão, Algoritmo de Huffman, LZW.

1. Introdução

Como parte da constante evolução tecnológica, a manipulação de dados tem exigido

cada vez mais poder de processamento e capacidade de armazenamento. Os

investimentos em ativos de TI podem alcançar valores astronômicos dependendo da

situação, como por exemplo, em empresas de grande porte. A preocupação com o

espaço nos direciona ao estudo de formas de compressão dos dados, o que também

envolve questões como velocidade, integridade e segurança das informações.

Embora possam parecer sinônimos, os termos compressão e compactação de

dados são processos diferentes. Ambos, serão detalhados nos tópicos a seguir.

2. Compactação

Talvez a melhor forma de conceituarmos a compactação de dados é exemplificando o

papel do Desfragmentador de Disco do Windows. Quando realizamos uma alteração em

um arquivo qualquer, dificilmente as mudanças são salvas no mesmo local do arquivo

original no disco rígido. O Desfragmentador vasculha o disco, procurando arquivos

fragmentados, e os une novamente, tornando as atividades do computador mais rápidas

e eficientes. Desta forma, podemos dizer que a compactação de dados é a união de

partes distribuídas dos dados.

3. Compressão

Compressão de um arquivo ou dado é a redução do seu número de bits e bytes, através

da identificação de caracteres repetidos, envolvendo a criação de um dicionário a ser

utilizado pelo programa que fará a extração do arquivo compactado ao seu formato e

tamanho originais.

De forma a demonstrar rapidamente a compactação, vamos compactar a seguinte

frase:

“Às vezes ouço passar o vento; e só de ouvir o vento passar, vale a pena ter nascido.”

Podemos notar que a frase possui 18 palavras, 64 letras, 17 espaços, um sinal

ponto-e-vírgula, uma vírgula e um ponto final. No total, temos 85 unidades de memória

ocupadas. Para diminuir o tamanho do arquivo, devemos procurar redundâncias, ou

seja, ocorrências repetidas de algum destes caracteres:

A palavra “passar” aparece duas vezes;

A palavra “vento” aparece duas vezes;

A palavra “o” aparece duas vezes;

Para construir a frase já reduzida, devemos criar apontadores para as palavras

redundantes e criar um dicionário, onde todos os apontadores são declarados. Na frase

do exemplo, podemos criar o seguinte dicionário:

1. passar

2. vento

3. o

A sentença seria lida da seguinte forma:

“As vezes ouço 1 3 2; e só de ouvir 3 2 1, vale a pena ter nascido.”

Sendo assim, temos uma redução de três palavras no resultado final da

compactação. O dicionário deve obrigatoriamente ser salvo juntamente com o arquivo,

de forma a ser encontrado facilmente pelo programa que fará a extração dos dados.

Apesar de na frase proposta termos identificado somente três palavras redundantes, este

número certamente aumenta significativamente se analisarmos arquivos pesados.

Ao contrário do que possa parecer, a compactação não é aplicada somente à

redução de tamanho de um arquivo, mas também utilizada em bancos de dados,

incorporando-a ao projeto de seus registros. Desta forma, permite um ganho

significativo em termos de ocupação em disco e velocidade de acesso.

Uma forma de tentar resolver esse problema consiste em codificar o conteúdo do

arquivo de maneira apropriada. Para representar um ganho de memória, é necessário

verificar se o arquivo codificado é de fato menor que o original. Como afirma Ziviani

(2007) “o ganho em espaço obtido por um método de compressão pode ser medido pela

razão de compressão, definida pela porcentagem que o arquivo comprimido representa

em relação ao tamanho do arquivo não comprimido”. Este modo de aplicação é o mais

comum e mais difundido comercialmente, pois neste meio se faz necessária a redução

do tamanho dos arquivos para facilitar seu transporte ou simplesmente seu

armazenamento.

Outra utilização é aplicada à transmissão de dados, basicamente utilizando duas

formas. Alterando a taxa de transmissão e permitindo o aumento no número de

terminais de uma rede ampliamos sua capacidade de transferência de informação. Além

disso, é possível expandir uma rede de computadores, o que pode tornar a rede

intermitente. Nesta situação, existem duas possibilidades de melhorias: troca dos

modems, utilizando modelos mais velozes, ou incorporar um chip com algoritmo de

compressão aos modens existentes.

3.1 Compressão Lógica

De acordo com Câmara (2009), a compressão lógica refere-se ao projeto de representação

otimizada de dados. O exemplo citado é o projeto de um banco de dados utilizando sequencias

de bits para a representação de campos de dados. As sequencias de caracteres são substituídas

por bits, reduzindo significativamente o espaço de utilização do banco de dados.

Este tipo de compressão é efetiva em campos projetados para representar dados

constantes, como datas, códigos e quaisquer outros campos formados por números.

3.2 Compressão Física

A compressão física realiza-se sobre dados existentes, a partir dos quais é verificada a repetição

de caracteres, de forma a reduzir o número de elementos de dados. É o caso citado

anteriormente, na redução de palavras redundantes em uma frase.

4. Técnicas de Compressão de Dados

As técnicas de compressão de dados podem ser classificadas em “Com Perdas” e “Sem Perdas”.

Como os próprios nomes sugerem, essas características definem se a compressão dos dados

pode acarretar algum prejuízo ao arquivo original. Detalhamos nos tópicos a seguir as principais

técnicas de compressão:

4.1 Técnicas de Compressão Com Perdas

São utilizadas em áudio, imagens e vídeos, onde erros e perdas são toleráveis devido aos seus

utilizadores serem geralmente humanos. Como os sentidos humanos não são perfeitos, pequenas

perdas e erros em áudios e vídeos não são percebidos. Essas técnicas podem ser baseadas no

algoritmo de compressão ou no resultado das técnicas de compressão. Através das técnicas de

compressão com perdas, altas taxas de compressão podem ser obtidas.

Como exemplos de métodos de compressão com perda de dados, podemos citar alguns

dos mais conhecidos tipos de arquivos: JPEG e JPEG 2000 (ambos para imagens fixas), Flash e

MPEG (animações e filmes), MP3 e WMA (música).

4.2 Técnicas de Compressão Sem Perdas

A compressão é classificada como “Sem Perdas” quando a informação pode ser perfeitamente

reconstruída após sua descompressão. Essa técnica é principalmente utilizada para compressão

de programas e documentos legais ou médicos, e exploram apenas estatísticas de dados

(redundância de dados) e a taxa de compressão é normalmente baixa.

Como exemplos de técnicas sem perdas, podemos citar as seguintes:

Codificação Aritmética – patenteada pela IBM, codifica utilizando um número real

entre 0 e 1. Utiliza um conjunto de probabilidades e necessita de uma precisão extrema.

Codificação de Huffman – de acordo com Dias (2011), baseia-se no probabilismo de

evento dos símbolos no conjunto de dados a ser comprimido para determinar códigos de

tamanho variável para cada símbolo. Foi desenvolvido em 1952 por David A. Huffman,

estudante de doutorado no MIT (Massachussets Institute of Technology).

Codificação Run-Lenght – identifica sequências de caracteres iguais e os substitui por

um número de ocorrências e um símbolo padrão. O exemplo abaixo mostra como um

fluxo de dados pode ser representado ao se utilizar a codificação Run-Lenght,

substituindo a sequência de seis caracteres “C” por “!6C”:

o Dado Original – ACCCCCC5667

o Dado comprimido – A!6C5667

Essa técnica não é utilizada para sequências de caracteres iguais ou menores que

quatro, pois nenhuma compressão seria obtida neste caso devido à utilização obrigatória

de alguns caracteres especiais.

5. Codificação de Huffman

Conforme citado anteriormente, baseia-se no probabilismo de evento dos símbolos no conjunto

de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo.

Permite acesso randômico às palavras dentro do texto comprimido, um aspecto crítico para

sistemas de recuperação de informação, como na pesquisa em páginas da web ou documentos.

A codificação para cada caractere deve ter um prefixo único. Este método serve para casos em

que não se deseja a perda de dados.

Temos como exemplo a situação de compressão da seguinte sequência de caracteres:

AAABBBCCD

Devemos criar um dicionário para armazenar os códigos de cada caractere, portanto

temos:

Caractere A B C D

Código 000 001 010 011

Gera-se assim a seguinte sequência de 27 bits para representar a sequência original:

000000000001001001010010011

Para usar o código Huffman e comprimir esta sequência, é necessário primeiro montar

uma árvore de Huffman como base na frequência de ocorrência de cada caractere, a partir dos

dois de menor possibilidade, que são então somados em símbolos secundários, e estes

recolocados no conjunto de símbolos. O processo termina quando todos os símbolos foram

unidos em símbolos auxiliares, formando uma árvore binária. A árvore é então percorrida, são

atribuídos valores binários de 1 ou 0 para cada aresta, e os códigos são gerados a partir desse

percurso.

A codificação de Huffman é um exemplo de técnica de codificação estatística, que diz

respeito ao uso de um código curto para representar símbolos comuns, e códigos longos para

representar símbolos pouco frequentes. É o mesmo princípio utilizado no código morse.

Em seu artigo, Dias gera um arquivo com extensão “.txt”, com a seguinte frase:

“Testando o algoritmo de compressão huffman”. Em seguida, coloca o algoritmo criado na

linguagem Java:

Tabela 1. Algoritmo em Java da Codificação de Huffman.

abstract class HuffmanTree implements Comparable<HuffmanTree> {

public int frequency; // the frequency of this tree

public HuffmanTree(int freq) { frequency = freq; }

public int compareTo(HuffmanTree tree) {

return frequency - tree.frequency;

}

}

class HuffmanLeaf extends HuffmanTree {

public char value; // the character this leaf represents

public HuffmanLeaf(int freq, char val) {

super(freq);

value = val;

}

}

class HuffmanNode extends HuffmanTree {

public HuffmanTree left, right;

public HuffmanNode(HuffmanTree l, HuffmanTree r) {

super(l.frequency + r.frequency);

left = l;

right = r;

}

}

package Huffman.code;

import java.io.BufferedInputStream;

import java.io.DataInputStream;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.util.PriorityQueue;

import java.util.Stack;

import java.util.logging.Level;

import java.util.logging.Logger;

public class HuffmanCode{

// input is an array of frequencies, indexed by character code

public static HuffmanTree buildTree(int[] charFreqs){

PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();

// initially, we have a forest of leaves

// one for each non-empty character

for (int i = 0; i < charFreqs.length; i++)

if (charFreqs[i] > 0)

trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));

assert trees.size() > 0;

// loop until there is only one tree left

while (trees.size() > 1) {

// two trees with least frequency

HuffmanTree a = trees.poll();

HuffmanTree b = trees.poll();

// put into new node and re-insert into queue

trees.offer(new HuffmanNode(a, b));

}

return trees.poll();

}

public static void printCodes(HuffmanTree tree, Stack<Character> prefix) {

assert tree != null;

if (tree instanceof HuffmanLeaf) {

HuffmanLeaf leaf = (HuffmanLeaf)tree;

// print out character and frequency

System.out.print(leaf.value + "\t" + leaf.frequency + "\t");

// print out code for this leaf, which is just the prefix

for (char bit : prefix)

System.out.print(bit);

System.out.println();

} else if (tree instanceof HuffmanNode) {

HuffmanNode node = (HuffmanNode)tree;

// traverse left

prefix.push('0');

printCodes(node.left, prefix);

prefix.pop();

// traverse right

prefix.push('1');

printCodes(node.right, prefix);

prefix.pop();

}

}

public static void main(String[] args) throws IOException {

String arquivo = "C:/teste.txt";

FileInputStream fis = null;

try {

fis = new FileInputStream(arquivo);

} catch (FileNotFoundException ex) {

Logger.getLogger(HuffmanCode.class.getName()).log(Level.SEVERE, null,

ex);

}

BufferedInputStream buffReader = new BufferedInputStream(fis);

DataInputStream data = new DataInputStream(buffReader);

byte[] b = new byte[fis.available()];

data.read(b);

int[] charFreqs = new int[256];

for (char c : new String(b).toCharArray())

{

charFreqs[c]++;

}

// build tree

HuffmanTree tree = buildTree(charFreqs);

// print out results

System.out.println("SYMBOL\tWEIGHT\tHUFFMAN CODE");

printCodes(tree, new Stack<Character>());

}

}

6. Codificação de Lempel-Ziv-Welch (LZW)

Criada em 1977 por Abraham Lempel e Jacob Ziv, a compressão LZW é utilizada na

compressão de textos e programas. Os algoritmos de compressão LZ78 são usados na

compressão de dados binários.

O LZW é um algoritmo que constrói um dicionário dos dados originais, também

chamado de tabela de tradução. Os padrões dos dados são identificados e registrados no

dicionário, e caso não esteja presente, é codificado e registrado no mesmo. Sendo um dos

algoritmos de compressão mais utilizados atualmente, é encontrado em vários formatos de

imagem, como o GIF, TIFF e PDF.

Em seu trabalho, Pereira mostra um simples algoritmo para entendimento de como

funciona a codificação de LZW.

Tabela 2. Codificação de LZW - Compactação.

1. No início o dicionário contém todas as raízes possíveis e P é vazio; 2. C <= próximo caracter da sequência de entrada; 3. A string P+C existe no dicionário?

a. Se sim, i. P <= P+C;

b. Senão, i. Coloque a palavra código correspondente a P na sequência

codificada; ii. Adicione a string P+C ao dicionário;

iii. P <= C; 4. Existem mais caracteres na sequência de entrada?

a. Se sim, i. Volte ao passo 2;

b. Senão, i. Coloque a palavra código correspondente a P na sequência

codificada; ii. FIM.

Tabela 2. Codificação de LZW - Descompactação.

1. No início o dicionário contém todas as raízes possíveis; 2. cW <= primeira palavra código na sequência codificada (sempre é uma raiz); 3. Coloque a string (cW) na sequência de saída

4. PW <= cW; 5. cW <= próxima palavra código da sequência codificada; 6. A string (cW) existe no dicionário?

a. Se sim, i. Coloque a string (cW) na sequência de saída;

ii. P <= string (pW); iii. C <= primeiro caracter da string (cW); iv. Adicione a string P+C ao dicionário;

b. Senão, i. P <= string (pW);

ii. C <= primeiro caracter da string (pW); iii. Coloque a string P+C na sequência de saída e adicione-a ao dicionário;

7. Existem mais palavras código na sequência codificada? a. Se sim,

i. Volte ao passo 4; b. Senão,

i. FIM.

Entretanto, podemos citar duas desvantagens, que seriam na recuperação de informação.

A primeira desvantagem é a necessidade de iniciar a decodificação desde o início do arquivo

comprimido, o que torna o acesso randômico muito caro. A segunda desvantagem é a

dificuldade de pesquisa ao arquivo sem ser necessário descomprimi-lo.

A tabela abaixo compara a compressão de dados entre a codificação de Huffman e de

LZW:

Tabela 3. Comparativo de compressão entre as codificações de Huffman e LZW.

Huffman LZW

Arquivo de Texto 66% 44%

Arquivo de Som 65% 64%

Arquivo de Imagem 94% 88%

7. Referências Bibliográficas

Ziviani, N. (2007) “Projetos de Algoritmos – Com Implementações em Java e C++”,

Cengage Learning, Primeira Edição.

Szwarcfiter, J. L. and Markenzon, L. (1994) “Estruturas de Dados e Seus Algoritmos”,

LTC, Segunda Edição.

Cunha, G., Pereira M., “Algoritmos de Compactação”. Disponível em:

<http://www.slideshare.net/mateuspioneiro/trabalho-estrutura-de-dados-algoritmos-de-

compactao?from_search=1>. Data de acesso: 05 de junho de 2013.

Câmara, M. (2009) Criptografia e Compreensão de Dados. Universidade Católica de

Salvador – UCSal.

Dias, D. (2011) “Algoritmo de Compressão Huffman”. Universidade Federal do Oeste

do Pará - UFOPA.