Vegem l'aproximació trivial, que en molts casos pot ser l'òptima:
Sería guardar:
- El número d'elements del rang (amb 31 bits, ja que les llistes estan limitades a Java a 2 ^ 31 - 1 elements).
- Després segueix 1 bit per a cada índex, indicant si l'element està present al Set o no.
Aquesta és la implementació que tenia la primera versió del compressor fractal d'imatges, per a guardar la informació dels split i merge de les triangulacions.
Però no era l'òptima, ja que a mida que avançaven les iteracions dels split, anava disminuint el número d'elements a guardar, arribant a ser d'un percentatge molt petit del total, cas en el que la codificació trivial pot millorar-se substancialment.
Ara l'objectiu és millorar aquesta codificació trivial, per a veure si es pot obtenir una codificació més comprimida en número de bits ocupats.
Primera aproximació. Quan el número d'elements del set és molt menor que la mida del rang, podem pensar en guardar els índex presents.
En aquest cas l'ocupació seria:
- 31 bits per el número d'elements del rang.
- 31 bits per el número d'elements presents al Set.
- 31 bits * el número d'elements presents al Set.
Segona aproximació. Millorem el número de bits per element guardat:
- 31 bits per al número d'elements del rang. Es calcularía el número de bits de l'element mes gran del rang (numBitsElem).
- 5 bits para a guardar numBitsElem. Així doncs, si el número d'elements del rang fos 1023, es guardaria un 10 en aquestos 5 bits.
- numBitsElem bits, para guardar el número d'elements del Set.
- numBitsElem bits * el número d'elements presents en el Set.
Buenoo, poc a poc ens anem acostant a una codificació millor ...
Tercera aproximació. Ens adonem de que si ordenem el set en ordre ascendent, les deltes (diferències entre elements consecutius), segurament es pugui codificar amb menys bits que un element absolut del rang:
- 31 bits per al número d'elements del rang. Calculem el numBitsElem menor per a poder codificar un element. Calculem també la llista de deltes (llista de diferències entre elements consecutius de la llista ordenada d'elements del Set). Finalment calculem també numBitsDelta
- 5 bits per a guardar numBitsElem.
- 5 bits per a guardar numBitsDelta.
- numBitsElem bits, per a guardar el número d'elements del Set.
- numBitsDelta bits * el número d'elements del Set.
Buenoo, doncs sembla que ja estem arribant a la codificació òptima, no ? ...
Continuem ...
Quarta aproximació. Ens centrarem en el fet de que pugui haver un número molt més gran de deltas menors, i potser només unes poques molt més grans, que ens trenquin el numBitsDelta.
En aquestes condicions, potser podriem trobar un numOptimumBitsDelta més petit que el máximo numMaxBitsDelta, que alhora és més petit o igual que numBitsElem.
Però com codifiquem un element delta que excedeixi numOptimumBitsDelta ?
Doncs ... com les deltes mai valdran 0 (en un Set no hi ha elements repetits), doncs podríem ver servir el valor 0, per a indicar que és un valor especial.
I a aquest 0, li continuaria el valor de la delta, pero codificat aquesta vegada amb numMaxBitsDelta.
El número de bits total, podria calcular-se així:
- 31 bits per al número d'elements del rang. Calculem el numBitsElem més petit per a poder codificar un element. Calculem també la llista de deltes (llista de diferències entre elements consecutius de la llista ordenada d'elementos del Set).
- 31 bits, per a guardar el número d'elements del Set.
- 5 bits per a guardar numOptimumBitsDelta.
- 5 bits per a guardar numMaxBitsDelta.
- numOptimumBitsDelta bits * el número d'elements del Set.
- numMaxBitsDelta bits * el número de deltes que excedeixin numOptimumBitsDelta.
Haurem arribat ja a la codificació òptima ?
Cinquena aproximació. Doncs ... aprofitant que ja hem programat tot això ... Podríem pensar en la situació complementària ... Podria ser que en codificar el complementari del Set amb aquest mateix algorisme produïs uns resultats millors ?
Entenguis el complementari del Set un altre Set, disjunt amb l'original, que si es fa l'unió amb el Set original sigui el rang complert.
És a dir, el Set complementari tindria tots els elements del rang absents al Set original, i cap dels del Set original.
La gràcia és que a partir d'un Set, és molt fàcil obtenir el Set complementari, i per tant podríem obtenir el Set original, havent codificat el Set complementari.
L'aplicació evident, és un Set que tingui tots els elements del rang menys un, o menys uns pocs ...
Doncs ... si guardem només els absents (el Set complementari), podria guardar-se en un número de bits molt més petit, no?
La codificació de aquest cas, podria ser així:
- 31 bits per al número d'elements del rang. Calculem el numBitsElem més petit per a poder codificar un element. Calculem també la llista de deltes (llista de diferències entre elements consecutius de la llista ordenada d'elements del Set).
- 1 bit, per a guardar si traballem amb el Set original, o amb el complementari. Aquest és el bit extra.
- 31 bits, per a guardar el número d'elementos del Set.
- 5 bits per a guardar numOptimumBitsDelta.
- 5 bits per a guardar numMaxBitsDelta.
- numOptimumBitsDelta bits * el número d'elementos del Set.
- numMaxBitsDelta bits * el número de deltas que excedeixin numOptimumBitsDelta, a les posicions en que apareguin.
Bueno ... doncs ara sii.
Aquí ja vaig parar ... Però sóc conscient de que si es poden ver totes aquestes meravelles, que no es podria fer buscant d'altres patrons, o simplemente fent anar un compresor sense pèrdues, tipus zip o 7z ...
Potser per a la propera ...
