Introdução
Run Length Encoding é um processo para comprimir caracteres quando existe uma sequência longa de caracteres repetidos (4 ou mais). Este funcionamento é considerado codificação simples.
O codec Run Length Encoding são codificadores sem predas e supressão de sequências repetitivas.
Áreas de aplicação
Este codec é usados para a compressão de texto e imagens, especialmente em áreas onde não se pode perder informação pois estes métodos são sem perdas.
Neste trabalho especifico só vamos abortar a compressão de texto.
O algoritmo do Método Run Length Encoding
Codificação
O algoritmo de codificação funciona da seguinte forma:
- Determinar uma FLAG que não exista no texto a comprimir.
- Ler um caracter. Ler os próximos caracteres enquanto forem iguais ao primeiro caracter lido.
- Se o número total de caracteres lidos for igual ou superior a 4, comprimir essa cadeia de caracteres da seguinte forma: FLAG + nº de repetições + caracter.
- Se o numero total de caracteres lidos for inferior a 4, não se efetua compressão, logo essa cadeia de caracteres permanece inalterável.
Algoritmo de codificação em pseudo-código:
INICIO VARIAVEIS flag,i,c,j,count,compress,string; i <- 0; j <- 0; count <- 0; flag <- searchForFlag(); string <- “aaabbbssscccddd”; size <- length of string compress <- “ “ FOR i<-0 to size c <- caracter na posição i FOR j<-i to size IF c == caracter na posição j count <- count + 1; ELSE IF count >= 4 compress <- compress + flag + count + c; i <- i + count -1 ; count <- 0; END FOR ELSE compress <- compress + substring(i , i + count); i <- i + count - 1; count <- 0; END FOR END IF END IF END FOR END FOR FIM
Descodificação
O algoritmo de descodificação funciona da seguinte forma:
- Flag previamente definida.
- Ler um caracter. Se esse caracter for flag identifica i+1 como sendo o número de repetições para o char na posição i+2;
- Se não for flag, copia o char diretamente para a string auxiliar.
Algoritmo de descodificação em pseudo-código:
INICIO VARIAVEIS FLAG,i,c,j, Nrepetições ,Decompress,STRrepets; FOR i=0 , i< size, i++ IF( string.char(i)==FLAG) Nrepetições=parseInt.String.char(i+1); c = string.char(i+2); FOR(j=0;j<Nrepetições;j++) STRrepets= STRrepets.concat( c ); END FOR Decompress = Decompress.concat(STRrepets); STRrepets = “”; i =i+2 END IF ELSE Decompress = Decompress.concat(string.char(i) ) ; END ELSE END FOR Imprime_String_Descomprimida_RLE( Decompress); FIM
Exemplo de aplicação
Codificação
FLAG: #
Lê primeira letra: ‘a’
Lê as próximas letras enquanto forem iguais à letra ‘a’.
Conjunto total letras repetidas: a a a a a a a a (8x).
Numero de Repetições >= 4 logo, é comprimido em: #8a
Efetua um salto de 8 posições.
Lê primeira letra: ‘b’
Lê as próximas letras enquanto forem iguais à letra ‘b’.
Conjunto total letras repetidas: b b b b b b (6x).
Numero de Repetições >= 4 logo, é comprimido em: #6b
Efetua um salto de 6 posições.
Lê primeira letra: ‘c’
Lê as próximas letras enquanto forem iguais à letra ‘c’.
Conjunto total letras repetidas: c c (2x).
Numero de Repetições < 4 logo, não é comprimido. Permanece como estava: cc
Resultado final da compressão:
Rácio de Compressão: 16/8 = 2:1
Descodificação
Flag: #
Cria uma StringAuxiliar vazia.
Lê a primeira posição da String original.
Encontra Flag.
Vai na casa i+1,da string original, obter o número de repetições para o char e o size de uma string char_repete.
Cria a string char_repete com size 8 , e com o seguinte conteúdo:
De seguida , faz a concatenação / junção com a string Auxiliar,como esta estava vazia vai ficar com o conteúdo igual à da char_repete.
De seguida zeramos a String char_repete para futuro uso.
Na principal , damos dois saltos em i , ou seja , i=i+2, incrementa e é como se tivesse avançado 3 posições.
Encontra flag e repete os passos anteriores.
No caso de encontrar apenas um simples char , ou seja, que não seja uma Flag, ele irá simplesmente concatenar à StringAuxiliar.
E por fim:
Implementação do algoritmo Run-length Encoding
Para desenvolver o algoritmo foi criado um programa usando linguagem javascript.
A nossa abordagem é especifica para a compressão de caracteres e não de números.
Esta limitação deve-se ao facto de o texto a comprimir ser lido caracter a caracter.
Em vez disso, deveria ser lido em modo binário, ou seja, byte a byte o que já resolvia a limitação da compressão de caracteres apenas.
Algoritmo Compressão RLE em javascript
Algoritmo Descompressão RLE em javascript
Comparação com outros métodos semelhantes
O método Run-length Encoding é um codec sem perdas e de supressão de sequências repetitivas.
Como já foi mencionado o codec Run-length Encoding não é dos mais eficientes para os diferentes idiomas porque é difícil ter a mesma letra várias vezes seguidas.
Conclusão
Na realização deste artigo cientifico ficamos a saber mais ao pormenor os algoritmos de RLE e conseguimos aprender uma nova linguagem pois nenhum elemento do grupo tinha trabalhado anteriormente com javascript. Deparamos com algumas dificuldades nomeadamente, com a leitura em modo binário do texto a comprimir. Apenas conseguimos implementar o modo de leitura caracter a caracter.
No entanto, o conceito já se encontra implementado, porém o modo de leitura deve ser alterado para modo binário para uma maior eficiência dos algoritmos de compressão e descompressão.
O método de compressão RLE não é eficiente se for utilizado, por exemplo, menos de quatro letras repetidas e seguidas, por este motivo e em comparação com os outros processos este é um pouco ineficaz.
Este trabalho pode ser melhorado através do conhecimento de melhores codificadores.
Bibliografia
Salomon, D., “Data Compression”, Springer, 4th. Edition, 2007
Nuno Magalhães Ribeiro, Método Run Length Encoding, http://multimedia.ufp.pt/, 23 de Maio de 2016
Nuno Ribeiro e José Torres, “Tecnologias de Compressão Multimédia”, FCA, Setembro de 2009
Abordagem alternativa ao RLE
Codificação
O algoritmo “RLE” tem como base de funcionamento substituir “n” caracteres repetidos por um único caracter seguido do número de repetições, tal como supramencionado.
Caso os dados a comprimir se tratassem apenas de números, seria difícil a percepção entre o número a comprimir e o número de repetições, motivo pelo qual este método utiliza um símbolo, denominado “flag” (um caracter indicador).
De forma a optimizar este algoritmo, o princípio das “flags” apenas é utilizado quando os caracteres a comprimir são superiores a 3. De facto, se utilizado em até 3 caracteres, este método de compressão não permite retirar qualquer vantagem.
Refira-se, a título exemplificativo: se num algoritmo estivermos perante a repetição de letra “c” (duas vezes a letra “c”), através da utilização deste algoritmo, iriamos aumentar o número de dados – “flag” + “c” + n.º de repetições. Assim, neste caso, o método não permitiria fazer qualquer tipo de compressão, aumentando o volume de dados a apresentar.
No caso de estarmos perante 3 caracteres, o presente método não apresenta vantagens nem desvantagens, não permitindo qualquer compressão, igualando a quantidade de informação apresentada.
Assim, de forma esquematizada:
- Lê dados;
- Lê o primeiro caracter “diferente”;
- Coloca o caracter num novo vector;
- Incrementa o contador representativo do número de repetições desse caracter;
- Caso o número de repetições seja ≥ a 3, coloca na posição seguinte o n.º de repetições do caracter e uma flag;
- Caso contrário, copia a string até novo caracter diferente (≥ a 3).
- Repete os procedimentos anteriores, a partir do n.º 2, até finalizar os dados a comprimir.
A codificação permite, assim, que se aceda à informação pretendida de forma mais fácil e rapidamente [ver mais].
Descodificação
A descompressão de dados, utilizando o algoritmo “RLE”, consiste na leitura dos dados comprimidos e posterior descompressão.
Numa primeira instância, o algoritmo lê os dados e quando encontra uma flag sabe que de seguida aparece o caracter a descodificar e, de seguida, o número de repetições, sendo aqui que inicia o seu processo de descompressão.
Refira-se, a título de exemplo: “!c4aa”. Após descompressão, a informação apresenta-se da seguinte forma: “ccccaa”.
Assim, de forma esquematizada:
- Lê dados;
- Caso encontre uma flag, passa ao caracter seguinte;
- Verifica o número de repetições;
- Repete o caracter o número de vezes lido.
Caso não encontre nenhuma flag, faz simplesmente a cópia dos dados.
Exemplo de aplicação
Veja-se a imagem infra [ver mais]:
Codificação
Na imagem é possível verificar uma sequência de letras repetidas que, após compressão, se apresentam de forma mais clara e sucinta, permitindo uma rápida análise.
Se no primeiro “friso” a informação referente ao número de vezes em que o número é repetido é apresentada através de uma repetição dos números e quadrados referentes a esse mesmo número, após compressão é possível verificar de apenas dispomos da letra e do número de vezes em que a mesma é repetida.
Após a compressão, rapidamente temo acesso à informação pretendida.
Descodificação
Veja-se a imagem infra:
O processo é aqui efectuado de forma inversa. A letra é repetida tantas vezes quanto as pretendidas, o que aumenta a informação que é necessário absorver.
Implementação do algoritmo “Run-Length-encoding”
Para exemplificar o modo de aplicação deste algoritmo, recorremos a um código da linguagem de programação “c”.
Trabalho desenvolvido no âmbito da disciplina de Multimédia II da Licenciatura em Engenharia Informática, lecionada pelo Prof. Doutor Nuno Magalhães Ribeiro da Faculdade de Ciência e Tecnologia da UFP.
Texto da autoria de A, B e C e revisto por Nuno Magalhães Ribeiro.
Texto da autoria de Gonçalo Silva (26329), Pedro Galocha (25999) e João Alves (27785) e revisto por Nuno Magalhães Ribeiro.
Código javascript da autoria de Gonçalo Silva (26329), Pedro Galocha (25999) e João Alves (27785)
Código java e abordagem alternativa ao RLE da autoria de Milton Coelho e Paulo Augusto.
Site planeado, desenhado, desenvolvido e programado por Daniel Dias Lima Mendes, Diogo Emanuel Lamas e Silva, Nelson José Santos Almeida no âmbito do Projeto de final de Licenciatura realizado na Unidade Curricular de Laboratório de Projeto Integrado sob a orientação técnica do Prof. Doutor Nuno Magalhães Ribeiro.