Posté par Adrien le Mercredi 11/09/2019 à 08:00
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 Cazaux, Eric Rivals dans Combinatorial Pattern Matching, 2019.
Dernières news
Installée en Allemagne et après seulement 23 jours de collecte de données, l’expérience KATRIN améliore déjà les erreurs de mesure des expériences...
Quel a été l’impact des réchauffements et refroidissements climatiques passés ? Une étude publiée dans la revue Ecology Letters impliquant des chercheurs de...
En combinant épidémiologie, modélisation mathématique et enquête historique, des chercheurs genevois et français confirment la longévité exceptionnelle de Jeanne...
Le télescope VISTA de l’ESO révèle une remarquable nouvelle vue du Grand Nuage de Magellan, l’un de nos plus proches voisins galactiques. VISTA a observé cette...
Mêmes atomes, mais formes différentes, certains produits avec une formule chimique identique présentent des propriétés parfois divergentes: une molécule pouvant...
À quel point pouvons-nous approximer un nombre irrationnel typique, comme Pi, par une fraction ? Cette question est loin d’être nouvelle en mathématiques, mais la...
La communauté internationale en climatologie est engagée dans un important exercice de simulations numériques du climat, passé et futur. Ses conclusions...
Les microtubules font partie du squelette des cellules. Des chercheurs de l'Irig montrent que les défauts dans leur structure s'avèrent utiles pour leur...
Du feu de bois au charbon, la combustion du carbone est une réaction omniprésente qui reste pourtant difficile à étudier. Des chimistes du Centre de Recherche Paul...
Une équipe internationale impliquant des chercheurs de l’Observatoire de Paris - PSL détecte des nuages moléculaires dans une galaxie située à 8 milliards...
Des chercheurs du Laboratoire plasma et conversion d'énergie, du Laboratoire d'optique appliquée et leurs collègues américains ont identifié une nouvelle...
Une collaboration entre l'Irfu et l'Université de Florence (Italie) est parvenue à réaliser la tomographie muonique d'un objet à partir de seulement trois prises de...
Des chercheurs du Laboratoire de chimie de coordination à Toulouse (CNRS) et de l’Institut des sciences chimiques de Rennes (CNRS/Université de Rennes 1/INSA...
La première campagne dédiée à l'observation directe d'exoplanètes a visé l'étoile Alpha du Centaure A depuis l'Observatoire austral européen (Chili). Elle...
L’infertilité touche de plus en plus de couples, et reste malgré tout difficile à étudier en raison de sa complexité. Récemment, une équipe de chercheurs de...
Deux semaines seulement après le lancement d’une expédition scientifique au large de la Guyane, les équipes de Greenpeace (1), en collaboration avec les chercheurs...
Plusieurs chercheurs du LSCE ont contribué au rapport spécial du Giec publié le 8 août 2019, consacré aux interactions entre terres émergées et climat. Cette...
Tous les êtres vivants ne perçoivent pas les mêmes conditions climatiques que celles mesurées par nos postes météorologiques situés à découvert et exposés aux...
Destinée aux télescopes Tcherenkov de CTA (Cherenkov Telescope Array), la caméra prototype NectarCAM développée par l'Irfu et ses partenaires a enregistré sa...
Une équipe de recherche internationale a élaboré une stratégie permettant de prédire les effets cliniques possibles de nouvelles molécules thérapeutiques à...
Ce site fait l'objet d'une déclaration à la CNIL
sous le numéro de dossier 1037632
Informations légales