Rechercher des séquences

[Yann]

Une des bases de la compression LZ, c'est de trouver des séquences identiques, appelées 'matches', afin de s'y référer en donnant une instruction du genre "va à tel endroit et copie N octets", ce qui est plus court que les N octets en question.

Ce principe simple peut être étudié et affiné par plusieurs angles.
Nous allons aujourd'hui nous intéresser à la première question : comment trouver les séquences identiques ?

En général, on essaie de trouver la séquence la plus longue possible.
Par exemple, si on doit coder "ménageries", on préférera utiliser comme référence "ménagerie" plutôt que "ménage" seulement. L'intérêt est de compresser davantage.
Il peut y avoir des exceptions; par exemple, si "ménage" est proche, décrire son emplacement peut finalement être moins coûteux que d'aller chercher "ménagerie" très très loin en arrière. Mais pour la simplification de cet article, nous allons ignorer cette subtilité.
L'objectif, pour l'instant, est donc de trouver la plus longue chaîne de caractères identique.

Une méthode naïve consiste à tester toutes les positions précédentes une par une, jusqu'à trouver la chaîne la plus longue. Cela fonctionne, mais le coût en temps de calcul est totalement prohibitif. Même un processeur moderne sera lent avec seulement quelques kilo octets de données.

Un dérivé de cette méthode consiste à accélérer la recherche, en ne testant que les positions les plus susceptibles d'être intéressantes. Par exemple, au lieu de tester toutes les positions précédentes, nous n'allons tester que les positions commençant par "m".
C'est simple, et le gain de performance est massif. La recherche ira 10 fois plus vite au bas mot.

Le principe : on a une première table, qui indique où trouver le premier "m" précédent. Ensuite, on a une seconde table, avec autant de cases que de caractères à rechercher. A chaque position de "m", on indique la position du précédent "m", et ainsi on peut tous les parcourir jusqu'au dernier.

Et on peut aller encore plus loin : si on décide de ne s'intéresser qu'au matchs de 2 octets minimum, alors on ne s'intéressera qu'aux positions commençant par "mé". La première table, recensant tous les couples de caractères, sera alors plus grande (2 octets = 65536 possibilités). En revanche, la recherche sera beaucoup plus rapide, puisqu'il n'y a aucun risque de tester un "ma" ou un "mX" par exemple.

Et ainsi de suite, on peut ne s'intéresser qu'aux séquences de 3 caractères minimum, soit 16 millions de possibilités, ou même de 4 caractères minimum, soit 4 milliards de combinaisons possibles.
On comprend très vite que cette première table peut coûter trop cher en mémoire. Heureusement il y a des solutions :
1) La méthode simple : on se contente d'une table plus petite (par exemple ne recensant que les 2 premiers octets), sachant qu'on fera alors trop de vérifications. Cela coûtera plus de temps, mais on économisera de la mémoire.
2) Plus subtil, on utilise un "hash", une méthode de calcul qui permet de transformer de façon garantie une séquence en une autre (mais pas l'opération inverse). Ainsi, on peut garantir qu'à une séquence de 4 octets quelconque correspond un code compris entre 0 et 65535 (16 bits). On obtient alors la même consommation mémoire que pour deux caractères, au prix d'un calcul (le "hash") supplémentaire.

La grande différence, ce sont les "collisions", c'est à dire deux séquences initiales différentes mais qui démarrent par le même code, et donc parcourent la même chaîne.
Pour la première méthode, "ména" et "méle" sont équivalents, car ils partagent les mêmes deux premiers caractères. Pour la seconde méthode, on ignore à priori quels sont les séquences partageant le même code (tout dépend de la formule mathématique du hash), mais il s'agira typiquement de deux séquences complètement différentes (comme "ména" et "souc" par exemple) alors que deux séquences voisines ont beaucoup moins de chances de partager le même code.

Dans la pratique, la seconde méthode est la plus performante, et de loin, ainsi que la plus flexible.
Avec une bonne dispersion, on approche la perfection en terme d'occupation des cases, alors qu'en "tronquant", on aura des cases vides ("zz" par exemple) et d'autres qui seront bien trop sollicitées.
On peut aussi dimensionner le tableau final très précisément (par exemple, en garantissant un résultat sur 14 bits, soit 16384 possibilités).
Au final, la dispersion par "hash" donne d'excellents résultats, avec des vitesses de recherche particulièrement accélérées et pour un coût mémoire contrôlable (plus on alloue de mémoire, plus c'est rapide, aux effets du cache prêt).

Voilà qui semble résoudre le problème pour la première table. Il n'en va hélas pas de même pour la seconde.

Pour chaîner les positions à comparer, on va indiquer les transitions avec un pointeur (ou un index) qui prend typiquement 4 octets. Donc, pour chercher les N positions précédentes, il faudra 4xN octets de mémoire.
Par exemple, pour chercher dans les 512 Mega-octets précédents, il faudrait 2 Giga octets de mémoire, rien que pour la seconde table. C'est prohibitif, et en général, il n'est pas possible d'utiliser autant de mémoire.

Par conséquent, la capacité de recherche est limitée par la mémoire disponible. En gros, et si on néglige la première table, elle est égale à la mémoire disponible, divisée par 5 (les données elle-même, plus la seconde table).

Conclusion

Nous pouvons nous arrêter là pour faire un bilan de ce billet.
La méthode présentée comporte un avantage gigantesque par rapport à la méthode naïve, en accélérant considérablement la recherche de la chaîne identique la plus longue.
Toutefois, elle comporte des limitations assez fortes :
1) On ne peut pas rechercher très loin en arrière, tout dépend de la mémoire disponible !
Ainsi, si on ne dispose que de 1 MegaOctet de mémoire, on sera typiquement limité à une recherche sur 128 KiloOctets.
2) Bien que très accélérée, la méthode par "hash" continue de nous faire tester des positions inutiles
Le nombre de comparaisons peut rester très important, et ceci pour deux raisons.

Tout d'abord, si on est économe sur la première table, alors il y aura de nombreuses collisions, et donc beaucoup de séquences différentes associées à la même chaîne. Par exemple, si on recherche sur les 16 millions précédentes positions, avec un hash de seulement 16 bits, on fera en moyenne 256 comparaisons par recherche. C'est énorme.
On peut mitiger cet effet en fabriquant une première table beaucoup plus grande, par exemple d'environ la même taille que la seconde table. On a alors l'impression qu'on aura en moyenne une comparaison par recherche. La réalité est malheureusement plus compliquée.

Ensuite, notre seul facteur discriminant, c'est le début de la séquence (par exemple les 4 premiers octets). Mais supposons que je trouve une première séquence avec 6 octets identiques, alors je vais devoir continuer à tester toutes les autres positions comportant 4 octets identiques, alors qu'en théorie, je ne devrais être intéressé que par celles qui ont au moins 7 octets identiques, d'où une perte de temps.

Ces deux effets, l'un limitant la profondeur de recherche, l'autre diminuant les performances de la recherche, peuvent être étudiés plus précisément. On constate toutefois qu'il y a des liens assez forts : plus on a de mémoire, plus on peut rechercher loin et vite. L'idée directrice est donc de faire le meilleur usage possible de cette mémoire, en choisissant les meilleurs compromis.