A compressão de dados permite o envio de um objecto de dados ou ficheiro por uma rede ou pela Internet de forma rápida, optimizando os recursos físicos de armazenamento. Aplicada amplamente nos serviços e soluções de computação, mais especificamente nas comunicações de dados. A compressão de dados funciona através de várias técnicas de compressão e soluções de software que usam algoritmos de compressão de dados com o intuito de reduzir o tamanho dos dados.
Uma técnica de compressão comum elimina e substitui elementos de dados repetitivos e símbolos para reduzir o tamanho dos dados. Para dados gráficos, a compressão de dados pode ser feita com ou sem perdas, sendo que a primeira opção guarda todas as substituições feitas salvando também todos os dados repetidos e a última elimina todos os dados repetidos.
Compressão baseada em qualidade
Sem perdas. Tal como o nome indica, na compressão sem perdas não há perda de informação, por exemplo os dados reconstruídos são idênticos aos originais. É utilizada em aplicações onde a perda de informação é indesejável como texto, imagens médica, direito forense, imagens militares, imagens de satélite, etc. As técnicas de compressão quase sem perdas são um outro tipo de técnicas de compressão onde as diferenças entre os valores dos dados originais e reconstruídos diferem entre si. No entanto, esta diferença é controlada pelo utilizador, uma vez que este especifica um valor máximo denominado “distorção máxima absoluta” (MAD). É usada na compressão de imagens médicas, imagens hiperespectrais, vídeos, etc.
Com perdas. Em alguns casos, o uso de técnicas de compressão com perdas são preferíveis. Neste tipo de compressão, os valores dos dados reconstruídos não correspondem de forma perfeita aos dados originais sendo a aproximação destes considerada também uma opção aceitável.
Compressão baseada em esquemas de codificação
Codificação de Huffman. A codificação de Huffman é uma técnica de codificação famosa que comprime os dados em quase todos os formatos, de forma eficiente. É um tipo de código prefixo optimizado que é usado vastamente em compressão de dados sem perdas. A ideia chave passa por designar códigos de comprimento variável a caracteres inseridos, dependendo da frequência de ocorrência. O resultado é uma tabela de código de comprimento variável para codificar um símbolo de origem. É descodificado unicamente e consiste em dois componentes, como a construção da árvore de Huffman a partir de uma sequência inserida e percorrendo a árvore de forma a designar códigos e caracteres. A codificação de Huffman ainda é popular devido à sua simplicidade de implementação, compressão mais rápida e à inexistência de cobertura de patente.
Codificação aritmética. A codificação aritmética é outra importante técnica de codificação na criação de códigos de comprimento variável. É superior á codificação de Huffman e é muito útil em situações em que a fonte contém pequenos alfabetos com probabilidades distorcidas. Uma vantagem da codificação aritmética em relação à codificação de Huffman é a capacidade de segregar a modelação e as funções de codificação da técnica de compressão. Quando uma linha de caracteres é codificada recorrendo à codificação aritmética, símbolos que ocorrem com maior frequência são codificados com um menor número de bits e vice-versa. Não é tão fácil de implementar quando comparada com outros métodos. Existem duas versões de codificação aritmética, nomeadamente a Codificação Aritmética Adaptativa e Codificação Aritmética Binária.
Baseada em dicionário. As abordagens de codificação baseada em dicionário são especialmente úteis em situações em que os dados originais contêm maior número de padrões repetidos. Quando um padrão é verificado na sequência de entrada, este é codificado com um índice associado ao dicionário. Quando o padrão não está disponível no dicionário então é codificado através de abordagens não menos eficientes. Pode ser dividida em duas classes, tais como padrões que ocorrem frequentemente ou raramente. Este método será eficiente pois considera uma palavra de código mais curta para padrões que ocorrem frequentemente e vice-versa. Os dois tipos de dicionários disponíveis são o estático e o dinâmico. O dicionário estático é útil quando o conhecimento prévio do output de origem está disponível. Quando esta informação não existe, será então utilizado o dicionário dinâmico. O algoritmo Lempel-Ziv (LZ) é uma técnica de codificação baseada em dicionário normalmente utilizada em compressão de ficheiros sem perdas. É muito utilizada devido à sua adaptabilidade a vários formatos de ficheiros. Procura padrões que ocorrem frequentemente, substituindo-os por um único símbolo. Preserva um dicionário destes padrões e o comprimento do dicionário é definido para um valor particular. Este método é muito mais eficiente para ficheiros maiores do que para ficheiros com menores tamanhos. Em 1977 e 1978, duas versões do LZ foram desenvolvidas por Ziv and Lempel denominadas LZ77 e LZ78. Estes algoritmos variam significativamente em termos de procura e descoberta de correspondências. O algoritmo LZ77, utiliza o conceito de janela deslizante procurando resultados numa janela dentro de uma distância pré-determinada atrás da actual posição. O algoritmo LZ78 segue uma abordagem mais conservadora de linhas de caracteres anexadas ao dicionário. Lempel-Ziv-Welch (LZW) é uma versão melhorada dos algoritmos LZ77 e LZ78. O codificador constrói um dicionário adaptável para caracterizar as linhas de caracteres de comprimento variável sem conhecimento prévio do input. O descodificador também constrói um dicionário semelhante ao criado pelo codificador baseado no código recebido de forma dinâmica. Compressão UNIX, imagens GIF e PNG bem como outros formatos de ficheiro utilizam a codificação LZW enquanto a LZ77 é usada em Gzip e ZIP.
Transformação de Burrows-wheeler. A transformação de Burrows-Wheeler (BWT) é uma técnica de compressão de selecção de blocos que reorganiza a linha de caracteres em execuções de caracteres idênticos. Utiliza duas técnicas para comprimir dados: transformação “move-to-front” e RLE. Comprime dados facilmente em situações em que a linha de caracteres consiste em execuções de caracteres repetidos. É usada para comprimir dados em bzip2.
Compressão Fractal. A compressão fractal é uma das técnicas de compressão com perdas utilizada na compressão de imagens digitais usando fractais. É altamente apropriada para texturas e imagens naturais, baseada no facto de que partes de uma imagem muitas vezes se assemelham a outras partes dessa mesma imagem. Os algoritmos fractais transformam partes semelhantes em dados matemáticos conhecidos como códigos fractais que são utilizados na geração da imagem codificada. A representação de uma imagem fractal pode ser definida matematicamente como um sistema de função iterativa (IFS). Algoritmos de compressão de imagens fractais apresentam duas fases: segmentação de imagem e codificação. Na primeira fase, a imagem é segmentada em partes e estas partes são individualmente codificadas pelas probabilidades IFS.
Quantização escalar e vectorial. Quantização é o processo de restringir algo de um conjunto de valores relativamente grande ou contínuo (como os números reais) a um conjunto relativamente pequeno ou discreto (como os inteiros). A quantização escalar é uma das ideias mais simples e generalistas no que toca à compressão com perdas. A quantização escalar é um mapeamento de um valor de entrada “x” num número finito. Muitas das ideias fundamentais acerca da quantização e compressão são facilmente apresentadas no simples contexto da quantização escalar. A quantização vectorial é um tipo diferente de quantização, que é tipicamente implementada ao selecionar um conjunto de representativos do espaço de entrada, mapeando todos os outros pontos no espaço do representativo mais próximo. Os representativos poderão ser fixados para todo o sempre e parte do protocolo de compressão ou poderão ser determinados para cada ficheiro (sequência de mensagem) e enviada como parte da sequência.
Codificação de tiragem. A codificação de tiragem (RLE) é uma forma muito simples de compressão de dados em sequências de dados repetidos (repetição de linhas de caracteres). São armazenadas em duas partes: um único valor de dados e a contagem, ao invés da execução original. Torna-se bastante útil em dados que contêm muitas repetições: por exemplo, imagens gráficas simples, tais como ícones, desenhos de linhas e animações. Não é útil em ficheiros que não têm muitas repetições visto que tal facto pode aumentar de forma significativa o tamanho do ficheiro.