Algoritmos e Estruturas de Dados III - AED3 10 02 Codificação Elias Gama

Videoaula da disciplina Algoritmos e Estruturas de Dados III no curso de Ciência da Computação da PUC Minas - 2018 ---------------------- A codificação Elias Gama é uma forma de codificação em que buscamos usar menos bits para números pequenos e mais bits para números grandes. Esse tipo de codificação considera, portanto, que números pequenos são muito mais frequentes que os números grandes. ---------------------- A compressão estatística, isto é, aquela baseada na probabilidade, é apenas uma das formas de compressão. Existem outras, mas, por enquanto, ficaremos com essa para ver como ela funciona. Nessa codificação, precisamos usar alguma sequência binária de tamanho variável. Se todos os símbolos (ex.: letras) dessa informação tiverem a mesma quantidade de bits, então não conseguiremos compactar nada. O segredo todo dessa compressão é, portanto, encontrar uma forma de codificação diferente. Por exemplo, em uma situação em que números pequenos apareçam muito mais vezes que números grandes, podemos uma compressão unária, em que: Valor Código 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 7 11111110 8 111111110 9 1111111110 10 11111111110 Mas, por essa tabela, dá para perceber que essa codificação logo, logo fica pior que a codificação binária tradicional (de tamanho fixo), não é? Então, precisamos encontrar alguma outra forma melhor. Uma delas, ainda aplicada apenas a números pequenos, mas que já é mais eficiente, é a codificação Elias Gama. Essa codificação se apoia no fato de que todo número N pode ser representado a partir de uma potência de 2: N = 2^p + q em que q deve ser menor que 2p. Por exemplo: - 5 = 2^2 + 1 - 13 = 2^3 + 5 - 38 = 2^5 + 6 Aí podemos codificar a potência p usando uma sequência unária (de zeros) e o resto q usando uma sequência binária (com mesmo número de bits de p). Dessa forma, chegaríamos aos seguintes códigos para os números pequenos. Valor Código 0 0 1 10 2 010 3 011 4 00100 5 00101 6 00110 7 00111 8 0001000 9 0001001 10 0001010 Melhorou bastante, não é? No entanto, números grandes ainda precisarão de muitos bits. Considere também que um número a ser codificado por ser usado para representar um alfabeto (A=0, B=1, C=3, ...), cores (branco=0, amarelo=1, verde=2, ...), eventos (clicar=0, arrastar=1, teclar=2, ...) e muito mais.