Cours INF7545 – Algorithmique du texte

Aspects algorithmiques et expérimentaux du traitement informatique des chaînes de caractères. Recherche de motifs, exacte et approchée: algorithmes déterministes et probabilistes, automates, expressions régulières, programmation dynamique. Indexation du texte: arbres des suffixes, automates des suffixes, tableaux des suffixes, problèmes liés à l’implémentation de ces différentes structures. Grammaires, modèles de Markov cachés et modèles probabilistes de séquences. Applications: bioinformatique, indexation et analyse de grands textes (banques de données, Web), traitement du langage naturel.