Huffman

Algorithme utilisé par Up ! System

Une valeur peut être un paquet de bits qui n'est pas forcément un octet.

Ainsi :

• Plus un octet est représenté, moins il utilise de bits.
  Au mieux 1.
  
• Moins un octet est représenté, plus il utilise de bits.
  Au pire 256.
  

Une statistique doit être établie sur la fréquence d'apparition d'un octet dans un flux :

• Soit une statistique a priori est employée.
  Elle sert alors de référentiel de compression et l'encodage est indépendant du flux.
  
• Soit une statistique a posteriori est employée.
  La statistique doit être calculée sur le flux avant la compression et l'encodage est dépendant du flux.
  

Cet algorithme n'est pas une norme : rien ne définit quelles sont les plages d'encodage - nombre de bits minimal - et quelle statistique employer.

Ce paramétrage varie en fonction de l'application utilisant l'algorithme. Par exemple, la compression pour les images au format Tagged Information File Format (TIFF) utilise la statistique du Comité Consultatif International pour le Téléphone et le Télégraphe (CCITT) établie pour les télécopies.

C'est la convention retenue par défaut par Up ! System dès lors que l'algorithme Huffman n'est pas encapsulé dans une norme en possédant une particulière.

Statistique retenue par le CCITT

La compression est réinitialisée à chaque ligne et, par convention, chaque ligne commence par un pixel blanc. Sinon, il faut encoder une longueur de 0 pixel blanc.

Une longueur peut être soit terminale - il existe un code - soit non terminale - elle est divisée en sous longueurs de tailles maximales et donc en plusieurs codes. Par exemple :

• 10 est une longueur terminale.
• 66 est une longueur non terminale. Elle est codée en 64 + 2, où 2 est une longueur terminale.
• 3 000 est une longueur non terminale. Elle est codée en 1728+ 1216+ 56, où 56 est une longueur terminale.

Les codes des longueurs sont ensuite assemblés en octets.

Pixels blanc

Pixels noirs