/* * Auteurs : Benjamin Bécar * Erwann Le Hesran * Cette FAQ est destinée ŕ donner les rudiments de la compression * LZSS, et d'expliciter notre programme. * Pour de plus amples informations sur le LZSS, vous pouvez * consultez la FAQ. * de Nicolas "Pixel" Noble, disponible ici * */ /******************************************************************/ /************************** N O T E S *****************************/ /******************************************************************/ 1. Je tiens avant tout ŕ remercier Pixel pour son aide précieuse sur ce projet, tant du point de vue de la compréhension, que de la réalisation. 2. Ce programme a été réalisé en tant que projet de fin de 1čre année ŕ l'ENSICAEN. Vous trouverez sur ce site le programme, ainsi que le rapport de ce projet : http://www.ifrance.com/psxtreme/lzss_2003/ /******************************************************************/ /*********************** Q U E S T I O N S ************************/ /******************************************************************/ Q: Qu'est-ce que la compression LZ77 ? R: Inventée en 1977 par Ziv et Lempel, il s'agit d'un algorithme de compression sans perte (lossless). Il s'agit d'une méthode ŕ fenętre coulissante. C'est ŕ dire que le texte est parcouru par des fenętres ciblées sur une partie du texte ŕ coder (lookahead buffer) et sur les derniers caractčres encodés (search buffer. Le texte ŕ encoder est lu pas ŕ pas, puis comparé au texte déjŕ encodé. Si des chaînes de caractčres sont identiques, le programme les codes par un bloc de 3 octets, indiquant la longueur, le saut et le caractčre suivant. La longueur correspond ŕ la taille de la chaîne correspondante. Le saut donne le nombre de bit dont il faut reculer pour voir le début de cette chaîne. Par exemple le texte I have to find you, I have to meet you Sera codé sous la forme I have to find you, eet Avec J=Jump (saut) et L=Lenght(longueur) En fait, tous les caractčres seront encodés suivant ce principe, y compris des caractčres seuls, codés sous la forme <0;0;'x'>. Le principal problčme est évident : on code des octets simples sur 3 octets. /******************************************************************/ Q: Je n'ai pas bien compris cette histoire de buffer ? R: Les buffer divisent le fichier ŕ compresser en plusieurs parties. |---------------------|------| La guerre fait rage depu|is si longtemps que l|a caus|e du confli... |---------------------|------| | Search Buffer | Look | | |Ahead | | |Buffer| |---------------------|------| Tout ce qui est ŕ droite de la séparation entre les deux buffer n'a pas été encodé. La chaîne "a caus" est en cours de compression. L'algorithme va regarder si dans le search buffer (et uniquement dans celui-ci) cette chaîne existe. S'il ne trouve aucune occurence, il va simplement coder le caractčre "a" et décaler les deux buffers d'un octet. /******************************************************************/ Q: Quels sont les différences entre LZ77, LZ78, LZSS, LZW ou autres ?R: Il existe de nombreuses versions des algorithmes de type LZ. ######## # LZ77 # ######## Méthode ŕ "fenętre coulissante." Les chaînes ŕ encoder sont comparées aux chaînes déjŕ codées. ######## # LZ78 # ######## Méthode ŕ dictionnaire. le fichier est lu pas ŕ pas. A chaque caractčre, l'algorithme insčre un code contenant , et ajoute ŕ ce dictionnaire la chaîne "ce caractčre+caractčre suivant." Exemple : Si six scies scient six cyprčs !! |-----------------------------------------------------| |Dictionnaire Code | Dictionnaire Code | |-----------------------|-----------------------------| |0 null | 6 " s" (3,"s") | |1 "S" (0,"S") | 7 "c" (0,"c") | |2 "i" (0,"i") | 8 "ie" (2,"e") | |3 " " (0," ") | 9 "s " (4," ") | |4 "s" (0,"s") | 10 "sc" (4,"c") | |5 "ix" (2,"x") | 11 "ien" (8,"n") | |-----------------------------------------------------| Męme inconvénient que dans le LZ77 : on code des octets simples sur 2 octets. ######## # LZW # ######## Amélioration du LZ78 part Terry Welch [84]. Méthode ŕ dictionnaire. Cet algorithme a été breveté. Cet algorithme n'écrit que des références ŕ un dictionnaire. Tout d'abord il ajoute dans le dictionnaire tous les caractčres individuels présents dans le texte. Ensuite il reparcourt le fichier, et quand il rencontre un caractčre, il donne son adresse et ajoute a la suite du dico cette chaine + le caractčre suivant. Ensuite il se place sur le caractčre suivant etc... Exemple : Entrée : Si six scies scient six [...] |----------------------------------------| |Dictionnaire | Dictionnaire | |----------------|-----------------------| |1 "S" | 7 "Si" | |2 "i" | 8 "i " | |3 " " | 9 " s" | |4 "s" | 10 "si" | |5 "x" | 11 "ix" | |6 "c" | 12 "x " | |7 "e" | 13 " sc" | |8 "n" | 14 "ci" | |9 "t" | 15 "ie" | |----------------------------------------| Lecture de "S" / En sortie : 1 / Dans le dico : "Si" Lecture de "i" / En sortie : 2 / Dans le dico : "i " Lecture de " " / En sortie : 3 / Dans le dico : " s" Lecture de "s" / En sortie : 4 / Dans le dico : "si" Lecture de "i" / En sortie : 2 / Dans le dico : "ix" Lecture de "x" / En sortie : 5 / Dans le dico : "x " Lecture de " s" / En sortie : 9 / Dans le dico : " sc" Lecture de "c" / En sortie : 6 / Dans le dico : "ci" Lecture de "i" / En sortie : 2 / Dans le dico : "ie" Lecture de "e" / En sortie : 7 / Dans le dico : "es" Lecture de "s" / En sortie : 4 / Dans le dico : "s " Lecture de " sc" / En sortie : 13 / Dans le dico : " sci" ... ######## # LZSS # ######## Méthode ŕ fenętre coulissante. Par Storer et Szymanski [82]. Amélioration du LZ77. Code le texte en laissant tel quel les caractčres individuels, et code sur 2 octets toute chaîne de longueur supérieure ŕ 3. Ce code est écrit sur 2 octets+1bit, et contient un "saut", une "longueur" et un bit dans la bitmap. /******************************************************************/ Q: Comment cela marche-t-il ? R: Comme l'algorithme distingue les chaînes supérieures ŕ 3 et les caractčres individuels, il établit une bitmap qui dira si les caractčres ŕ lire sont des "caractčres" ou des "codes pour une chaîne". Exemple : |Bitmaps | Datas |--------|---------------------------|--------| |00000000| 49 20 68 61 76 65 20 74 |I have t| |00000000| 6f 20 68 69 6e 64 20 79 |o find y| |00001000| 6f 75 2c 20<47 01>6d 65 65|ou,..mee| |01000000| 74<41 01>FF FF |t.. | ".." représente une chaîne compressée (il s'agit de caractčres, mais pour ne pas surchargé, j'ai mis ".."). Un zéro dans la bitmap indique qu'il faut simplement copier le prochain octet lu, et un 1 indique qu'il faut lire les 2 suivants, les décoder pour avoir le saut et la longueur de la chaine ŕ copier. Finalement, le fichier compressé ressemblera ŕ ceci: 0000: |00 49 20 68| |61 76 65 20| |74 00 6f 20| |68 69 6e 64| I have to find 0010: |20 79 00 6f| |75 2c 20 47| |01 6d 65 65| |74 41 01 FF| you, I have to meet you 0020: |FF| (les caractčres FF FF correspondent ŕ la fin du codage) /******************************************************************/ Q: Comment sont stockés le saut et la longueur? R: Voici un exemple de stockage(ce n'est pas le seul possible): O3 O2 O1 O0 L3 L2 L1 L0 | OB OA O9 O8 O7 O6 O5 O4 Cela signifie que nos 2 informations sont stockées ainsi: le saut voit ses bits de poids faibles "rangés" ŕ la place des 4 bits de poids forts du premier octet, etles 8 bits de poids forts sont stockés directement dans le second octet. La longueur, qui tient sur 4 bits, est stockée sur les bits de pids faibles du premier octet. On peut coder des longueurs d'au maximum 18 octets (4 puissance 2 = 16, mais on ne code pas les longueurs 2 et moins.) Le saut tient donc sur 12 bits et la longueur sur 4 bits(au moins dans notre explication, caron peut faire varier ces valeurs ŕ par exemple 5/11). (12 bits donne des jumps maximums de 4096 octets). En codant la longueur sur 5 bits, on peut trouver des chaînes de 35octets, mais dans le męme temps, le search buffer (sur 11 octets, ne fait plus que 2048 octets). /******************************************************************/ Q: Quand on a les 2 octets codés, commment retrouver le saut et la longueur? R: La premičre chose pouvant poser problčme est le fait que nos 2 octets sont des char, et que nous voulons longueur et saut sous la forme de int. Il va donc falloir faire des cast. longueur=(char_en_cours&0x0F)+3; cette premičre commande permet,grâce ŕ un masque, de ne garder que les bits de poids faibles du premier octet, auxquels on rajoute 3 afin de d'obtenir un int compris entre 3 et 18. Ceci est la longueur. int saut; char_en_cours=char_en_cours>>4; saut=char_suivant; saut=saut<<4; saut=saut|char_en_cours; Ces commandes permettent de retrouver la taille du saut ŕ accomplir. On commence par déplacer les bits de poids fort du premier octet de 4 rangs vers la droite, en les remplaçant par des 0. Puis on cast le second octet en un int , pour pouvoir décaler ensuite tous les bits de 4 rangs vers la gauche. On réalise finalement un "ou" logique (avec le symbole "|") entre nos variables char_en_cours et saut, afin de réunir tous les bits, et on obtient notre saut. /******************************************************************/ Q: Il existe différentes paramčtres d'implémentations, quels sont-ils ? R: il existe plusieurs paramčtres réglables pour le LZSS, parmi lesquels : 1iscomp overlap negative inverse Ces paramčtres permettent de changer le comportement de l'algorithme. 1iscomp change le codage de la bitmap: 0 code une chaîne compressée, et 1 un caractčre. L'overlap est un outil puissant qui permet de coder une chaîne de caractčres ŕ l'aide de carctčres qui n'ont pas encore été codés. C'est ŕ dire que le saut sera plus petit que la longueur de la chaîne ŕ coder. 123123123123 sera codé 123 Au moment oů on code ce saut et cette longueur, on n'a pas assez de caractčres, donc on va se servir des 3 premiers codés pour trouver les 3 suivants puis les 3 derniers. En fait c'est parfaitement logique si on prend le temps de comprendre que l'algorithme avance "pas ŕ pas". Le paramčtre negative est lŕ pour les cas oů on se retrouverait ŕ faire un saut qui nous amčnerait avant le début du fichier. Dans ce cas, on considčre alors que l'on lit des zéros. Exemple : En hexadécimal, on au début du fichier 01 00 00 00 01 00 00 00 Si le negative trick est activé, on a donc ...00 00 00 00 00 00 00 | 01 00 00 00 01 00 00 00 "00 avant le fichier | Début du fichier On codera donc cette chaîne de la façon suivante : 01 Dans le cas contraire on aura 01 00 00 00 Détail amusant : devinez le résultat de 01 00 00 00 01 00 00 00 si overlap + negative sont activés. [Réponse au bas de la page]. Il existe d'autres paramčtres que Pixel détaillent dans sa FAQ. /******************************************************************/ Q: Comment pourrait-on améliorer ce programme? R: Le fait est que ce programme, męme si il compresse bien, et avec un taux acceptable, reste trčs lent.Cela vient du fait que nous n'avons pas totalement utilisé les possibilités du LZSS: Le fait de ranger les chaînes codables dans un arbre binaire permettait de gagner beaucoup de temps, mais nous n'avons pas eu le temps de nous en occuper. La premičre amélioration ŕ apporter serait donc de faire cet arbre binaire. /******************************************************************/ Remerciements : - Xenogears [PlaystatiĘŤfËŤfĚŤfÍŤfÎŤfĎŤfĐŤfŃŤfŇŤfÓŤfÔŤfŐŤfÖŤf×ŤfŘŤfŮŤfÚŤfŰŤfÜŤfÝŤfŢŤfßŤfŕŤfáŤfâŤfăŤfäŤfĺŤfćŤfçŤfčŤféŤfęŤfëŤfěŤfíŤfîŤfďŤfđŤfńŤfňŤfóŤfôŤfőŤföŤf÷ŤfřŤfůŤfúŤfűŤfüŤfýŤfţŤf˙ŤfŽfŽfŽfŽfŽfŽfŽfŽfŽf Žf ŽfŽfŽf ŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽfŽf Žf!Žf"Žf#Žf$Žf%Žf&Žf'Žf(Žf)Žf*Žf+Žf,Žf-Žf.Žf/Žf0Žf1Žf2Žf3