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: C_e N, onde C_e é 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: C_e C N, onde C_e é 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: C_e (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.