Justement, les meilleurs algos existants sont basés sur ce principe
Je ne connais pas d'exemple d'implémentation de codage de Huffman qui regénère tout un arbre à chaque octet envoyé. En revanche, il y a des algos dits "à dictionnaire" qui peuvent générer leur dictionnaire au cours de l'encodage et du décodage. Le meilleur exemple est LZW, qui fait le pari qu'une phrase déjà rencontrée a des chances de revenir plus tard, et donc stocke en dictionnaire la dernière séquence trouvée (un octet unique, ou une suite d'octets déjà dans le dictionnaire) à laquelle on rajoute l'octet suivant. Ainsi pour coder la séquence ABAB, on va faire dans l'ordre :
- écrire le code du caractère A, mettre en dictionnaire la séquence AB
- écrire le code du caractère B, mettre en dictionnaire la séquence BA
- écrire le code de la séquence AB
Si tu as des exemples d'implémentations de Huffman avec génération d'arbres en direct, je prends ;) Notamment, je n'ai pas bien compris comment tu peux encoder un caractère qui n'est pas encore disponible dans ton arbre de Huffman.
Par contre, j'ai pas vraiment compris ce que tu explique (pourtant, ça à l'air intéressant), tu pourrais essayer de détailler plus ou de donner un exemple ?
Je te conseille d'aller voir la spec de l'algorithme deflate (RFC-1951). Cela parle de l'écriture d'arbres de Huffman sous forme compressée.
Deflate c'est grosso modo une variante de LZ77 encodée en Huffman. Le principe de LZ77 est d'écrire les octets sous forme d'une alternance de séquences non compressées et de paires (distance,longueur) permettant de recopier une sous-séquence déjà vue auparavant dans le texte. Une implémentation un peu naïve de LZ77 nécessite une en-tête avant chaque séquence, permettant de différencier le cas non compressé du cas d'une paire distance/longueur.
Deflate code en Huffman des codes allant de 0 à 285. Les codes de 0 à 255 correspondent à des octets non compressés (plus besoin d'en-tête), 256 correspond à une fin de bloc et les autres valeurs permettent de déterminer une paire distance/longueur selon le nombre de bits nécessaires. L'avantage du codage de Huffman est de ne plus avoir à stocker d'en-têtes LZ77, on gagne donc une place significative par rapport à du LZ77, sans compter le gain de place pour le stockage des séquences "non compressées".
[^] # Re: sympa
Posté par zerkman . En réponse au journal Découvrez la compression de données ! (et l'humour algorithmique). Évalué à 5.
Je ne connais pas d'exemple d'implémentation de codage de Huffman qui regénère tout un arbre à chaque octet envoyé. En revanche, il y a des algos dits "à dictionnaire" qui peuvent générer leur dictionnaire au cours de l'encodage et du décodage. Le meilleur exemple est LZW, qui fait le pari qu'une phrase déjà rencontrée a des chances de revenir plus tard, et donc stocke en dictionnaire la dernière séquence trouvée (un octet unique, ou une suite d'octets déjà dans le dictionnaire) à laquelle on rajoute l'octet suivant. Ainsi pour coder la séquence ABAB, on va faire dans l'ordre :
- écrire le code du caractère A, mettre en dictionnaire la séquence AB
- écrire le code du caractère B, mettre en dictionnaire la séquence BA
- écrire le code de la séquence AB
Si tu as des exemples d'implémentations de Huffman avec génération d'arbres en direct, je prends ;) Notamment, je n'ai pas bien compris comment tu peux encoder un caractère qui n'est pas encore disponible dans ton arbre de Huffman.
Je te conseille d'aller voir la spec de l'algorithme deflate (RFC-1951). Cela parle de l'écriture d'arbres de Huffman sous forme compressée.
Deflate c'est grosso modo une variante de LZ77 encodée en Huffman. Le principe de LZ77 est d'écrire les octets sous forme d'une alternance de séquences non compressées et de paires (distance,longueur) permettant de recopier une sous-séquence déjà vue auparavant dans le texte. Une implémentation un peu naïve de LZ77 nécessite une en-tête avant chaque séquence, permettant de différencier le cas non compressé du cas d'une paire distance/longueur.
Deflate code en Huffman des codes allant de 0 à 285. Les codes de 0 à 255 correspondent à des octets non compressés (plus besoin d'en-tête), 256 correspond à une fin de bloc et les autres valeurs permettent de déterminer une paire distance/longueur selon le nombre de bits nécessaires. L'avantage du codage de Huffman est de ne plus avoir à stocker d'en-têtes LZ77, on gagne donc une place significative par rapport à du LZ77, sans compter le gain de place pour le stockage des séquences "non compressées".