LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » Actualité » Doctorants

BOURDAILLET Julien

Docteur
Équipe : ACASA
Date de départ : 31/08/2008
Direction de recherche : Jean-Gabriel GANASCIA

Alignement textuel monolingue avec recherche de déplacements: algorithmique pour la critique génétique

Ce travail de thèse répond à une problématique suscitée par la critique génétique textuelle. Cette discipline étudie les brouillons d'écrivains, en recherchant, entre autres, les déplacements entre deux versions d'un même texte. Ceci nous amené à définir la problématique de l'alignement textuel monolingue avec recherche de déplacements.
D'un point de vue informatique, nous avons mis à jour la nécessité de calculer un alignement entre deux textes de type distance d'édition avec recherche des déplacements; or ce problème est NP-difficile.
De plus, notre objectif était l'obtention d'un algorithme efficace permettant le passage à l'échelle, ce qui permet d'envisager la recherche des déplacements dans de longs textes comme des livres. Il devait également permettre l'alignement de textes très différents, tout en identifiant les modifications au caractère près.
Nous proposons une formalisation en un problème d'optimisation combinatoire multiobjectif intégrant un critère syntaxique. Celle-ci permet de résoudre théoriquement de petites instances du problème avec un solveur SAT, mais ne permet pas le passage à l'échelle, soit l'alignement de livres entiers.
Pour résoudre ce problème, nous proposons un algorithme d'alignement par fragments utilisé en bioinformatique pour l'alignement de génomes de mammifères. Cet algorithme heuristique résout le problème avec une complexité efficace, en coordonnant la résolution des recouvrements entre occurrences d'une répétition. Il permet le passage à l'échelle et présente de bons résultats face à d'autres méthodes connexes.
L'implémentation de notre méthode est maintenant utilisée par les généticiens du texte afin d'étudier les brouillons d'écrivains.
Soutenance : 03/12/2007 - 10h30 - Site Passy-Kennedy - salle 549
Membres du jury :
Maxime Crochemore - Professeur, Université de Marne-la-Vallée (Rapporteur)
Béatrice Daille - Professeur, Université de Nantes (Rapporteur)
Jean-Gabriel Ganascia - Professeur, Université Pierre et Marie Curie
Philippe Langlais - Maître de conférences, Université de Montréal
Jean-Louis Lebrave - Directeur de recherche, Ecole Normale Supérieure
Patrice Perny - Professeur, Université Pierre et Marie Curie

Publications 2005-2009

 Mentions légales
Carte du site |