Grammaire à substitution d’arbre de complexité polynomiale : un cadre efficace pour DOP
Jean-Cédric Chappelier, Martin Rajman
Résumé : Trouver l’arbre d’analyse le plus probable dans le cadre du modèle DOP (Data-Oriented Parsing) — une version probabiliste de grammaire à substitution d’arbres développée par R. Bod (1992) — est connu pour être un problème NP-difficile dans le cas le plus général (Sima’an, 1996a). Cependant, si l’on introduit des restrictions a priori sur le choix des arbres élémentaires, on peut obtenir des instances particulières de DOP pour lesquelles la recherche de l’arbre d’analyse le plus probable peut être effectuée en un temps polynomial (par rapport à la taille de la phrase à analyser). La présente contribution se propose d’étudier une telle instance polynomiale de DOP, fondée sur le principe de sélection miminale-maximale et d’en évaluer les performances sur deux corpus différents.
Abstract : Finding the most probable parse tree in the framework of Data-Oriented Parsing (DOP), a Stochastic Tree Substitution Parsing scheme developed by R. Bod (1992), has proven to be NP-hard in the most general case (Sima’an, 1996a). However, introducing some a priori restrictions on the choice of the elementary trees leads to interesting DOP instances with polynomial time-complexity. The purpose of this paper is to present such an instance, based on the minimal-maximal selection principle, and to evaluate its performances on two different corpora.