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...
Kaydedildi:
| Yazar: | |
|---|---|
| Diğer Yazarlar: | |
| Materyal Türü: | Thèse et Mémoire papier |
| Dil: | Français |
| Baskı/Yayın Bilgisi: |
[S.l.] :
[s.n.]
1992.
|
| Konular: | |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | On string machine |
| Özet: | 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. |
|---|---|
| Fiziksel Özellikler: | 1 vol. (148 f.) : graph. ; 30 cm. |
| Bibliyografya: | Bibliogr. f. 109-111 |
| Erişim: | Publication autorisée par le jury |