Rechercher des séquences (2)

Sur le précédent billet, nous avons vu que pour rechercher des séquences identiques, il est préférable de préparer la recherche en chaînant les bonnes positions, ce qui améliore les performances d'un facteur 100 voire 1000.
Malgré ces gains plutôt impressionnants, il reste possible d'identifier des sources d'inefficacités, et donc des pistes d'amélioration. Nous allons donc étudier ces pistes, par niveau de difficulté croissant.

Commençons par l'une des plus évidentes : lorsqu'on chaîne les bonnes positions sur la base d'un "hash", alors deux séquences différentes mais produisant un hash identique parcourront la même chaîne. Lors d'une recherche sur une de ces chaînes, nous allons donc "tester" des positions inutiles, car appartenant à l'autre séquence.

Première solution
La première réponse à ce problème, c'est le "brute force" : nous allons créer un hash très long, de façon à diminuer les probabilités que deux séquences différentes produisent un même hash. Et cela fonctionne plutôt bien : avec une formule hash bien dispersante, lorsqu'on multiplie par deux la table des hash (et donc le nombre de chaînes gérées), on divise en gros par deux le nombre de collisions.

Il y a bien entendu une limite à cet exercice.
Tout d'abord, si le hash a la même taille que la séquence initiale, alors le hash ne sert plus à rien; autant utiliser directement la séquence, et il n'y a plus aucune collision. Malheureusement, comme nous l'avons vu, cela n'est en général pas possible : si la séquence est longue (4 caractères par exemple), alors il faut trop de mémoire (16Go pour cet exemple).
Le hash a donc nécessairement une taille plus petite que la séquence, et par conséquent, il est mathématiquement impossible de garantir l'absence de collisions. Nous ne pouvons qu'espérer que celles-ci seront suffisamment rares pour ne pas trop impacter la vitesse de recherche.

Empiriquement, et intuitivement, un nombre de collisions "suffisamment bas" est à peu près atteint lorsque le nombre de hash est supérieur ou égal au nombre de positions à tester. Hé oui, en moyenne, nous aurons alors un seul test par recherche.
Bien entendu, ce n'est qu'une moyenne mathématique, et nous verrons dans un autre billet que la réalité est assez différente, du fait même des propriétés de redondance des fichiers à compresser. Mais gardons pour l'instant ce résultat.

Par conséquent, la taille de la table de hash devient non négligeable, et impacte significativement le budget mémoire total.
Reprenons l'exemple d'un buget mémoire de 1Mo.
Nous avons vu dans un précédent billet que la table des "positions chaînées" est égale à 4x le nombre de positions à comparer.
Donc si cette table "principale" fait un maximum de 512Ko, alors nous recherchons parmi les 512/4=128Ko précédents.
Il reste alors 384Ko de mémoire, soit un maximum de 256Ko pour la table de hash (65536 hash possibles, soit 16 bits).

C'est en général suffisant, mais nous pourrions privilégier la table de hash pour limiter les collisions, en lui attribuant 512Ko (soit 17 bits), ce qui du même coup diminue la mémoire disponible pour la table des chaînes (qui prendra 256Ko) et donc la profondeur de recherche (256/4=64Ko). On comprends donc rapidement qu'il ne faut pas trop abuser sur la table des hash, sous peine de réduire significativement la distance de recherche, qui est un critère important pour obtenir une bonne compression.

Pour résumer : grandir la table des hash pour limiter les collisions est une méthode simple et efficace, mais coûteuse en mémoire.


Seconde solution

Toutefois, la première solution ne peut pas atteindre la perfection : statistiquement, il restera quelques collisions de ci de là.
On peut résoudre ce problème en faisant intervenir une troisième table.

L'idée, c'est qu'une fois qu'on atteint une position de "hash", on peut ensuite vérifier la séquence source.
Si elle correspond, tout va bien, on est bien seul sur la chaîne.
Si elle ne correspond pas, il y a alors collision.
On peut utiliser une troisième table pour recenser les séquences produisant des hash identiques, puis attribuer à chaque séquence différente un début de chaîne différent. Nous aurons alors, rigoureusement, autant de chaînes que de séquences différentes, donc aucune collision.
(Note : au maximum, il y a autant de chaînes que de positions à tester, ce qui dans ce cas signifie que c'est incompressible).

Cela semble résoudre notre problème de collision. Mais il y a un hic.
Pour quelle raison essayons-nous de réduire le nombre de collisions ? Rappelons-nous, c'est seulement pour augmenter la vitesse de la recherche.

Nous avons donc ici une méthode qui réduit les collisions à zéro, mais qui malheureusement a aussi un coût de gestion non négligeable.

En effet, avec une table de hash "simple", la procédure est très simple :
il suffit de calculer le hash, regarder dans la table la position du précédent hash, puis démarrer la comparaison à cette position.
L'update est également simple : lorsqu'on ajoute une nouvelle séquence à la table, on calcule le hash, remplace le pointeur dans la table de hash, et ajoute une valeur dans la table des chaîne.

Désormais, c'est plus compliqué :
- Pour rechercher : on calcule le hash, on recherche dans la table de hash la séquence source et on la compare. Si elle correspond, tout va bien, on va lire le pointeur et on démarre la recherche. Par conséquent, nous avons eu une comparaison supplémentaire. Mais c'est le meilleur cas...
Si les séquences sont différentes, alors il faut vérifier s'il y a d'autres séquences enregistrées avec le même hash.
Il faut alors parcourir la liste des séquences, ce qui pose la question de la structure de données qui les enregistre, car ce nombre de séquences est variable d'un hash à l'autre. Pour l'instant nous allons simplifier le problème en prétendant qu'il s'agit d'une liste. Nous allons donc parcourir les éléments de la liste un à un, ce qui introduit la lecture d'un pointeur, le renvoi vers la cellule suivante, la comparaison de la séquence source, et ainsi de suite, jusqu'à avoir trouvé la bonne séquence, ou avoir parcouru toutes les séquences.
De façon intuitive, ce nouveau procédé est sérieusement plus long. Il dépend surtout de la taille moyenne des chaînes, qui peut toutefois être assez courte si le nombre de hash est élevé (voir solution 1).

- Pour l'update : malheureusement, la difficulté n'est pas seulement sur la recherche, elle est aussi et surtout sur la mise à jour de la table.
Le départ est le même : recherche dans la table de hash de la première séquence, comparaison, et si tout va bien, on met à jour la table de hash et la table des chaînes. Ça c'est le cas favorable...
Si les séquences sont différentes, il faut parcourir la liste de toutes les séquences, jusqu'à trouver la bonne, puis mettre à jour.
S'il n'y a aucune séquence correspondante, il faut en ajouter une à la liste.

Cet algorithme est compréhensible, et semble déjà bien coûteux, mais des questions supplémentaires se posent :
- Pour des questions de performance, on peut souhaiter mettre en début de chaîne les séquences les plus probables, pour que les recherches soient statistiquement plus rapides. Ceci introduit une notion de ré-ordonnancement des éléments.
- En ne faisant qu'agrandir les chaînes, on finit par consommer de plus en plus de mémoire, jusqu'à éventuellement dépasser un budget. Hors, parmi ces séquences sauvegardées, certaines sont peut être déjà "sorties" de la fenêtre de comparaison. Il serait donc bon de les "nettoyer" pour économiser de l'espace, ce qui pose toutefois la question du recyclage des positions libérées. Ceci peut amener à la création d'un "garbage collector", ce qui devient assez lourd.
- Malgré le nettoyage, les contraintes mémoires peuvent être telles qu'il n'y a pas assez de place pour conserver toutes les séquences différentes. Il faut alors choisir celles qui seront "éliminées" bien que valides. On peut également les fusionner pour éviter de les perdre, au prix d'une collision, mais cela rend la structure de données encore plus compliquée.
- Tous ces pointeurs coûtent de la mémoire ! A budget mémoire identique, au sauvegardera moins de positions avec des séquences chaînées qu'avec seulement une table de hash ! Du coup, on peut se demander s'il n'est pas préférable, tout simplement, d'augmenter la taille de la table des hash...


Pour toutes ces raisons, je n'ai jamais implémenté cette méthode dans mes compresseurs. Sans l'avoir codé, il m'est impossible de parler par expérience; on peut juste dire que, intuitivement, compte tenu de l'importance des problèmes mentionnés, cette méthode plus complexe a de sérieux risques d'être en définitive bien plus lente que la simple table de hash, et ceci malgré les collisions supplémentaires.

Elle est toutefois intéressante à présenter car elle introduit une nouvelle structure de recherche qui peut être fouillée davantage.

Un coup plus loin

En effet, l'un des principaux problèmes de la méthode "hash", c'est son principe de fonctionnement même : repérer la liste des positions démarrant par un même préfixe. Hors cette liste peut être très longue si ce préfixe est très fréquent. On peut donc être amené à faire beaucoup de comparaisons, et ceci même en l'absence de collision.
En fait, une fois le nombre de "collisions" (séquences différentes) raisonnablement bas, ce n'est plus vraiment la peine d'essayer de gagner les quelques % supplémentaires. Le vrai problème vient des préfixes fréquents (par exemple, une longue liste de zéros). Et plus la fenêtre à rechercher est grande, plus le nombre de comparaisons augmente. Si la fenêtre de comparaison est très grande (100Mo par exemple), cela devient prohibitif, et la vitesse de compression pâtira considérablement de ce nombre trop important de comparaisons.

L'idée serait donc d'aller plus loin dans la méthode de recherche.

Ainsi, si la première question reste :
"y a-t-il une séquence d'au moins 4 caractères qui est identique",
si la réponse est oui, la seconde question devrait être :
"y a-t-il une séquence d'au moins 5 caractères qui est identique"
et ainsi de suite. Au lieu de cela, ce que nous obtenons est plutôt :
"donne moi la liste de toutes les séquences démarrant par ces 4 caractères",
qui est le résultat de la chaîne. La chaîne impose donc le test de nombreuses positions inutiles dès lors qu'on a répondu à la première question.

Cette nouvelle façon de procéder impose une nouvelle structure de recherche, très différente.
Nous en ferons le thème d'un prochain billet.