Supervision : 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.

2005-2009 Publications

• 2009
  • Ch. Jouis, J. Bourdaillet, B. Habib, J.‑G. Ganascia : “Exceptions in Ontologies: A Theoretical Model for Deducing Properties from Topological Axioms”, chapter in Ontology Theory, Management and Design: Advanced Tools and Models, (IGI-Global) (2009)
• 2008
  • Ch. Jouis, J. Bourdaillet : “Exceptions in Ontologies: when Topology meets Typicality”, Proceeding of the 21^st International Florida Artificial Intelligence Research Society Conference, (FLAIRS-21), Coconut Grove, Florida, United States, pp. 482-487, (AAAI) (2008)
  • Ch. Jouis, J. Bourdaillet : “Representation of Atypical Entities in Ontologies”, Proceedings of the six International Language Resources and Evaluation (LREC’08), Marrakech, Morocco, pp. 122-126 (2008)
• 2007
  • J. Bourdaillet : “Alignement textuel monolingue avec recherche de déplacements: algorithmique pour la critique génétique”, thesis, phd defence 12/03/2007, supervision Ganascia, Jean-Gabriel (2007)
  • J. Bourdaillet, J.‑G. Ganascia : “Alignements monolingues avec déplacements”, 14^e Conférence sur le Traitement Automatique des Langues Naturelles (TALN), Toulouse, France, pp. 303-312 (2007)
  • J. Bourdaillet, J.‑G. Ganascia, I. Fénoglio : “Machine Assisted Study of Writers’ Rewriting Processes”, 4^th International Workshop on Natural Language Processing and Cognitive Science (NLPCS), Madeire, Portugal, pp. 222-227, (SCITEPRESS Digital Library) (2007)
  • J. Bourdaillet, J.‑G. Ganascia : “Practical block sequence alignment with moves”, 1^st International Conference on Language and Automata Theory and Applications (LATA), Tarragona, Spain, pp. 199-210 (2007)
  • J. Bourdaillet, J.‑G. Ganascia : “Alignment of Noisy Unstructured Text Data”, 20^th International Joint Conference on Artificial Intelligence (IJCAI). Workshop on Analytics for Noisy Unstructured Text Data (AND 2007), Hyderabad, India, pp. 139-146 (2007)
• 2006
  • J. Bourdaillet, J.‑G. Ganascia : “Unilingual alignement: a building block for digital resources constitution”, 1^st International Conference on Multidisciplinay Information Sciences and Technologies (INSCIT 2006), Merida, Spain, pp. 303-307 (2006)
  • J. Bourdaillet, J.‑G. Ganascia : “MEDITE: A unilingual textual aligner”, 5^th International Conference on Natural Language Processing (FinTAL 2006), vol. 4139, Lecture Notes in Computer Science, Turku, Finland, pp. 458-469, (Springer) (2006)
  • J.‑G. Ganascia, J. Bourdaillet : “Alignements unilingues avec MEDITE”, Huitièmes Journées Internationales d'Analyse Statistique des Données Textuelles (JADT 2006), Besançon, France, pp. 427-437 (2006)
• 2005
  • J. Bourdaillet, J.‑G. Ganascia : “Etiquetage morpho-syntaxique du français à base d’apprentissage supervisé”, TALN 2005 - 12^e Conférence sur le Traitement Automatique des Langues Naturelles, Dourdan, France, pp. 409-414, (Association pour le Traitement Automatique des Langues) (2005)