Journal Découvrez la compression de données ! (et l'humour algorithmique)

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes :
34
6
août
2013

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  (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  (site web personnel) . Évalué à 3.

      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 :-)

      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  (site web personnel) . Évalué à 5.

        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  (site web personnel) . Évalué à 6.

          Si tu as des exemples d'implémentations de Huffman avec génération d'arbres en direct, je prends

          Je me réponds à moi-même, je me suggère d'aller voir cette page Wikipedia

        • [^] # Re: sympa

          Posté par  (site web personnel) . Évalué à 2.

          Ok, merci pour toutes ces infos.

          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.

          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 !

          Si tu as des exemples d'implémentations de Huffman avec génération d'arbres en direct, je prends ;)

          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  . É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  (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  . Évalué à 7.

    Je parle aussi de chaîne de Markov

    En effet je ne connaissait pas, c'est fortement intéressant comme concept, surtout pour générer les phrases aléatoires !

    On peut utiliser les chaînes de Markov pour générer des suites de mots à partir d’un texte de base.
    Le principe est simple : on part d’un mot choisi au hasard au début d’une phrase du texte. Ensuite, on va boucler en prenant le dernier mot choisi, et en regardant les mots qui suivent ce dernier dans le texte de base. Parmi tous ces mots, il suffit d’en choisir un au hasard (en respectant les proportions, si un mot apparaît deux fois plus, il aura deux fois plus de chances d’être pris), et de recommencer.

    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 !

  • # sys.stdout.buffer

    Posté par  . Évalué à 3.

    C'est une question un peu hors-sujet, mais pourquoi remplacer sys.stdout et sys.stdin?
    Pourquoi ne pas utiliser plutôt:

    sys.stdout.buffer.write()
sys.stdin.buffer.read()

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.