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.