Algorithme de Cocke-Younger-Kasami

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaires non contextuelles. Il permet de déterminer si un mot peut être engendré par une grammaire, et si oui, d'en donner une dérivation.

L'algorithme opère par analyse ascendante, et emploie la programmation dynamique. Il permet d'obtenir l'arbre syntaxique du mot. L'algorithme suppose que la grammaire est en forme normale de Chomsky. Si la grammaire est pondérée, CYK permet de générer l'arbre le plus lourd qui engendre la phrase. Le temps de calcul de cet algorithme est de l'ordre n^3 \cdot |G|, où n est la longueur du mot analysé, et |G| est la taille de la grammaire.

Principe[modifier | modifier le code]

L'algorithme met à profit les observations suivantes à partir d'une forme normale de Chomsky pour un mot non vide :

  • Si le mot est de longueur 1, il suffit de vérifier s'il figure dans un membre droit d'une règle transformant un symbole non terminal en symbol terminal ;
  • Sinon, le mot w ne peut éventuellement être issu que d'une dérivation commençant par une règle du type XY Z, et se décompose donc en w[1..k] engendré à partir de Y et w[k+1..|w|] engendré à partir de Z pour un certain entier k compris entre 1 et |w|-1.

On peut donc se ramener à résoudre des sous-problèmes fonctions de trois paramètres :

  • l'indice i de la lettre initiale du sous-mot ;
  • l'indice j de la lettre finale du sous-mot ;
  • le symbole non terminal X à partir duquel est potentiellement engendré le sous-mot.

En notant P[i, j, X] ce sous-problème générique, on peut ainsi déduire un algorithme pour résoudre le problème initial qui n'est autre que P[1, |w|, S] où w est le mot considéré et S l'axiome de la grammaire sous forme normale de Chomsky.

Voir aussi[modifier | modifier le code]