[Maths]Compression de données

Bonsoir,

Je vais démarrer un projet d'initiative personnel encadré à propos de la compression. (peut-être rajouter un peu de crypto par dessus ? ça reste à voir)

Pour le moment, j'en suis au stade de la recherche de documents.

Je ne sais pas encore si je vais me centrer sur un algo, ou bien sur la théorie générale de compression.

Je compte dans tous les cas parler de Huffman et autres algos célèbres et très utilisés, mais je ne sais pas encore comment je le ferai.

Je viens donc vous demander ici si vous auriez des liens particulièrement intéressants, ou toute autre information qui pourrait m'être utile.

Ce qui m'intéresserait le plus, ce serait une étude théorique plutôt axée maths. Mais je ne risque pas de faire le difficile, pour le coup ;)

Merci beaucoup.

PS : j'ai déjà cherché sur google et developpez, mais je viens ici recueillir vos expériences sur le sujet ainsi que des liens en plus peut-être que ceux que j'ai pu trouver jusqu'à maintenant.

PPS : J'ai repéré le livre "Théorie des codes" --- vous l'avez déjà lu ?

Merci encore à tous.

Tu cherches à compresser "quoi"? La est la question ;)

Un exemple de math:

http://www.institut.math.jussieu.fr/...s/BandTheo.pdf

Attention, c'est compliqué... sorry :(

J'ai donné ce lien dernièrement, ça pourra éventuellement t'être utile :

http://tuxtina.de/files/seminar/LempelZiv.pdf

Citation:

---

J'ai repéré le livre "Théorie des codes" --- vous l'avez déjà lu ?

---

Ca fait presque un mois que je l'ai acheté, mais je n'ai pas encore eu le temps de l'ouvrir :aie:. . Mais il a l'air bien (attention tout de même, la partie compression n'est pas la plus importante)

Je pensais étudier la compression de son point de vue mathématique. Quelque chose du genre : on a une série de N caractères (par exemple), on cherche à diminuer la taille avec/sans perte (si j'ai le temps j'étudierai les deux).

J'ai déjà quelques documents mais je vais regarder les liens que vous m'avez donné.

Je sors du placard un vieux cours sur Huffman, mais bon... je reste mitigé sur la qualité de l'implémentation :

http://tcharles.developpez.com/Huffman/

Mathématiquement parlant, la compression sans perte est impossible à tous les coups car il n'existe pas d'application bijective vers deux ensembles finis n'ayant pas la même cardinalité. Fin du TIPE :mouarf:

En effet, je compte par exemple parler de ce genre de choses.

Pour l'url que tu as donné, je l'avais déjà mise de côté. Merci quand même :)

Citation:

---

Envoyé par Alp

Je vais démarrer un projet d'initiative personnel encadré à propos de la compression. (peut-être rajouter un peu de crypto par dessus ? ça reste à voir)

---

Bonsoir

Je n'ai aucun lien en particulier à te donner, mais au moins des mots clés, et ensuite, google est ton ami.
Théorie de l'information
Entropie
Shannon (théorèmes de..., borne de...)
Codage arithmétique
Burrows-Wheeler (ça ne fait pas de la compression à proprement parler, mais c'est ludique, et surtout ça montre que l'entropie n'est pas quelque chose de simple à calculer)


Pour le bouquin "théorie des codes", a priori, il traite plus des codes correcteurs, qui ont tendance à ralonger plutôt qu'à racourcir ;-) En revanche, je te les conseillerais plus comme extention d'un TIPE que la crypto je pense. C'est déjà plus dans le domaine "théorie de l'information", et en plus, pour un taupin, ça colle pas mal au programme d'algèbre linéaire, avec des chtites matrices à inverser etc (par exemple pour les codes de Hamming par exemple). Après tu peux faire mumuze avec les turbos codes, mais bon, tout ça ensemble, ça risque de faire beaucoup pour un TIPE tétra-concours (pour les ENS, je dis pas).

Bref, have fun !

Un des meilleurs algos de compression actuels (meilleur qu'Huffman), le codage arithmétique. C'est costaud (et sous brevet IBM).