Algoritmos de compressão

Este artigo faz uma apresentação dos algoritmos de compressão e qual a lógica de funcionamento dos mesmos. É o primeiro de uma série de três artigos que pretendo escrever falando sobre isso, que serão divididos em como começou, o que usamos hoje em dia, e por último a prática com implementação dos mais usados.

[ Hits: 11.451 ]

Por: Pablo Margreff em 23/03/2016 | Blog: https://pmargreff.wordpress.com/


Códigos de comprimento variável



Toda a informação que geramos em qualquer área associada e derivada da computação no final das contas é binária, o que a codificação tenta fazer é representar em menos bits e ter o mesmo significado (compressão) ou que possa representado em menos bits e possa ser transformado de volta na informação original (compactação). Resumindo: Quanto menor, melhor.

Começaremos com códigos de comprimento variável, que são nada mais que o número de bits que um certo código (letra, número ou símbolo) ocupa. Esse tipo de compressão necessita zero de perda de informação.

A teoria de informação fundamentada por Claude Shannon, basicamente relaciona a conteúdo de uma informação com a probabilidade de um símbolo aparecer em uma sequência. O que mede esta probabilidade é uma função logarítmica. Que consegue encontrar o tamanho que teremos de informação binária. A função logarítmica é definida por:
Outra fórmula que teremos que entender será a definição de entropia, que é o número mínimo de bits que conseguimos representar uma informação, e é definida por:
Achou complicado meu/minha jovem? Tudo bem, vamos por isso em prática. Imaginemos que temos uma palavra com apenas quatro símbolos e a mesma probabilidade de ocorrência para todos os símbolos, como mostra a tabela abaixo
Neste caso, se aplicarmos a fórmula teremos uma entropia 2 o que nos diz que precisamos em média do dois bits para representar cada símbolo. A representação se faz como na tabela a seguir.
Agora vamos alterar apenas a frequência que a primeira e a última letras aparecem. Como a próxima tabela.
Aplicando a fórmula novamente então temos que uma entropia de 1.57, isso quer dizer que cada variável tem em média o tamanho de 1.57 bits. Mas como isso pode acontecer? Na verdade é bem simples, se sabemos que uma variável aparece mais que outras, podemos representar a mesma com um código menor.
Eficiente, porém pare, volte a tabela anterior e pense qual o problema que ela pode gerar. Encontrou? Não, então pense mais um pouco. Sim, é isso mesmo, não podemos ser formado por uma palavras que contenha sub-palavras que já estão na tabela, isso (a não ser que tenhamos uma máquina que possa gerar soluções não determinísticas) nos resulta em um problema de indecidibilidade. No exemplo da tabela a baixo temos que o código de D é formado por sub-palavras que formam os códigos de A e B.
Isso para o exemplo da palavra formada por 000011 nos deixa impossibilitados de sabermos com absoluta certeza se estávamos representando CD ou CBA.

Este foi o primeiro tipo de codificação usada na área, existem diversos códigos de comprimento variável, você pode se aprofundar neles aqui.

Página anterior     Próxima página

Páginas do artigo
   1. Introdução
   2. Códigos de comprimento variável
   3. Árvores de Huffmann
   4. Classe Lempel-Ziv-Welch
   5. Conclusões
Outros artigos deste autor

Aumentando sua produtividade com o teclado padrão Dvorak

Manipulação de imagens no formato PPM

Gerando Números Aleatórios

Leitura recomendada

Ativando zRAM no Slackware

Implementando um kernel GNU/Linux mais seguro

Guerra Infinita, uma análise da Ciência da Computação

Atualizando kernel de 2.4.31 para 2.6.13 no Slackware 10.2

Recompilando o Kernel no Ubuntu Linux 9.04

  
Comentários
[1] Comentário enviado por ivo_cruz em 29/03/2016 - 08:30h

A saída do Q é 0100


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts