Réordonner les textes pour optimiser la compression de leur index
Jouer sur l’ordre des textes pour une meilleure compression ? C’est ce qu’ont récemment démontré Eric Rivals, directeur de recherche au Laboratoire d’informatique, de robotique et de microélectronique de Montpellier (LIRMM - CNRS/Université de Montpellier) et Bastien Cazaux, post-doctorant à l’Université d’Helsinki.
Chercher un mot dans un livre : rédhibitoire sans un index ! Imaginez : vous cherchez le mot "imagine" sans index. Vous devez passer en revue tous les blocs de 7 lettres possibles jusqu'à en trouver un qui contienne "imagine", puis recommencer cette procédure pour trouver l'occurrence suivante, et ainsi jusqu'à la fin du livre. C'est l'équivalent de la fonction "Rechercher" que vous utilisez sur votre navigateur ou traitement de texte préféré (vous savez le "Ctrl+F"). Nécessairement, cela prend un temps proportionnel au nombre de blocs possibles, c’est-à-dire au nombre de caractères du livre.
Maintenant, changeons de dimension : comment chercher un mot dans l'ensemble des documents de la Bibliothèque Nationale de France (BNF) ? ou de Wikipedia ? Dans le cas de ces gigantesques bases de textes, l’algorithme du Ctrl+F devient trop lent. Impensable sans index. En informatique, on fabrique des index, ou structures d'indexation, qui, stockés dans la mémoire de l'ordinateur, permettent d'accélérer toute recherche de mot. Heureusement, en algorithmique du texte, on connaît de bonnes structures d'indexation, rapide à construire, compacte et efficace, par exemple l'arbre des suffixes défini depuis 40 ans. Mais lorsque le volume de documents est immense, l'index peut devenir trop volumineux pour la mémoire à disposition. On est face à une question dite de "passage à l'échelle" : jusqu'à quel volume cela peut-il fonctionner ?
Depuis les années 2000, on conçoit et utilise des structures d'indexation qui peuvent être compressées (comme lorsque vous compressez vos fichiers sur votre disque dur) et donc occuper moins de mémoire. Pour cela, la structure la plus utilisée est la Transformée de Burrows Wheeler (BWT). Dans le cas de la BNF ou de Wikipedia, chaque document est un texte séparé des autres. Une question algorithmique surgit : peut-on jouer sur l'ordre des documents pour optimiser la compression de l'index ? Récemment, Bastien Cazaux et Eric Rivals (respectivement de l'Université Helsinki en Finlande et du LIRMM à Montpellier) ont trouvé le premier algorithme pour calculer l'ordre des documents qui engendrera la plus forte compression de l'index (pour la BWT avec une méthode classique de compression). Cet algorithme est suffisamment efficace pour repousser les limites actuelles de l'indexation. On peut donc envisager d'indexer des collections plus volumineuses grâce à cet algorithme, par exemple pour créer un serveur web qui offre une fonction de recherche sur la collection de la BNF ou de Wikipedia. Mais pas seulement : les outils de fouilles de données ou d'apprentissage automatique utilisent à grande échelle ce type de fonction de recherche (on parle aussi de "requête") pour analyser des corpus de textes de plus en plus volumineux. Eux aussi pourront s'attaquer à des volumes plus importants qu'avant, d'autant plus que les structures d'indexation visées permettent aussi des recherches plus complexes (recherches avec erreur, recherches de paires, etc.) ou facilitent le calcul de statistiques sur le vocabulaire utilisé. Elles sont déjà très exploitées en bioinformatique pour indexer des séquences de génomes complets ou de collections de génomes et y rechercher à loisir des séquences d'intérêt (par centaines de millions).
Publication :
Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding
Bastien Cazaux1 , Eric Rivals2 dans Combinatorial Pattern Matching, 2019