Recherches en grandes profondeurs (2)

Bon, allez, voici la solution de l'énigme d'hier.

Nous avons vu qu'en augmentant le nombre de comparaisons par recherche, on améliore le taux de compression, alors que paradoxalement, on n'augmente pas (ou très peu) le nombre d'octets qui sont répétés, ce qui est pourtant le coeur du principe de compression LZ77.

L'explication est la suivante : l'objectif premier, lorsqu'on augmente le nombre de comparaisons, c'est de trouver des "matchs", c'est à dire des séquences identiques, plus longs. Ça marche très bien : plus on compare, plus on a de probabilité de dénicher un "match" encore plus long.
Puisque nous avons des séquences répétées plus longues, mais que le nombre total d'octets répétés ne change (presque) pas, c'est que nous avons moins de séquences répétées.
Tout simplement.

Avec moins de séquences à répéter, il y a moins d'ordres de copies, ce qui résulte en un fichier compressé plus petit.
Il est plus efficace de dire une seule fois "va copier 20 octets" que de dire deux fois "va copier 10 octets". On aura adressé la même quantité de données, en les décrivant avec un seul ordre de copie, qui occupe pratiquement deux fois moins de place que deux ordres de copies.

Voilà donc la principale source d'amélioration de la compression. Notez qu'on gagne aussi un petit peu de données répétées jusque vers 4 comparaisons, mais après, seul l'allongement des matchs compte.

Afin de mieux mesurer cet impact, j'ai créé un graphique, qui mesure la taille moyenne des matchs en fonction du nombre maximum de comparaisons autorisé. En voici le résultat :



Voilà qui est plus parlant, nous avons en effet une augmentation bien visible de la taille moyenne de matchs, ce qui se traduit par une amélioration quasiment proportionnelle de la compression (ce sera la thème d'un prochain billet).

Que constatons-nous ? Tout d'abord l'amélioration est très progressive, avec des gains très marqués jusque vers 32 comparaisons, puis un rendement de moins en moins bon. La courbe est similaire sur les trois fichiers, avec toutefois des proportions d'amélioration qui varient grandement, firefox gagnant peu, mais enwik8 faisant des progrès étonnants.

On constate qu'un plateau est à peu près atteint aux alentours de 512 comparaisons, les gains suivants étant moins importants. C'est donc une quantité de comparaison qui reste très importante, ce qui affecte d'une part les performances que l'on peut atteindre, et d'autres part remet en question l'idée d'un précédent billet sur une table "2D", qui n'est efficace que pour un nombre de comparaisons faible (16 par exemple).

Toutefois, même avec des valeurs importantes (comme 512), les temps de compression sont grandement améliorés. A tel point d'ailleurs qu'il devient possible de faire des tests avec une fenêtre de recherche de 8M, ce qui était inenvisageable avec la précédente méthode de recherche complète.
Voici les résultats :



La courbe est similaire, mais les améliorations vont beaucoup plus loin. La plus impressionnante est sans conteste enwik8, qui parvient même à chipper la deuxième place à firefox. On constate ici que si on veut atteindre le palier optimal, il faut monter jusqu'à 2048 comparaisons ! C'est beaucoup, la vitesse de compression en devient très lente.

Il y a autre chose d'intéressant sur cette courbe : regardez les premières valeurs (1, 2 et 4 comparaisons).
Oui elles ressemblent beaucoup à celles du graphique 512K.
D'ailleurs, si nous faisons une comparaison directe, nous obtenons ceci :



Très intéressant ce graphique, puisqu'on mesure nettement les progrès en fonction des tailles de fenêtre.
Tout d'abord, les débuts de courbe sont à peu près communs. C'est logique, cela signifie que la très grande majorité des premiers matches valides (4 caractères identiques) se trouvent à courte distance, dans les premiers 64K.
Ensuite, lorsqu'on augmente le nombre de comparaisons, la courbe 64K est la première à décrocher (vers 4 comparaisons), puis la courbe 512K (vers 16 comparaisons). Ces courbes convergent vers des valeurs nettement différentes en fonction de la taille de la fenêtre : plus la fenêtre est grande, plus la taille moyenne des matches est importante, mais pour pouvoir en bénéficier, il faut davantage de comparaisons.
Enfin, on peut noter des différences assez sensibles de comportement en fonction des fichiers, certains bénéficiant plus que d'autres de l'augmentation des tailles de fenêtre ou du nombre de comparaisons.

Tous ces résultats sont conformes à l'intuition. Toutefois, ils permettent aussi de fixer des ordres de grandeur plus précis.
Ainsi, le nombre de comparaisons "optimal" dépend un peu du fichier, mais surtout de la taille de la fenêtre. Plus important encore, ce nombre est très grand si on souhaite atteindre le "palier" de performance, au delà duquel les gains deviennent faibles.

Cette méthode permet d’améliorer sérieusement la vitesse de compression, surtout dans les cas auparavant défavorables.
L'amélioration est telle qu'elle permet d'envisager l'usage de fenêtres de recherche très grandes.
Toutefois, on ne peut pas dire qu'on obtient là une solution suffisamment satisfaisante, car il faut quand même un nombre de comparaisons très important pour obtenir une compression "optimale", c'est à dire proche de ce que la taille de la fenêtre peut offrir.

Je souhaite trouver une méthode de recherche qui, en quelques essais seulement, donne le meilleur match possible, ou statistiquement très proche. Nous en sommes encore très loin. Il va donc nous falloir changer de méthode...