Codificação run-length
Codificação run-length é uma forma simples de compressão sem perda de dados onde sequências longas de valores repetidos são armazenadas como um único valor e sua contagem no lugar de sua sequência original. É principalmente útil em dados com muitas repetições de valores. Considere, por exemplo, imagens gráficas simples tais quais ícones, line art, jogos da vida e animações. Não é útil em arquivos que não possuem muitas repetições, pois pode aumentar bastante o tamanho do arquivo.
Quando temos a ocorrência de uma repetição contínua de determinado caractere, por exemplo, AAAAAAAAAAAA, é possível substituir sua representação pelo par (12, A). Entretanto não podemos simplesmente substituir no meio do texto a sequência de letras pelo número, senão uma frase como: Como identificar se o número 2 estava realmente presente no texto original ou foi introduzido pela codificação? Neste caso precisamos identificar o início da codificação por um caractere especial. Assim, se usarmos por exemplo o símbolo de "@" como caractere especial, teremos: E conseguimos identificar exatamente onde o número 2 realmente existe na frase, e onde ele é parte da codificação. Entretanto, a cadeia ao invés de ser comprimida, foi na verdade expandida. Usando um caractere de escape a sequência mínima que podemos codificar sem causar expansão do arquivo precisa ter tamanho 3. Além disso o caractere especial não pode ser um dos caracteres que ocorrem dentro do texto.
Para a compressão de textos o método de RLE não é muito eficiente. Na língua inglesa, por exemplo, as repetições de duas letras iguais são até bastante comuns, mas repetições de 3 ou mais letras são muito raras. Repetições de 4 caracteres iguais só ocorreriam em tabelas, quadros, ou com caracteres especiais (final de linha, espaços, tabulações, etc). Um exemplo dessa situação pode ser visto no parágrafo abaixo: Na língua portuguesa a situação é ainda pior, pois mesmo as repetições de 2 letras iguais consecutivas é rara. Isso inviabiliza o uso de RLE para comprimir textos diretamente. Entretanto existem técnicas que podem ser aplicadas aos textos de forma a torná-los mais facilmente comprimíveis usando RLE. Uma dessas técnicas é o Método de Burrows-Wheeler empregado no compactador bzip2.
Na compressão de imagens esta técnica é mais promissora pois imagens apresentam maiores áreas contínuas de uma mesma cor. Desenhos e outras imagens com número limitados de cores tendem a ser melhor comprimíveis usando esta técnica. Uma abordagem interessante é a usada na compressão de imagens monocromáticas. Nessas imagens cada pixel é representado por apenas um bit. Assim o arquivo pode ser armazenado como uma lista dos tamanhos das sequências alternadamente de pixels brancos (1) e pretos (0), sem precisar indicar qual o valor da próxima sequência. Caso o primeiro pixel não seja da cor branca (1), o primeiro valor armazenado é 0, indicando uma sequência de tamanho 0 de pixels brancos. Em imagens de tons de cinza uma abordagem mais tradicional tem de ser adotada pois cada pixel pode variar em geral, entre os 256 valores de um byte. Usa-se nesse caso um caractere de escape ou alguma técnica similar à do MNP5. Para a escolha de um caractere de escape uma das cores menos frequentes é eliminada da imagem sendo substituída por um dos tons de cinza próximos. Por exemplo elimina-se o tom de cinza 255, sendo este substituído pelo 254, e o símbolo correspondente a 255 será usado como caractere de escape.
Além do protocolo MNP5 usado em modems, mencionado anteriormente, várias aplicações usam RLE como compressão, entre eles: Em geral a técnica de RLE é uma técnica auxiliar que não gera uma compressão muito grande sozinha, mas que aliada a outras técnicas é um instrumento simples e poderoso de compressão.
