Composition filtrée et marqueurs de règles de réécriture pour une distance d’édition flexible. Application à la correction des mots hors vocabulaire [Filtered Composition and Markers for a Flexible Edit-Distance. Application to the Correction of Out-Of-Vocabulary Words.]

Composition filtrée et marqueurs de règles de réécriture pour une distance d’édition flexible Application à la correction des mots hors vocabulaire Richard Beaufort Centre de traitement automatique du langage Université de Louvain Place Blaise Pascal 1, 1348 Louvain-la-Neuve, Belgique richard.beaufort@uclouvain.be RÉSUMÉ. Nous présentons une implémentation flexible et originale de la distance d’édition : la composition filtrée, un type particulier de composition de deux machines à états finis au travers d’un filtre qui modélise l’ensemble des opérations d’édition valides. Le filtre est un transducteur pondéré ou une cascade de transducteurs pondérés. Il est obtenu par compilation de règles de réécriture qui profitent d’un nouveau concept défini dans notre bibliothèque de machines à états finis : le marqueur de règles, un symbole qui n’appartient pas à l’alphabet utilisé, mais est inséré dans une règle de réécriture afin d’identifier un phénomène et d’en suivre l’évolution. Les marqueurs désambiguïsent et facilitent l’expression de conditions et de contraintes. La méthode est illustrée dans le cadre de la correction des mots hors vocabulaire. ABSTRACT. We present an original and flexible implementation of the edit-distance: the filtered composition, a special kind of composition of two finite-state machines through a filter that mod- els all valid edit-operations. The filter is either a weighted transducer or a cascade of weighted transducers. It is built from weighted rewrite rules that take advantage of a new concept defined in our finite-state framework: the rules’ marker, a symbol that does not belong to the alpha- bet in use, but is inserted into a rewrite rule in order to mark a phenomenon and to track its evolution. Markers disambiguate and make it easy to express conditions and constraints. The method is illustrated on the task of correcting out-of-vocabulary words. MOTS-CLÉS : distance d’édition, composition filtrée, marqueurs de règles, correction orthogra- phique. KEYWORDS: edit distance, filtered composition, rules’ markers, spelling correction. TAL. Volume 51 – n˚ 1/2010, pages 11 à 40 12 TAL. Volume 51 – n˚ 1/2010 1. Introduction La distance d’édition D(u, v) de deux séquences u et v mesure le nombre minimal d’opérations d’édition (substitution, insertion, suppression) nécessaires pour convertir u en v. Le principe est très intéressant, mais son implémentation pose de nombreuses questions pratiques auxquelles de nombreuses études ont tenté de répondre. Comment pondérer efficacement les opérations d’édition ? Comment modéliser des substitutions n–m ? Et, enfin et surtout, comment construire rapidement l’ensemble V de séquences v appartenant à un lexique L, pour lesquelles la distance d’édition D(u, v) ne dépasse pas un certain seuil ? La méthode que nous présentons est une extension de la distance d’édition de deux automates définie par Mohri (2003). Étant donné une forme u et un lexique L, nous proposons de construire l’ensemble V de candidats v pour u dans L au travers de la cascade de compositions suivante : V = U ◦ F ◦ L [1] où F est un transducteur pondéré qui modélise les opérations d’édition acceptées. La méthode est appelée composition filtrée, parce que le transducteur pondéré F peut …

Content truncated to 500 words