LZ78,LZW

Os algoritmos da família LZ (LZ77, LZ78 e LZW), ao contrário dos métodos baseados na codificação estatística, que produzem códigos de comprimento variável associados a símbolos de comprimento fixo, efetuam uma codificação baseada em dicionários, produzindo códigos de comprimento fixo que estão associados a sequências de símbolos de comprimento variável que, normalmente, ocorrem em conjunto como, por exemplo, as palavras de um determinado idioma.

O método LZ78 usa um dicionário explícito e consiste em referir que parte do dicionário, que vai sendo construído à medida que o algoritmo de codificação avança, se está a repetir de forma que se use um número de Bytes inferior ao número de Bytes do código original.  Neste método é utilizado o formato: gzip.

Já o método LZW produz uma sequência de dados comprimidos porque utiliza um único código para representar vários símbolos de entrada, ao contrário da codificação de Shannon-Fano e da codificação de Huffman que obtêm a compressão pela utilização de um código diferente para cada símbolo de entrada, mas produzindo códigos com menos bits para os símbolos que ocorrem com mais frequência.Neste método são usados os formatos : TIF e GIF.

O artigo completo sobre ao algoritmos LZ78 e LZW irá ser publicado no Portal da Compressão Multimédia, em http://multimedia.ufp.pt, onde será disponibilizada uma applet java para cada um destes algoritmos que ilustra o detalhadamente o funcionamento destes métodos de compressão sem perdas.

Anúncios

QM-Coder

O QM-Coder é um método de codificação aritmética binária para imagens JPEG (Joint Photographic Experts Group), mas também é utilizado para imagens JBIG (Joint Photographic Experts Group) e no âmbito do formato mais recente JPEG-2000.

Este codec é propriedade de 3 organizações (IBM, Mitsubishi e Lucent),tem uma variante, o MQ-coder, que, por sua vez, é igualmente propriedade de 2 organizações (IBM e Mitsubishi), sendo este último utilizado para compressão de imagens JBIG2 e JPEG-2000.

O QM-Coder utiliza a codificação aritmética, que é um método de codificação de entropia, logo, um método sem perdas, aliado a métodos de codificação estatística. Sendo um codificador aritmético binário, não se centra apenas na codificação aritmética, mas usa este método somente para a geração do código binário. Isto faz com que o QM-Coder seja um codec rápido e simples, mas o facto de ser um método patenteado limita um pouco o seu uso.

O artigo completo sobre o QM-Coder irá ser publicado no Portal da Compressão Multimédia, em http://multimedia.ufp.pt, onde será disponibilizada uma applet java que ilustra o detalhadamente o funcionamento deste método de compressão.

Shannon-Fano, Huffman, Huffman adaptativo

Este artigo refere-se à demonstração dos algoritmos de compressão e descompressão de dados sem perdas Shannon-Fano, Huffman e Huffman adaptativo, para melhor se compreenderem os passos necessários para a codificação e descodificação da informação.

O algoritmo de Shannon-Fano trata-se de um algoritmo de codificação de entropia, uma vez que efetua uma compressão sem perdas, e corresponde ao melhoramento da eficiência de representação da informação digital, sendo independente do tipo de dados a comprimir, representando uma codificação da informação com códigos de comprimento variável. Baseia-se na construção de uma árvore binária, de acordo com uma abordagem top-down.

O algoritmo de Huffman é igualmente um algoritmo de codificação de entropia, uma vez que também efetua uma compressão sem perdas (melhoramento da eficiência de representação da informação binária), sendo igualmente independente do tipo de dados a comprimir, e codificando a informação de entrada recorrendo a códigos binários de comprimento variável.

Um dos codecs mais conhecidos que usa o algoritmo de Huffman é o mp3. O algoritmo de Huffman é igualmente utilizado no âmbito dos formatos JPEG e MPEG, embora com algumas modificações. Este algoritmo baseia-se igualmente na construção de uma árvore binária, mas desta vez acordo com uma abordagem bottom-up.

O método de Huffman Adaptativo é considerado um método de compressão simétrico, já que a complexidade e o tempo de execução do respetivo codificador são idênticos aos da descompressão. Este método insere-se na categoria dos codificadores de entropia (compressão sem perdas). Relativamente ao algoritmo de Huffman adaptativo, pretendemos demonstrar a eficiência do método e a sua diferença em termos de rácio de compressão com o método original no contexto do artigo completo a ser publicado brevemente.

O artigo completo sobre os algoritmos de Shannon-Fano, Huffman e Huffman Adaptativo irão ser publicados no Portal da Compressão Multimédia, em http://multimedia.ufp.pt , onde será disponibilizada uma applet java que ilustra o detalhadamente o funcionamento de cada um destes métodos de compressão.

Deflate

O deflate é um método de compressão sem perdas e uma técnica de codificação de entropia, baseado na combinação do algoritmo LZ77 com Huffman. Foi originalmente definido por Phil Katz e mais tarde especificado no RFC 1951. O LZ77 foi publicado por Abraham Lempel e Jacob Zib em 1977, enquanto que o algoritmo da codificação de Huffman foi desenvolvido por David A. Huffman enquanto estudante do MIT, e foi publicado em 1952. No entanto o método de compressão deflate foi criado apenas em 2008.

O método deflate é um método de compressão muito popular, originalmente usado nos formatos ZIP e GZIP, mas que tem sido adoptado por diversas aplicações, destacando-se o protocolo HTTP, o formato PNG e o formato PDF. O método deflate foi concebido por Philip Katz como parte do formato ZIP, estando ambos disponíveis para utilização pública, o que faz com que partes destes algoritmos apareçam em várias plataformas.

O formato PNG (Portable Network Graphics) surgiu nos anos 90, especificamente em 1994, fruto das questões legais em torno do formato GIF e das respetivas patentes, nomeadamente do facto da Unisys ter decidido patentear o algoritmo base do GIF, o LZW, e começar a cobrar direitos pelo seu uso.

O artigo completo sobre o método deflate e o formato PNG irá ser publicado no Portal da Compressão Multimédia, em http://multimedia.ufp.pt , onde será disponibilizada uma applet java que ilustra o detalhadamente o funcionamento deste método de compressão.

Codificação Aritmética

A codificação aritmética é um técnica de compressão de tamanho variável da qual também faz parte também por exemplo, a codificação de Huffman. No caso da codificação de Huffman esta só produz códigos de tamanho variável ideais (códigos cujo o tamanho médio iguala a entropia ) quando os símbolos têm probabilidades de ocorrência que são potências negativas de 2 (ou seja, números, como 1/2, 1/4 ou 1/8).

A codificação aritmética ultrapassa o problema de atribuição de códigos inteiros para os símbolos individuais, atribuindo um código único para todo o ficheiro de entrada, começando por percorrer o ficheiro de entrada símbolo a símbolo, e usa a probabilidade de cada símbolo para ir limitando o intervalo final resultante. A especificação de um intervalo mais curto requer mais bits (maior precisão), o que significa que o número fracionário determinado pelo algoritmo da codificação aritmética cresce continuamente. Para se conseguir a compressão, o algoritmo está concebido de tal maneira que um símbolo de alta probabilidade reduz mais o intervalo do que um símbolo de baixa probabilidade, resultando assim que os símbolos de alta probabilidade contribuem com menos bits para a saída.

O código de saída produzido é um número binário fracionário que se situa dentro do intervalo final calculado pelo algoritmo da codificação aritmética. Existem várias formas para obter este número binário que serão abordadas no artigo completo. A codificação aritmética é, de entre os métodos de compressão de comprimento variável, o mais eficiente uma vez que atinge sempre a entropia; contudo, a sua utilização é limitada, pois este algoritmo é uma patente registada ao contrário dos outros algoritmos, e isso pode ter implicação no custo final de um produto/sotfware que use este algoritmo.

O artigo completo sobre a codificação aritmética irá ser publicado no Portal da Compressão Multimédia, em http://multimedia.ufp.pt, onde será disponibilizada uma applet java que ilustra o detalhadamente o funcionamento deste método de compressão.