Compressão sem perdas (ou lossless compression) é uma classe de compressão de dados que permite que os dados originais sejam perfeitamente reconstruídos a partir dos dados comprimidos, sem perda de informação. A compressão sem perdas é possível porque a maioria dos dados do mundo real exibe redundância estatística. Em contraste, a compressão com perdas permite apenas a reconstrução de uma aproximação dos dados originais, embora geralmente com taxas de compressão muito melhores (e, portanto, tamanhos de mídia reduzidos).

Pela operação do princípio da casa dos pombos, nenhum algoritmo de compressão sem perdas pode reduzir o tamanho de todos os dados possíveis: alguns dados ficarão maiores em pelo menos um símbolo ou bit.

Os algoritmos de compressão são geralmente eficazes para documentos legíveis por humanos e máquinas e não podem reduzir o tamanho de dados aleatórios que não contêm redundância. Existem diferentes algoritmos projetados seja com um tipo específico de dados de entrada em mente, seja com suposições específicas sobre quais tipos de redundância os dados não comprimidos provavelmente contêm.

A compressão de dados sem perdas é usada em muitas aplicações. Por exemplo, é usada no formato de arquivo ZIP e na ferramenta GNU gzip. Também é frequentemente usada como um componente dentro de tecnologias de compressão de dados com perdas (por exemplo, pré-processamento estéreo mid/side sem perdas por codificadores MP3 e outros codificadores de áudio com perdas).

A compressão sem perdas é usada em casos onde é importante que os dados originais e os descomprimidos sejam idênticos, ou onde desvios dos dados originais seriam desfavoráveis. Exemplos comuns são programas executáveis, documentos de texto e código-fonte. Alguns formatos de arquivo de imagem, como PNG ou GIF, usam apenas compressã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 mais frequentemente usados para fins de arquivamento ou produção, enquanto arquivos de áudio com perdas menores são tipicamente usados em players portáteis e em outros casos onde o espaço de armazenamento é limitado ou a replicação exata do áudio é desnecessária.

Técnicas A maioria dos programas de compressã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 este modelo para mapear os dados de entrada para sequências de bits de tal forma que dados "prováveis" (ou seja, frequentemente encontrados) produzam saída mais curta do que dados "improváveis".

Os principais algoritmos de codificação 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 atinge taxas de compressão próximas do melhor possível para um determinado modelo estatístico, que é dado pela entropia da informação, enquanto a compressão de Huffman é mais simples e rápida, mas produz resultados ruins para modelos que lidam com probabilidades de símbolo próximas de 1.

Existem duas maneiras 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 comprimidos. Esta abordagem é simples e modular, mas tem a desvantagem de que o próprio modelo pode ser caro para armazenar, e também que força o uso de um único modelo para todos os dados sendo comprimidos, e portanto tem desempenho ruim em arquivos que contêm dados heterogêneos. Modelos adaptativos atualizam dinamicamente o modelo à medida que os dados são comprimidos. Tanto o codificador quanto o decodificador começam com um modelo trivial, produzindo baixa compressão dos dados iniciais, mas à medida que aprendem mais sobre os dados, o desempenho melhora. Os tipos mais populares de compressão usados na prática agora usam codificadores adaptativos.

Os métodos de compressão sem perdas podem ser categorizados de acordo com o tipo de dados que foram projetados para comprimir. Embora, em princípio, qualquer algoritmo de compressão sem perdas de uso geral (uso geral significando que pode aceitar qualquer sequência de bits) possa ser usado em qualquer tipo de dados, muitos são incapazes de alcançar compressão significativa em dados que não são da forma para a qual foram projetados para comprimir. Muitas das técnicas de compressão sem perdas usadas para texto também funcionam razoavelmente bem para imagens de cor indexada.

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 em relação ao seu vizinho esquerdo. Isso leva a valores pequenos tendo uma probabilidade muito maior do que valores grandes. Isso também é frequentemente aplicado a arquivos de som, e pode comprimir arquivos que contêm principalmente baixas frequências e baixos volumes. Para imagens, este passo pode ser repetido tomando a diferença em relação ao pixel superior, e então em vídeos, a diferença em relação ao pixel no próximo quadro pode ser tomada.

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 transformada wavelet, as probabilidades também são passadas através da hierarquia.

Questões legais históricas Muitos desses métodos são implementados em ferramentas de código aberto e proprietárias, 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 a patentes sobre certos tipos de compressão LZW, e em particular práticas de licenciamento pelo detentor da patente Unisys que muitos desenvolvedores consideraram abusivas, alguns proponentes de código aberto encorajaram as pessoas a evitar o uso do Graphics Interchange Format (GIF) para comprimir arquivos de imagem estáticos em favor do Portable Network Graphics (PNG), que combina o algoritmo deflate baseado em LZ77 com uma seleção de filtros de predição específicos do domínio. No entanto, as patentes sobre LZW expiraram em 20 de junho de 2003.

Muitas das técnicas de compressão sem perdas usadas para texto também funcionam razoavelmente bem para imagens indexadas, mas há outras técnicas que não funcionam para texto típico e são úteis para algumas imagens (particularmente bitmaps simples), e outras técnicas que aproveitam as 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 imagens coloridas geralmente têm uma preponderância de uma gama limitada de cores dentre aquelas representáveis no espaço de cor).

Como mencionado anteriormente, a compressão de som sem perdas é uma área um tanto especializada. Algoritmos de compressão de som sem perdas podem aproveitar os padrões repetitivos mostrados pela natureza ondulatória dos essencialmente usando modelos autorregressivos para prever o próximo valor e codificar a diferença (possivelmente pequena) entre o valor esperado e o dado real. Se a diferença entre o valor previsto e o dado real (chamada 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, o que pode ser explorado codificando-os em poucos bits de saída.

Às vezes é benéfico comprimir apenas as diferenças entre duas versões de um arquivo (ou, na compressão de vídeo, de imagens sucessivas dentro de uma sequência). Isso é chamado de codificação delta (da letra grega Δ, que em matemática denota uma diferença), mas o termo é tipicamente usado apenas se ambas as versões são significativas fora da compressão e descompressão. Por exemplo, enquanto o processo de compressão do erro no esquema de compressão de áudio sem perdas mencionado acima poderia 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 compressão sem perdas pode comprimir eficientemente todos os dados possíveis . Por esta razão, existem muitos algoritmos diferentes que são projetados seja com um tipo específico de dados de entrada em mente, seja com suposições específicas sobre quais tipos de redundância os dados não comprimidos provavelmente contêm.

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

Uso geral ANS – Codificação de entropia, usado por LZFSE e Zstandard Codificação aritmética – Codificação de entropia Transformada de Burrows–Wheeler – transformada reversível para tornar dados textuais mais compressíveis, usada por 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 Deflate – Combina LZ77 com codificação de Huffman, usado por imagens ZIP, gzip, zlib e PNG Brotli – Usa LZ77 com tamanho de janela deslizante alto (até 16 MiB), codificação de Huffman e modelagem de contexto. LZ4 – Compressão e descompressão muito rápidas. Algoritmo de cadeia de Markov Lempel–Ziv (LZMA) – Taxa de compressão muito alta, usado por 7zip e xz Lempel–Ziv–Storer–Szymanski (LZSS) – Usado por WinRAR em conjunto com codificação de Huffman Lempel–Ziv–Welch (LZW) – Usado por imagens GIF e pelo utilitário compress do Unix Predição por correspondência parcial (PPM) – Otimizado para comprimir texto simples Codificação run-length (RLE) – Esquema simples que fornece boa compressão de dados contendo muitas execuções 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) Direct Stream Transfer (DST) Dolby TrueHD DTS-HD Master Audio Free Lossless Audio Codec (FLAC) Meridian Lossless Packing (MLP) Monkey's Audio (Monkey's Audio APE) MPEG-4 SLS (também conhecido como HD-AAC) OptimFROG Original Sound Quality (OSQ) RealPlayer (RealAudio Lossless) Shorten (SHN) TTA (True Audio Lossless) WavPack (WavPack lossless) Windows Media Audio 9 Lossless (WMA Lossless)

Gráficos raster Codificação apenas sem perdas BMP PNG – Portable Network Graphics GIF – Graphics Interchange Format Opções de codificação com e sem perdas AVIF – AV1 Image File Format FLIF – Free Lossless Image Format HEIF – High Efficiency Image File Format, usando HEVC ILBM – (compressão RLE de imagens Amiga IFF) JBIG2 – compressão de imagens PB JPEG 2000 – (via transformada ondeleta inteira reversível Le Gall–Tabatabai 5/3) JPEG-LS JPEG XL JPEG XR – anteriormente WMPhoto e HD Photo LDCT – Transformada discreta de cosseno PCX – PiCture eXchange QOI – Quite OK Image Format TGA – Truevision TGA TIFF – Tag Image File Format WebP

Gráficos 3D OpenCTM – Compressão sem perdas de malhas de triângulos 3D

Vídeo Ver lista de codecs de vídeo sem perdas

Criptografia Criptossistemas frequentemente comprimem dados (o "texto simples") antes da criptografia para maior segurança. Quando implementado corretamente, a compressão aumenta muito a distância de unicidade removendo padrões que poderiam facilitar a criptoanálise. No entanto, muitos algoritmos de compressão sem perdas comuns produzem cabeçalhos, wrappers, tabelas ou outras saídas previsíveis que podem, em vez disso, tornar a criptoanálise mais fácil. Assim, os criptossistemas devem utilizar algoritmos de compressão cuja saída não contenha esses padrões previsíveis.

Genética e genômica