Algorithme de Cocke-Younger-Kasami

L'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaire non contextuelle. 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.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Cocke-Younger-Kasami de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme CYK — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • CYK (Algorithme) — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • CYK (algorithme) — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • Cyk (algorithme) — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • CYK — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • Cyk — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • CKY — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”