L'autre limite

[Yann]

J'ai failli oublier, il existe une autre façon de définir une limite de recherche qui est très populaire; alors, avant de passer à plus compliqué, nous allons terminer ce sujet sur un dernier billet.

Nous avons défini une limite en "nombre de recherches maximal". Il est également possible de définir un "nombre d'octets répétés maximal" ou suffisant.
L'idée est la suivante : une fois qu'on a trouvé un nombre d'octets égal ou supérieur à la limite, on arrête la recherche et on passe à la suivante.

Cette idée est très populaire, car elle correspond à des restrictions usuelles dans les algorithmes de compression "historiques".
Tout d'abord, il est fréquent que le format de description des "match" soit limité à une longueur maximale. C'est d'ailleurs le cas même d'algorithmes LZ77 modernes, tels que 7zip, qui est limité à 273 si ma mémoire est bonne. Pour ces formats, il est "naturel" d'arrêter la recherche une fois que la longueur maximale est atteinte.
Plus complexe, l'usage de la longueur comme limite permet d'éviter l'usage d'un compteur de comparaisons, soit une variable de moins. Dans certaines architectures processeur, notamment les plus anciens, limiter le nombre de variables pour travailler exclusivement sur les registres permet de gagner sur les performances.
Toutefois, sur les processeurs PC modernes, on a beaucoup d'autres facteurs de perte de performance, l'absence de compteur n'est
donc pas une source notable d'amélioration.

LZ4 n'ayant aucune restriction sur son format de longueurs (il peut décrire des longueurs infinies), la question est ouverte pour sélectionner la meilleure méthode limite. Idéalement, la meilleure solution doit compresser mieux et plus vite que sa compétitrice.

De fait, il y a bien un vainqueur. L'équivalent en compression de maxSearch=256 est maxLength=32 (trouvé empiriquement).
En compétition frontale, les deux méthodes obtiennent pratiquement les mêmes taux de compression, mais maxSearch est nettement plus rapide.

	Compression Ratio	Speed	Decoding
LZ4OC (maxSearch=256)	2.339	28.8 MB/s	796 MB/s
LZ4 maxLength=32	2.338	10.4 MB/s	794 MB/s
LZ4HC (no limit)	2.345	2.3 MB/s	808 MB/s