Java Run Length Encoding – (RLE), Algorítimo de compressão de dados

O que é RLE?

RLE é um algorítimo de compressão de dados que é suportado pela maioria dos formatos de arquivos de bitmap, como TIFF, BMP e PCX. Esse algorítimo é adequado para comprimir qualquer tipo de dados, independente do seu conteúdo de informação, mas o conteúdo dos dados irão afetar a taxa de compressão conseguindo RLE. Embora a maioria dos algorítimos de RLE não poderem alcançar as altas taxas de compressão porem exitem outros métodos mais avançados.

Funcionamento:

Ele funciona reduzindo o tamanho físico de uma sequência de repetição de caracteres. Esta cadeia de repetição, chamada de corrida, é normalmente codificados em dois bytes. O primeiro byte representa o número de caracteres na corrida e é chamado de contagem de prazo. Na prática, uma execução codificada pode conter de 1 a 128 ou 256 caracteres, a contagem de execução geralmente contém, como o número de caracteres menos um (um valor na gama de 0 a 127 ou 255). O segundo byte é o valor do caractere na corrida, que é na faixa de 0 a 255, e é chamado o valor de execução.

Sem compressão, uma corrida de caráter 15 caracteres A, normalmente, necessitam de 15 bytes para armazenar:

AAAAAAAAAAAAAAA

A mesma cadeia após a codificação RLE exigiria apenas dois bytes:

15A

O código gerado 15A para representar a cadeia de caracteres é chamado de um pacote RLE. Aqui, o primeiro byte, 15, é a contagem de execução e contém o número de repetições. O segundo byte, A, é o valor de execução e contém o valor repetido real no prazo. Um novo pacote é gerado toda vez que o personagem correr muda, ou cada vez que o número de caracteres no prazo excede a contagem máxima.

Suponha que nossa sequência de 15 caracteres agora contém quatro corridas de personagens diferentes:

AAAAAAbbbXXXXXt

Usando a codificação run-length isso poderia ser comprimido em quatro pacotes de 2 bytes:

6A3b5X1t

Fonte: fileformat.info

[ads1]

Desafio:

Um simples desafio que me foi proposto durante o terceiro semestre da faculdade pelo Prof. Derig Almeida Vidal, MSc, já a algum tempo, mais que me foi de grande valor e tive que estudar um pouquinho a respeito… e sim acho que consegui a resolução.

Um dos algorítimos mais fáceis para compactar uma imagem é aquele já conhecemos por RLE (Run Length Encoding). Basicamente esse algorítimo percorre uma imagem “bitmap” linha a linha e, se em uma linha ele encontrar dois ou mais bits consecutivos com a mesma cor, lê compacta essa informação escrevendo o número de vezes que o bit foi repetido e em seguida a informação da cor.

Por exemplo, considere que temos uma imagem de 8 por 8 bits, em preto e branco. Uma maneira de representá-la seria por meio de uma matriz 8 x 8, como a figura abaixo:

matriz1                                matriz2

Os dois únicos valores presentes na Matriz são os números 0 e 1, representando, respectivamente, pixels brancos e pretos da imagem. Observe que existe uma representação de valores 1 e 0 consecutivos em algumas linhas (ou colunas) da matriz. Pode-se também representar essa imagem como um vetor de caracteres, no qual o valor 0 será representado pela letra (B) e o valor 1 pela letra (P). Dessa forma, levando em conta as repetições de cores, pode-se codificar a primeira linha assim: 8B (8 pixels repetidos da cor branca). E a terceira linha desse modo: 1B 1P 4B 1P 1B (1 branco, 1preto, 4 brancos, 1 preto e 1 braco).

Agora surge a dúvida:

Como armazenar a imagem inteira?

Pode-se definir o número (0) como indicador de separação de linhas.

E o fim da imagem?

Utilize dois zeros (00) como marcador de fim da imagem. Então, a imagem pode ser codificada como se fosse o seguinte vetor de caracteres:

‘8B02B4P2B01B1P4B1P1B01P1B1P2B1P1B1P01P6B1P01B1P1B2P1B1P1B01B1P4B1P1B02B4P2B00’

Desenvolver um algorítimo que leia uma imagem bitmap (valores inteiros 0 e 1) em uma matriz 8 x 8 e que compacte essa imagem em um vetor de tamanho máximo 64, conforme o método discutido anteriormente.

Fonte: Livro ALGORITMOS E LOGICA DE PROGRAMAÇÃO

[ads2]

Até a próxima.

Sobre o autor:

Servo de DEUS, Pós-Graduando em Docência do Ensino Superior - IDJ/UVA, Graduando em Automação Industrial - IFCE, Tecnólogo em Analise e Desenvolvimento de Sistemas - FALS, casado com a mulher mais maravilhosa, Tamires Alencar e amante Java, Games, Eletrônica, Robótica, Violão, Aviação...

Uma resposta

Deixe uma resposta

Seu e-mail não será publicado.