Examinons l'approche triviale, qui dans de nombreux cas peut être optimale:
Il stockerait :
- Le nombre d'éléments dans la plage (avec 31 bits, puisque les listes en Java sont limitées à 231 - 1 éléments).
- Suivi de 1 bit pour chaque index, indiquant si l'élément est présent dans l'ensemble ou non.
C'est l'implémentation que la première version du compresseur d'image fractale avait, pour stocker les données des scissions et des fusions des triangulations.
Bien que ce ne soit pas optimal, car au fur et à mesure que les itérations des splits progressaient, le nombre d'éléments à stocker diminuait, devenant un très faible pourcentage du total, auquel cas le codage trivial peut être considérablement amélioré.
Maintenant, le but est d'améliorer ce codage trivial, pour voir si un codage plus compressé en termes de nombre de bits utilisés peut être obtenu.
Première approche : Lorsque le nombre d'éléments de l'ensemble est beaucoup plus petit que la taille de la plage, nous pouvons envisager de stocker les indices présents.
Dans ce cas, l'utilisation serait:
- 31 bits pour le nombre d'éléments dans la plage.
- 31 bits pour le nombre d'éléments présents dans l'ensemble.
- 31 bits * le nombre d'éléments présents dans l'ensemble.
Deuxième approche . Nous améliorons le nombre de bits par élément stocké :
- 31 bits pour le nombre d'éléments dans la plage. Le nombre de bits de l'élément le plus grand dans la plage ( numBitsElem ) serait calculé.
- 5 bits pour stocker numBitsElem .Donc, si le nombre d'éléments dans la plage était 1023, un 10 serait stocké dans ces 5 bits.
- numBitsElem bits, pour stocker le nombre d'éléments dans le Set.
- numBitsElem bits * le nombre d'éléments présents dans l'ensemble.
Eh bien, petit à petit, nous nous rapprochons d'un meilleur encodage...
Troisième approximation Nous réalisons que si nous trions l'ensemble dans l'ordre croissant, les deltas (différences entre éléments consécutifs) peuvent probablement être codés avec moins de bits qu'un élément absolu de la plage:
- 31 bits pour le nombre d'éléments dans la plage.
- Nous calculons le plus petit numBitsElem pour encoder un élément.Nous calculons également la liste des deltas (liste des différences entre les éléments consécutifs de la liste triée des éléments de l'ensemble).Enfin, nous calculons également numBitsDelta
- 5 bits pour stocker numBitsElem .
- 5 bits pour stocker numBitsDelta .
- numBitsElem bits, pour stocker le nombre d'éléments dans le Set.
- numBitsDelta bits * le nombre d'éléments dans l'ensemble.
Eh bien, il semble que nous atteignons déjà l'encodage optimal, non?...
Continuons...
Quatrième approximation . Nous nous concentrons sur le fait qu'il peut y avoir un nombre beaucoup plus grand de petits deltas, et peut-être seulement quelques-uns beaucoup plus grands, qui brisent le numBitsDelta .
Dans ces conditions, nous pourrions trouver un numOptimumBitsDelta plus petit que le maximum numMaxBitsDelta , qui à son tour est inférieur ou égal à numBitsElem .
Mais comment encoder un élément delta qui dépasse numOptimumBitsDelta ?
Eh bien... puisque les deltas ne seront jamais 0 (il n'y a pas d'éléments répétés dans un ensemble), nous pouvons utiliser la valeur 0 pour indiquer qu'il s'agit d'une valeur spéciale.
Et ce 0 serait suivi de la valeur du delta, mais codé cette fois avec numMaxBitsDelta .Le nombre total de bits pourrait être calculé comme suit:
- 31 bits pour le nombre d'éléments dans la plage. Nous calculons le plus petit numBitsElem Nous calculons également la liste des deltas (liste des différences entre les éléments consécutifs de la liste ordonnée des éléments de l'ensemble).
- 31 bits, pour stocker le nombre d'éléments dans le Set.
- 5 bits pour stocker numOptimumBitsDelta .
- 5 bits pour stocker numMaxBitsDelta .
- numOptimumBitsDelta bits * le nombre d'éléments dans l'ensemble.
- numMaxBitsDelta bits * le nombre de deltas qui dépassent numOptimumBitsDelta .
Avons-nous déjà atteint l’encodage optimal?
Cinquième approximation . Eh bien... puisque nous avons déjà programmé tout cela...Nous pourrions penser à la situation complémentaire...Serait-il possible que le codage du complément de l'ensemble avec le même algorithme produirait des résultats plus compressés?
Le complément de l'ensemble est compris comme un autre ensemble, disjoint de l'original, dont l'union avec l'ensemble d'origine est la gamme entière.
Autrement dit, l'ensemble complémentaire aurait tous les éléments de la gamme absents dans l'ensemble d'origine, et aucun de ceux dans l'ensemble d'origine.
La beauté est qu'à partir d'un ensemble, il est très facile d'obtenir l'ensemble complémentaire, et donc on pourrait obtenir l'ensemble original, ayant codé l'ensemble complémentaire.
L'application évidente est un ensemble qui a tous les éléments de la gamme sauf un, ou quelques-uns...
Eh bien... si nous ne stockons que les absents (l'ensemble complémentaire), il pourrait être stocké dans une taille beaucoup plus petite, non?
L'encodage dans ce cas pourrait être comme ceci:
- 31 bits pour le nombre d'éléments dans la plage. Nous calculons le plus petit numBitsElem Nous calculons également la liste des deltas (liste des différences entre les éléments consécutifs de la liste ordonnée des éléments de l'ensemble).
- 1 bit, pour stocker si nous stockons l'ensemble d'origine, ou le complément.C'est l'extra bit.
- 31 bits, pour stocker le nombre d'éléments dans le Set.
- 5 bits pour stocker numOptimumBitsDelta .
- 5 bits pour stocker numMaxBitsDelta .
- numOptimumBitsDelta bits * le nombre d'éléments dans l'ensemble.
- numMaxBitsDelta bits * le nombre de deltas qui dépassent numOptimumBitsDelta dans les positions où elles apparaissent.
Eh bien... maintenant nous parlons.
Mais je suis conscient que si toutes ces merveilles peuvent être faites, ce qui ne pourrait pas être fait en cherchant d'autres modèles, ou simplement en utilisant un compresseur sans perte, comme zip ou 7z...
Il faudra attendre la prochaine fois sur le brûleur arrière...
