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
Une équipe internationale d’astronomes comprenant des chercheurs de l’Observatoire de Paris - PSL a obtenu en décembre 2019 une image de la surface de la célèbre...
Océans: la fragmentation des particules joue un rôle majeur dans la séquestration du carbone Une équipe franco-britannique pilotée par le Laboratoire...
La vie en ville peut faire évoluer les populations urbaines différemment des autres. Des chercheurs du laboratoire Biogéosciences (CNRS/EPHE/Université de Bourgogne)...
Les télescopes de l’ESO scrutent la baisse de luminosité de surface de l’étoile Bételgeuse Grâce au Very Large Telescope (VLT) de l’ESO, les astronomes ont...
Une initiative de l’UE a publié un rapport sur les solutions et recommandations adoptées pour répondre aux préoccupations environnementales liées à la production...
"Travailler l’imaginaire est l’une des parties qui m’intéresse le plus dans ma recherche. Si on avait une géométrie qui n’est pas comme la géométrie plate...
Un progrès important vient d'être réalisé en développant un algorithme permettant de calculer le problème quantique à N corps jusqu’à l’ordre 15, très...
L’organisation tridimensionnelle des chromosomes doit être régulée afin d’assurer le bon fonctionnement de processus biologiques tels que la transcription, la...
Des chercheurs d’Aix Marseille Université, du CNRS et de l’Université de Montréal ont identifié dans la séquence de la protéine "Spike" du 2019-nCoV (nommé...
Une équipe de recherche canadienne, dont a fait partie un microbiologiste de l’Université de Montréal, a révélé un mécanisme d’action inédit présent dans...
Les nanomatériaux trouvent de plus en plus d’applications médicales. Parfois capables de remplir plusieurs rôles à la fois, ils offrent une flexibilité...
Des chercheurs du Centre Interdisciplinaire de Nanoscience de Marseille (CNRS/Aix Marseille Université), en collaboration avec des équipes japonaise, coréenne et...
Détecter rapidement la bactérie Legionella pneumophila Des experts de multiples horizons disciplinaires ont accompli une percée majeure: développer un nouveau...
En excitant un gaz avec des impulsions laser ultra-courtes, les physiciens ont montré que, même si habituellement les collisions au sein du gaz sont la cause...
Dans des travaux publiés dans la revue Nanomedicine, une méthode a permis d’interrompre la production d’ARN messager et de protéines de certains gènes, avec des...
Des chercheurs de l’Unité mixte de physique CNRS/Thales et du Centre de nanosciences et de nanotechnologies (C2N, CNRS/Université Paris-Sud), en collaboration avec...
L’ADN peut transitoirement revêtir des structures plus complexes que celle en double hélice. Les quadruples hélices, ou quadruplexes d’ADN, en sont un exemple. Ce...
En comprimant la matière à des pressions qui peuvent dépasser le million d’atmosphères, les cellules à enclumes de diamant mettent en lumière les propriétés...
Les archées, constituant l'un des trois domaines du vivant, sont désormais considérées comme des modèles incontournables pour étudier les mécanismes moléculaires...
La sonde européenne commence son voyage en direction du centre de notre Système solaire, la science française à l’honneur. Lundi 10 février 2020, à 05h03,...
Ce site fait l'objet d'une déclaration à la CNIL
sous le numéro de dossier 1037632
Informations légales