Recherches en grandes profondeurs

[Yann]

Tiens, je regarderais bien le grand bleu tout à coup...

L'étape logique après le billet sur l'accélération des recherches consiste à trouver la limite optimale, si elle existe, préservant l'essentiel de la compression, mais évitant les défauts d'une recherche complète qui peut entrer dans des boucles vertigineuses.

Attention, les choses sérieuses commencent.

La première question à se poser, c'est si une telle limite existe. En effet, puisque nous avons vu qu'en fonction des fichiers, le nombre moyen de recherches pour trouver la meilleure séquence varie considérablement, on peut s'attendre à ce que la limite idéale dépende du fichier, ce qui serait un handicap important. Le réflexe serait donc de prendre une limite "assez haute", couvrant l'essentiel des situations, mais coûtant plus de temps de calcul que nécessaire.
L'autre résultat important de cette étude, c'est de savoir si l'approche en "tableau 2D" est viable, sachant qu'elle ne devient avantageuse que si le nombre de comparaisons est (relativement) faible.

Pour fixer les idées, j'ai commencé par mesurer le nombre d'octets "répétés" pour chaque fichier. Il ne s'agit pas à proprement parler d'un taux de compression, qui combine plusieurs mécanismes, mais c'est assez significatif de l'efficacité de la recherche.
On obtient alors le graphique suivant :



La première chose qui marque, c'est le niveau d'efficacité de la recherche dès la première tentative. En effet, même avec une seule comparaison par recherche, on trouve la presque totalité des octets que l'on peut "répéter" !
Ce résultat est tout à fait bluffant, et prouve l'efficacité de la recherche par Hash.
Ce principe est d'ailleurs employé par "LZ4".

En seulement 4 comparaisons, on arrive à un résultat proche de la limite. Puis vers 16 comparaisons, il n'y a pratiquement plus de progrès.
Le plus important, c'est que si on prend pour référence le résultat obtenu avec une seule comparaison, on n'a pratiquement pas progressé, entre 1% et 3% seulement.
Hors, il y a bel et bien une différence de compression importante entre "LZ4" (une seule comparaison) et "LZ4HC" (pas de limite). Celle-ci ne peut donc en aucun cas s'expliquer par la quantité de données répétées.

Il faut donc trouver une autre explication à l'amélioration visible de la compression.