Double indexation

[Yann]

Passons désormais aux choses sérieuses. Comment accélérer les recherches, maintenant qu'on a bien investigué les limites de la chaîne de hash.
La première idée que nous allons étudier est aussi la plus simple à concevoir : la double chaîne, aussi appelée double indexation.

Le principe est très simple : on garde la première chaîne de hash, traditionnelle, non modifiée.
Simplement, dès qu'on a atteint un certain seuil, nous passons sur la seconde chaîne.

Pour l'exemple, nous prendrons comme seuil 5 octets.
Au début, c'est comme d'habitude : on calcule le hash de la séquence minimale, on cherche la précédente occurrence dans la table de hash, et c'est parti, on pointe sur la première position de la chaîne, et on déduit ainsi toutes les occurrences précédentes.

La différence intervient lorsque le seuil minimal (5 octets) est atteint. On passe alors sur la seconde chaîne. Celle-ci est également indexée sur la position dans le buffer, donc il y a correspondance immédiate. Puis on complète le lien avec la position courante.
Ce comportement est décrit sur le schéma suivant :



L'avantage évident, c'est que dès qu'on embraye sur la seconde chaîne, on teste beaucoup moins de positions. Par conséquent, on diminue notablement le nombre de comparaisons à effectuer.
De plus, en garantissant que toutes les positions de la chaîne ont au moins les 5 premiers octets identiques, on n'a plus qu'à comparer à partir du 6e.

Toutefois, il y a aussi des coûts.
Tout d'abord, il y a deux chaînes à mettre à jour désormais. Si dans le cas d'une recherche, cette mise à jour est à peu près naturelle, elle n'en est pas gratuite pour autant. Plus embêtant, lorsqu'on ajoute des positions qui ne sont pas pas recherchées (typiquement à l'intérieur d'une séquence "match"), le coût de la mise à jour devient sérieux. En effet, pour assurer la complétude de la seconde chaîne, il faut rechercher la prochaine séquence qui a au moins 5 octets identiques avec la position courante. Une sorte de mini-recherche, mais uniquement pour mettre à jour la table.
De plus, deux chaînes coûtent deux fois plus de mémoire. Puisqu'il faut 4 fois la taille de la fenêtre de recherche pour une seule chaîne, cela nous fait désormais 8 fois (soit, par exemple 128Mo pour une recherche sur 16Mo), auxquels il faut toujours ajouter la table de Hash initiale.
C'est beaucoup, mais la bonne nouvelle, c'est que c'est prédictible.

L'idée suivante serait de comparer les performances de cette structure avec l'algorithme de recherche classique à une seule chaîne.