algos de compression - Page 1

avec l'algo de huffman semi adaptatif j'obtient même pas 50% sur un ficheir texte

il existe quoi comme autres algos de compression ( et c koi le huffman avec l'abre dynamique ?)

Le Huffman adaptatif (pas semi) ne sauve pas l'arbre dans le fichier, car il est construit au fur et à mesure de l'encodage. Cette méthode est bcp + efficace sur les gros fichiers que le Huffman semi-adaptatif.

t'arrive a faire un algo plus puissant que celui du format ppg !???
pt1 fais en une librairie !

hue, pr le texte, le MN5P est pas plus puissant?? (sinon, y'a tjrs le LZW avec buffer que je prefere a huffman)

et ca marche comment l'algo adaptatif ?

Bon je te fais un cours, tu as intérêt à t'en servir parceque je me suis fait chier à essayer d'être clair

1) Tu pars d'une table d'occurences où tous les caractères ont la même probabilité : 1.
2) Tu construis l'arbre associé à cette table : en fait tu penses bien que pour l'instant rien n'est compressé, comme tous les caractères ont la même occurence, chaque octet sera codé sur 8 bits par l'arbre...
3) Tu compresses avec cet arbre, disons 128 octets du fichier (saches que moins tu compresses de caractères à la fois plus ça va être long... Mais plus ça va être efficace. On peut pas tout avoir
4) En encodant ces 128 octets, tu as compté la fréquence d'apparition de chacun (= mis à jour la table d'occurences). Tu peux donc reconstruire l'arbre avec la table qui s'est améliorée depuis le début !
5) Et c'est repartit pour 128 octets, hop, étape 3 !

Tu vois que petit à petit l'arbre devient de plus en plus efficace, il s'adapte au fichier. Donc si on a beaucoup de 'a' à un endroit d'un fichier, puis plus loin beaucoup de 'b', la compression va être bien meilleur qu'avec le Huffman "de base" qui aurait compté tous les 'a' et tous les 'b' pour l'ensemble du fichier.
Avec le Huffman adaptatif, l'arbre va se construire de façon à privilégier les 'a' à l'endroit où il y en a le plus, puis avec l'augmentation du nombre de 'b' la tendance va s'inverser et se sont les 'b' qui sont codés sur le plus petit nombre de bits *<|: o)

>obza_Fazer: pt1 fais en une librairie !

Tu as oublié un petit mot: statique.

lol!
le LZW c plus simple (à comprendre, à coder je sais pas) et c ptet + efficace

et on a pas besoin de stocker un arbre tous les 128 caracteres parce aue on le construit a partir du
texte precedent. genial

en gros la longueur de chaque paquet ca va etre mon parametre de compression (bcp compresse ou pas beacoup compresse)

le seul truc c'est que l'arbre code avec du retard... tous mes 'a' peuvent etre codes sur bcp de bits une fois puis lorsqu ils sont pris en compte dans l'arbre ils peuvent ne plus reapparaitre dans le texte.......

le lzw est beaucoup plus efficace (TNT sur hp)

>>obza_Fazer: pt1 fais en une librairie !
>Kevin:Tu as oublié un petit mot: statique.
Non, non. Il ne l'a pas oublie puisqu'il n'y est pas.

exactement

en fait j'ai pensé a le mettre mais je me suis dis vaut mieux que chacun le prenne ds le sens qui veut

mais je pensais aussis surtout a ziplib, donc dynamique

et au passage, imaginez si ziplib etait une lib statique, avec le nbre de mec qui s'en sert, on aurais 5 ou 6 fois le mm algo sur sa TI pasque chacun l'aura inclut ds son prog, donc perte enorme de memoire !!!
[edit]Edité par obza_Fazer le 10-12-2001 à 17:28:54[/edit]

farib : c'est pourquoi plus tu actualise l'arbre souvent, moins il y a de retard possible, donc mieux ça compresse !

J'avais trouvé il y a quelques temps un source en c++ de lzw, tres tres simple, c'est simple a coder, peut etre pas a optimiser, s'il est couplé a un rle ca peut donner de tres bonnes choses. A savoir qu'on peut s'en sortir avec peu de memoire...
le code source en c++ etait tres pres du c niveau code

Au passage, ziplib, c'est huffman...

Le meilleur algo existant, c'est l'arithmétique, mais bonjour le ramage...

Pour l'adaptif, ne met rien dans les feuilles sinon un caractère spécial qui insique que les 8 bits suivants sont un nouveau caractère. Cela permet de s'affranchir des problèmes de compression au début. En effet, les premiers caractères prendront rapidement moins de place que les 8bits de Thibaut si ils se ressemblent...

l'arithmetique, c'est le meilleur parmi les algos bases sur la frequence des caracteres (comme huffman). Il est tres difficile a coder (reels longs) et pas extraordinairement plus efficace que huffman

il existe d'autres algos bien plus efficaces (lzw of course)

Miles je comprend pas ce que tu veux dire....

au départ tu commence avec un seul caractère, le caractère spécial. Dès que tu le rencontres, tu dois rajouter une feuille avec comme caractère les 8bits suivant et avec un poids de 1. C'est la création d'un nouveau caractère. Puis tu continues comme Thibaut l'as dit.

Au passage, arithmétique est le meilleur algo... lzw font pâle figure face à lui. LZW a été inventé parce qu'on savait que l'arithmétique serait trop compliqué. Il faut en effet augmenter le mode - le nombre de caractères codés à la fois - ce qui fait ralentir le processus. Donc ils ont inventés un mode différent qui en fait est un morceau de l'arithmétique.

En gros l'arithmétique code comme cela : si il y a 99 a et 1 b, donc un seul bit, au lieu d'attribuer a à 1 et b à 0, on attribue 0.1 à a et 0.99 à b comme place sur le bit...

l'arithmetique est effectivement le meilleur, et c'est prouve theoriquement, PARMI ceux qui n'utilisent que la frequence des caracteres.

Prenons un fichier comportant la liste de tous les caracteres ascii de 0 a 255, le tout repete 10000 fois.

Huffman, ou bien l'arithmetique, ne compressera rien.
lzw compressera bien.

faux. L'arithmétique et huffman en mode supérieur en cherchant des occurences d'au moins 2 caractères marchera. C'est en fait du lzw, mais amélioré, puisque le codage sera optimal. C'est ce que font les compresseurs aujourd'hui.

ah pardon.

mais alors on a pas la meme definition des algos

En fait, j'ai trouvé, c'est ordre qu'il fallait comprendre, pas mode. En augmentant l'ordre, on augmente la taille des arbres en exponentielle, mais on compresse bien.
On maintient autant d'arbres que l'ordre, et chaque arbre, selon son rang, a une profondeur variable. Puis, on code, mais je ne sais comment choisir dans les différents arbres

ouais je commence a voir ce que tu veux dire. mais ca rame

l'algo semi-adaptatif ne devient-il pas aussi perofrmant que le semi-adaptatif sur les gros fichiers, car la table de frequence devient vite représentative du fichier tout entier ?

Ha non !!!!!

Les nouvelles occurences "écrasent" les anciennes (la relativité ça marche aussi pour la compression ).

donc on "remet a zero" les frequences tous les paquets définis ! on refait un arbe totalement nouveau !c'est pas une mise a jour des frquence, masi une nouvelle table de frequence et un nouvel arbre !

Mais non !!!!

donc c'est bien ce que je dis, au bout d'un certain temps, l'arbre est suffisemment représentatif de l'ensemble du fichier et ne sera plus modifié !

moui si tu veux, mais ça peut s'arranger... C'est ça qui est passionnant dans la programmation, je trouve : chercher !!