Alignement monolingue avec recherche de déplacements pour la critique génétique [Monolingual alignment with moves for genetic criticism]

Alignement monolingue avec recherche de déplacements pour la critique génétique Julien Bourdaillet Laboratoire RALI Département d’Informatique et de Recherche Opérationnelle Université de Montréal C.P. 6128, succursale Centre-Ville H3C 3J7, Montréal, Québec, Canada julien.bourdaillet@umontreal.ca RÉSUMÉ. Cet article présente la problématique de l’alignement monolingue avec recherche de déplacements. Celle-ci est posée par la critique génétique, une discipline d’études littéraires. Les solutions informatiques existantes ne sont pas satisfaisantes pour répondre à ce problème NP-difficile. Nous proposons d’emprunter à la bioinformatique et l’algorithmique textuelle une famille d’algorithmes appelée alignement par fragments. Une adaptation de ce type d’algo- rithmes pour le TAL est décrite. Notre méthode permet d’aligner deux textes en recherchant les déplacements, au caractère près, en passant à l’échelle, et pour n’importe quelle langue alphabétique. Une évaluation expérimentale présente les bons résultats obtenus face à d’autres méthodes. ABSTRACT. This paper describes the problem of monolingual alignment with search for displaced segments (hereafter called move search). It occurs in genetic criticism, a subfield of literary studies. Existing alignment applications fare poorly on this NP-hard problem. We propose to borrow a family of algorithms from bioinformatics and text algorithmics called fragment chaining alignment. An adaptation of this type of algorithms to NLP is described. Our method enables us to align a pair of texts with move search at the character level. It works for any alphabetic language and achieves scalability. An experimental evaluation presents the good results we obtained compared to other approaches. MOTS-CLÉS : alignement monolingue, recherche de déplacements, algorithmique textuelle, cri- tique génétique. KEYWORDS: monolingual alignment, move search, text algorithmics, genetic criticism. TAL. Volume 50 – n˚ 1/2009, pages 61 à 85 62 TAL. Volume 50 – n˚ 1/2009 1. Introduction L’alignement monolingue consiste à rechercher les invariants et les différences existants entre deux textes écrits dans une même langue. Très tôt dans l’histoire de l’in- formatique cette question s’est révélée importante. Pouvoir comparer deux versions du code source d’un programme, afin d’en visualiser facilement les différences, est à l’origine des premiers aligneurs, tel le programme diff (Hunt et McIlroy, 1976). La sauvegarde incrémentale des fichiers texte, à l’époque où l’espace disque était rare, fut également une des principales motivations liées au développement de ces aligneurs. Avec la généralisation de la diffusion des ordinateurs et l’apparition des applications de traitement de texte, l’alignement s’est naturellement imposé comme un outil des plus utiles pour l’écriture sur machine. On trouve par exemple dans Microsoft Word un outil intégré d’alignement textuel. De nombreux autres aligneurs commerciaux sont également disponibles. Une pre- mière étude qualitative, portant sur neuf aligneurs commerciaux dont Microsoft Word, nous a montré qu’ils obtenaient de mauvais résultats dès lors que les textes à compa- rer devenaient trop différents (Bourdaillet et Ganascia, 2006). Les aligneurs ont alors beaucoup de difficulté à repérer les différences avec précision, soit au caractère près ; celles-ci sont largement exagérées et l’alignement résultant devient très vite peu li- sible. Classiquement, les différences identifiées entre deux textes sont de trois types : suppressions, insertions et remplacements. On notera qu’un remplacement …

Content truncated to 500 words