psycho81
Messages postés84Date d'inscriptionmardi 4 mai 2004StatutMembreDernière intervention17 février 2008 16 nov. 2005 à 09:17
Petite information en passant :
La méthode de base de réorganisation BWT a été mise au point en 1994. Depuis, les meilleurs taux de compression réalisés sont souvent à base de cette méthode de réorganisation. Il est à prévoir que de nouvelle méthode post BWT, similaire à l'algorhytme JPEG verront le jour. Pour l'instant les possiblités offertes par cet algorhytme n'ont pas encore été totalement exploités (à l'inverse de Hufmann par exemple dont on a défini une certaine limite). BWT est donc très récent et est donc succeptible de provoquer une véritable révolution dans les méthodes de compression (une autre ...). Bientot dans le zip, je mettrai une documentation sur BWT et MTF, un recueil de texte glané ci et là sur le net.
Bonne prog !
psycho81
Messages postés84Date d'inscriptionmardi 4 mai 2004StatutMembreDernière intervention17 février 2008 14 nov. 2005 à 09:54
Doodoo256,
L'efficacité de cette méthode est ... dans ce cas précis nulle vu qu'elle ne fait que réorganiser les données vers une forme plus ... facilement compressible. Il allourdit meme le packet de la référence de ligne qui permettra de retrouver la chaine originelle. Cependant, la réorganisation effectué permet de dégager un très grand nombre de zéro dans la chaine binaire (vu que le move to front remplace 1111100000 par 1000010000). Pour ce qui est de l'implémentation de cet algorhytme, bzip2 l'utilise ainsi que compressia et ... bien d'autre je pense (au fait Doodoo256 j'ai une version beta de compressia en ligne de commande qui devrait t'interesser, pour que je te le fasse aprvenir contacte moi à rebel_thc AroBaBase yahoo point afrreux -Super ce mail non ? :p)
Pour répondre à la compression qui sera utilisé par la suite, vu le très grand nombre de zéro que nous pourrons trouver, j'ai opté pour une compression arithmétiqe binaire pas au point encore pour le moment( us_30 Huffman serait un acte inutile dans ce cas la vuq ue je travaille en binaire et donc le gain serait nul sous cette forme vu qu'il faudrai au moins 1 bit pour coder 1 bit alors que la compression aritmétique permet de coder n bit avec un seul bit ! je suis arrivé chez moi à n = 1236 bits sans forcer soit un gain considérable !).
Doodoo256, l'avantage de cette méthode est qu'il n'est pas nécessaire d'avoir un tableau (n,n) donc exponentielle mais plutot du genre (3 ou 4,n) donc linéaire ce qui permet d'avoir une montée de mémoire moindre suivant la taille du bloc (le BWT expliqué est toujours de la forme (n,n)). Donc pour conclure... plus la mémoire est grande, plus grand est le buffer, et ... plus la réorganisation des données est efficiente.
Le fait de travailler sous forme binaire permet de trouver des cycles de répétitions plus précis que par octects par exemple ab n'a aucun cycle alors que 0110000101100010 (ab en binaire) contient des cycles ici 011000 01 011000 10
La taille du buffer optimale serait donc de la forme Total mémoire / NombreDeBitsDuBloc*BitsUtilisésPourTraitementDunBit
Bientot la suite ...
Bonne prog
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 12 nov. 2005 à 16:48
Salut,
Je découvre cet algo, que je cherchais depuis des années dans ma pauvre tête... Pour comprendre, faut mieux lire l'adresse donné sur wikipedia ... Désolé psycho81. Bon, je me pencherai dessus, et si j'ai une bonne remarque, je te tiendrai au courant. Le .NET , c'est pas ma spécialité, mais on le comprend assez bien, en connaissant VB...
Par contre, pour avancer un peu sur le débat, je me pose qlq questions.
- Pourquoi choisir la forme binaire plutôt que par octet directement.
- Ce qui me semble évident, pour répondre à DooDoo, c'est de découper par bloc. Si on pense à des fichiers de plusieurs Méga, voir Giga, on rendrait fou le PC sans bloc ! Mais il reste une question. Y a-t-il une taille optimum... (surement, si on tient compte des déclarations des variables)
- Ensuite, après transformation, je ne vois pas l'intérêt d'utiliser Huffman. Le plus direct serait comme pour le PCX d'antant, non ? (surtout si la taille traitée est assez conséquente)
Amicalement,
Us.
Doodoo256
Messages postés5Date d'inscriptionmardi 15 avril 2003StatutMembreDernière intervention11 novembre 2005 11 nov. 2005 à 20:31
Ok, un petit tour sur Google m'a ouvert les yeux..
Le site de Compressia est mort on dirait.
En tout cas, quel algo de compression as-tu l'intention d'appliquer après BWT ?
Question bête :
Si on applique BTW sur un fichier binaire d'environ 500 Ko, il faut une grosse bécane pour faire les rotations ou alors découper en blocs c'est ça ?
Doodoo256
Messages postés5Date d'inscriptionmardi 15 avril 2003StatutMembreDernière intervention11 novembre 2005 11 nov. 2005 à 19:28
Bonsoir,
je viens de faire un petit tour dans les sources et je tombe là dessus...
Je vais suivre avec intérêt tes travaux ça m'a l'air révolutionnaire malgré la complexité de l'algo.
Où se situe l'efficacité de cette méthode par rapport à du 7z, LZW et Huffman par exemple ?
L'algo a déjà été implémenté ? Dans quel soft ?
a++ ;
psycho81
Messages postés84Date d'inscriptionmardi 4 mai 2004StatutMembreDernière intervention17 février 2008 4 nov. 2005 à 09:23
Salut mon bisouilleur ...
Et vi je me sentais un peu seul. Déjà que dans les méandres de mon cerveau torturé, il y a peu de monde .... Mais bon, tu me dira ... C'est pas avec des codes pareil qu'on attire du monde :p Entre le crypteur multiiidimensionel (à ne pas confondre avec le distruuucteur dimensionneeeeel - allusion à "Hé mec elle est où ma caisse" que Chris81 connait sur le bout des doigts) et çà, je suis pas sur de passer pour quelqu'un de très clair :) ) Enfin test le code, tu verra des résultat surprenant avec des chaines style abcabcabc ou aaaaaaaaa. C'est ... surprenant :)
Bisoux a toi mon unique fan :)
cs_chris81
Messages postés589Date d'inscriptionjeudi 2 octobre 2003StatutMembreDernière intervention29 avril 20082 3 nov. 2005 à 23:08
slt, tu as pas l'air de parler tt seul :), bon je vois qu'il est toujours aussi compliqué de comprendre un tel code. c'est bien toi t. Des que j'ai 5 min je te le teste et te dis en attendant bisous a+ :)
psycho81
Messages postés84Date d'inscriptionmardi 4 mai 2004StatutMembreDernière intervention17 février 2008 3 nov. 2005 à 10:37
Ce modèle EST binaire.Le pire EST à craindre ... J'ai décidement un petit problème avec mon "t" parfois ... Et d'autres fois avec mon orthographe (je me souviens d'une série de ligne que m'avais donné mon père une fois : Je ne ferai plus de fautes d'orthographe à "orthographe". J'ai trouvé le moyen d'en faire ailleurs ... :p )
psycho81
Messages postés84Date d'inscriptionmardi 4 mai 2004StatutMembreDernière intervention17 février 2008 3 nov. 2005 à 10:35
Bientôt les premiers commentaires dans le code ... Le pire es à craindre :)
psycho81
Messages postés84Date d'inscriptionmardi 4 mai 2004StatutMembreDernière intervention17 février 2008 3 nov. 2005 à 10:14
Ah si j'oubliai, le modèle que j'ai préconisé dans ce modèle es binaire, c'est a dire que plutot que d'avoir une chaine du type abcabdabe nous aurons une chaine du type 01110010000110001100101. Voili voilou.
psycho81
Messages postés84Date d'inscriptionmardi 4 mai 2004StatutMembreDernière intervention17 février 2008 3 nov. 2005 à 09:42
1ère série de commentaires :
Tout d'abord, je me dois d'expliquer l'utilité de ce code. Il rentre dans la composante de beaucoup de compresseur surpuissant comme bzip2 ou compressia (compcl.exe pour les intimes, un exécutable qui compresse, en version beta plus que tout autre compresseur existant sur la marché - Me contacter si vous souhaitez cet exécutable qui relègue bzip2 au rang d'outsider bien lointain).La méthode BWT permet de réorganiser les données (celà ne compresse nullement au contraire cela rajoute un tout petit bloc de données supplémentaires). Ou est l'utilité alors me dire d'appliquer cette méthode ?
Prenons par exemple la chaine "abcabdabe" (qui sommes toutes est une chaine peux courante dans nos fichiers textes :) )
La méthode BWT demande en théorie la longueur de la chaine au carré d'octets mémoire pour son traitement car pour effectuer cette opération nous devons faire un tableau[LongueurChaine] de Chaine qui sera disposer comme suit :
et maintenant prenons le dernier octet de chaque élément du tableau d'octet. Ce qui nous donne "ecdaaabbb" (n'oublions pas que nous devrons rajouter a ce bloc l'index du tableau, c'est à dire le 1). Nous nous apercevons que la sequence "ab" a été réoganiser de telle manière à ce qu'une compression RLE classique pourrait déjà avoir un avantage notable.
Mais comment retrouver la chaine originale me direz vous ? En fesant l'opération inverse. je m'explique.
La chaine "ecdaaabbb" est ce qu'on apelle la Tranformée de Burrows
Nous savons (puisque nous l'avons fait précédemment) que les données sont triées. Et c'est là qu'est la clé !
donc voici notre tableau de départ
e
c
d
a
a
a
b
b
b
Donc nous allons rajouter les octets triés (c'est un bon début :) )
e a
c a
d a
a b
a b
a b
b c
b d
b e
Bon ensuite je n'ai pas encore beaucoup appronfondu l'algo pour recréer la chaine mais on sait qu'après l'unique c il y a un a donc on met un a après tous les c (euh l'unique aprdon).
e a
c a
d a
a b
a b
a b
b ca
b d
b e
Et ainsi de suite pour arriver au tableau suivant (nous n'aurons pas forcement besoin de calculer l'intégralité de ce tableau)
1 e abcabdabe <-- chaine originale
2 c abdabeabc
3 d abeabcabd
4 a bcabdabea
5 a beabcabda
6 a bdabeabca
7 b cabdabeab
8 b dabeabcab
9 b eabcabdab
A suivre ... La prochaine fois explication du MTF (Move To Front)
16 nov. 2005 à 09:17
La méthode de base de réorganisation BWT a été mise au point en 1994. Depuis, les meilleurs taux de compression réalisés sont souvent à base de cette méthode de réorganisation. Il est à prévoir que de nouvelle méthode post BWT, similaire à l'algorhytme JPEG verront le jour. Pour l'instant les possiblités offertes par cet algorhytme n'ont pas encore été totalement exploités (à l'inverse de Hufmann par exemple dont on a défini une certaine limite). BWT est donc très récent et est donc succeptible de provoquer une véritable révolution dans les méthodes de compression (une autre ...). Bientot dans le zip, je mettrai une documentation sur BWT et MTF, un recueil de texte glané ci et là sur le net.
Bonne prog !
14 nov. 2005 à 09:54
L'efficacité de cette méthode est ... dans ce cas précis nulle vu qu'elle ne fait que réorganiser les données vers une forme plus ... facilement compressible. Il allourdit meme le packet de la référence de ligne qui permettra de retrouver la chaine originelle. Cependant, la réorganisation effectué permet de dégager un très grand nombre de zéro dans la chaine binaire (vu que le move to front remplace 1111100000 par 1000010000). Pour ce qui est de l'implémentation de cet algorhytme, bzip2 l'utilise ainsi que compressia et ... bien d'autre je pense (au fait Doodoo256 j'ai une version beta de compressia en ligne de commande qui devrait t'interesser, pour que je te le fasse aprvenir contacte moi à rebel_thc AroBaBase yahoo point afrreux -Super ce mail non ? :p)
Pour répondre à la compression qui sera utilisé par la suite, vu le très grand nombre de zéro que nous pourrons trouver, j'ai opté pour une compression arithmétiqe binaire pas au point encore pour le moment( us_30 Huffman serait un acte inutile dans ce cas la vuq ue je travaille en binaire et donc le gain serait nul sous cette forme vu qu'il faudrai au moins 1 bit pour coder 1 bit alors que la compression aritmétique permet de coder n bit avec un seul bit ! je suis arrivé chez moi à n = 1236 bits sans forcer soit un gain considérable !).
Doodoo256, l'avantage de cette méthode est qu'il n'est pas nécessaire d'avoir un tableau (n,n) donc exponentielle mais plutot du genre (3 ou 4,n) donc linéaire ce qui permet d'avoir une montée de mémoire moindre suivant la taille du bloc (le BWT expliqué est toujours de la forme (n,n)). Donc pour conclure... plus la mémoire est grande, plus grand est le buffer, et ... plus la réorganisation des données est efficiente.
Le fait de travailler sous forme binaire permet de trouver des cycles de répétitions plus précis que par octects par exemple ab n'a aucun cycle alors que 0110000101100010 (ab en binaire) contient des cycles ici 011000 01 011000 10
La taille du buffer optimale serait donc de la forme Total mémoire / NombreDeBitsDuBloc*BitsUtilisésPourTraitementDunBit
Bientot la suite ...
Bonne prog
12 nov. 2005 à 16:48
Je découvre cet algo, que je cherchais depuis des années dans ma pauvre tête... Pour comprendre, faut mieux lire l'adresse donné sur wikipedia ... Désolé psycho81. Bon, je me pencherai dessus, et si j'ai une bonne remarque, je te tiendrai au courant. Le .NET , c'est pas ma spécialité, mais on le comprend assez bien, en connaissant VB...
Par contre, pour avancer un peu sur le débat, je me pose qlq questions.
- Pourquoi choisir la forme binaire plutôt que par octet directement.
- Ce qui me semble évident, pour répondre à DooDoo, c'est de découper par bloc. Si on pense à des fichiers de plusieurs Méga, voir Giga, on rendrait fou le PC sans bloc ! Mais il reste une question. Y a-t-il une taille optimum... (surement, si on tient compte des déclarations des variables)
- Ensuite, après transformation, je ne vois pas l'intérêt d'utiliser Huffman. Le plus direct serait comme pour le PCX d'antant, non ? (surtout si la taille traitée est assez conséquente)
Amicalement,
Us.
11 nov. 2005 à 20:31
Le site de Compressia est mort on dirait.
En tout cas, quel algo de compression as-tu l'intention d'appliquer après BWT ?
Question bête :
Si on applique BTW sur un fichier binaire d'environ 500 Ko, il faut une grosse bécane pour faire les rotations ou alors découper en blocs c'est ça ?
11 nov. 2005 à 19:28
je viens de faire un petit tour dans les sources et je tombe là dessus...
Je vais suivre avec intérêt tes travaux ça m'a l'air révolutionnaire malgré la complexité de l'algo.
Où se situe l'efficacité de cette méthode par rapport à du 7z, LZW et Huffman par exemple ?
L'algo a déjà été implémenté ? Dans quel soft ?
a++ ;
4 nov. 2005 à 09:23
Et vi je me sentais un peu seul. Déjà que dans les méandres de mon cerveau torturé, il y a peu de monde .... Mais bon, tu me dira ... C'est pas avec des codes pareil qu'on attire du monde :p Entre le crypteur multiiidimensionel (à ne pas confondre avec le distruuucteur dimensionneeeeel - allusion à "Hé mec elle est où ma caisse" que Chris81 connait sur le bout des doigts) et çà, je suis pas sur de passer pour quelqu'un de très clair :) ) Enfin test le code, tu verra des résultat surprenant avec des chaines style abcabcabc ou aaaaaaaaa. C'est ... surprenant :)
Bisoux a toi mon unique fan :)
3 nov. 2005 à 23:08
3 nov. 2005 à 10:37
3 nov. 2005 à 10:35
3 nov. 2005 à 10:14
3 nov. 2005 à 09:42
Tout d'abord, je me dois d'expliquer l'utilité de ce code. Il rentre dans la composante de beaucoup de compresseur surpuissant comme bzip2 ou compressia (compcl.exe pour les intimes, un exécutable qui compresse, en version beta plus que tout autre compresseur existant sur la marché - Me contacter si vous souhaitez cet exécutable qui relègue bzip2 au rang d'outsider bien lointain).La méthode BWT permet de réorganiser les données (celà ne compresse nullement au contraire cela rajoute un tout petit bloc de données supplémentaires). Ou est l'utilité alors me dire d'appliquer cette méthode ?
Prenons par exemple la chaine "abcabdabe" (qui sommes toutes est une chaine peux courante dans nos fichiers textes :) )
La méthode BWT demande en théorie la longueur de la chaine au carré d'octets mémoire pour son traitement car pour effectuer cette opération nous devons faire un tableau[LongueurChaine] de Chaine qui sera disposer comme suit :
abcabdabe
bcabdabea
cabdabeab
abdabeabc
bdabeabca
dabeabcab
abeabcabd
beabcabda
eabcabdab
Jusque la, rien de très compréhensible. Trions maintenant ce tableau (et c'est là qu'est concentré mon travail actuellement)
1 abcabdabe <-- chaine originale
2 abdabeabc
3 abeabcabd
4 bcabdabea
5 beabcabda
6 bdabeabca
7 cabdabeab
8 dabeabcab
9 eabcabdab
et maintenant prenons le dernier octet de chaque élément du tableau d'octet. Ce qui nous donne "ecdaaabbb" (n'oublions pas que nous devrons rajouter a ce bloc l'index du tableau, c'est à dire le 1). Nous nous apercevons que la sequence "ab" a été réoganiser de telle manière à ce qu'une compression RLE classique pourrait déjà avoir un avantage notable.
Mais comment retrouver la chaine originale me direz vous ? En fesant l'opération inverse. je m'explique.
La chaine "ecdaaabbb" est ce qu'on apelle la Tranformée de Burrows
Nous savons (puisque nous l'avons fait précédemment) que les données sont triées. Et c'est là qu'est la clé !
donc voici notre tableau de départ
e
c
d
a
a
a
b
b
b
Donc nous allons rajouter les octets triés (c'est un bon début :) )
e a
c a
d a
a b
a b
a b
b c
b d
b e
Bon ensuite je n'ai pas encore beaucoup appronfondu l'algo pour recréer la chaine mais on sait qu'après l'unique c il y a un a donc on met un a après tous les c (euh l'unique aprdon).
e a
c a
d a
a b
a b
a b
b ca
b d
b e
Et ainsi de suite pour arriver au tableau suivant (nous n'aurons pas forcement besoin de calculer l'intégralité de ce tableau)
1 e abcabdabe <-- chaine originale
2 c abdabeabc
3 d abeabcabd
4 a bcabdabea
5 a beabcabda
6 a bdabeabca
7 b cabdabeab
8 b dabeabcab
9 b eabcabdab
A suivre ... La prochaine fois explication du MTF (Move To Front)