Algorithme de Cocke-Younger-Kasami
Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
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 phrase. 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 de n³.