Carregando Pesquisa
YouTube Facebook Twitter
Apostilas Artigos Tutoriais Aulas Blog Ferramentas de Rede Fórum Downloads Colabore Fale Conosco
» artigos
:: Técnicas de Compactação e Compressão

José Mauricio Santos Pinheiro em 22/09/2004

 

A evolução dos sistemas de telecomunicações trouxe uma substancial redução nos custos e aumento da capacidade de processamento e transmissão, contribuindo na melhora do tráfego de dados entre as redes de computadores, como também disponibilizou recursos para a interação on-line através da Internet.

Em conseqüência, o crescimento da Internet e o uso cada vez maior das redes locais de computadores estão criando uma necessidade cada vez maior de comprimir arquivos de dados. Nesse aspecto, a melhoria da eficiência das redes está fortemente associada à evolução das tecnologias de compactação e compressão de dados. Poupar espaço em disco e poupar tempo on-line em conexões telefônicas são os principais benefícios.

Compactação de Dados

Uma característica comum dos sinais gerados em redes de comunicação é que, em sua forma básica, esses sinais contém uma quantidade significativa de informação redundante, cuja transmissão acaba por desperdiçar importantes recursos na banda de comunicação.

Para uma transmissão mais eficiente, devem-se eliminar do sinal essas informações redundantes antes da transmissão. Essa operação, sem perda de informação, é realizada normalmente sob a forma digital, sendo denominada de compactação ou compressão de dados sem perdas.

O código resultante dessa operação fornece um sinal eficiente em termos do número médio de bits por símbolo, sendo uma representação exata da informação original que poderá ser reconstruída no destino sem qualquer perda. Basicamente, essa compactação de dados é obtida atribuindo-se descrições breves para as combinações de sinais mais freqüentes e descrições mais longas para as menos freqüentes.

Compressão de Dados

A compressão de dados envolve uma redução intencional ou inevitável no conteúdo da informação dos dados transmitidos. A compressão é essencial para que as informações ocupem menor espaço em unidades de disco e que possam ser transmitidas através dos sistemas de comunicação com taxas razoáveis de transmissão.

Embora a utilização mais conhecida da compressão de dados seja a redução do espaço físico ocupado por arquivos, comprimir dados não é somente reduzir o tamanho do arquivo. A redução do espaço físico é mais comumente utilizada em bancos de dados que, incorporando a compressão no projeto de seus registros, permite um significativo ganho em termos de ocupação em disco e velocidade de leitura dos dados.

A compressão também é utilizada para agilizar a transmissão de dados basicamente de duas formas: alterando a taxa de transmissão e permitindo o aumento no número de terminais de uma rede. Por exemplo, um modem que opera a uma taxa de 9600bps pode transmitir com uma taxa de 14400bps desde que ele permita a compressão dos dados transmitidos, ampliando sua capacidade de transferência de informação. Na verdade, o modem continuará transmitindo a uma taxa de 9600bps, mas a taxa de transferência de informação estará ampliada para 14400bps.

Outra vantagem da compressão, derivada do aumento de velocidade, é a possibilidade de expansão de uma rede de computadores. Como a ampliação do número de hosts de uma rede pode ocasionar queda no desempenho devido ao aumento do tráfego de dados, torna-se necessária uma transmissão mais rápida desses dados. Há, portanto, duas alternativas: trocar os equipamentos ativos da rede ou incorporar um algoritmo de compressão aos equipamentos existentes (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, sempre associada às técnicas de cabeamento estruturado.

Assim, através da redução do espaço físico proporcionado pela técnica de compressão, obtém-se um significativo ganho em termos de ocupação em disco e velocidade de acesso, além da possibilidade de atender expansões da rede.

Tipos de Compressão

A compressão de dados é uma forma de codificar um grupo de informações de maneira que o código gerado seja menor que o código fonte. O uso de técnicas de compressão de dados é variado e extenso nos sistemas de comunicação atuais. As aplicações são inúmeras, tanto em hardware quanto em software, e os codificadores podem ser classificados em dois tipos básicos: com perda ou sem perda de informação.

Os codificadores com perda de informação são normalmente conhecidos como quantizadores, pois a informação original é submetida a um processo de quantização, permitindo altas taxas de compressão ao custo da perda de fidelidade de informação. Já os algoritmos sem perda, conhecidos como codificadores universais, mantém a integridade da informação codificada, porém as taxas de compressão são visivelmente mais modestas, devido ao limite entrópico da mensagem. A entropia de uma mensagem pode ser caracterizada como a quantidade real de informação existente. Dentre os tipos de compressão destacam-se:

Compressão Lógica - Refere-se ao projeto de representação otimizada de dados. Um exemplo é o projeto de um banco de dados utilizando seqüências de bits para a representação de campos de dados. No lugar de seqüências de caracteres ou inteiros, utiliza-se bits, reduzindo significativamente o espaço de utilização do banco de dados. Este tipo de compressão é possível de ser efetivada em campos projetados para representar dados constantes, como datas, códigos e quaisquer outros campos formados por números. A característica lógica da compressão encontra-se no fato dos dados já serem comprimidos no momento do armazenamento, não ocorrendo sua transformação de dados estendidos para comprimidos;

Compressão Física - É realizada sobre dados existentes, a partir dos quais é verificada a repetição de caracteres para efetivar a redução do número de elementos de dados.

Compressão Estatística - A idéia é realizar uma representação otimizada de caracteres ou grupos de caracteres. Caracteres de maior freqüência de utilização são representados por códigos binários pequenos, e os de menor freqüê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. 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.

Antes da discussão das técnicas de compressão propriamente ditas, é necessário esclarecer como são codificados os caracteres especiais a serem substituídos pelos caracteres repetidos neste tipo de compressão física. Há basicamente três formas de representação: run-length, run-length estendido e inserção e deleção:

Codificação run-length - Quando temos a ocorrência de uma repetição contínua de determinado caractere, por exemplo, AAAAAAAAAAAA, é possível sua representação através da codificação run-length da seguinte forma: Ce 12 A, onde A é o caractere repetido 12 vezes, o que é indicado pelo caractere especial Ce. O caractere especial é um daqueles caracteres não-imprimíveis do código ASCII, por exemplo. Cabe salientar que esta codificação ocupa somente 3 bytes;

Codificação run-length estendido - A diferença para o run-length simples é que há caracteres delimitadores no início e no fim da seqüência de codificação: SO R A 980 SI, onde SO (shift out) é um caractere especial indicador de início de uma seqüência de caracteres definida pelo usuário até que SI (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;

Codificação por inserção e deleção - Há determinados casos que os caracteres especiais utilizados conflitam com outros aplicativos. Desta forma, utiliza-se um caractere convencional como indicador de compressão. Como na língua portuguesa utilizam-se muito pouco as letras K, W, Y, pode-se, por exemplo, indicar a compressão de um arquivo de texto na forma: K 12 A.

Compressão Orientada a Caractere

As técnicas de compressão orientadas a caractere não são as mais eficientes ou as mais sofisticadas. Pelo contrário, em geral elas são utilizadas em um primeiro nível de compressão multinível, onde os demais níveis podem ser técnicas estatísticas de compressão.

Supressão dos Caracteres Nulos – É uma das técnicas mais simples de compactação de dados que tem como objetivo comprimir apenas os caracteres nulos ou brancos. Consiste em criar uma seqüência de dois caracteres que não serão usadas no resto do texto e usá-la para marcar onde estará o caractere seguido um byte com o número de caracteres repetidos. Em geral, são comprimidos caracteres correspondentes ao espaço em branco. Para a compressão, utiliza-se a seleção de caracteres indicadores: Ce N, onde Ce é um caractere especial e N é o número (em binário) de caracteres brancos repetidos seqüencialmente. Observar que, por usar três bytes para marcar seqüências, este método é ineficiente para dados com menos de três bytes;

Mapeamento de Bit - Esta técnica é usada quando é sabida a existência de múltiplas ocorrências não consecutivas de determinado caractere no arquivo a comprimir, por exemplo, seqüências de números misturadas com letras. Esta técnica utiliza-se de um byte no arquivo comprimido para indicar, através dos bits, a ocorrência do caractere repetido. Desta forma, caso desejarmos comprimir todos os caracteres de uma determinada letra de um texto, devemos indicá-lo no mapa de bits. Cada mapa descreve 8 bytes, um por bit do arquivo manipulado. Portanto, para letra encontrada a cada trecho de 8 bytes, será assinalada no mapa de bits. Funciona com o uso de um caractere para marcar o inicio e outro para o fim da compactação e os dados dentro dos parâmetros são escritos em 4 bits;

Comprimento da Fileira – Semelhante a Supressão de Caracteres Nulos, este método serve para compactar qualquer seqüência. Usa como principio dois caracteres que não são usados no arquivo, para indicar repetição, o caractere a ser repetido e o número de vezes a repetir. O formato permite a determinação do caractere repetido: Ce C N, onde Ce é o caractere especial, C é o caractere repetido e N é o número (binário) de repetições. Como se pode perceber, esta técnica também permite apenas a compressão de um caractere por vez;

Compactação de Meio Byte - Este tipo de compactação é utilizado quando encontramos uma seqüência de bits em comum nos caracteres de determinado arquivo. Um tipo de repetição de bits de grande ocorrência é a que acontece em caracteres numéricos. A técnica consiste em substituir um par de caracteres por um caractere especial. Parte do principio que existam dois caracteres bastante comuns e um caractere que não é usado em lugar nenhum, substituindo-se então um pelo outro. Por exemplo, se observarmos o conjunto binário da tabela ASCII para os caracteres numéricos, se isolarmos os primeiros 4 bits de cada byte de caractere numérico, veremos que há uma constância de valores. Estes valores constantes são um exemplo de objetos de compactação de meio byte. A compactação de meio byte consiste na seguinte seqüência de caracteres indicadores: Ce (1 byte), N Cn (1 byte), C2 C3 (1 byte), C4 C5, onde Ce é o caractere especial, N é o número (binário) de caracteres comprimidos e Cn é a metade do caractere comprimido. Na seqüência apresentada são representados 5 caracteres porque este é o mínimo para que a compressão seja válida, uma vez que até 4 caracteres ela necessita um número de byte igual ou maior;

Compactação de Byte Inteiro - Estende o formato da compactação de meio byte para permitir a compactação de uma seqüência maior de caracteres. Nesse caso, o número N ocupa 1 byte, ao invés de meio. Neste formato estendido, o restante dos caracteres indicadores permanecem os mesmos, sendo alterada apenas a representação do número de caracteres. Com a representação de byte inteiro, a capacidade de compressão aumenta permitindo um ganho expressivo em se tratando de longas seqüências de caracteres;

Codificação Relativa - Esta técnica de compressão é realizável quando existe a transmissão de seqüências de caracteres numéricos. Estas seqüências podem ser valores dentro de intervalos definidos ou valores binários (para cada um dos casos existe um processamento adequado aos tipos de valores envolvidos).

Codificação Diatômica - Esta técnica de compressão permite a representação de um par de caracteres em apenas um caractere especial. Normalmente utilizam-se tabelas com pares de caracteres e sua freqüência de ocorrência em determinado tipo de arquivo. Obviamente procura-se substituir os caracteres de maior freqüência, associando a cada dupla um caractere especial;

Substituição de Padrões - É semelhante à codificação diatômica, pois também ocorre a substituição de um conjunto de caracteres por um caractere especial, com a diferença de que é avaliado um número maior de caracteres. Desta forma, são estabelecidas tabelas de palavras de maior freqüência de ocorrência para substituição com o caractere especial. A utilização mais comum para este tipo de compressão é a de arquivos de programas de linguagens de programação.

Codificação Huffman

Esta técnica de compressão permite a representação em forma binária de caracteres a partir de sua probabilidade de ocorrência. Esta representação é gerada por um sistema de decodificação em árvore binária, o que impede a ambigüidade na análise do código.

A ambigüidade, neste caso, refere-se a uma decodificação que permite a confusão com outros caracteres. Por exemplo, determinado caractere C1 tem o código binário 01 e outro caractere C2 tem o código 0100, isto implica que, ao verificarmos a seqüência binária para C2 poderemos estar interpretando como C1, ao serem lidos apenas os bits 01. A codificação Huffman utiliza o projeto em árvore binária para projeto dos bits que representam os caracteres, de forma que permitam uma decodificação única para cada caractere.

Cabe salientar que a codificação Huffman mantém a propriedade de permitir a decodificação direta, não permitindo que os bits da codificação de um caractere confunda com a de outro.

Codificação Shannon-Fano

A forma desta técnica tem muitas semelhanças com a de Huffman. Necessita-se de uma tabela com a probabilidade de ocorrência de cada caractere e de um procedimento para a codificação binária. Por outro lado, o procedimento para a codificação, diferentemente de Huffman, baseia-se na divisão de conjuntos de probabilidades para a obtenção do código binário.

Codificação Lempel-Ziv e CCITT V.42 bis

A codificação Lempel-Ziv utiliza um conjunto de regras para analisar as cadeias de um conjunto de caracteres pré-definido. As cadeias são montadas e codificadas à medida que são lidos os caracteres a codificar.

A codificação Lempel-Ziv é um tipo de compressão de cadeia que forma strings de caracteres a partir de sua ocorrência, criando tabelas de strings conforme estes ocorrem. A forma de composição destas cadeias está descrita na técnica V. 42 bis do CCITT (Consultative Committee for International Telephone and Telegraph), que é utilizada para a compressão na transmissão de dados via modem. Ela baseia-se na codificação em cadeia de Lempel-Ziv, utilizando-se da multiplicação das probabilidades de ocorrência de caracteres, para, em cima das estatísticas de cadeias, permitir a compressão de bits utilizados na transmissão de dados.

 

José Maurício Santos Pinheiro
Professor Universitário, Projetista e Gestor de Redes, 
membro da BICSI, Aureside e IEC.

Autor dos livros:
 
· Guia Completo de Cabeamento de Redes ·
· Cabeamento Óptico ·
· Infraestrutura Elétrica para Redes de Computadores
·
· Biometria nos Sistemas Computacionais - Você é a Senha ·

E-mail: jm.pinheiro@projetoderedes.com.br

© www.projetoderedes.com.br - Termos e Condições de Uso