Abstract FR:

L'une des tâches les plus importantes en informatique est de pouvoir effectuer des requêtes sur des données. Une approche couramment utilisée pour accélérer les réponses aux requêtes consiste à faire une phase de prétraitement sur les données afin de construire une structure de données occupant un certain espace mémoire et permettant ensuite de répondre aux requêtes en un temps beaucoup plus rapide que si toutes les données originelles devaient être lues. Néanmoins cette approche peut poser des problèmes de performance au cas où la structure de données occupe beaucoup plus d'espace que les données originelles. Ainsi le domaine des structures de données compactes a pour objectif l'encodage des structures de données de sorte à ce qu'elles occupent un espace le plus compact possible tout en préservant un temps de réponse le plus petit possible. Notre premier résultat dans ce domaine est une structure de données compacte et rapide pour des requêtes consistant à trouver l'ensemble des occurrences des mots d'un dictionnaire donné dans un texte quelconque. Notre second résultat est une structure de données compacte et rapide, permettant de répondre à des recherches tolérantes à une erreur d'édition sur un dictionnaire donné à l'avance. Le résultat central de cette thèse est une nouvelle définition d'un nouveau genre de hachage parfait que nous appelons hachage parfait monotone. Dans les deux derniers chapitres nous présentons deux applications du hachage parfait monotone à l'amélioration de deux solutions existantes pour les problèmes de l'indexation de texte et de la recherche des k-plus-pertinents documents.