Algorithme de Cocke-Younger-Kasami

Sans perte de généralité, on suppose que la grammaire ${\displaystyle G}$ n'engendre pas le mot vide ${\displaystyle \epsilon }$ . Ainsi, on peut supposer que la grammaire ${\displaystyle G}$ est sous forme normale de Chomsky et qu'elle ne contient pas de règles de la forme ${\displaystyle N\rightarrow \epsilon }$ (on parle de grammaire propre, voir grammaire non contextuelle).

Soit ${\displaystyle m}$ un mot non vide à analyser. L'algorithme emploie la programmation dynamique. Les sous-problèmes sont les suivants : ${\displaystyle P[i,j]}$ est l'ensemble des non-terminaux qui engendrent le mot ${\displaystyle m[i..j]}$ pour tout ${\displaystyle i,j}$ tels que ${\displaystyle 1\leq i\leq j\leq |m|}$ où ${\displaystyle |m|}$ est la longueur du mot ${\displaystyle m}$ .

On peut calculer les ensembles ${\displaystyle P[i,j]}$ par récurrence sur ${\displaystyle |j-i|}$ .

• Cas de base : ${\displaystyle P[i,i]}$ est l'ensemble des non-terminaux ${\displaystyle N}$ tel que ${\displaystyle N\rightarrow m[i]}$ est une règle de la grammaire.
• Cas récursif : Si ${\displaystyle i<j}$ , ${\displaystyle P[i,j]}$ est l'ensemble des non-terminaux ${\displaystyle N}$ tels qu'il existe une règle ${\displaystyle N\rightarrow BC}$ où ${\displaystyle B}$ et ${\displaystyle C}$ sont des non-terminaux et un entier ${\displaystyle k\in \{i,\dots ,j-1\}.}$ tels que ${\displaystyle B}$ est dans ${\displaystyle P[i,k]}$ et ${\displaystyle C}$ est dans ${\displaystyle P[k+1,j]}$ .

La figure à droite montre le cas de base et le cas récursif.

On en déduit un algorithme de programmation dynamique qui calcule tous les ensembles ${\displaystyle P[i,j]}$ . Le mot ${\displaystyle m}$ est engendré par la grammaire si et seulement si ${\displaystyle S}$ est dans ${\displaystyle P[1,|m|]}$ où ${\displaystyle S}$ est l'axiome de la grammaire et ${\displaystyle |m|}$ est la longueur du mot ${\displaystyle m}$ .

Considérons la grammaire suivante en forme normale de Chomsky :

${\displaystyle {\begin{array}{lcl}{\mathit {S}}&\to &{\mathit {GN}}\;{\mathit {GV}}\\{\mathit {GV}}&\to &{\mathit {GV}}\;{\mathit {C}}\\{\mathit {GV}}&\to &{\mathit {V}}\;{\mathit {GN}}\\{\mathit {GV}}&\to &{\textit {mange}}\\{\mathit {C}}&\to &{\mathit {P}}\;{\mathit {GN}}\\{\mathit {GN}}&\to &{\mathit {Det}}\;{\mathit {N}}\\{\mathit {GN}}&\to &{\textit {elle}}\\{\mathit {V}}&\to &{\textit {mange}}\\{\mathit {P}}&\to &{\textit {avec}}\\{\mathit {N}}&\to &{\textit {poisson}}\\{\mathit {N}}&\to &{\textit {fourchette}}\\{\mathit {Det}}&\to &{\textit {du}}\\{\mathit {Det}}&\to &{\textit {une}}\end{array}}.}$

où l'ensemble des non-terminaux est ${\displaystyle \{S,GV,C,GN,V,P,N,Det\}.}$ et l'ensemble des terminaux (lettres) est ${\displaystyle \{elle,poisson,fourchette,mange,du,avec,une\}.}$ . Ici, « elle » s'appelle une lettre (bien que ce soit un mot) et une phrase comme « elle mange du poisson avec une fourchette » s'appelle un mot.

Maintenant, analysons le mot ${\displaystyle m}$ qui est la phrase « elle mange du poisson avec une fourchette » avec l'algorithme CYK. Dans la table suivante, on indique les valeurs de ${\displaystyle P[i,j]}$  :

Le mot « elle mange du poisson avec une fourchette » est reconnu car l'axiome ${\displaystyle S}$ est dans ${\displaystyle P[1,7]}$ .

Voici un pseudo-code inspiré de l'analyse de la section précédente :

Pour i = 1 à ${\displaystyle |m|}$     ${\displaystyle P[i,i]}$  := ensemble des non-terminaux ${\displaystyle N}$  tel que ${\displaystyle N\rightarrow m[i]}$  est une règle de la grammairePour d = 1 à ${\displaystyle |m|-1}$     Pour i = 1 à ${\displaystyle |m|}$ -d         j := i+d         ${\displaystyle P[i,j]}$  := ensemble des non-terminaux ${\displaystyle N}$  tels qu'il existe une règle ${\displaystyle N\rightarrow BC}$  et un entier ${\displaystyle k\in \{i,\dots ,j-1\}.}$  tels que                                ${\displaystyle B}$  est dans ${\displaystyle P[i,k]}$  et ${\displaystyle C}$  est dans ${\displaystyle P[k+1,j]}$ Retourne oui si ${\displaystyle S}$  est dans ${\displaystyle P[1,|m|]}$  ; non sinon.

On peut donner un pseudo-code qui montre la complexité cubique en ${\displaystyle |m|}$  :

Pour i = 1 à ${\displaystyle |m|}$     ${\displaystyle P[i,i]}$  := ensemble des non-terminaux ${\displaystyle N}$  tel que ${\displaystyle N\rightarrow m[i]}$  est une règle de la grammairePour d = 1 à ${\displaystyle |m|-1}$     Pour i = 1 à ${\displaystyle |m|}$ -d         j := i+d         ${\displaystyle P[i,j]}$  := ensemble vide         Pour tout k = i à j-1                  Pour tout ${\displaystyle B}$  est dans ${\displaystyle P[i,k]}$  et ${\displaystyle C}$  est dans ${\displaystyle P[k+1,j]}$                             Pour tout non-terminal ${\displaystyle N}$  tel que ${\displaystyle N\rightarrow BC}$  est une règle                                  Ajouter ${\displaystyle N}$  à ${\displaystyle P[i,j]}$ Retourne oui si ${\displaystyle S}$  est dans ${\displaystyle P[1,|m|]}$  ; non sinon.

Si la grammaire est pondérée, l'algorithme de CYK permet de générer l'arbre le plus lourd qui engendre la phrase^[7],[8].

La restriction qui consiste à avoir une grammaire en forme normale de Chomsky est essentiellement esthétique et Lange et Leiß ^[9] discutent une variante de l'algorithme CYK avec des restrictions plus faibles.

L'algorithme CYK est en ${\displaystyle \Theta (|m|^{3}\cdot |G|)}$ , où ${\displaystyle |m|}$ est la longueur du mot à analyser et ${\displaystyle |G|}$ est la taille de la grammaire en forme normale de Chomsky. Valiant^[10] donne une extension de l'algorithme CYK en ${\displaystyle O(|m|^{2,81}\cdot |G|)}$ en adaptant l'algorithme de Strassen sur les matrices.

En utilisant l'algorithme de Coppersmith-Winograd^[11] pour multiplier les matrices, on atteint une complexité asymptotique de ${\displaystyle O(|m|^{2,38}\cdot |G|)}$ . Mais la constante cachée dans la notation grand O fait que l'algorithme n'a pas d'intérêt en pratique^[12]. La dépendance sur un algorithme efficace pour multiplier des matrices ne peut pas être évitée dans le sens suivant : Lee^[13] a montré que l'on peut construire un algorithme pour multiplier des matrices 0-1 de taille ${\displaystyle (n\times n)}$ en temps ${\displaystyle O(n^{3-\varepsilon /3})}$ à partir d'un analyseur pour des grammaires non contextuelles en ${\displaystyle O(|m|^{3-\varepsilon }\cdot |G|)}$ .

• Une démonstration de l'algorithme CYK en Javascript
• Une autre démonstration de l'algorithme CYK en JavaScript
• Applet de l'université de Leipzig (site en allemand)
• Un exerciseur pour générer des exemples pour l'algorithme CYK
• Exemple d'implémentation en Python