Vamos olhar para a abordagem trivial, que em muitos casos pode ser ideal:
Ele armazenaria:
- O número de elementos no intervalo (com 31 bits, uma vez que as listas em Java são limitadas a 2-31 - 1 elementos).
- Seguido por 1 bit para cada índice, indicando se o elemento está presente no conjunto ou não.
Esta é a implementação que a primeira versão do compressor de imagem fractal tinha, para armazenar os dados das divisões e fusões das triangulações.
Embora não fosse ideal, uma vez que à medida que as iterações das divisões progrediam, o número de elementos a serem armazenados diminuiu, tornando-se uma porcentagem muito pequena do total, caso em que a codificação trivial pode ser substancialmente melhorada.
Agora o objetivo é melhorar essa codificação trivial, para ver se uma codificação mais compactada em termos do número de bits usados pode ser obtida.
Primeira abordagem Quando o número de elementos no conjunto é muito menor do que o tamanho do intervalo, podemos considerar armazenar os índices presentes.
Neste caso, o uso seria:
- 31 bits para o número de elementos no intervalo.
- 31 bits para o número de elementos presentes no conjunto.
- 31 bits * o número de elementos presentes no conjunto.
Segunda abordagem . Melhoramos o número de bits por elemento armazenado:
- 31 bits para o número de elementos no intervalo. O número de bits do maior elemento no intervalo ( numBitsElem ( ) serão calculados.
- 5 bits para armazenar numBitsElem .Então, se o número de elementos no intervalo fosse 1023, um 10 seria armazenado nesses 5 bits.
- numBitsElem para armazenar o número de elementos no conjunto.
- numBitsElem * o número de elementos presentes no conjunto.
Bem, pouco a pouco estamos nos aproximando de uma codificação melhor...
Terceira aproximação . Percebemos que, se classificarmos o conjunto em ordem crescente, os deltas (diferenças entre elementos consecutivos) provavelmente podem ser codificados com menos bits do que um elemento absoluto do intervalo:
- 31 bits para o número de elementos no intervalo.
- Calculamos o menor numBitsElem para codificar um elemento.Também calculamos a lista de deltas (lista de diferenças entre elementos consecutivos da lista ordenada de elementos no conjunto).E, finalmente, também calculamos numBitsDelta
- 5 bits para armazenar numBitsElem .
- 5 bits para armazenar numBitsDelta .
- numBitsElem para armazenar o número de elementos no conjunto.
- numBitsDelta * o número de elementos no conjunto.
Bem, parece que já estamos chegando à codificação ideal, certo?...
Vamos continuar...
Quarta aproximação . Nós nos concentramos no fato de que pode haver um número muito maior de deltas menores, e talvez apenas alguns muito maiores, que quebram o numBitsDelta .
Nestas condições, podemos encontrar um numoptimumBitsDelta menor que o máximo numMaxBitsDelta , que por sua vez é menor ou igual a numBitsElem .
Mas como codificamos um elemento delta que excede numoptimumBitsDelta ?
Bem... uma vez que os deltas nunca serão 0 (não há elementos repetidos em um conjunto), podemos usar o valor 0 para indicar que é um valor especial.
E que 0 seria seguido pelo valor do delta, mas codificado desta vez com numMaxBitsDelta .O número total de bits pode ser calculado da seguinte forma:
- 31 bits para o número de elementos no intervalo. Calculamos o menor numBitsElem para poder codificar um elemento. Também calculamos a lista de deltas (lista de diferenças entre elementos consecutivos da lista ordenada de elementos no Conjunto).
- 31 bits, para armazenar o número de elementos no conjunto.
- 5 bits para armazenar numoptimumBitsDelta .
- 5 bits para armazenar numMaxBitsDelta .
- numoptimumBitsDelta * o número de elementos no conjunto.
- numMaxBitsDelta * o número de deltas que excedem numoptimumBitsDelta .
Já atingimos a codificação ideal?
Quinta aproximação Bem... já que já programámos tudo isto...Podemos pensar na situação complementar...Seria possível que codificar o complemento do conjunto com o mesmo algoritmo produziria resultados mais comprimidos?
O complemento do conjunto é entendido como outro conjunto, desarticulado do original, cuja união com o conjunto original é toda a gama.
Ou seja, o conjunto complementar teria todos os elementos do intervalo ausentes no conjunto original, e nenhum deles no conjunto original.
A beleza é que a partir de um conjunto, é muito fácil obter o conjunto complementar e, portanto, poderíamos obter o conjunto original, tendo codificado o conjunto complementar.
A aplicação óbvia é um conjunto que tem todos os elementos do intervalo, exceto um, ou alguns...
Bem... se armazenarmos apenas os ausentes (o conjunto complementar), ele pode ser armazenado em um tamanho muito menor, certo?
A codificação neste caso poderia ser assim:
- 31 bits para o número de elementos no intervalo. Calculamos o menor numBitsElem Também calculamos a lista de deltas (lista de diferenças entre elementos consecutivos da lista ordenada de elementos no Conjunto).
- 1 bit, para armazenar se nós armazenamos o conjunto original, ou o complemento.Esta é a parte extra.
- 31 bits, para armazenar o número de elementos no conjunto.
- 5 bits para armazenar numoptimumBitsDelta .
- 5 bits para armazenar numMaxBitsDelta .
- numoptimumBitsDelta * o número de elementos no conjunto.
- numMaxBitsDelta * o número de deltas que excedem numoptimumBitsDelta nas posições em que aparecem.
Bem... agora estamos a falar.
Mas estou ciente de que, se todas essas maravilhas puderem ser feitas, o que não poderia ser feito procurando outros padrões, ou simplesmente usando um compressor sem perdas, como zip ou 7z...
Isso vai ter que esperar, em segundo plano para a próxima vez...
