Merci pour cet article, même si effectivement je ne suis pas sûr que recalculer l'arbre de Huffman à chaque octet fois soit très efficace :-)
surtout qu'il y a des façons de stocker ces arbres de façon très efficace : on peut réorganiser un arbre de Huffman de telle sorte que les clés soient triées dans l'ordre croissant des valeurs à représenter, pour chaque taille de clé. Du coup on n'a besoin de ne stocker que la taille de clé pour chaque valeur (octet) à encoder, et cette table de tailles peut elle-même se compresser très efficacement (en Huffman par exemple :-))
Et chose très intéressante, le codage de Huffman peut servir aussi à stocker des clés correspondant à des codes de contrôle pour un autre algo, type LZSS: on stocke ainsi directement en Huffman les données compressées et non compressées de LZSS. C'est ce que fait l'encodage deflate utilisé dans les formats zip et gzip.
# sympa
Posté par zerkman . En réponse au journal Découvrez la compression de données ! (et l'humour algorithmique). Évalué à 6.
Merci pour cet article, même si effectivement je ne suis pas sûr que recalculer l'arbre de Huffman à chaque octet fois soit très efficace :-)
surtout qu'il y a des façons de stocker ces arbres de façon très efficace : on peut réorganiser un arbre de Huffman de telle sorte que les clés soient triées dans l'ordre croissant des valeurs à représenter, pour chaque taille de clé. Du coup on n'a besoin de ne stocker que la taille de clé pour chaque valeur (octet) à encoder, et cette table de tailles peut elle-même se compresser très efficacement (en Huffman par exemple :-))
Et chose très intéressante, le codage de Huffman peut servir aussi à stocker des clés correspondant à des codes de contrôle pour un autre algo, type LZSS: on stocke ainsi directement en Huffman les données compressées et non compressées de LZSS. C'est ce que fait l'encodage deflate utilisé dans les formats zip et gzip.