Introdução

A compressão padrão deste algoritmo é uma variante do LZ77. No final da codificação, obtém-se através da descompressão um código em hexadecimal com menos bytes que a string original. O output de um codificador QIC-122 é constituído por um fluxo de dados. Programas que usam o QIC-122: PKZIP, o formato de arquivos gzip e até no formato de imagens PNG.

Algoritmo

A codificação da string começa da esquerda para a direita. Os caracteres isolados (1 bit) chamados de caracteres “raw” não são considerados como uma repetição, logo são codificados colocando no início o binário 0 seguido do respectivo código ASCII (8bits). Na string inicial  procuram-se substrings que se repitam. Cada substring terá um mínimo de comprimento (nº de bytes, o seu código codificado está numa tabela pré-definida) de 2 caracteres e terá também o maior tamanho possível, e o seu offset é calculado pela diferença da posição do primeiro caracter da substring mais a frente, com a posição do primeiro caracter da substring menos à esquerda da string original. O 1º bit da codificação é sempre o binário 11, seguido do seu offset em binário, seguido do seu comprimento que é codificado através da tabela definida por defeito. No final, o buffer usa o binário 1100000 (End marker) para finalizar a string. A codificação é feita, ligando todos os códigos binários, agrupando-o 4 a 4 bits, e verificando o respectivo código hexadecimal.

Definições importantes

Caracter Raw – Caracter que será codificado apenas com o seu código ASCII em binário.

Length – Tamanho da string (número de bytes). A partir desse número de bytes, teremos de verificar o seu código respectivo através da tabela.

Offset – Subtracção da 1ª posição da string original com a 1ª posição da string repetida (7 bits).

End Marker – Código binário que indica o final da string (110000000 = 9 bits).

Code

while ( !out_of_symbols ){
    length = find_longest_match(&offset);
    if (length > 1){
        output_bit(11);
        length = find_longest_match( &offset );
        output_bits( offset );
        output_bits( length );
        shift_input_buffer( length );
    }else {
        output_bit( 0 );
        output_byte( buffer[ 0 ] );
        shift_input_buffer( 1 );
    }
}

Explicação do codigo:

1. Enquanto existir caracteres no buffer;
2. Entra no ciclo while;
3. Procura string e verifica tamanho;
4. Se o tamanho for maior que 1 significa que é uma string.
5. Entra no ciclo if;
6. Como é uma string é iniciada com os dois bits 11;
7. Verifica o tamanho da string e onde está a string repetida;
8. Passa o offset para um número binário de 7 bits;
9. Com esse tamanho, verifica-se na tabela o código;
10. Consulta-se a tabela por defeito para verificar qual o código correspondente ao tamanho em bytes da string.
11. Tamanho igual a 1 significa que é um “raw” byte, Entra no ciclo;
12. Primeiro bit da codificação é sempre o bit 0.
13. Verifica o código ASCII do carácter;
14. Procura o código na tabela correspondente ao tamanho 1 byte(não existe código).
15. Fecha o ciclo else;
16. Fecha o ciclo while;

Exemplo prático

Codificação

String: “ABAAAAAACABABABA”

Byte ‘A’ = 0 | 01000001

Byte ‘B’ = 0 | 01000010

Byte ‘A’ = 0 | 01000001

String ‘AAAA’, offset = 1     1 | 1 0000001 | 1100

Byte ‘C’ = 0 | 01000011

String ‘ABA’, offset = 9       1 | 1 0001001 | 01

String ‘BABA’, offset = 2    1 | 1 0000010 | 10

Marcador de fim   1  1  0000000

No fim junta-se todo o codigo binário –> 00100000100100001011000000111000010000111100010010111000001010110000000

Agrupa-se 4 a 4 bits:

No final, verificamos o codigo hexadecimal correspondente e assim temos a string inicial codificada:

20 90 88 38 1C 21 E2 5C 15 80

String inicial: ABAAAAAACABABABA

Tamanho: 16 bytes

String Codificada: 20 90 88 38 1C 21 E2 5C 15 80

Tamanho: 10 bytes

Racio = 16/10 = 1,6

Descodificação:

Codigo: 20 90 88 38 1C 21 E2 5C 15 80

-Passar para binário e agrupar em bloco de 4 bits:

-Juntar todos os bits

001000001   001000010   001000001|   11*0000001*1100001000011*11*0001001*01|   *11*0000010*10   |110000000

1. Verificar sempre o primeiro bit. Como neste caso é zero sabemos que é um raw byte. Então separamos o 1º bit dos restantes 8 bits que são o ASCII do carácter. Através do mesmo verificamos que o primeiro carácter é o “A”;
2. Seguidamente fazemos o mesmo processo já que é também um raw byte e verificamos que é o carácter “B”;
3. Vem o carácter “A” de novo;
4. Depois vemos que o próximo é uma string, então vemos o seu offset e verificamos qual o carácter anterior a string. Como é o “A” conseguimos verificar através do tamanho da string e seu offset que a string codificada é o “AAAAA”;
5. Depois vem de novo um carácter raw, o “C”;
6. String, através da string descodificada anteriormente, o offset e tamanho verifica-se que a string é: “ABA”;
7. Fazemos o mesmo processo, e vem a string “BABA”;
8. Os últimos 9 bits sabemos que são o marcador final da string.

Verificamos que a string original é: ABAAAAAACABABABA
O processo de descodificação é o processo simétrico ao da codificação.

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 Ricardo Coelho (13137) e revisto por Nuno Magalhães Ribeiro.

 

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.