[PDF] Untitled motif est un mot x

View - Download Untitled

Previous PDF

Next PDF

Algorithmique du texte

Maxime CrochemoreChristophe HancartThierry Lecroq

Algorithmique du texte

Vuibert Informatique

Algorithmique du texte- Maxime Crochemore, Christophe

Hancart et Thierry Lecroq

Conception de la couverture : Jean Widmer

Les programmes et exemples figurant dans cet ouvrage ont pourbut d"illustrer les sujets traités. Il n"est donné aucune garantie quant à leur utilisation dans le cadre d"une activité professionnelle ou commerciale.

Contact :informatique@vuibert.fr

Web :www.vuibert.fr

c ?Vuibert, Paris, 2001

ISBN 2-7117-8628-5

Toute représentation ou reproduction intégrale ou partielle, faite sans le consentement de l"auteur, etc.

Table des matières

PréfaceVII

1 Outils1

1.1 Mots et automates2

1.2 Un peu de combinatoire8

1.3 Algorithmes et complexité17

1.4 Mise en mémoire d"automates21

1.5 Techniques de base26

1.6 Base de techniques élaborées38

2 Automates de localisation53

2.1 Arbre d"un dictionnaire54

2.2 Localisation de plusieurs mots55

2.3 Implantation avec fonction de suppléance63

2.4 Implantation avec successeur par défaut69

2.5 Localisation d"un mot79

2.6 Localisation d"un mot et fonction de suppléance81

2.7 Localisation d"un mot et successeur par défaut88

3 Localisation avec fenêtre glissante97

3.1 Localisation sans mémoire98

3.2 Temps de recherche103

3.3 Calcul de la table du bon suffixe108

3.4 Automate du meilleur facteur111

3.5 Localisation avec une mémoire115

3.6 Localisation avec plusieurs mémoires121

3.7 Localisation d"un dictionnaire130

4 Table des suffixes139

4.1 Recherche dans une table de mots140

4.2 Recherche avec les préfixes communs143

4.3 Préparation de la liste148

VI Table des matières

4.4 Tri des suffixes149

4.5 Préfixes communs des suffixes155

5 Structures pour index163

5.1 Arbre des suffixes164

5.2 Arbre compact des suffixes169

5.3 Contextes des facteurs178

5.4 Automate des suffixes184

5.5 Automate compact des suffixes195

6 Index203

6.1 Implantation d"un index203

6.2 Opérations de base206

6.3 Transducteur des positions211

6.4 Répétitions213

6.5 Mots interdits214

6.6 Machine de recherche217

6.7 Recherche d"un conjugué222

7 Alignements225

7.1 Comparaison de mots226

7.2 Alignement optimal233

7.3 Plus long sous-mot commun244

7.4 Alignement avec brèches254

7.5 Meilleur alignement local257

7.6 Heuristique pour l"alignement local260

8 Motifs approchés267

8.1 Recherche de mots à jokers268

8.2 Recherche avec différences272

8.3 Recherche avec inégalités284

8.4 Recherche de motifs courts293

8.5 Heuristique pour la recherche avec différences302

9 Périodes locales309

9.1 Partitionnement des facteurs309

9.2 Localisation des puissances318

9.3 Recherche de carrés322

9.4 Tri des suffixes330

Bibliographie339

Index347

Préface

Cet ouvrage présente un large panorama des méthodes algorithmiques utilisées pour traiter le texte. À ce titre il s"agit d"un livre d"algorith- mique, mais dont l"objet est focalisé sur la manipulation dutexte par ordinateur. L"idée de cette publication résulte du constatqu"il n"existe aucune autre référence en français abordant le sujet avec cette ampleur (et les rares livres en anglais consacrés au sujet sont essentiellement des monographies de recherche). Ce constat est d"autant plus surprenant que les problèmes du domaine sont connus depuis le développement des systèmes d"exploitation évolués et que le recours à des solutions effi- caces devient crucial depuis l"utilisation massive de l"informatique et de la bureautique dans de nombreux secteurs de la société. Sous une forme écrite ou vocale, le texte est le seul véhiculefiable des concepts abstraits. Il reste donc le support privilégiédes systèmes d"informations, en dépit d"efforts importants vers l"utilisation d"autres médias (interfaces graphiques, systèmes de réalité virtuelle, films de syn- thèse, etc.). Cet aspect est encore renforcé par les bases deconnaissances littéraires, juridiques, commerciales ou autres qui se développent sur l"In- ternet grâce en particulier aux services de la Toile. Le contenu de l"ouvrage porte sur les éléments formels et lesbases techniques utilisés dans les domaines de la recherche documentaire, de l"indexation automatique pour les moteurs de recherche, etdes logiciels systèmes, ce qui inclut l"édition, le traitement et la compression de textes. Les méthodes qui sont décrites s"appliquent au traitement de la langue naturelle, au traitement et à l"analyse des séquences génétiques, à l"ana- lyse de séquences musicales, aux questions de sécurité liées aux flux de données, et à la gestion des bases de données textuelles, pour ne citer que quelques applications immédiates. Les sujets retenus comprennent la localisation de motifs textuels, l"indexation de données textuelles, la comparaison de textes par aligne- ment et la recherche de régularités locales. En plus de leur intérêt pra- tique, ces sujets possèdent des aspects théoriques et combinatoires qui fournissent d"étonnants exemples de solutions algorithmiques.

VIII Préface

Le but de l"ouvrage est avant tout pédagogique. Il s"adresseen pre- mier lieu aux étudiants des classes préparatoires aux grandes écoles, aux étudiants des seconds et troisièmes cycles universitairesd"informatique, ainsi qu"aux élèves-ingénieurs en informatique. Mais il peut aussi être utilisé par des ingénieurs de production de logiciels. Nous remercions vivement les chercheurs qui ont pris le temps de relire et de commenter les ébauches préalables de ce livre. Il s"agit de Saïd Abdeddaïm, Marie-Pierre Béal, Christian Charras, Sabine Mercier, Laurent Mouchard, Johann Pelfrêne, Bruno Petazzoni, Mathieu Raffi- not, Giuseppina Rindone, Marie-France Sagot. Les erreurs qui restent sont les nôtres. Le lecteur avisé notera l"utilisation des règles de l"or- thographe recommandées par le Conseil supérieur de la langue française (Journal officieldu 6 décembre 1990) qui nous fait par exemple écrire " apparaitre » et " ambigüité » sous ces formes. Enfin, des éléments complémentaires au contenu de l"ouvragesont accessibles sur le sitehttp://chl.univ-mlv.fr/ou depuis les pages des auteurs.

Maxime Crochemore

Christophe Hancart

Thierry Lecroq

Marne-la-Vallée et Rouen,

juin 2001

1 Outils

Ce chapitre présente le cadre algorithmique et combinatoire dans lequel sont développés les chapitres suivants. Il précise pour commencer les notions et notations utilisées pour travailler sur les mots, les langages et les automates. La suite est principalement consacrée à l"introduction des structures de données retenues pour la réalisation d"automates et à la présentation de résultats combinatoires. Cette organisation s"appuie sur la constatation que les algorithmes efficaces de traitement du texte reposent sur l"un ou l"autre de ces aspects. La section 1.2 fournit quelques propriétés combinatoires des mots qui reviennent dans bon nombre de preuves de validité d"algorithmes ou d"évaluations de leurs performances. Il s"agit principalement de résultats sur les périodicités qui apparaissent dans certains mots. Le formalisme de description des algorithmes est présenté dans la section 1.3 qui est surtout centrée sur le type d"algorithmes décrits dans l"ouvrage et qui introduit quelques objets standard concernant la gestion de files et d"automates. La section 1.4 détaille plusieurs procédés pour implanter des auto- mates en mémoire, procédés qui contribuent notamment aux résultats des chapitres 2, 5 et 6. Les premiers algorithmes de localisation de mots sont présentés dans la section 1.5. Les techniques de fenêtre glissante, d"automate de recher- che et d"utilisation de mots machine qui y sont décrites sontreprises et améliorées dans les chapitres 2, 3 et 8, en particulier. La section 1.6 est le joyau algorithmique du chapitre. Elle présente deux méthodes algorithmiques fondamentales utilisées pour le traitement du texte. Elles servent à calculer la table des bords et la table des préfixes d"un mot qui constituent deux tables essentielles car ellescondensent une partie des propriétés combinatoires du mot. Leur utilisation ou adapta- tion est considérée dans les chapitres 2 et 3, mais revient ponctuellement dans d"autres chapitres. Enfin, on notera que l"intuition s"appuie quelquefois sur des figures dont le style est introduit dans le chapitre et conservé ensuite.

2 Outils

1.1 Mots et automates

On introduit dans cette section les notations sur les mots, les langages et les automates.

Alphabet et mots

Unalphabetest un ensemble fini non vide dont les éléments sont appelés deslettres. Unmotsur un alphabetAest une suite finie d"éléments deA. La suite de zéro lettre est appelée lemot videet notéeε. Pour simplifier, les délimiteurs et les séparateurs utilisés habituellement dans les notations des suites sont supprimés et l"on écrit un mot comme la simple juxtaposition des lettres qui le composent. Ainsi,ε,a,betbaba sont-ils des mots sur tout alphabet qui contient les deux lettresaetb. L"ensemble de tous les mots sur l"alphabetAest notéA?, et l"ensemble de tous les mots sur l"alphabetAexcepté le mot videεest notéA+. Lalongueurd"un motxest définie comme la longueur de la suite associée au motxet est notée|x|. On notex[i], pouri= 0,1,...,|x|-1, la lettre à l"indiceidexen convenant de commencer la numérotation des indices à partir de0. Lorsquex?=ε, on dit plus spécifiquement de chaque indicei= 0,1,...,|x|-1qu"il est unepositionsurx. Il s"ensuit que laj-ième lettre dexest la lettre à la positionj-1surxet que : x=x[0]x[1]...x[|x| -1]. D"où aussi une définition élémentaire de l"identité de deux mots quel- conquesxety: x=y si et seulement si |x|=|y|etx[i] =y[i]pouri= 0,1,...,|x| -1. L"ensemble des lettres sur lequel est formé le motxest notéalph(x). Par exemple, six=abaaab, on a|x|= 6etalph(x) ={a,b}. Leproduit- on dit aussi laconcaténation- de deux motsxety est le mot composé des lettres dexpuis de celles deydans cet ordre. On le notexyou encorex·ypour faire apparaitre une décomposition du mot résultant. L"élément neutre pour le produit estε. Pour tout motxet tout natureln, on définit lan-ièmepuissancedu motx, notéexn, par x

0=εetxk=xk-1xpourk= 1,2,...,n. Sont notés respectivement

zy -1etx-1zles motsxetylorsquez=xy. Lerenversé- ouimage miroir- du motxest le motx≂défini par : x ≂=x[|x| -1]x[|x| -2]...x[0]. Un motxest unfacteurd"un motys"il existe deux motsuetv tels quey=uxv. Lorsqueu=ε,xest unpréfixedey; et lorsque

1.1 Mots et automates3

b a b a a b a b a Figure 1.1Une occurrence du motabadans le motbabaababaà la position (gauche) 1. v=ε,xest unsuffixedey. Le motxest unsous-motdeys"il existe |x|+ 1motsw0,w1,...,w|x|tels quey=w0x[0]w1x[1]...x[|x| -1]w|x|; de manière moins formelle,xest un mot obtenu deyen lui supprimant |y| - |x|lettres. Un facteur ou un sous-motxd"un motyest qualifié de propresix?=y. On note respectivementx?facty,x?facty,x?préfy, x?préfy,x?suffy,x?suffy,x?smotyetx?smotylorsquexest un facteur, un facteur propre, un préfixe, un préfixe propre, un suffixe, unquotesdbs_dbs41.pdfusesText_41

[PDF] raccourci clavier rechercher mot

[PDF] rechercher un mot dans un texte word

[PDF] raccourci clavier recherche mot mac

[PDF] rechercher sur un site avec google

[PDF] mobile volume musculation

[PDF] cycle musculation niveau 3

[PDF] exemple musculation bac

[PDF] guide des mouvements de musculation 5e édition pdf

[PDF] programme entrainement lancer de poids

[PDF] lancer de javelot exercice physique

[PDF] musculation javelot

[PDF] lancer du disque exercices

[PDF] etude de marché du bricolage en france

[PDF] combien de salles au louvre

[PDF] plan du louvre et des tuileries