Compression LZ77

Cette page a été réalisée par Nicolas Delerue pour un article publié dans

Imaginons la suite de caractères hexadécimaux suivantes:
215AB87F67E454CD5AB87F33DEA9806783458778 776576DB06E66EA98003CD5AB87CD5AB87F33DEA 98006EA98006EA9800766EA9800F333DEA215AB8 7F69806EA9806EA9800766EA903406EA98006EA9 80766EA9803406EA98215AB87FEA980766EA5B64 65D7E98BDA89456F345B6465D798BDA89456FEA9 80076345B6465D7
Elle contient: 255 caractères

Dico: les caractères hexadécimaux permettent de représenter tous les nombres compris entre 0 et 15 en utilisant la lettre A pour 10, B pour 11 et ainsi de suite jusqu'à F pour 15. Les nombres hexadécimaux sont souvent utilisés en informatique car ils permettent de représenter tous les nombres pouvant être écrit avec 4 bits, c'est à dire tous les nombres compris entre 2 puissance 0 (c'est à dire 0) et 2 puissance 4 moins 1 (c'est à dire 15)...

Un emplacement dans cette chaîne a une adresse comprise entre 0 et 255, il faut donc 8 bits, c'est à dire deux nombres hexadécimaux pour écrire une telle adresse (car 255 en hexadécimal s'écrit FF).
Nous allons chercher toutes les séquences repétées dans cette chaîne et les remplacer par l'adresse et la longueur de la première occurrence de la séquence.
Cependant pour pouvoir faire la différence entre des données et l'adresse d'une séquence répétée, il faut utiliser un "code" particulier, par exemple en mettant un "0" devant l'adresse d'un séquence repétée. Cela veut dire que à chaque fois qu'il y aura un "0" dans nos données, les deux caractères suivants donneront l'adresse d'une séquence, suivis de deux caractères indiquant la longueur de cette séquence. Ainsi, si je vois 03A1B dans les données, cela veut dire que à cet emplacement, il faut insérer la séquence qui se trouve à l'adresse 3A (c'est à dire 58 en notation décimale) et de longueur 1B (c'est à dire 27 en décimal).
Un problème risque de se poser quand un zéro apparait dans les données! Il faut donc remplacer tous les zéros par une combinaison choisie, par exemple "0FFFF". Vu qu'il y a en moyenne un zero pour 16 caractères, cela veut dire que la taille du texte va être augmentée d'un quart (puisque l'on ajoute en moyenne 4 caractères par séquence de 16 caractères).
Notre chaîne devient:
215AB87F67E454CD5AB87F33DEA98 0FFFF6783458778776576DB 0FFFF6E66EA980FFF F0FFFF3CD5 AB87CD5AB87F33DEA980FFFF 0FFFF6EA98 0FFFF 0FFFF6EA980FFFF 0FFFF766EA98 0FFFF0FFFF F333DEA215AB87F6980FFFF 6EA980FFFF6EA98 0FFFF0FFFF 766EA90FFFF34 0FFFF6EA980FFFF 0FFFF6EA98 0FFFF766EA980FFFF 340FFFF6EA 98215AB87FEA980FFFF 766EA5B6465D7E98BDA89456F345B6465D798BDA 89456FEA980FFFF 0FFFF76345B6465D7
Elle contient: 359 caractères
Pour qu'un remplacement soit rentable, il faut au moins que la séquence à remplacer soit plus longue que la séquence utilisée pour indiquer les adresses des chaînes, c'est à dire qu'il faut que la séquence fasse au moins 6 caractères.
Pour commencer nous allons prendre les 6 premiers caractères de la chaîne et chercher si la même séquence apparaît ailleurs dans le texte.
215AB87F67E454CD 5AB87F33DEA980FFFF6783458778776576DB0FFF F6E66EA980FFFF0FFFF3CD5AB87CD5AB87F33DEA 980FFFF0FFFF6EA980FFFF0FFFF6EA980FFFF0FF FF766EA980FFFF0FFFFF333DEA 215AB8 7F6 980FFFF6EA980FFFF6EA980FFFF0FFFF766EA90F FFF340FFFF6EA980FFFF0FFFF6EA980FFFF766EA 980FFFF340FFFF6EA98 215AB8 7FEA980FFFF766EA5 B6465D7E98BDA89456F345B6465D798BDA89456F EA980FFFF0FFFF76345B6465D7
Chaque fois que cette chaîne est trouvée (caractères en vert ci-dessus), il faut regarder si les caractères suivants sont aussi similaires à ceux du début (les caractères similaires sont en rouge ci-dessus). Puis chacune des ces occurences est remplacée par l'adresse de la première occurence de la chaîne (c'est à dire 00 suivi de sa longueur codée en hexadécimal: 9 dans le premier cas et 8 dans le second). Notre chaîne devient:
215AB87F67E454CD 5AB87F33DEA980FFFF6783458778776576DB0FFF F6E66EA980FFFF0FFFF3CD5AB87CD5AB87F33DEA 980FFFF0FFFF6EA980FFFF0FFFF6EA980FFFF0FF FF766EA980FFFF0FFFFF333DEA 00009980FFFF6EA980FFFF6EA980FFFF0 FFFF766EA90FFFF340FFFF6EA980FFFF0FFFF6EA 980FFFF766EA980FFFF340FFFF6EA98 00008EA980FFFF766EA5B6465D7E98BDA 89456F345B6465D798BDA89456FEA980FFFF0FFF F76345B6465D7
Elle contient: 352 caractères
Maintenant, il faut faire la même chose en commencçant à partir du second caractère, puis du troisième et ainsi de suite. Cette fois-ci l'adresse de la séquence n'est plus 00, mais 01, 02 et ainsi de suite...
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 3 (adresse: 02), qui est repétée à la position 17.
215AB87F67E454CD 5AB87F 33DEA980FFFF6783458778776576DB0FF FF6E66EA980FFFF0FFFF3CD5AB87CD 5AB87F33DE A980FFFF0FFFF6EA980FFFF0FFFF6EA980FFFF0F FFF766EA980FFFF0FFFFF333DEA00009980FFFF6 EA980FFFF6EA980FFFF0FFFF766EA90FFFF340FF FF6EA980FFFF0FFFF6EA980FFFF766EA980FFFF3 40FFFF6EA9800008EA980FFFF766EA5B6465D7E9 8BDA89456F345B6465D798BDA89456FEA980FFFF 0FFFF76345B6465D7
Notre chaîne devient:
215AB87F67E454CD 0020633DEA980FF FF6783458778776576DB0FFFF6E66EA980FFFF0F FFF3CD5AB87CD00206 33DEA980FFFF0FFFF6EA980FFFF0FFFF6EA980FF FF0FFFF766EA980FFFF0FFFFF333DEA00009980F FFF6EA980FFFF6EA980FFFF0FFFF766EA90FFFF3 40FFFF6EA980FFFF0FFFF6EA980FFFF766EA980F FFF340FFFF6EA9800008EA980FFFF766EA5B6465 D7E98BDA89456F345B6465D798BDA89456FEA980 FFFF0FFFF76345B6465D7
Elle contient: 350 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 15 (adresse: 0E), qui est repétée à la position 83.
215AB87F67E454CD0020 633DEA980FFFF6783458778776576DB0FFFF6E66 EA980FFFF0FFFF3CD5AB87 CD0020 633DEA980F FFF0FFFF6EA980FFFF0FFFF6EA980FFFF 0FFFF766EA980FFFF0FFFFF333DEA00009980FFF F6EA980FFFF6EA980FFFF0FFFF766EA90FFFF340 FFFF6EA980FFFF0FFFF6EA980FFFF766EA980FFF F340FFFF6EA9800008EA980FFFF766EA5B6465D7 E98BDA89456F345B6465D798BDA89456FEA980FF FF0FFFF76345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020 633DEA980FFFF6783458778776576DB0FFFF6E66 EA980FFFF0FFFF3CD5AB87 00E130FFFF6EA980FFFF0FFFF6EA980FF FF0FFFF766EA980FFFF0FFFFF333DEA00009980F FFF6EA980FFFF6EA980FFFF0FFFF766EA90FFFF3 40FFFF6EA980FFFF0FFFF6EA980FFFF766EA980F FFF340FFFF6EA9800008EA980FFFF766EA5B6465 D7E98BDA89456F345B6465D798BDA89456FEA980 FFFF0FFFF76345B6465D7
Elle contient: 336 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 25 (adresse: 18), qui est repétée à la position 61.
215AB87F67E454CD0020633D EA980FFFF6783458778776576DB0FFFF6 E66E A980F FFF0FFFF3CD5AB870 0E130FFFF6 EA980F FFF0FFFF6 EA980F FFF 0FFFF766 EA980F FFF0FFFFF333DEA00 009980FFFF6 EA980F FFF6 EA980F FFF 0FFFF766EA90FFFF340FFFF6 EA980F FFF 0FFFF6 EA980F FFF766 EA980F FFF 340FFFF6EA9800008 EA980F FFF766EA5B6465D7E 98BDA89456F345B6465D798BDA89456F EA980F FFF 0FFFF76345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633D EA980FFFF6783458778776576DB0FFFF6 E66018090FFFF3C D5AB8700E130FFFF601809 0FFFF601809 0FFFF766018090F FFFF333DEA00009980FFFF6 0180A01809 0FFFF766EA90FFFF340FFFF6 018090FFFF60180 976601809 340FFFF6EA980000801809 766EA5B6465D7E98BDA89456F345B6465 D798BDA89456F01809 0FFFF76345B6465D7
Elle contient: 291 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 27 (adresse: 1A), qui est repétée à la position 136.
215AB87F67E454CD0020633DEA 980FFFF6783458778776576DB0FFFF6E6 6018090FFFF3CD5AB8700E130FFFF6018090FFFF 6018090FFFF766018090FFFFF333DEA00009 980FFF F60 180A018090FFFF766EA90FFFF340FFFF6018090F FFF60180976601809340FFFF6EA9800008018097 66EA5B6465D7E98BDA89456F345B6465D798BDA8 9456F018090FFFF76345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA 980FFFF6783458778776576DB0FFFF6E6 6018090FFFF3CD5AB8700E130FFFF6018090FFFF 6018090FFFF766018090FFFFF333DEA00009 01A080180A018090FFFF766EA90FFFF34 0FFFF6018090FFFF60180976601809340FFFF6EA 980000801809766EA5B6465D7E98BDA89456F345 B6465D798BDA89456F018090FFFF76345B6465D7
Elle contient: 288 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 29 (adresse: 1C), qui est repétée à la position 52.
215AB87F67E454CD0020633DEA98 0FFFF6783458778776576DB 0FFFF6E660 18090FFFF3CD5AB8700E13 0FFFF60180 90FFFF6 018090FFFF766018090FFFFF333DEA000 0901A080180A018090FFFF766EA90FFFF34 0FFFF60180 90FFFF6 018097660180934 0FFFF6EA98 0000801809766EA5B6465D7E98BDA89456F345B6 465D798BDA89456F018090FFFF76345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA98 0FFFF6783458778776576DB 01C06E66018090FFFF3CD5AB8700E13 01C060180901C06 018090FFFF766018090FFFFF333DEA000 0901A080180A018090FFFF766EA90FFFF34 01C060180901C06 018097660180934 01C06EA980000801809766EA5B6465D7E 98BDA89456F345B6465D798BDA89456F018090FF FF76345B6465D7
Elle contient: 282 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 52 (adresse: 33), qui est repétée à la position 196.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E 66018090FFFF3CD5AB8700E1301C060180901C06 018090FFFF766018090FFFFF333DEA0000901A08 0180A018090FFFF766EA90FFFF3401C060180901 C0601809766018093401C0 6EA9800008 01809766EA5B6465D7E98BDA89456F345B6465D7 98BDA89456F018090FFFF76345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E 66018090FFFF3CD5AB8700E1301C060180901C06 018090FFFF766018090FFFFF333DEA0000901A08 0180A018090FFFF766EA90FFFF3401C060180901 C060180976601809340330 6A980000801809766EA5B6465D7E98BDA 89456F345B6465D798BDA89456F018090FFFF763 45B6465D7
Elle contient: 281 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 58 (adresse: 39), qui est repétée à la position 109.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E660180 90FFFF3CD5AB8700E1301C060180901C0 6018090FFFF7 660180 90FFFFF333DEA0000 901A080180A018090FFFF766EA90FFFF3401C060 180901C06018097 660180 93403306A98000080 1809766EA5B6465D7E98BDA89456F345B6465D79 8BDA89456F018090FFFF76345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E660180 90FFFF3CD5AB8700E1301C060180901C0 6018090FFFF70390C F333DEA0000901A080180A018090FFFF766EA90F FFF3401C060180901C06018097 039073403306A980000801809766EA5B6 465D7E98BDA89456F345B6465D798BDA89456F01 8090FFFF76345B6465D7
Elle contient: 272 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 59 (adresse: 3A), qui est repétée à la position 87.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E660180 90FFFF3CD5AB8700E1301C0 601809 01C 0601 809 0FFFF70390CF333DE A0000901A080180A018090FFFF766EA90FFFF340 1C06 01809 01C0 6018097039 073403306A980000801809766EA5B6465D7E98BD A89456F345B6465D798BDA89456F018090FFFF76 345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E660180 90FFFF3CD5AB8700E1301C0 03A071C003A0B 70390CF333DEA0000901A080180A018090FFFF76 6EA90FFFF3401C003A07 1C003A067039073 403306A980000801809766EA5B6465D7E98BDA89 456F345B6465D798BDA89456F018090FFFF76345 B6465D7
Elle contient: 261 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 60 (adresse: 3B), qui est repétée à la position 128.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E660180 90FFFF3CD5AB8700E1301C003A071C003 A0B70390CF333DEA0000901A080180A 018090 FFFF 766EA90FFFF3401C003A071C003A067039073403 306A980000801809766EA5B6465D7E98BDA89456 F345B6465D798BDA89456F 018090 FFFF 76345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E660180 90FFFF3CD5AB8700E1301C003A071C003 A0B70390CF333DEA0000901A080180A 03B0A766EA90FFFF3401C003A071C003A 067039073403306A980000801809766EA5B6465D 7E98BDA89456F345B6465D798BDA89456F 03B0A76345B6465D7
Elle contient: 251 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 64 (adresse: 3F), qui est repétée à la position 138.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E660180 90FFFF3CD5AB8700E1301C003A071C003 A0B70390CF333DEA0000901A080180A03B0A766E A90F FFF 3401C003A071C003A 067039073403306A980000801809766EA5B6465D 7E98BDA89456F345B6465D798BDA89456F03B0A7 6345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E660180 90FFFF3CD5AB8700E1301C003A071C003 A0B70390CF333DEA0000901A080180A03B0A766E A03F07401C003A0 71C003A067039073403306A980000801809766EA 5B6465D7E98BDA89456F345B6465D798BDA89456 F03B0A76345B6465D7
Elle contient: 249 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 83 (adresse: 52), qui est repétée à la position 144.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A071C003 A0B70390CF333DEA0000901A080180A03B0A766E A03F074 01C003 A071C003A06703907 3403306A980000801809766EA5B6465D7E98BDA8 9456F345B6465D798BDA89456F03B0A76345B646 5D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A071C003 A0B70390CF333DEA0000901A080180A03B0A766E A03F07405210670 39073403306A980000801809766EA5B6465D7E98 BDA89456F345B6465D798BDA89456F03B0A76345 B6465D7
Elle contient: 238 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 84 (adresse: 53), qui est repétée à la position 92.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A07 1C003A 0B7 0390CF333DEA0000901A080180A03B0A766EA03F 0740521067039073403306A980000801809766EA 5B6465D7E98BDA89456F345B6465D798BDA89456 F03B0A76345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A07 05307B70390CF333DEA0000901A080180 A03B0A766EA03F0740521067039073403306A980 000801809766EA5B6465D7E98BDA89456F345B64 65D798BDA89456F03B0A76345B6465D7
Elle contient: 236 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 119 (adresse: 76), qui est repétée à la position 167.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A 080180A03B0A766EA03F0740521067039 073403306A98000080180 9766EA5B6465D7E98 BDA89456F345B6465D798BDA89456F03B0A76345 B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A 080180A03B0A766EA03F0740521067039 073403306A9800007606 9766EA5B6465D7E98BDA89456F345B6465D798BD A89456F03B0A76345B6465D7
Elle contient: 235 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 126 (adresse: 7D), qui est repétée à la position 219.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A08 0180A03B0A766EA0 3F0740521067039073403306A98000076069766E A5B6465D7E98BDA89456F345B6465D798BDA8945 6F03 B0A7 6345B6465D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A08 0180A03B0A766EA0 3F0740521067039073403306A98000076069766E A5B6465D7E98BDA89456F345B6465D798BDA8945 6F07D07345B6465 D7
Elle contient: 233 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 178 (adresse: B1), qui est repétée à la position 200.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A08 0180A03B0A766EA03F0740521067039073403306 A98000076069766EA5B6465 D7E98BDA89456F34 5B6465 D79 8BDA89456F07D0734 5B6465 D7
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A08 0180A03B0A766EA03F0740521067039073403306 A98000076069766EA5B6465 D7E98BDA89456F34 0B10898BDA89456F07D0734 0B108
Elle contient: 227 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 187 (adresse: BA), qui est repétée à la position 205.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A08 0180A03B0A766EA03F0740521067039073403306 A98000076069766EA5B6465D7E 98BDA89456F340B108 98BDA8 9456F 07D07340B108
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A08 0180A03B0A766EA03F0740521067039073403306 A98000076069766EA5B6465D7E 98BDA89456F340B108 0BA0B07D07340B108
Elle contient: 221 caractères
Par exemple, un autre remplacement est possible avec la chaîne commençant à la position 198 (adresse: C5), qui est repétée à la position 215.
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A08 0180A03B0A766EA03F0740521067039073403306 A98000076069766EA5B6465D7E98BDA89456F 340B1080BA0B07D07 340B10 8
Notre chaîne devient:
215AB87F67E454CD0020633DEA980FFFF6783458 778776576DB01C06E66018090FFFF3CD5AB8700E 1301C003A0705307B70390CF333DEA0000901A08 0180A03B0A766EA03F0740521067039073403306 A98000076069766EA5B6465D7E98BDA89456F 340B1080BA0B07D07 0C507
Elle contient: 219 caractères

Page made by Nicolas Delerue