Veamos la aproximación trivial, que en muchos casos puede ser la óptima:
Sería almacenar:
- El número de elementos del rango (con 31 bits, ya que las listas en Java están limitadas a 2 ^ 31 - 1 elementos).
- Seguido de 1 bit para cada índice, indicando si el elemento está presente en el Set o no.
Esa es la implementación que tenía la primera versión del compresor fractal de imágenes, para almacenar los datos de los split y merge de las triangulaciones.
Aunque no era la óptima, ya que a medida que avanzaban iteraciones de los split, iba disminuyendo el número de elementos a almacenar, llegando a ser de un porcentaje muy pequeño del total, en cuyo caso la codificación trivial puede mejorarse substancialmente.
Ahora el objetivo es mejorar esa codificación trivial, para ver si se puede obtener una codificación más comprimida en número de bits ocupados.
Primera aproximación. Cuando el número de elementos del set es mucho menor que el tamaño del rango, podemos pensar en guardar los índices presentes.
En este caso la ocupación sería:
- 31 bits para el número de elementos del rango.
- 31 bits para el número de elementos presentes en el Set.
- 31 bits * el número de elementos presentes en el Set.
Segunda aproximación. Mejoramos el número de bits por elemento almacenado:
- 31 bits para el número de elementos del rango. Se calcularía el número de bits del mayor elemento del rango (numBitsElem).
- 5 bits para almacenar numBitsElem. Así pues, si el número de elementos del rango fuera 1023, se almacenaría un 10 en estos 5 bits.
- numBitsElem bits, para almacenar el número de elementos en el Set.
- numBitsElem bits * el número de elementos presentes en el Set.
Buenoo, poco a poco nos vamos acercando a una codificación mejor ...
Tercera aproximación. Nos damos cuenta de que si ordenamos el set en orden ascendente, las deltas (diferencias entre elementos consecutivos), seguramente se pueda codificar con menos bits que un elemento absoluto del rango:
- 31 bits para el número de elementos del rango. Calculamos el numBitsElem menor para poder codificar un elemento. Calculamos también la lista de deltas (lista de diferencias entre elementos consecutivos de la lista ordenada de elementos del Set). Y por último calculamos también numBitsDelta
- 5 bits para almacenar numBitsElem.
- 5 bits para almacenar numBitsDelta.
- numBitsElem bits, para almacenar el número de elementos del Set.
- numBitsDelta bits * el número de elementos en el Set.
Buenoo, parece que ya estamos alcanzando la codificación óptima, no ? ...
Seguimos ...
Cuarta aproximación. Nos centramos en el hecho de que puede haber un número mucho mayor de deltas menores, y quizás sólo unas pocas mucho mayores, que nos rompen el numBitsDelta.
En esas condiciones, quizás podríamos encontrar un numOptimumBitsDelta menor que el máximo numMaxBitsDelta, que a su vez es menor o igual que numBitsElem.
Pero como codificamos un elemento delta que exceda numOptimumBitsDelta ?
Pues ... como las deltas nunca valdrán 0 (en un Set no hay elementos repetidos), pues podemos usar el valor 0, para indicar que es un valor especial.
Y a ese 0, le seguiría el valor de la delta, pero codificado esta vez con numMaxBitsDelta.
El número de bits total, podría calcularse así:
- 31 bits para el número de elementos del rango. Calculamos el numBitsElem menor para poder codificar un elemento. Calculamos también la lista de deltas (lista de diferencias entre elementos consecutivos de la lista ordenada de elementos del Set).
- 31 bits, para almacenar el número de elementos del Set.
- 5 bits para almacenar numOptimumBitsDelta.
- 5 bits para almacenar numMaxBitsDelta.
- numOptimumBitsDelta bits * el número de elementos en el Set.
- numMaxBitsDelta bits * el número de deltas que excedan numOptimumBitsDelta.
Habremos alcanzado ya la codificación óptima ?
Quinta aproximación. Pues ... aprovechando que ya hemos programado todo esto ... Podríamos pensar en la situación complementaria ... Podría ser que codificar el complementario del Set con ese mismo algoritmo produjera resultados más comprimidos ?
Entiéndase el complementario del Set como otro Set, disjunto con el original, cuya unión con el Set original sea el rango completo.
Es decir, el Set complementario tendría todos los elementos del rango ausentes en el Set original, y ninguno de los del Set original.
La gracia es que a partir de un Set, es muy fácil obtener el Set complementario, y por lo tanto podríamos obtener el Set original, habiendo codificado el Set complementario.
La aplicación evidente, es un Set que tenga todos los elementos del rango menos uno, o unos pocos ...
Pues ... si guardamos solo los ausentes (el Set complementario), podría almacenarse en un tamaño mucho menor, no?
La codificación de este caso, podría ser así:
- 31 bits para el número de elementos del rango. Calculamos el numBitsElem menor para poder codificar un elemento. Calculamos también la lista de deltas (lista de diferencias entre elementos consecutivos de la lista ordenada de elementos del Set).
- 1 bit, para guardar si almacenamos el Set original, o el complementario. Este es el bit extra.
- 31 bits, para almacenar el número de elementos del Set.
- 5 bits para almacenar numOptimumBitsDelta.
- 5 bits para almacenar numMaxBitsDelta.
- numOptimumBitsDelta bits * el número de elementos en el Set.
- numMaxBitsDelta bits * el número de deltas que excedan numOptimumBitsDelta, en las posiciones en las que aparezcan.
Bueno ... ahora sii.
Pues ahí me quedé ... Pero soy consciente de que si se pueden hacer todas esas maravillas, que no se podría hacer buscando otros patrones, o simplemente usando un compresor sin pérdidas, tipo zip o 7z ...
Ahí se queda, en el tintero para la próxima ...
