O que é compactação de dados sem perdas?

A compactação sem perda de dados é um método computacional de armazenar arquivos e combiná-los em arquivos que ocupam menos espaço físico na memória do que os arquivos teriam, sem perder as informações que os dados contêm no processo. A compactação com perdas, por outro lado, reduz o tamanho do arquivo com aproximações dos dados e a restauração é um fac-símile próximo ao conteúdo original do arquivo. Os algoritmos usados ​​para a compactação de dados sem perdas são essencialmente um conjunto de regras ou instruções simplificadas para codificar as informações usando menos bits de memória, mantendo a capacidade de restaurar os dados para o formato original sem alterações.

Alguns tipos de arquivos comuns que usam compactação de dados sem perdas incluem os arquivos zip baseados em computador da International Business Machines (IBM) e os arquivos gzip baseados em computador Unix. Também são usados ​​os formatos de arquivo de imagem, como o formato de intercâmbio gráfico (GIF), os gráficos de rede portátil (PNG) e os arquivos de bitmap (BMP). Os algoritmos de compactação de dados também variam com base no tipo de arquivo que está sendo compactado, com variações comuns para arquivos de texto, áudio e programas executáveis.

As duas principais categorias de algoritmos para compactação de dados sem perda são baseadas em um modelo estatístico de dados de entrada e um modelo de mapeamento de cadeias de bits em um arquivo de dados. Os algoritmos estatísticos de rotina utilizados são a transformação Burrows-Wheeler (BWT), o algoritmo Abraham Lempel e Jacob Ziv (LZ77) publicado em 1977 e o método Prediction by Partial Matching (PPM). Os algoritmos de mapeamento freqüentemente empregados incluem o algoritmo de codificação Huffman e a codificação aritmética.

Alguns dos algoritmos de compactação de dados sem perdas são ferramentas de código aberto e outros são proprietários e patenteados, embora algumas patentes também já tenham expirado. Isso pode resultar em métodos de compactação às vezes sendo aplicados no formato de arquivo errado. Devido ao fato de que certos métodos de compactação de dados são incompatíveis entre si, o armazenamento de arquivos mistos geralmente pode degradar um componente de um arquivo. Por exemplo, um arquivo de imagem com texto compactado pode mostrar degradação na legibilidade do texto depois de restaurado. Scanners e softwares que empregam indução gramatical podem extrair o significado do texto armazenado junto com os arquivos de imagem aplicando o que é conhecido como análise semântica latente (LSA).

Outra forma de método do algoritmo de mapeamento para compactação de dados sem perdas é o uso de código universal. Mais flexível de usar que a codificação Huffman, não requer conhecimento dos valores máximos inteiros antes do tempo. A codificação de Huffman e a aritmética produzem melhores taxas de compactação de dados. Também estão em andamento esforços para produzir métodos universais de compactação de dados que criem algoritmos que funcionem bem para diversas fontes.