Recherches de mot
La recherche de mot consiste à trouver une ou toutes les occurrences d'un mot de longueur m dans un texte de longueur n. Nous étudions ici l'algorithme de Boyer-Moore qui compare les caractères du mot et du texte de la droite vers la gauche ce qui lui confère un bon comportement en pratiqu...
שמור ב:
| מחבר ראשי: | |
|---|---|
| מחברים אחרים: | |
| פורמט: | Thèse et Mémoire papier |
| שפה: | Français |
| יצא לאור: |
[S.l.] :
[s.n.]
1992.
|
| נושאים: | |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | On string machine |
| LEADER | 02563nam a22002777a 4500 | ||
|---|---|---|---|
| 001 | 191272 | ||
| 008 | 030219s1992 xxe ||| |||| 00| 0 fre d | ||
| 009 | PPN069756392 | ||
| 041 | 0 | |a fre |b fre | |
| 084 | |a 004 | ||
| 100 | 1 | |a Lecroq, Thierry, |d 1965- | |
| 240 | 1 | 0 | |a On string machine |
| 245 | 1 | 0 | |a Recherches de mot |c par Thierry Lecroq ; sous la direction de Gérard Ferrand. |
| 260 | |a [S.l.] : |b [s.n.], |c 1992. | ||
| 300 | |a 1 vol. (148 f.) : |b graph. ; |c 30 cm. | ||
| 502 | |a Thèse de doctorat. Informatique fondamentale. Orléans. 1992 | ||
| 504 | |a Bibliogr. f. 109-111 | ||
| 506 | |a Publication autorisée par le jury | ||
| 520 | |a La recherche de mot consiste à trouver une ou toutes les occurrences d'un mot de longueur m dans un texte de longueur n. Nous étudions ici l'algorithme de Boyer-Moore qui compare les caractères du mot et du texte de la droite vers la gauche ce qui lui confère un bon comportement en pratique. Nous étudions également ses variantes et en présentons une nouvelle appelée Turbo-BM simple à mettre en oeuvre. Nous présentons également deux nouveaux algorithmes de recherche de mot basés sur l'utilisation de l'automate déterministe minimal des suffixes du renversé du mot à trouver. Le premier algorithme nommé Reverse Factor est quadratique sans le pire des cas, le second appelé Turbo Reverse Factor est linéaire dans le pire des cas et effectue au plus 2n comparaisons. Ces deux algorithmes ont un comportement optimal en moyenne. Nous montrons qu'il est possible d'étendre cette technique à la recherche d'un ensemble fini de mots à l'aide d'un nouvel algorithme nommé Multi Reverse Factor. Enfin nous exhibons des résultats de tests de plusieurs algorithmes de recherche de mot sur différents types de textes. Ces résultats montrent que pour de petits alphabets ou pour de longs mots les algorithmes du type Reverse Factor ont un très bon comportement en pratique. | ||
| 650 | |a Traitement de texte | ||
| 650 | |a Algorithmes | ||
| 650 | |a Thèses et écrits académiques | ||
| 700 | 1 | |a Ferrand, Gérard, |d 19..-...., |c professeur d'informatique. |4 ths | |
| 710 | 2 | |a Université d'Orléans. |4 dgg | |
| 787 | 0 | 8 | |i Reproduced as: |0 246639792 |t Recherches de mot |f par Thierry Lecroq |d 1992 |c Grenoble |n Atelier national de reproduction des thèses |p Microfiches |s [Grenoble thèses] |
| 997 | |0 191272 |1 Thèse et Mémoire papier |a Ressource papier |c 0/Orléans/ |c 1/Orléans/BU Sciences, Technologies, STAPS/ |z Orléans, BU Sciences, Technologies, STAPS, TS 19-1992-45 |z Orléans, BU Sciences, Technologies, STAPS, TS 19-1992-45 b | ||