Compressão Lossless

História

A compressão de dados, que pode ser entendida como o processo de transformação de um conjunto de dados noutro conjunto de tamanho mais pequeno, começou a ganhar relevância durante a década de 80 e 90 e atualmente está presente em muitos aspetos do quotidiano. Curiosamente, com o desenvolvimento tecnológico exponencial destas décadas, o custo do armazenamento de dados diminuiu drasticamente, mas foi também durante este período que os algoritmos de compressão mais evoluíram. A primeira vez que ficou registada uma utilização de um sistema de compressão foi a meio do século XIX por Samuel Morse no seu famoso código morse. Neste sistema de traços e pontos usados para comunicar à distância, Samuel Morse apercebeu-se que certas letras eram mais comuns do que outras, decidindo assim atribuir uma combinação de traços e pontos mais pequenas às letras mais comuns e combinações maiores às menos frequentes. A compressão de dados segue um processo muito semelhante. No entanto, só em 1948, Claude E. Shannon, através do seu trabalho “A Mathematical Theory of Communication”, formalizou os conceitos de compressão de informação em termos teóricos. Este artigo, entre vários conceitos matemáticos complexos, introduziu o conceito de compressão de informação dividida em duas vertentes, lossless (onde não existe perda de informação) e lossy (existe perda de informação durante o processo de compressão) como ilustrado na figura 1 sendo que x=y para lossless e x≠y na lossy. Definiu também que uma compressão lossless iria estar limitada por um limite fundamental, definido pelo rácio de entropia.

Lossless é então obtida através de um método de compressão onde é possível obter exatamente o mesmo conjunto de informação após descompressão, pois é um método não destrutivo. Contrastante com este método, a compressão Lossy é um método destrutivo, impossibilitando reverter Assim, ao longo dos anos, foram várias as empresas e cientistas que investiram muito no desenvolvimento de algoritmos de compressão para que hoje esteja presente em praticamente todos os aspetos da vida do ser humano, uma vez que muitos dos formatos mais comuns e genéricos do dia-a-dia são baseados em formas de compressão, desde as imagens, aos vídeos, passando pelos ficheiros “zipados”.

“I have made these letters longer than usual because I lack the time to make it shorter”

Blaise Pascal

Porquê compressão Lossless?

A necessidade de existirem métodos de compressão que consigam garantir a integridade dos dados é de elevada importância, pois por vezes, uma pequena diferença numa letra pode alterar substancialmente o significado de uma frase. Por exemplo as frases “Os rapazes, que comeram marisco, ficaram doentes” e “Os rapazes que comeram marisco ficaram doentes” ficam alteradas apenas pela adição de virgulas. Esta necessidade é exprimida por áreas onde a perda de dados pode originar problemas enormes, como imagem médica, dados de satélites, GPS, etc.

Algoritmos Lossless

Entre os algoritmos de compressão lossless mais famosos, são dignos de nota os LZ77 e LZ78 (também conhecidos como LZ1 e LZ2 respetivamente) não só pela importância cientifica, como pelo facto de serem a base de muitos outros algoritmos importantes. Estes dois algoritmos são codificadores de dicionário, o que significa que estes algoritmos operam através da procura de ligações entre os strings dos dados a comprimir e um set pré-determinado de strings numa estrutura de data - chamada dicionário. A importância destes dois métodos ganha ainda mais relevância, pois foi devido a eles e aos seus pressupostos que mais tarde surgiram os modelos probabilísticos que começaram a criar mapas de probabilidades para serem codificados posteriormente, aumentando drasticamente a capacidade de compressão.

LZ77

O algoritmo da LZ77 atinge a compressão por trocar ocorrências repetidas com referência a uma única cópia existente numa certa posição anterior na corrente de dados. A principal característica deste algoritmo é que usa um método de janela deslizante. Esta janela vai acompanhando a leitura dos dados de input e está dividida em duas partes. A primeira parte é o bloco anterior ao caracter que está a ser lido – cursor - e irá funcionar como dicionário. A segunda parte é o bloco a seguir ao cursor, sendo que este também faz parte do bloco (lookahead buffer). Estes dois blocos são de comprimento fixo e embutidos no algoritmo. Ele é executado da seguinte forma:

1. Encontrar o maior match entre uma string que começa no cursor e está completamente embutida no lookahead buffer e uma string que começa no dicionário;
2. Devolve um valor triplo (p, n, c) onde p é a posição da ocorrência na janela, n é o comprimento do match e c o caracter após o match;
3. Mover o cursor n +1 caracteres para a frente.

No exemplo da imagem, onde o dicionário tem comprimento de 6 (negrito) e o lookahead de 4 (sublinhado) e a posição do cursor dentro do quadrado. A posição p pode ser 0, sendo que significa que não tem match, sendo 1 o primeiro caracter do dicionário (direita para esquerda). Caso encontre strings com tamanhos iguais, guarda o último por questões de performance. Para a descodificação, basta seguir as posições ao contrário e reconstruir. Um caso particular está na imagem no passo 3, em que n>p. O string a copiar está presente no lookahead buffer e, portanto, ao descodificar ainda não foi construído. O algoritmo corrige este problema repetindo o elemento até preencher n posições.

LZ78

O algoritmo LZ78 é mais conservador na adição de strings ao dicionário e atualmente a variante Lempel-Ziv-Welch (LZW) é a mais comum, dai ser a estudada neste trabalho. O primeiro passo deste algoritmo é formar o dicionário com um tamanho determinado pela memória disponível. Se forem 8 bits, vai-se construir com as 255 primeiras entradas já ocupadas, sendo aumentado ao longo da leitura/codificação e pode ser traduzido com a seguinte interface:

1. C’’ = AddDict (C, x) cria uma nova entrada no dicionário por aumentar uma entrada no dicionário existente pelo índex C com o byte x. Retorna novo índex
2. C’’ = GetIndex (C, x) retorna o índex de uma string por extensão de uma string correspondente ao índex C com o byte x. Se a entrada n existir, retorna -1
3. W = GetString (C) retorna a string W correspondente ao índex C
4. Flag = IndexInDict? (C) retorna verdadeiro se o índex C está no dicionário e falso caso contrário.

Para a compressão de “abcabca”, ele inicia a criação do dicionário e vai procurar por “a” que já existe. Como “a” já existe, vai procurar “ab” que não existe e por isso vai criar uma nova entrada no dicionário. Após esta criação vai procurar pelo segundo elemento que é o “b” que também vai existir no dicionário e por isso vai procurar “bc” que não vai existir no dicionário. Assim sendo irá criar uma nova entrada. O mesmo acontece para o “c” e “ca”. No entanto, quando procura de novo “a” após criar o “ca”, vai procurar “ab” que também existe e por isso, irá procurar “abc” que não irá existir e, por conseguinte, criar uma nova entrada., Para a descodificação, o algoritmo vai procurar as entradas no dicionário e devolve a string equivalente.

Burrows-wheeler

Este algoritmo, desenvolvido por Michael Burrows e David Wheeler em 1943, é dos grandes algoritmos mais recentes e dos que consegue maiores ganhos de compressão, sendo também muito genérico, resulta muito bem em imagens, sons e texto. O funcionamento deste algoritmo é um pouco diferente dos referidos até agora que analisam o código a comprimir do início como um todo. Este método aborda os dados a comprimir dividido em blocos separados e codifica-os separadamente. A principal ideia por detrás deste algoritmo passa por transformar uma string S com n símbolos numa string L que satisfaça as seguintes condições:

(1) Cada região de L terá tendencialmente uma concentração de poucos símbolos. Ou seja, se encontrarmos um certo símbolo em L, deveremos encontrar outras instâncias do mesmo por perto. Assim este string poderá ser eficientemente comprimido com outros métodos como move-to-front, RLE ou os já vistos anteriormente. De notar que este método só se torna eficaz a partir de valores elevados de n. (2) A possibilidade de reconstruir S a partir de L.

As possibilidades de permutações de símbolos são fatoriais, por isso as possibilidades são enormes, mesmo em casos de poucos símbolos, o que torna vital a escolha adequada das permutações a realizar. Assim sendo, este método irá começar por criar uma matriz de “n x n” em que n é o tamanho do bloco a ser comprimido, sendo que a primeira linha é o texto original e a seguinte sofre uma translação/shift para a esquerda uma posição, incrementando a translação por 1 a cada linha até termos a translação até n-1. Após isto, ordena-se a matriz por ordem alfabética. Desta matriz retiramos a última coluna (que irá sempre preencher o requisito 1) e guardamos a valor da linha original para poder descodificar. A última coluna e a localização da linha original é então enviado para o codificador. Para a descodificação, após reconstruir a coluna escolhida para a compressão suplementar, conseguimos facilmente criar a primeira coluna (devido à ordenação léxica). A primeira e última coluna juntas dão-nos a informação necessária para reconstruir pois temos todos os pares de caracteres e a sua sequência. Esta informação permite construir um vetor para as seguintes colunas e a informação guardada da linha original permite reconstruir tudo.

PPM

Não sendo um algoritmo de compressão propriamente dito, mas antes um algoritmo de previsão, o PPM (prediction by partial matching) é usado, entre outras coisas, para fins de compressão de dados. O conceito é elegantemente simples, tendo, no entanto, implementações bem complexas. O algoritmo consegue retornar a probabilidade de distribuição do próximo símbolo a ser codificado, tendo em conta os dados anteriores, semelhante ao formato do dicionário da LZ77, aqui chamada de contexto. Comparando com a língua portuguesa, sabemos que a letra “u” é pouco comum, mas é extremamente comum que apareça depois de um “q”. O mesmo acontece ao contrário: uma consoante a seguir a um “q” é extremamente improvável (para não dizer impossível) na língua portuguesa. Estes casos são muito simples com diferenças de probabilidades enormes, mas a capacidade deste algoritmo passa por detetar tendências mais suaves nos conjuntos de 1 e 0. No entanto, o uso de contextos grandes iria requerer um grande número de cálculos e capacidade de armazenamento das probabilidades condicionais calculadas, o que poderia comprometer o uso do algoritmo. Para fazer face a esta dificuldade, o PPM executa este procedimento faseadamente ao longo da leitura. Este é chamado um modelo de contexto adaptativo porque usa o contexto exatamente precedente ao caracter a codificar e não uma tabela fixa. Ele começa por analisar o contexto C precedente ao caracter S de ordem n (ou tamanho de n caracteres). Caso não encontre no conjunto de dados já processado um contexto C seguido de caracter S, ele assume probabilidade de 0 e recomeça com um contexto de tamanho n-1. Quando a probabilidade é maior que 0, envia para o codificador o símbolo S com probabilidade P. Como um exemplo de compressão de texto, suponhamos que o algoritmo está a analisar um contexto de ordem 3 “dos” que apareceu 27 vezes no passado e 11 vezes foi seguido por um espaço, 9 vezes por uma “s”, 6 vezes por um “e” e 1 vez por um “i”. Se o símbolo a codificar for um espaço, é enviado para o codificador aritmético com uma probabilidade de 11/27 e as probabilidades são atualizadas para 12/28, 9/28, 6/28 e 1/28. Se o símbolo fosse diferente destes (por exemplo um “p”) passaríamos para a ordem 2 (“os”), 1 (“s”), 0 que são as vezes que simplesmente apareceu um ”p” no passado e se mesmo assim nunca tivesse aparecido um “p”, passaríamos para contexto -1 e seria codificado com 1/(tamanho do alfabeto). Ordem -1 é muito comum no início da codificação. Para se conseguir descodificar, a alteração da ordem do contexto tem de ficar contabilizada e perfeitamente indicada, pois descodificador não sabe qual é o caracter seguinte. Isto é feito através de um escape symbols para o descodificador saber que tem de reduzir a ordem do contexto. Assim no caso referido em cima, quando o codificador chega a um contexto de ordem -1, vindo de um de ordem 3, deve antes ter codificado 4 escape symbols antes.

Seguindo o exemplo da figura 6, assumindo que “assanissimassa” já foi codificado e está-se a utilizar uma ordem de contexto 2 (“sa” portanto), podem acontecer 1 de 4 alternativas baseadas no caracter a seguir: (1) Caso fosse “n”, o algoritmo já tinha encontrado “sa” seguido por um “n” e, portanto, iria enviar a probabilidade (1/2) (2) Caso fosse “s”, o algoritmo nunca viu “sa” seguido de um “s”, e iria, portanto, descer um nível de ordem de contexto que passaria a “a” e enviaria para o codificador um escape symbol com probabilidade (1/2). Como o codificador já viu um “a” seguido de um “s”, envia com a probabilidade associada (2/5) (3) Caso fosse “m”, o algoritmo não iria encontrar match nos contextos de ordem 2 nem 1 por isso passaria para o contexto 0 (enviando dois escape symbols) e mandaria o “m” sozinho e a sua probabilidade (1/19) (4) Finalmente temos o caso de ser por exemplo um “d” que o algoritmo nunca viu. Por isso nenhuma das ordens de contexto anteriores iria encontrar match e, portanto, iriam ser codificados 3 escape symbols e enviaria o “m” com a probabilidade de 1/28 (todo o alfabeto/hipóteses)

PAQ e Content-mixing

O PAQ é um algoritmo open-source veio trazer alguma disrupção ao mundo da compressão. Este algoritmo de alta-performance baseado em context-mixing está atualmente no topo dos rankings de compressão, apesar de ter um custo elevado de memória e tempo (quem tem vindo a ser combatida). Mas a grande revolução está associada ao facto de ser open-source e permitir muitas versões, subversões, derivações e spin-offs. O uso de context-mixing tem sido o principal objeto de intervenção e desenvolvimento nos últimos tempos, principalmente devido à aplicação de conceitos experimentais de machine-learning. De certa forma este formato teve origem através do PPM e do Burrows-Wheeler , uma vez que é baseado em distribuição algorítmica. No entanto existem duas grandes diferenças:

(1) O contexto passa a ser uma função complexa dos dados já vistos; (2) Ao invés de um único modelo previsor, existem vários modelos. O PAQ consegue ultrapassar algumas das limitações do PPM, não requisitando que os contextos sejam contíguos. Context-mixing entra neste modelo na medida em que o PAQ não usa apenas um modelo de probabilidades, mas vários que posteriormente cruza e atribui pesos diferentes. Os principais modelos de contexto são:

• n-grams; em que é baseado nos últimos n bytes antes do símbolo a prever (tal como o PPM); • whole-word n-grams, ignorando letras maiúsculas e caracteres não alfabéticos (útil em texto); • Contextos “sparse” que apenas conta o segundo e quarto byte antes do símbolo a prever (útil em alguns formatos binários); • Contextos analógicos, consistindo em bits de ordem elevada 8-16 bit (útil em multimédia); • Modelos especializados que são executados quando um certo formato de ficheiro é detetado.

A união dos resultados destes modelos irá originar a probabilidade a codificar para o caracter. A probabilidade é ponderada tendo em conta os pesos dos modelos. A título de exemplo, do PAQ1 ao PAQ3, as várias probabilidades eram combinadas por somatório ponderado, sendo que era atribuído um peso superior aos contextos mais longos. Do PAQ4 ao 6, eram atribuídos mais pesos aos contextos mais exatos e finalmente a partir do PAQ7, as probabilidades eram atribuídas usando redes neurais.

Formatos de ficheiros

Entre os formatos de compressão mais conhecidos, o que é sem duvida mais conhecido é o “.zip”. Este formato está amplamente difundido a nível mundial pela sua capacidade de compressão, rapidez e compatibilidade. Este formato foi criado por Phil Katz em 1989 e consegue utilizar vários algoritmos, mas usa essencialmente DEFLATE que é baseado no LZ77 e que também foi desenvolvido por Katz. Consegue comprimir até 16 exabytes de ficheiros. 9 O formato .rar também tem tido alguma popularidade pelo publico geral e é baseado nos algoritmos de Lempel-Ziv e PPM. Foi criado por Eugene Roshal, sendo que é dai que deriva o seu nome – Roshal ARchive. Os programas usados são o RAR e o WinRAR que oferecem completo suporte para .rar e .zip. Consegue também descomprimir um conjunto de outros formatos, mas não comprimir. Consegue comprimir até 8,6 biliões de gigabytes (ou qualquer coisa como 7.8 zettabytes).

Benchmark

Para se perceber de que maneira se fazem as comparações entre algoritmos, é preciso perceber alguns conceitos que serão comuns a todos. São eles rácio de compressão, fator de compressão e ganhos de compressão. O rácio é uma fórmula simples e intuitiva:

Rácio de compressão=(Tamanho do output) / (Tamanho do input)

Esta também é reconhecida por bit per bit, porque irá traduzir na quantidade de bits necessários para traduzir um bit do input. A expressão 100x (1- rácio de compressão) é usada como intermutável com o rácio, embora neste caso um valor de 80% indicará que o resultado ocupa 20% do original. O fator de compressão é o rácio elevado a -1 ou:

Fator de compressão=(Tamanho do input)/(Tamanho do output)

Neste momento no topo em termos de capacidade de compressão estão os algoritmos baseados em context-mixing como nanozip, modificações da PAQ e do PPM que já conseguem valores de compressão ao nível do bit por byte, com os seguintes valores:

Atualmente existe um concurso chamado de “Hutter Prize”, iniciado em 2006 por Marcus Hutter, onde a candidatura é aberta a toda a gente e oferece 500 euros por cada 1% de compressão adicional sobre o atual vencedor. O ficheiro a comprimir é o enwik8 que se baseia nos primeiros 100 000 000 caracteres da wikipedia em inglês. Os últimos 3 algoritmos vencedores foram da autoria de Alexander Rhatushnyak com versões do PAQ.