Códigos de compressão

RKA10GM Quando representamos uma informação digitalmente, tal como uma imagem, significa que devemos cortá-la em pequenos pedaços. Isso nos permite enviar a imagem como uma sequência de símbolos coloridos, e essas cores podem ser representadas como números únicos usando alguns códigos. Considere o desafio a seguir: Alice e Bob podem transmitir e receber mensagens em binário. Eles cobram de seus clientes um centavo por bit para usar o seu sistema. Suponha que um cliente chegue e queira mandar uma mensagem, sendo que esta mensagem tem um tamanho de 1.000 símbolos. O significado das mensagens é completamente desconhecido. Normalmente, isso é enviado por um código padrão de 2 bits, o que resulta em cobrar 2.000 bits. No entanto, Alice e Bob já fizeram algumas análises desse cliente anteriormente e determinaram que a probabilidade de aparecer cada símbolo na mensagem é diferente. Será que eles podem usar essas probabilidades conhecidas para comprimir a transmissão e aumentar seu lucro? Qual é a estratégia de codificação ideal? David Huffman forneceu a estratégia ideal, que ele publicou em 1952, e na qual se baseou em construir uma árvore binária da base ao topo. Para começar, podemos listar todos os símbolos na base, que chamamos de nós. Então, achamos os dois nós menos prováveis. Nesse caso, "B" e "C", e os fundimos em um só, e adicionamos as probabilidades umas às outras. Depois, repetimos isso com os próximos dois nós menos prováveis e continuamos fundindo até termos apenas um único nó no topo. Finalmente, etiquetamos as pontas nesta árvore com zero ou 1 em qualquer ordem. Agora, o código para cada letra é apenas o caminho do topo da árvore até a letra dada. Então, para "A" é apenas uma ponta ou 1. Agora, isto é conhecido como codificação Huffman e levando em conta os exemplos a seguir, não é possível decifrá-la. Vá em frente e tente. Por exemplo, se você diminuir o código para "D", para apenas zero, então, a mensagem 011 poderá significar, talvez, DAA. Ou talvez apenas "B". Para isso funcionar, você precisa introduzir o espaço das letras, que cancelarão qualquer economia durante a transmissão. Até onde vai essa compressão de mensagem comparada ao original de 2.000 bits? Precisamos calcular o número de bits por letra em média. Então, multiplicamos o comprimento de cada código vezes a probabilidade de ocorrência e adicionamos um ao outro, o que resultará no comprimento médio de 1,75 bits por símbolo em média. Significa que com essa codificação Huffman, esperamos comprimir as mensagens de 2.000 bits para 1.750 bits. E Claude Shannon foi o primeiro a reivindicar que o limite da compressão será sempre a entropia da fonte da mensagem. À medida que a entropia ou a incerteza de nossa fonte diminui para estruturas estatísticas conhecidas, a habilidade de compressão aumenta. Enquanto que se a entropia aumenta devido à imprevisibilidade, nossa habilidade de compressão diminui. Se queremos comprimir além da entropia, precisamos, necessariamente, retirar informação das nossas mensagens.