Codificação run-length (RLE)

Cada sequência — não importa o quão longa — custa o mesmo para armazenar: 2 unidades, uma para o símbolo, uma para a contagem. Uma sequência de comprimento L só vale a pena codificar quando isso custa menos do que escrever L caracteres brutos — ou seja, quando L é maior que 2. Em média, sobre toda a entrada, essa condição se torna L̄ = N/R maior que 2, onde N é o comprimento total e R é o número de sequências — exatamente a linha que a fórmula acima verifica. Essa é também a razão pela qual o RLE é um compressor de propósito geral fraco: texto em inglês, código-fonte e dados aleatórios raramente têm sequências mais longas que 2, por isso o RLE fica reservado a dados projetados de propósito para ter sequências longas — digitalizações de fax de 1 bit, bitmaps esparsos e imagens com paleta e áreas de cor sólida. Formatos reais levam essa ideia mais longe: o PNG aplica um filtro delta Paeth/Sub/Up em cada linha de varredura antes de comprimir, transformando primeiro gradientes suaves em longas sequências de diferenças quase nulas — o RLE (via DEFLATE) faz o resto. Experimente o exemplo de pior caso acima: dezesseis caracteres distintos geram dezesseis sequências de comprimento 1, então a codificação precisa de 32 unidades para armazenar 16 — a entrada dobra de tamanho.

A codificação por comprimento de série é a única ideia de compressão que você poderia reinventar por conta própria: em vez de escrever WWWWWWW letra por letra, você diz apenas "7 W" — o mesmo atalho que usamos ao ler "três vezes sete" em um número de telefone. Ela percorre os dados numa única passagem da esquerda para a direita e não guarda nada além da série que está contando, o que a torna rápida e fácil de transmitir em fluxo. E é sem perdas: a partir dos pares (símbolo, contagem) você reconstrói o original exatamente, ao contrário de JPEG ou MP3, que descartam detalhe para sempre.

O RLE ingênuo pode dobrar dados incompressíveis, mas a variante PackBits da Apple — nascida no MacPaint dos anos 1980 e ainda um modo de compressão padrão no TIFF — é projetada para quase nunca crescer. Cada bloco começa com um byte de controle com sinal: um valor não negativo significa "os próximos bytes são literais", um negativo "repita o byte seguinte". Dados únicos são copiados sem alteração em blocos de até 128 bytes, então o pior caso acrescenta apenas um byte de controle por 128 — menos de 1% de sobrecarga em vez dos 100% que o RLE ingênuo pode atingir.