Accélérer la recherche

[Yann]

Nous avons vu dans un précédent billet que baser les recherches sur une chaîne de préfixes ne suffisait pas pour obtenir des performances décentes lorsque la profondeur de recherche devient importante.

Ainsi, pour une profondeur de 512K, on converge vers 960 comparaisons par recherche pour calgary, qui est un cas défavorable, ou 160 comparaisons par recherche pour enwik8, qui est un cas très favorable.
C'est bien entendu beaucoup trop, et nous n'en sommes qu'à 512K. Que se passera-t-il pour des profondeurs de recherche énormes ? J'ai bien essayé de tester avec 8M, mais les temps de compression sont tellement longs qu'il faut un bon quart d'heure par fichier. Inacceptable.

Notez, à contrario, que lorsque la profondeur de recherche est faible, il n'y a pas vraiment de problème.
Ainsi, avec une profondeur de 4K, on converge vers 23 recherches pour le cas défavorable, et 4 recherches pour le cas favorable. C'est très bon, et il n'y a pas matière à en vouloir davantage.
C'est donc un premier résultat important : nous ne sommes intéressés par une méthode rapide que pour des profondeurs de recherche importantes.

Première solution : la limite

La première solution est on ne peut plus simple : on va introduire un compteur, qui limite le nombre de comparaisons. Ainsi, on s'arrêtera à la comparaison numéro N, et on ne continuera pas plus loin.
Nous nous dirigeons donc vers une recherche imparfaite, qui ne garanti pas de trouver la meilleure compression, mais garanti les performances. C'est la méthode employée par "zip".

On peut alors se demander quel serait le bon seuil. Et bien il n'y a pas de solution unique. Tout est affaire de compromis. Plus la limite sera élevée, plus nous aurons de chances de trouver la meilleure séquence identique. Sinon, nous aurons tout simplement une séquence "moins bonne".
Pour préparer le terrain, j'ai mesuré le nombre moyen de comparaisons nécessaire pour trouver la meilleure séquence. On obtient le graphe suivant :



La forme de la courbe est identique aux précédentes, avec un plateau à peu près atteint vers 16 bits.
Mais notez les valeurs absolues : elles sont bien moindres. Pour Calgary, nous avions 960 comparaisons en moyenne par recherche, mais nous atteignons la meilleure solution en moyenne en 100 comparaisons seulement. Donc, si nous fixons la limite à 100 comparaisons par recherche, nous avons des chances raisonnables de trouver une grande partie des meilleures séquences. Les autres seront moins optimales, ce qui résultera en un taux de compression inférieur.

Notez que ce nombre de comparaisons moyen pour atteindre la meilleure séquence dépend du fichier à compresser.
De plus, on s'en doute, ce nombre dépend aussi de la fenêtre de recherche (512K sur le graphe).

Voilà qui ne va pas nous aider à fixer le meilleur seuil possible.
Dans la pratique, nous avons là une des explications du fameux "niveau de compression" de "Zip" : plus le niveau est élevé, plus il compare. C'est une façon de laisser l'utilisateur en charge de ce paramètre.

Seconde solution : la table de hash 2D

Un raffinement de la méthode précédente consiste à dire : puisque nous avons, de toutes façon, limité le nombre de comparaisons à "N", alors toutes les autres positions de la table des chaîne ne servent à rien, puisqu'elles ne seront jamais parcourues.
Autant, dans ce cas, ne créer qu'une seule table, la "table des hash", qui désormais contiendra des lignes.

Oui, des lignes de hash. C'est stupéfiant, je sais...

La taille des lignes sera tout simplement égale au nombre maximal de comparaisons autorisé. L'effet en terme d'efficacité de la recherche sera donc exactement le même qu'avec une limite. En revanche, la quantité de mémoire consommée sera très différente.


Exemple avec 64K :

1) Ring Chain : 64K x 4 = 256K; Hash : 15bits = 32K x 4 = 128K; total : 384K
Valable pour toute limite au nombre de comparaisons.

2) Hash : 15bits = 32K x 4 = 128K;
Nombre de comparaisons 4 => 512K
Nombre de comparaisons 8 => 1M
Nombre de comparaisons 16 => 2M


Exemple avec 512K :

1) Ring Chain : 512K x 4 = 2M; Hash : 16bits = 64K x 4 = 256K; total : 2.25M
Valable pour toute limite au nombre de comparaisons.

2) Hash : 16bits = 64K x 4 = 256K;
Nombre de comparaisons 8 => 2M
Nombre de comparaisons 16 => 4M
Nombre de comparaisons 32 => 8M


Exemple avec 8M :

1) Ring Chain : 8M x 4 = 32M; Hash : 17bits = 128K x 4 = 512K; total : 32.5M
Valable pour toute limite au nombre de comparaisons.

2) Hash : 17bits = 128K x 4 = 512K;
Nombre de comparaisons 16 => 8M
Nombre de comparaisons 32 => 16M
Nombre de comparaisons 64 => 32M


Conclusion

On le constate, le budget mémoire de la méthode par "chaîne" augmente principalement avec la fenêtre de recherche.
Il est donc borné et relativement faible si la fenêtre est courte, mais explose pour des fenêtres importantes.

De l'autre côté, la méthode par table hash 2D augmente essentiellement avec le nombre de comparaisons (nous l'avons vu précédemment, la taille optimale du hash n'augmente que très peu avec la taille de la fenêtre de recherche). C'est donc un meilleur choix lorsque la fenêtre est grande et le nombre de comparaisons faible.

Dans la pratique, la "chaîne" est préférée aussi pour sa flexibilité : en effet, on peut modifier le nombre de comparaisons optimal à tout moment, c'est juste une limite, la chaîne elle-même reste toujours la même.

De son côté, la table 2D a un autre avantage : sa rapidité. En effet, en raison de la latence d'accès mémoire, il est plus rapide d'accéder à une seule ligne d'une table que de chaîner de multiples positions non adjacentes.

Nous analyserons tout ceci plus en détail dans de prochains billets.