La simplicité des chaînes de caractères rendent leur traitement crucial pour de nombreuses applications, telles que la bio-informatique, la recherche d’informations et la cybersécurité. Le problème de la recherche exacte d’un motif a naturellement été largement étudié, cependant, de nombreuses applications nécessitent également des requêtes plus complexes. De plus, dans ces domaines applicatifs, la quantité de données à traiter augmente à une vitesse stupéfiante, et les complexités des requêtes ne permettent pas toujours de passer à l’échelle. Dans cette thèse, nous proposons plusieurs algorithmes efficaces en temps et en espace pour divers problèmes sur les chaînes de caractères, en nous appuyant sur des « sketchs » : des compressions (avec ou sans perte) qui ne conservent que les caractéristiques essentielles de l’entrée pour répondre à une requête précise. Dans la première partie de cette thèse, nous étudions des requêtes complexes telles que la recherche par expressions régulières, la recherche de motifs consécutifs avec espacement et la détection de carrés. Pour la recherche d’expressions régulières, nous présentons un algorithme utilisant peu d’espace dans le modèle de flot de données (« streaming ») : les caractères du texte arrivent un par un, et nous ne pouvons accéder aux anciens que si nous les avons stockés explicitement. Ensuite, nous étudions la recherche de motifs consécutifs avec espacement, un type de requête plus simple, où étant donnés deux motifs P1, P2 et un intervalle [a, b], il faut renvoyer toutes les occurrences consécutives (sans autres occurrences des motifs entre les deux) de P1 suivies de P2 espacées d’une distance comprise entre a et b. Nous étudions ce problème sous plusieurs angles : l’indexation compressée et la recherche de motifs dans un texte compressé. Motivés par l’importance de la périodicité, nous étudions ensuite la détection de carrés pour alphabets sans ordres (le cadre le plus abstrait dans lequel les carrés peuvent être définis). Nous fournissons un algorithme optimal et répondons à une question ouverte posée par Main et Lorentz en 1984. La seconde partie de cette thèse propose quelques utilisations d’approximations pour aider à passer à l’échelle sur des grandes quantités de données, en particulier avec application à la bio-informatique. Nous étudions tout d’abord la recherche approximative de motifs, où nous devons rapporter toutes les occurrences à une distance au plus égale à k pour une mesure de similarité donnée. Nous fournissons des algorithmes paramétrés efficaces pour calculer la longueur de la plus longue sous-chaîne commune avec environ k différences, puis pour permettre la recherche de motifs apparaissant avec une distance de « dynamic time warping » au plus k. Enfin, nous proposons un index compressé pour des collections de lectures de séquençage. Cet index tire parti d’alignements sur un génome assemblé pour améliorer la compression, mais l’index est approximatif car il peut renvoyer des faux positifs lors de ses requêtes.