Hello world,
Je cherche à monter une séance sur la compression de données.
Public : ma MP de niveau moyen (fonds de commerce : les CCP).
Durée : 1 semaine soit 1h de cours et 1h de TP. Allez, mettons 2 semaines s'il le faut.
On trouve pas mal de doc sur internet, le sujet est vaste, l'information abondante, mais de qualité et difficulté variable.
Avant que je passe n>>1 heures à découvrir l'eau chaude puis à réinventer la chaudière, qui pourrait me donner quelques tuyaux ? (Re-humour, décidément je suis très en verve.)
Qu'est-il envisageable de faire sur le sujet sans déborder ni larguer son troupeau ?
1) Un topo général sur le problème (avec ou sans perte d'info).
2) Un algo sans perte d'info basique : RLE (codage par répétition) : AAABBBBBBCCCCC devient A3B6C5.
3) Un algo sans perte d'info évolué ??? Du genre LZ-77. Auriez-vous une source compréhensible et mathématiquement crédible ?
4) Un algo avec perte d'info basique ??? Ceci existe-t-il ? JPEG, ondelettes, fractales ? Auriez-vous une source compréhensible et mathématiquement crédible ?
Quid de la partie TP ? Grosses listes aléatoires de 0/1 à compresser/décompresser ? Image en N&B ?
Pour du "sans perte" des 0/1 sans signification conviennent, mais du "avec pertes" rien ne vaut deux images à comparer visuellement (avant/après).
Rq : je ne veux pas effectuer de TP de manipulation d'images (appliquer des filtres, flouter, etc.). Mon objectif est de travailler sur les algos de compression/ décompression de données.
J'ai trouvé pas mal de sites, mais où les exemples sont incomplets ou la théorie rédigée par des personnes largement plus compétentes que moi et visant un public plutôt trié.
Merci par avance pour toute piste, ou pour toute non-piste ("sujet pas faisable pour ton public").
Bien cordialement,
Charles Cochet
(Maths et Informatique)
Compression de données
Re: Compression de données
[url=http://www.ece.rice.edu/~wakin/images/]Lena est à ta disposition pour les tests avec perte sur photo.[/url]
Sinon n’importe quoi fonctionne. À titre personnel, je trouve la séquence de 0 et de 1 aléatoire peu pédagogique car cela rend le problème très peu concret. Pourquoi pas une phrase avec un véritable sens ? En codant les caractères en quelques bits.
L’exemple de la compression JPG (ou n’importe quelle compression utilisée quotidiennement par n’importe qui) te permettra peut-être d’être mieux écouté de ton auditoire. Il s’agit d’un cas concret.
A contrario, la présentation d’un algorithme de compression obscure et pas connu, même très joli d’un point de vue académique, peut être passablement ennuyeuse pour un non-passionné.
Concernant la crédibilité mathématique, je suis perplexe. J’aimerais bien savoir si tous les implémenteurs et concepteurs de codes de compression sont des mathématiciens de haut-vol et je suis sûr qu’on peut coder de manière raisonnable sans être doué d’une expertise à toute épreuve en terme de groupes de Gallois.
[Edit]J’ai fait cette dernière remarque en ignorant m’adresser à un professeur de mathématique. Je comprends après relecture l’importance de cet aspect pour l’exposé. Mais je maintiens que pour compresser des données, les mathématiques me paraissent souvent apporter plus de complication que de clarté (exception faites des quatre opérations nécessaire et de la dérivée).[/Edit]
Sinon n’importe quoi fonctionne. À titre personnel, je trouve la séquence de 0 et de 1 aléatoire peu pédagogique car cela rend le problème très peu concret. Pourquoi pas une phrase avec un véritable sens ? En codant les caractères en quelques bits.
L’exemple de la compression JPG (ou n’importe quelle compression utilisée quotidiennement par n’importe qui) te permettra peut-être d’être mieux écouté de ton auditoire. Il s’agit d’un cas concret.
A contrario, la présentation d’un algorithme de compression obscure et pas connu, même très joli d’un point de vue académique, peut être passablement ennuyeuse pour un non-passionné.
Concernant la crédibilité mathématique, je suis perplexe. J’aimerais bien savoir si tous les implémenteurs et concepteurs de codes de compression sont des mathématiciens de haut-vol et je suis sûr qu’on peut coder de manière raisonnable sans être doué d’une expertise à toute épreuve en terme de groupes de Gallois.
[Edit]J’ai fait cette dernière remarque en ignorant m’adresser à un professeur de mathématique. Je comprends après relecture l’importance de cet aspect pour l’exposé. Mais je maintiens que pour compresser des données, les mathématiques me paraissent souvent apporter plus de complication que de clarté (exception faites des quatre opérations nécessaire et de la dérivée).[/Edit]
Employé.
Re: Compression de données
Merci beaucoup pour les informations et remarques fort pertinentes !
Quand je parle de crédibilité mathématique, je voulais en fait dire crédibilité scientifique.
C'est pour éviter le gars qui a un super algo qui tourne vachement plus vite que les autres, du genre, pour les tris : "mon algo trie une liste de 10 éléments en 1 opération de moins que quicksort, et j'en tire que ma complexité est meilleure". (On ne rigole pas, j'ai amendé un article de la sorte sur wikipedia.)
Ou qui fait des "tests statistiques" (sic) sur 10 listes de 10 chiffres, et qui en "déduit" la complexité de son algo...
Si je donne un algo, je dois pouvoir au moins expliquer pourquoi il marche et pourquoi il est efficace (voire pouvoir le prouver, si c'est faisable à bac+2 sans perdre mon auditoire).
Le calcul de la complexité d'un algo est officiellement au programme, sur des exemples simples (boucles imbriquées -> O(n^2)).
Il faut que cela soit compréhensible et programmable en python par des étudiants ayant au compteur 2h hebdo d'Info, ce qui est hélas tout petit. Eventuellement un arbre, éventuellement de la récursivité, mais pas de folie au dessert.
Idéalement : compréhensible en 1h (position du problème + algo), programmable en 1h (tests inclus).
Je vais donc fouiller du côté du codage JPG. Si tu as une référence en la matière, je suis preneur !
Quand je parle de crédibilité mathématique, je voulais en fait dire crédibilité scientifique.
C'est pour éviter le gars qui a un super algo qui tourne vachement plus vite que les autres, du genre, pour les tris : "mon algo trie une liste de 10 éléments en 1 opération de moins que quicksort, et j'en tire que ma complexité est meilleure". (On ne rigole pas, j'ai amendé un article de la sorte sur wikipedia.)
Ou qui fait des "tests statistiques" (sic) sur 10 listes de 10 chiffres, et qui en "déduit" la complexité de son algo...
Si je donne un algo, je dois pouvoir au moins expliquer pourquoi il marche et pourquoi il est efficace (voire pouvoir le prouver, si c'est faisable à bac+2 sans perdre mon auditoire).
Le calcul de la complexité d'un algo est officiellement au programme, sur des exemples simples (boucles imbriquées -> O(n^2)).
Il faut que cela soit compréhensible et programmable en python par des étudiants ayant au compteur 2h hebdo d'Info, ce qui est hélas tout petit. Eventuellement un arbre, éventuellement de la récursivité, mais pas de folie au dessert.
Idéalement : compréhensible en 1h (position du problème + algo), programmable en 1h (tests inclus).
Je vais donc fouiller du côté du codage JPG. Si tu as une référence en la matière, je suis preneur !
Re: Compression de données
La page https://fr.wikipedia.org/wiki/JPEG est très bien faite (pour ce que je veux en tirer).
L'exemple 8x8 est pertinent et fonctionne.
C'est d'ailleurs assez bluffant de compresser une telle matrice en une liste de "seulement" une dizaine de chiffres.
Maintenant, va falloir passer à une "grosse" image... Demain !
L'exemple 8x8 est pertinent et fonctionne.
C'est d'ailleurs assez bluffant de compresser une telle matrice en une liste de "seulement" une dizaine de chiffres.
Maintenant, va falloir passer à une "grosse" image... Demain !
Re: Compression de données
Pourquoi ne pas proposer d'étudier le code de Huffman par exemple? Ça permet de faire une (brève) introduction à la théorie de l'information (les sources sont considérées comme des variables aléatoires, sans forcément devoir parler d'entropie etc), vous pouvez enchaîner ensuite sur l'intérêt des codes sans préfixe pour la compression sans perte, puis introduire le code de Huffman: l'algorithme est simple et facile à implémenter (en Python ou en Caml), on peut s'amuser à faire des exemples concrets sur des textes dans différentes langues etc, et bien sûr expliquer en quoi cet algorithme est intéressant sur le plan théorique (espérance de la longueur des données compressées minimale parmi les codes sans préfixe, sans nécessairement leur donner la preuve bien qu'elle soit abordable niveau prépa).
En 2h de cours + 2h de TP ça passe largement.
En 2h de cours + 2h de TP ça passe largement.
ENS Lyon
Ingénieur de recherche
Ingénieur de recherche
Re: Compression de données
Voici une première mouture de séance sur la compression de données :
[url]https://www.fenelonsaintemarie.org/prepasmp/files/MP20162017Info17CompressionDonnees.pdf[/url]
C'est imparfait... Plein d'impasses... Je ne parle que de RLE et JPEG...
Mais bon, pour une découverte du sujet c'est déjà pas mal.
Je verrai si cela tient deux semaines.
En fonction des RETEX, peut-être développerai-je plus le sujet (Huffman) l'an prochain.
Encore merci pour vos messages !
Bien cordialement,
Charles.
[url]https://www.fenelonsaintemarie.org/prepasmp/files/MP20162017Info17CompressionDonnees.pdf[/url]
C'est imparfait... Plein d'impasses... Je ne parle que de RLE et JPEG...
Mais bon, pour une découverte du sujet c'est déjà pas mal.
Je verrai si cela tient deux semaines.
En fonction des RETEX, peut-être développerai-je plus le sujet (Huffman) l'an prochain.
Encore merci pour vos messages !
Bien cordialement,
Charles.
Re: Compression de données
Pour ce qui est de JPEG explique pourquoi les hautes fréquences sont plus importantes que les basses fréquences.
De plus, tu peux facilement expliquer avec les mains pourquoi la compression sans pertes marche mal sur de "vraies" données. C'est parce que les vraies données contiennent du bruit et que donc on a jamais la même valeur ou le même motif qui se répète exactement. Si on accepte de lisser ce bruit alors on a des choses qui se répètent plus et donc ça se compresse mieux.
Dans les méthodes avec dico, il faut bien dire qu'il faut transférer également le dico* pour pouvoir décoder. L'exemple trivial étant de dire "le dico c'est le texte et le message compressé c'est '1'"
* : dans certains algos, on ne transmet pas le dico en tant que tel. Il est encodé dans le message compressé lui même.
De plus, tu peux facilement expliquer avec les mains pourquoi la compression sans pertes marche mal sur de "vraies" données. C'est parce que les vraies données contiennent du bruit et que donc on a jamais la même valeur ou le même motif qui se répète exactement. Si on accepte de lisser ce bruit alors on a des choses qui se répètent plus et donc ça se compresse mieux.
Dans les méthodes avec dico, il faut bien dire qu'il faut transférer également le dico* pour pouvoir décoder. L'exemple trivial étant de dire "le dico c'est le texte et le message compressé c'est '1'"
* : dans certains algos, on ne transmet pas le dico en tant que tel. Il est encodé dans le message compressé lui même.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Compression de données
Avec un peu de retard : MERCI !