Compressão sem perdas

Compactação sem perdas é uma classe de compactação de dados que permite que os dados originais sejam perfeitamente reconstruídos a partir dos dados compactados sem perda de informações. A compactação sem perdas é possível porque a maioria dos dados do mundo real exibe redundância estatística. Por outro lado, a compactação com perdas permite a reconstrução apenas de uma aproximação dos dados originais, embora geralmente com taxas de compactação bastante aprimoradas (e, portanto, tamanhos de mídia reduzidos).

Pela operação do princípio da casa dos pombos, nenhum algoritmo de compactação sem perdas pode compactar com eficiência todos os dados possíveis. Por esse motivo, existem muitos algoritmos diferentes projetados com um tipo específico de dados de entrada em mente ou com suposições específicas sobre quais tipos de redundância os dados não compactados provavelmente conterão. Portanto, as taxas de compactação tendem a ser mais fortes em documentos e códigos legíveis por humanos e máquinas em comparação com dados binários entrópicos (bytes aleatórios).

A compactação de dados sem perdas é usada em muitos aplicativos. Por exemplo, é usado no formato de arquivo ZIP e na ferramenta GNU gzip. Também é frequentemente usado como um componente em tecnologias de compressão de dados com perdas (por exemplo, pré-processamento estéreo sem perda de meio/lado por codificadores de MP3 e outros codificadores de áudio com perdas).

A compactação sem perdas é usada nos casos em que é importante que os dados originais e descompactados sejam idênticos, ou onde os desvios dos dados originais seriam desfavoráveis. Exemplos típicos são programas executáveis, documentos de texto e código-fonte. Alguns formatos de arquivo de imagem, como PNG ou GIF, usam apenas compactação sem perdas, enquanto outros, como TIFF e MNG, podem usar métodos sem perdas ou com perdas. Os formatos de áudio sem perdas são usados com mais frequência para fins de arquivamento ou produção, enquanto arquivos de áudio menores com perdas são normalmente usados em reprodutores portáteis e em outros casos em que o espaço de armazenamento é limitado ou a replicação exata do áudio é desnecessária.

Técnicas

A maioria dos programas de compactação sem perdas faz duas coisas em sequência: a primeira etapa gera um modelo estatístico para os dados de entrada e a segunda etapa usa esse modelo para mapear os dados de entrada para sequências de bits dessa maneira que "provável" (ou seja, encontrados com frequência) os dados produzirão uma saída mais curta do que "improvável" dados.

Os algoritmos de codificação primários usados para produzir sequências de bits são a codificação de Huffman (também usada pelo algoritmo deflate) e a codificação aritmética. A codificação aritmética consegue taxas de compressão próximas das melhores possíveis para um determinado modelo estatístico, que é dado pela entropia de informação, enquanto a compressão Huffman é mais simples e rápida, mas produz resultados ruins para modelos que lidam com probabilidades de símbolos próximas a 1.

Existem duas formas principais de construir modelos estatísticos: em um modelo estático, os dados são analisados e um modelo é construído, então este modelo é armazenado com os dados compactados. Essa abordagem é simples e modular, mas tem a desvantagem de que o próprio modelo pode ser caro para armazenar e também de forçar o uso de um único modelo para todos os dados que estão sendo compactados e, portanto, ter um desempenho ruim em arquivos que contêm dados heterogêneos. Os modelos adaptáveis atualizam dinamicamente o modelo à medida que os dados são compactados. Tanto o codificador quanto o decodificador começam com um modelo trivial, resultando em uma compactação insatisfatória dos dados iniciais, mas à medida que aprendem mais sobre os dados, o desempenho melhora. Os tipos mais populares de compactação usados na prática agora usam codificadores adaptativos.

Os métodos de compactação sem perdas podem ser categorizados de acordo com o tipo de dados que são projetados para compactar. Embora, em princípio, qualquer algoritmo de compactação sem perdas de uso geral (uso geral, o que significa que eles podem aceitar qualquer bitstring) pode ser usado em qualquer tipo de dados, muitos são incapazes de obter compactação significativa em dados que não são da forma para a qual foram projetados para comprimir. Muitas das técnicas de compactação sem perdas usadas para texto também funcionam razoavelmente bem para imagens indexadas.

Multimídia

Essas técnicas aproveitam as características específicas das imagens, como o fenômeno comum de áreas 2-D contíguas de tons semelhantes. Cada pixel, exceto o primeiro, é substituído pela diferença para seu vizinho esquerdo. Isso faz com que valores pequenos tenham uma probabilidade muito maior do que valores grandes. Isso geralmente também é aplicado a arquivos de som e pode compactar arquivos que contêm principalmente baixas frequências e volumes baixos. Para imagens, essa etapa pode ser repetida tomando a diferença para o pixel superior e, em vídeos, a diferença para o pixel no próximo quadro pode ser tomada.

Uma versão hierárquica desta técnica pega pares vizinhos de pontos de dados, armazena suas diferenças e somas e, em um nível mais alto com resolução mais baixa, continua com as somas. Isso é chamado de transformada wavelet discreta. O JPEG2000 também usa pontos de dados de outros pares e fatores de multiplicação para misturá-los à diferença. Esses fatores devem ser inteiros, para que o resultado seja um inteiro em todas as circunstâncias. Portanto, os valores são aumentados, aumentando o tamanho do arquivo, mas esperamos que a distribuição de valores seja mais pontiaguda.

A codificação adaptativa usa as probabilidades da amostra anterior na codificação de som, do pixel esquerdo e superior na codificação de imagem e adicionalmente do quadro anterior na codificação de vídeo. Na transformação wavelet, as probabilidades também são passadas pela hierarquia.

Questões jurídicas históricas

Muitos desses métodos são implementados em ferramentas proprietárias e de código aberto, particularmente LZW e suas variantes. Alguns algoritmos são patenteados nos Estados Unidos e em outros países e seu uso legal requer licenciamento pelo detentor da patente. Devido às patentes de certos tipos de compactação LZW e, em particular, às práticas de licenciamento do detentor da patente Unisys, consideradas abusivas por muitos desenvolvedores, alguns proponentes do código aberto encorajaram as pessoas a evitar o uso do Graphics Interchange Format (GIF) para compactar arquivos de imagem estática em favor do Portable Network Graphics (PNG), que combina o algoritmo deflate baseado em LZ77 com uma seleção de filtros de previsão específicos de domínio. No entanto, as patentes do LZW expiraram em 20 de junho de 2003.

Muitas das técnicas de compactação sem perdas usadas para texto também funcionam razoavelmente bem para imagens indexadas, mas existem outras técnicas que não funcionam para texto típico que são úteis para algumas imagens (principalmente bitmaps simples) e outras técnicas que tiram vantagem das características específicas das imagens (como o fenômeno comum de áreas 2-D contíguas de tons semelhantes e o fato de que as imagens coloridas geralmente têm uma preponderância de uma gama limitada de cores daquelas representáveis no espaço de cores).

Como mencionado anteriormente, a compressão de som sem perdas é uma área um tanto especializada. Algoritmos de compressão de som sem perdas podem tirar proveito dos padrões de repetição mostrados pela natureza ondulatória dos dados - essencialmente usando modelos autorregressivos para prever o "próximo" valor e codificando a diferença (esperançosamente pequena) entre o valor esperado e os dados reais. Se a diferença entre os dados previstos e reais (chamados de erro) tende a ser pequena, então certos valores de diferença (como 0, +1, -1 etc. em valores de amostra) tornam-se muito frequentes, que pode ser explorado codificando-os em poucos bits de saída.

Às vezes, é benéfico compactar apenas as diferenças entre duas versões de um arquivo (ou, na compactação de vídeo, de imagens sucessivas em uma sequência). Isso é chamado de codificação delta (da letra grega Δ, que em matemática denota uma diferença), mas o termo normalmente é usado apenas se ambas as versões forem significativas fora da compressão e descompressão. Por exemplo, embora o processo de compactação do erro no esquema de compactação de áudio sem perdas mencionado acima possa ser descrito como codificação delta da onda sonora aproximada para a onda sonora original, a versão aproximada da onda sonora não é significativa em nenhum outro contexto.

Métodos

Nenhum algoritmo de compactação sem perdas pode compactar com eficiência todos os dados possíveis (consulte a seção Limitações abaixo para obter detalhes). Por esse motivo, existem muitos algoritmos diferentes projetados com um tipo específico de dados de entrada em mente ou com suposições específicas sobre quais tipos de redundância os dados não compactados provavelmente conterão.

Alguns dos algoritmos de compactação sem perdas mais comuns estão listados abaixo.

Propósito geral

• ANS – Codificação de entropia, usada por LZFSE e Zstandard
• Codificação aritmética – codificação de entropia
• Burrows-Wheeler transformar a transformação reversível para tornar os dados textuais mais compressíveis, usados pelo bzip2
• Codificação de Huffman – Codificação de entropia, combina bem com outros algoritmos
• Compressão Lempel-Ziv (LZ77 e LZ78) – Algoritmo baseado em dicionário que forma a base para muitos outros algoritmos
  • Algoritmo de cadeia Lempel–Ziv–Markov (LZMA) – Razão de compressão muito alta, usada por 7zip e xz
  • Lempel–Ziv–Storer–Szymanski (LZSS) – Usado pelo WinRAR em conjunto com codificação Huffman
    • Deflate – Combina compressão LZSS com codificação Huffman, usado por ZIP, gzip e imagens PNG
  • Lempel–Ziv–Welch (LZW) – Usado por imagens GIF e Unix's compress utilidade
• Predição por correspondência parcial (PPM) – Otimizado para comprimir texto simples
• Codificação de comprimento de execução (RLE) – esquema simples que fornece boa compressão de dados contendo muitas corridas do mesmo valor

Áudio

• Adaptive Transform Acoustic Coding (ATRAC)
• Apple Lossless (ALAC – Apple Lossless Audio Codec)
• Audio Lossless Coding (também conhecido como MPEG-4 ALS)
• Transferência de fluxo direto (DST)
• Dolby TrueHD
• DTS-HD Master Audio
• Gratuito Lossless Audio Codec (FLAC)
• Embalagem sem perdas de meridiano (MLP)
• Áudio de Macaco (APE áudio de Macaco)
• MPEG-4 SLS (também conhecido como HD-AAC)
• OptiFROG
• Qualidade de som original (OSQ)
• RealPlayer (RealAudio Lossless)
• Curto (SHN)
• TTA (True Audio Lossless)
• WavPack (WavPack sem perdas)
• WMA Sem perdas (Windows Media Lossless)

Gráficos raster

• AVIF – Formato de arquivo de imagem AV1
• FLIF – Formato de imagem sem perdas livre
• HEIF – Formato de arquivo de imagem de alta eficiência (compressão perdida ou perdida, usando HEVC)
• ILBM – (compressão RLE perdida de imagens Amiga IFF)
• JBIG2 – (compressão sem perdas ou perda de imagens B&W)
• JPEG 2000 – (inclui método de compressão sem perdas via Le Gall–Tabatabai 5/3 de transformação de onda de inteiro reversível)
• JPEG-LS – (padrão de compressão sem perdas / sem perdas)
• JPEG XL – (compressão sem perdas ou perda)
• JPEG XR – anteriormente WMPhoto e Foto HD, inclui um método de compressão sem perdas
• LDCT – Transformação de Cosina Discreta Sem Perda
• PCX – PiCture eXchange
• PDF – Formato de Documento Portátil (compressão sem perdas ou perda)
• QOI – Formato de imagem bastante OK
• PNG – Gráficos de rede portáteis
• TGA – Truevision TGA
• TIFF – Tagged Formato de arquivo de imagem (compressão perdida ou perdida)
• WebP – (compressão perdida ou com perda de imagens RGB e RGBA)

Gráficos 3D

• OpenCTM – Compressão sem perdas de malhas triangulares 3D

Vídeo

Veja a lista de codecs de vídeo sem perdas

Criptografia

Criptosistemas geralmente compactam dados (o "texto simples") antes da criptografia para aumentar a segurança. Quando implementada adequadamente, a compactação aumenta muito a distância de unicidade removendo padrões que podem facilitar a criptoanálise. No entanto, muitos algoritmos comuns de compactação sem perdas produzem cabeçalhos, wrappers, tabelas ou outras saídas previsíveis que podem facilitar a criptoanálise. Assim, os criptosistemas devem utilizar algoritmos de compressão cuja saída não contenha esses padrões previsíveis.

Genética e Genômica

Algoritmos de compressão genética (não confundir com algoritmos genéticos) são a última geração de algoritmos sem perdas que comprimem dados (normalmente sequências de nucleotídeos) usando algoritmos de compressão convencionais e algoritmos específicos adaptados a dados genéticos. Em 2012, uma equipe de cientistas da Universidade Johns Hopkins publicou o primeiro algoritmo de compressão genética que não depende de bancos de dados genéticos externos para compressão. O HAPZIPPER foi adaptado para dados do HapMap e atinge uma compactação de mais de 20 vezes (redução de 95% no tamanho do arquivo), fornecendo uma compactação de 2 a 4 vezes melhor, muito mais rápido do que os principais utilitários de compactação de uso geral.

Algoritmos de compressão de sequência genômica, também conhecidos como compressores de sequência de DNA, exploram o fato de que as sequências de DNA possuem propriedades características, como repetições invertidas. Os compressores de maior sucesso são XM e GeCo. Para eucariotos, o XM é um pouco melhor na taxa de compressão, embora para sequências maiores que 100 MB seus requisitos computacionais sejam impraticáveis.

Executáveis

Executáveis de extração automática contêm um aplicativo compactado e um descompactador. Quando executado, o descompactador descompacta e executa o aplicativo original de forma transparente. Isso é especialmente usado na codificação de demonstração, onde as competições são realizadas para demonstrações com limites de tamanho rígidos, tão pequenos quanto 1k. Esse tipo de compactação não é estritamente limitado a executáveis binários, mas também pode ser aplicado a scripts, como JavaScript.

Referências

Algoritmos de compressão sem perdas e suas implementações são rotineiramente testados em benchmarks frente a frente. Existem vários benchmarks de compressão mais conhecidos. Alguns benchmarks cobrem apenas a taxa de compactação de dados, portanto, os vencedores desses benchmarks podem ser inadequados para o uso diário devido à baixa velocidade dos melhores desempenhos. Outra desvantagem de alguns benchmarks é que seus arquivos de dados são conhecidos, portanto, alguns criadores de programas podem otimizar seus programas para obter o melhor desempenho em um conjunto de dados específico. Os vencedores nesses benchmarks geralmente vêm da classe de software de compactação de mixagem de contexto.

Matt Mahoney, em sua edição de fevereiro de 2010 do livreto gratuito Data Compression Explained, lista adicionalmente o seguinte:

• O Corpus Calgary que remonta a 1987 já não é amplamente utilizado devido ao seu tamanho pequeno. Matt Mahoney manteve o Calgary Compression Challenge, criado e mantido a partir de 21 de maio de 1996, até 21 de maio de 2016, por Leonid A. Broukhis.
• O Large Text Compression Benchmark e o similar Hutter Prize ambos usam um conjunto de dados UTF-8 da Wikipédia guarnecido.
• O Compression Benchmark Genérico, mantido por Matt Mahoney, testa compressão de dados gerados por máquinas de Turing aleatórias.
• Sami Runsas (o autor de NanoZip) manteve o Compression Ratings, um benchmark semelhante ao teste de múltiplos arquivos de compressão máxima, mas com requisitos mínimos de velocidade. Ofereceu a calculadora que permitiu ao usuário ponderar a importância da relação velocidade e compressão. Os principais programas foram bastante diferentes devido à exigência de velocidade. Em janeiro de 2010, o programa foi NanoZip seguido por FreeArc, CCM, flashzip e 7-Zip.
• O Monster of Compression benchmark de Nania Francesco Antonio testou compressão em 1Gb de dados públicos com um limite de tempo de 40 minutos. Em dezembro de 2009, o arquivador top classificado foi NanoZip 0,07a e o compressor de arquivo único top classificado foi ccmx 1.30c.

O site Compression Ratings publicou um resumo do gráfico da "fronteira" na taxa de compressão e no tempo.

A Compression Analysis Tool é um aplicativo do Windows que permite aos usuários finais comparar as características de desempenho de implementações de streaming de LZF4, Deflate, ZLIB, GZIP, BZIP2 e LZMA usando seus próprios dados. Ele produz medições e gráficos com os quais os usuários podem comparar a velocidade de compactação, a velocidade de descompactação e a taxa de compactação dos diferentes métodos de compactação e examinar como o nível de compactação, o tamanho do buffer e as operações de liberação afetam os resultados.

Limitações

Algoritmos de compactação de dados sem perdas (que não anexam rótulos de ID de compactação a seus conjuntos de dados de saída) não podem garantir compactação para todos os conjuntos de dados de entrada. Em outras palavras, para qualquer algoritmo de compactação de dados sem perdas, haverá um conjunto de dados de entrada que não diminui quando processado pelo algoritmo e, para qualquer algoritmo de compactação de dados sem perdas que torne pelo menos um arquivo menor, haverá pelo menos um arquivo que torna maior. Isso é facilmente comprovado com matemática elementar usando um argumento de contagem chamado princípio da casa dos pombos, como segue:

• Assuma que cada arquivo é representado como uma cadeia de bits de algum comprimento arbitrário.
• Suponha que há um algoritmo de compressão que transforma cada arquivo em um arquivo de saída que não é mais do que o arquivo original, e que pelo menos um arquivo será compactado em um arquivo de saída que é mais curto do que o arquivo original.
• Vamos. M ser o menor número tal que há um arquivo F com comprimento M bits que comprime a algo mais curto. Vamos. N ser o comprimento (em bits) da versão compactada de F.
• Porque... N<M, cada um arquivo de comprimento N mantém seu tamanho durante a compressão. Há 2^N tais arquivos possíveis. Junto com F, isto faz 2^N+1 arquivos que todos comprimem em um dos 2^N arquivos de comprimento N.
• Mas...^N é menor que 2^N+1, assim pelo princípio de pombo buraco deve haver algum arquivo de comprimento N que é simultaneamente a saída da função de compressão em duas entradas diferentes. Esse arquivo não pode ser descompactado de forma confiável (que dos dois originais devem que rendem?), o que contradiz a suposição de que o algoritmo era sem perda.
• Devemos, portanto, concluir que nossa hipótese original (que a função de compressão não faz mais arquivo) é necessariamente falsa.

A maioria dos algoritmos de compactação práticos fornecem uma "escape" facilidade que pode desativar a codificação normal para arquivos que se tornariam mais longos ao serem codificados. Em teoria, apenas um único bit adicional é necessário para informar ao decodificador que a codificação normal foi desativada para toda a entrada; no entanto, a maioria dos algoritmos de codificação usa pelo menos um byte completo (e geralmente mais de um) para essa finalidade. Por exemplo, arquivos compactados deflate nunca precisam crescer mais de 5 bytes por 65.535 bytes de entrada.

Na verdade, se considerarmos arquivos de tamanho N, se todos os arquivos forem igualmente prováveis, então, para qualquer compactação sem perdas que reduza o tamanho de algum arquivo, o tamanho esperado de um arquivo compactado (média de todos os arquivos possíveis de tamanho N) deve necessariamente ser maior que N. Portanto, se não sabemos nada sobre as propriedades dos dados que estamos compactando, podemos também não compactá-los. Um algoritmo de compactação sem perdas é útil apenas quando temos mais probabilidade de compactar certos tipos de arquivos do que outros; então o algoritmo poderia ser projetado para comprimir melhor esses tipos de dados.

Assim, a principal lição do argumento não é que se arrisca grandes perdas, mas apenas que nem sempre se pode ganhar. Escolher um algoritmo sempre significa implicitamente selecionar um subconjunto de todos os arquivos que se tornarão utilmente mais curtos. Esta é a razão teórica pela qual precisamos ter diferentes algoritmos de compactação para diferentes tipos de arquivos: não pode haver nenhum algoritmo que seja bom para todos os tipos de dados.

O "truque" que permite algoritmos de compactação sem perdas, usados no tipo de dados para os quais foram projetados, para compactar consistentemente esses arquivos em um formato mais curto é que todos os arquivos nos quais os algoritmos são projetados para agir têm alguma forma de redundância facilmente modelada para a qual o algoritmo foi projetado remover e, portanto, pertencer ao subconjunto de arquivos que esse algoritmo pode tornar mais curto, enquanto outros arquivos não seriam compactados ou até mesmo maiores. Os algoritmos geralmente são ajustados especificamente para um determinado tipo de arquivo: por exemplo, programas de compactação de áudio sem perdas não funcionam bem em arquivos de texto e vice-versa.

Em particular, arquivos de dados aleatórios não podem ser consistentemente compactados por qualquer algoritmo concebível de compactação de dados sem perdas; na verdade, esse resultado é usado para definir o conceito de aleatoriedade na complexidade de Kolmogorov.

É comprovadamente impossível criar um algoritmo que possa compactar qualquer dado sem perdas. Embora tenha havido muitas reivindicações ao longo dos anos de empresas que alcançaram a "compressão perfeita" onde um número arbitrário N de bits aleatórios sempre pode ser compactado para N − 1 bits, esses tipos de reivindicações podem ser descartados com segurança sem nem mesmo olhar para mais detalhes sobre o suposto esquema de compressão. Tal algoritmo contradiz as leis fundamentais da matemática porque, se existisse, poderia ser aplicado repetidamente para reduzir sem perdas qualquer arquivo ao tamanho 1.

Por outro lado, também foi provado que não existe um algoritmo para determinar se um arquivo é incompressível no sentido da complexidade de Kolmogorov. Portanto, é possível que qualquer arquivo específico, mesmo que pareça aleatório, possa ser significativamente compactado, mesmo incluindo o tamanho do descompactador. Um exemplo são os dígitos da constante matemática pi, que parecem aleatórios, mas podem ser gerados por um programa muito pequeno. No entanto, embora não possa ser determinado se um determinado arquivo é incompressível, um teorema simples sobre strings incompressíveis mostra que mais de 99% dos arquivos de qualquer tamanho não podem ser compactados em mais de um byte (incluindo o tamanho do descompactador).

Fundo matemático

Abstratamente, um algoritmo de compressão pode ser visto como uma função em sequências (normalmente de octetos). A compactação é bem-sucedida se a sequência resultante for menor que a sequência original (e as instruções para o mapa de descompactação). Para que um algoritmo de compactação seja sem perdas, o mapa de compactação deve formar uma injeção de "simples" para "comprimido" sequências de bits. O princípio da casa dos pombos proíbe uma bijeção entre a coleção de sequências de comprimento N e qualquer subconjunto da coleção de sequências de comprimento N−1. Portanto, não é possível produzir um algoritmo sem perdas que reduza o tamanho de todas as sequências de entrada possíveis.

Pontos de aplicação na teoria de compressão real

Os projetistas de algoritmos de compactação reais aceitam que os fluxos de alta entropia de informações não podem ser compactados e, consequentemente, incluem recursos para detectar e lidar com essa condição. Uma maneira óbvia de detecção é aplicar um algoritmo de compactação bruta e testar se sua saída é menor que sua entrada. Às vezes, a detecção é feita por heurística; por exemplo, um aplicativo de compactação pode considerar arquivos cujos nomes terminam em ".zip", ".arj" ou ".lha" incompressível sem qualquer detecção mais sofisticada. Uma maneira comum de lidar com essa situação é citar a entrada ou partes não compressíveis da entrada na saída, minimizando a sobrecarga de compactação. Por exemplo, o formato de dados zip especifica o 'método de compactação' de 'Armazenado' para arquivos de entrada que foram copiados no arquivo textualmente.

O desafio de um milhão de dígitos aleatórios

Mark Nelson, em resposta às alegações de "mágica" algoritmos de compressão que aparecem em comp.compression, construiu um arquivo binário de 415.241 bytes de conteúdo altamente entrópico e lançou um desafio público de $ 100 para qualquer um escrever um programa que, junto com sua entrada, seria menor do que seus dados binários fornecidos ainda seriam capaz de reconstituí-lo sem erro. Um desafio semelhante, com $ 5.000 como recompensa, foi lançado por Mike Goldman.