Hop, voici un journal bookmark dans lequel je présente une méthode de compression de données plutôt simple, mais utilisée par les plus grands.
L'article est ici : http://www.palkeo.com/code/compression.html
C'est le résultat de quelques jours à me poser des questions existentielles sur la compression de données (for fun and profit).
À la fin, vous avez un script de moins de 300 lignes qui arrive à faire de la compression/décompression avec un ratio qui s'approche pas mal des algos classiques, et qui a pas mal de potentiel d'amélioration. Je pense que c'est l'algo de compression le plus lent jamais conçu, mais c'est de la faute à python (ou pas).
Je parle aussi de chaîne de Markov, et de codage de Huffman.
Vous y trouverez aussi un interlude qui vous apprendra à passer du texte au mixeur pour générer des phrases choc :
- 17:1 Les Philistins réunirent leurs armées pour faire la connaissance de toutes les poitrines ! Harry Potter / Bible
- Il contempla ses mains, mais il n'y a aucun blessé. Harry Potter
- Fleur Delacour qui montait en courant les marches menant dans le territoire d'Israël. Harry Potter / Bible
- Ceins tes reins comme un canon en les forçant à adopter le nouveau mode de production fondée sur les serpents pour en dilater encore l’échelle des entreprises. Marx / Bible / Harry Potter
- Et l'Éternel dit: C'est dans le filet à bagages et ils étaient rassemblés. Harry Potter / Bible
- 17:13 S'il se retire dans sa maison, et Mical, fille de Saül, n'eut point d'enfants jusqu'au jour de sa combustion, dit Dumbledore en adressant un sourire moqueur. Harry Potter / Bible
Voilà, amusez-vous bien !
# sympa
Posté par zerkman (site web personnel) . É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.
[^] # Re: sympa
Posté par palkeo (site web personnel) . Évalué à 3.
Justement, les meilleurs algos existants sont basés sur ce principe : Il faut recalculer l'arbre de Huffman à chaque fois, afin d'émettre des prédictions sur le texte qui va suivre, basé sur la toute fin de ce qu'on a déjà compressé/décompressé.
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 ?
[^] # Re: sympa
Posté par zerkman (site web personnel) . É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".
[^] # Re: sympa
Posté par zerkman (site web personnel) . Évalué à 6.
Je me réponds à moi-même, je me suggère d'aller voir cette page Wikipedia
[^] # Re: sympa
Posté par palkeo (site web personnel) . Évalué à 2.
Ok, merci pour toutes ces infos.
Actuellement, j'ai un prédicteur qui renvoie tous les octets possibles (donc 256) et qui est pris en compte (mais avec un poids très faible), du coup n'importe quel caractère peut de toute façon être codé avec ce prédicteur (mais son code risque d'être long).
Mais c'est vrai que le codage de huffman adaptatif à l'air mieux !
Tout est là : https://fr.wikipedia.org/wiki/Pr%C3%A9diction_par_reconnaissance_partielle
C'est la méthode que j'utilise, et ça à l'air d'être une grosse référence pour compresser lentement, mais avec un des meilleurs ratio.
[^] # Re: sympa
Posté par programLyrique . Évalué à 2.
Est-ce que tu aurais des exemples d'applications qui utilisent ce genre de compression ?
J'ai trouvé un benchmark ici et 7z semble utiliser ce genre de compression, mais ça ne semble pas trop répandu. A cause de la lenteur en compression et décompression ?
[^] # Re: sympa
Posté par palkeo (site web personnel) . Évalué à 3.
Tu as lrzip, avec l'option « -z », qui peut utiliser zpaq.
C'est relativement rapide, et tu as un taux de compression très bon.
# Horoscope
Posté par Aluminium95 . Évalué à 7.
En effet je ne connaissait pas, c'est fortement intéressant comme concept, surtout pour générer les phrases aléatoires !
Je pensais faire un générateur d'Horoscopes à partir de ça, étant donné que ces phrases n'ont jamais vraiment qu'un sens très généraliste, je pense que ça peut marcher assez bien !
[^] # Re: Horoscope
Posté par yohann (site web personnel) . Évalué à 4.
il me semble que les chaines markov sont utilisées dans la majorité des pipotrons (http://pipo.alacon.org/)
[^] # Re: Horoscope
Posté par Benoît Laurent (site web personnel) . Évalué à 2.
J'aime beaucoup ce générateur de texte aléatoire, http://enneagon.org/phrases , qui justement utilise les chaine de Markov sur un corpus romans du XIXe siècle.
Ça s'utilise comme ça pour récupérer uniquement un nombre n de phrases, ici une : http://enneagon.org/phrases/1
[^] # Re: Horoscope
Posté par khivapia . Évalué à 6. Dernière modification le 06 août 2013 à 17:29.
Ou le fameux générateur de papiers scientifiques aléatoires, dont certains ont même été acceptés pour publication !
http://pdos.csail.mit.edu/scigen/
[^] # Re: Horoscope
Posté par Batchyx . Évalué à 4.
Celui là utilise une grammaire sans contexte écrite à la main et non pas de la déduction de chaîne de markov. Les mecs ont bien du s'amuser, mais à mon avis, au final ça rend les articles générés plus crédibles puisque les constructions de phrases sont toujours correctes et la grammaire est remplie de constructions de phrases percutantes qui buzzent.
[^] # Re: Horoscope
Posté par dave_null (site web personnel) . Évalué à 1.
Je pense qu'il y a une possibilité de vendre des livres en se basant sur ce type de textes et une couverture en noir et blanc : http://fr.wikisource.org/wiki/Cat%C3%A9gorie:Romans_%C3%A9rotiques
# sys.stdout.buffer
Posté par ch651 . Évalué à 3.
C'est une question un peu hors-sujet, mais pourquoi remplacer sys.stdout et sys.stdin?
Pourquoi ne pas utiliser plutôt:
[^] # Re: sys.stdout.buffer
Posté par palkeo (site web personnel) . Évalué à 1.
Je ne connaissait pas du tout. Merci pour la découverte :)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.