Codage d'Entropie

J'ai commencé à progresser récemment sur un sujet majeur lié à la compression de données, qu'on appelle le "codage d'entropie".
Une excellente définition du concept est présentée sur Wikipédia :
http://en.wikipedia.org/wiki/Entropy_encoding

Pour résumer, un élément est remplacé par sa probabilité d'apparaître.
Cet élément peut-être n'importe quoi, dans le cas présent un caractère ou un octet, mais cela pourrait être aussi un mot entier, ou un index.

Si l'élément a une chance sur deux d'apparaître, on le remplace par un bit.
S'il a une chance sur 4, on le remplace par 2 bits, une chance sur 1000, par 10 bits. etc.
Suivant les algorithmes, on peut également avoir des valeurs non entières, comme par une chance sur 10 qui devient 3,32 bits. C'est notamment le cas pour le codeur arithmétique. Tout est alors question de compromis entre vitesse de traitement et précision des calculs.

Mes premiers codeurs d'entropie sont disponibles en téléchargement :
http://phantasie.tonempire.net/pc-compression-f2/entropy-coders-t97.htm

Ce sont avant tout des logiciels de démonstration, qui permettent de se faire une idée des performances relatives de chaque méthode. Ils me permettent aussi de me mesurer face à la compétition, et il semble d'ailleurs que ces deux premiers codeurs soient champions du monde de vitesse dans leur catégorie respective. Sympa.

Je pense investir un peu de temps dans l'algorithme de Huffman, le plus rapide, mais également le moins précis. Toutefois, j'ai découvert que la différence de précision n'était pas très importante. De plus on peut "échanger" du temps de calcul contre davantage de précision; Au final, on obtient alors un codeur Huffman plus précis et plus rapide que le codage Arithmétique ou sa version utilisant des nombres entiers.
Cela semble donc un bon pari.

Une fois bien étudiée, ce codage pourra être intégré à un compresseur existant, comme par exemple LZ4, pour obtenir une solution assez proche de Zip. Si je parviens en plus à conserver un niveau de performance élevé, ce sera un nouveau "champion du monde" du rapport compression/vitesse, se traduisant par un nouveau point sur la Frontière Pareto de Matt Mahoney. Ce sera également un assez bon candidat pour tous les autres benchmark de compression de données.