Treffer: Algorithmes d’approximation efficaces pour les langages formels ; Fast approximation algorithms for formal languages
Weitere Informationen
Depuis les années 1970, la recherche en informatique a produit de nombreux outils et algorithmes très efficaces pour le traitement de données textuelles. Toutefois, ces techniques ont principalement été conçues pour les problèmes exacts, et ne sont pas directement applicables aux tâches d’approximation ou ne sont pas adaptées à la taille des jeux de données modernes. Dans cette thèse, nous étudions des algorithmes d’approximation efficaces (en termes de ressources), qui sont plus adaptés aux tâches modernes de traitement de texte. Dans la première partie de cette thèse, on s’intéresse à plusieurs variantes du problème de recherche de motif, un ensemble de tâche dans lesquelles on doit trouver toutes les sous-chaînes d’un texte qui sont similaires à un motif donné, pour plusieurs notions de similarité. On étudie tout d’abord le cas de la recherche circulaire de motif. Nous donnons une structure de données avec un compromis temps-espace mémoire pour le problème de recherche interne de motif, dans le modèle read-only, puis nous montrons comment l’utiliser pour obtenir des algorithmes pour le problème de recherche circulaire de motif et celui de calculer la plus longue sous-chaîne commune en utilisant un espace mémoire faible. Ensuite, on s’intéresse au cas où la similarité est définie par la distance de Hamming, et où les chaînes de caractères peuvent contenir des jokers, c’est-à-dire des caractères considérés égaux à n’importe quel autre caractère. Dans le cas particulier des distances faibles et où les chaînes contiennent un petit nombre de groupes contigus de jokers, nous donnons un algorithme efficace et une caractérisation combinatoire de la structure des occurrences dans ce contexte. Nous donnons également une borne inférieure qui montre que notre caractérisation est presque optimale. Enfin, on étudie les structure de données pour calculer les plus longues extensions communes dans les chaînes avec jokers (abrégé LCEW en anglais). Nous donnons une structure de données avec un compromis espace-temps dans le ...