Réordonner les textes pour optimiser la compression de leur index
Publié par Adrien le 11/09/2019 à 08:00
Source: CNRS INS2I
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é (Une université est un établissement d'enseignement supérieur dont l'objectif est la production du savoir (recherche), sa conservation et sa...) d'Helsinki.

Chercher un mot dans un livre: rédhibitoire sans un index ! Imaginez: vous cherchez le mot "imagine" sans index. Vous devez passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) 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 (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) proportionnel au nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de blocs possibles, c'est-à-dire au nombre de caractères du livre.

Maintenant, changeons de dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa...): comment chercher un mot dans l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) des documents de la Bibliothèque Nationale de France (La Bibliothèque nationale de France (BnF) est la plus importante bibliothèque de France. Elle a le statut d'établissement public. Ses activités sont réparties sur différents sites, dont...) (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 (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique...), on fabrique des index, ou structures d'indexation, qui, stockés dans la mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) de l'ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler...), permettent d'accélérer toute recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension...) de mot. Heureusement, en algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus...) du texte, on connaît de bonnes structures d'indexation, rapide à construire, compacte et efficace, par exemple l'arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les...) des suffixes défini depuis 40 ans. Mais lorsque le volume (Le volume, en sciences physiques ou mathématiques, est une grandeur qui mesure l'extension d'un objet ou d'une partie de l'espace.) 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 (Le mot disque est employé, aussi bien en géométrie que dans la vie courante, pour désigner une forme ronde et régulière, à l'image d'un palet —...) 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 (Dans son acception courante un document est généralement défini comme le support physique d'une information.) 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 (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) ou d'apprentissage (L’apprentissage est l'acquisition de savoir-faire, c'est-à-dire le processus d’acquisition de pratiques, de connaissances, compétences, d'attitudes ou de valeurs culturelles, par l'observation, l'imitation, l'essai, la...) automatique (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la modélisation, de l'analyse, de la commande et, de la régulation des systèmes dynamiques. Elle a pour...) utilisent à grande échelle (La grande échelle, aussi appelée échelle aérienne ou auto échelle, est un véhicule utilisé par les sapeurs-pompiers, et qui emporte une...) ce type de fonction de recherche (on parle aussi de "requête (Le mot requête, synonyme de demande, est employé dans les domaines suivants :)") 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 (La statistique est à la fois une science formelle, une méthode et une technique. Elle comprend la collecte, l'analyse, l'interprétation de données ainsi que la présentation de ces...) 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.
Page générée en 1.530 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique