Codificação Run-length
Origem: Wikipédia, a enciclopédia livre.
Run-length (ou RLE) é uma técnica para comprimir cadeias de caracteres onde existem seqüências longas de caracteres repetidos.
O princípio do funcionamento dessa codificação é simples: 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 seqüencia de letras pelo número, senão uma frase como:
2. all is too well.
Se tornaria:
2. a2l is t2o we2l.
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:
2. a@2l is t@2o we@2l.
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 seqüencia 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.
Uma solução alternativa para o caractere de escape foi usada pelo protocolo MNP5, usado por fabricantes de modems. Nesse protocolo, ao invés de um caractere de escape, sempre que encontra uma repetição de 3 ou mais caracteres o codificador escreve os 3 primeiros caracteres repetidos no arquivo de saída, seguidos do número de repetições (além das 3 que já foram). Ou seja, se encontrar 3 caracteres "a" em seqüencia, imprime "aaa0", se forem 4 caracteres "b": "bbb1" e assim por diante. Repare que ainda assim existe um risco de expansão, mas ela é ligeiramente menor (e mais rara) do que no caso do caractere de escape.
Índice |
[editar] Compressão de textos
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:
 |
The abbott from Abruzzi accedes to the demands of all abbesses from Narragansett and Abbevilles from Abyssinia. He will accommodate them, abbreviate his sabbatical, and be an accomplished accessory. |  — [1]
|
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.
[editar] Compressão de imagens
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 seqüências alternadamente de pixels brancos (1) e negros (0), sem precisar indicar qual o valor da próxima seqüencia. Caso o primeiro pixel não seja da cor branca (1), o primeiro valor armazenado é 0, indicando uma seqüencia 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 freqüentes é 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.
Em imagens coloridas as cores são representadas como intensidades de Vermelho, Verde e Azul (sistema RGB) e para efeitos de compressão são tratadas como 3 imagens comprimidas separadamente. Assim emprega-se as mesmas técnicas das imagens em tons de cinza para cada "banda" de cor da imagem colorida (comprime-se separadamente o Vermelho, o Verde e o Azul da imagem, juntando tudo após a descompressão).
[editar] Aplicações
Além do protocolo MNP5 usado em modems, mencionado anteriormente, várias aplicações usam RLE como compressão, entre eles:
- O compactador bzip2 que usa RLE em conjunto com método de Burrows-Wheeler e a técnica de move-to-front.
- Imagens BMP do windows usam essa forma de compressão quando possível.
- Aparelhos de FAX usam um misto de Codificação de Huffman e RLE para transmitir os dados.
- O formato de arquivos BinHex dos computadores Macintosh usam compressão RLE.
- O algoritmo chamado reducing usado no PKZIP combina RLE com métodos estatísticos.
- O formato de imagens JPEG usa RLE em conjunto com diversas outras técnicas (a principal delas é a Transformada Discreta de Cosseno).
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.
[editar] Bibliografia
- (en) SALOMON, David. Data Compression: The Complete Reference. 2.ed. Nova Iorque: Springer, 2000. ISBN 0-387-95045-1
[editar] Referências
- ↑ SALOMON, David. Data Compression: The Complete Reference. 2.ed. Nova Iorque: Springer, 2000. ISBN 0-387-95045-1 página 19.
