Alignement Textuel Monolingue Avec Recherche de D placements

Ce travail rpond une problmatique suscite par la critique gntique. Cette discipline tudie la gense des oeuvres littraires grce aux brouillons d'crivains en recherchant, entre autres, les dplacements entre deux versions d'un mme texte. Ceci nous a amen dfinir la problmatique de l'alignement textuel monolingue avec recherche de dplacements. D'un point de vue informatique, nous avons mis jour la ncessit de calculer un alignement entre deux textes de type distance d'dition avec recherche des dplacements, ce qui est NP-difficile. Nous proposons une formalisation en un problme d'optimisation combinatoire multiobjectif intgrant un objectif syntaxique. Un algorithme d'alignement de squences par fragments est propos. En bioinformatique, cette technique permet de traiter des gnomes de mammifres. Notre algorithme est bas sur la coordination de la rsolution des recouvrements entre occurrences d'une rptition. Il rsout le problme avec une complexit efficace et passe l'chelle. Il est maintenant utilis par les gnticiens du texte afin d'tudier les brouillons d'crivains.