L'analyse CKY (également appelée CYK, pour Cocke-Younger-Kasami) est un algorithme d'analyse syntaxique pour les grammaires hors contexte qui utilise l'analyse ascendante et la programmation dynamique. Il a été publié pour la première fois par Itiroo Sakai en 1961, puis redécouvert indépendamment par John Cocke, Daniel Younger, Tadao Kasami et Jacob T. Schwartz, dont il porte le nom. L'algorithme détermine si une chaîne donnée peut être générée par une grammaire et, si c'est le cas, peut construire tous les arbres d'analyse possibles pour cette chaîne.
La version standard de CKY ne fonctionne que sur les grammaires hors contexte en forme normale de Chomsky (CNF), où chaque règle de production est soit de la forme A → BC (deux non-terminaux), soit A → a (un terminal). Toute grammaire hors contexte qui ne génère pas la chaîne vide peut être transformée algorithmiquement en une grammaire CNF équivalente, donc cette restriction ne limite pas l'applicabilité de l'algorithme en principe. Pour les grammaires qui génèrent la chaîne vide, on peut explicitement autoriser une règle S → ε, où S est le symbole de départ.
L'importance de l'analyse CKY découle de sa complexité temporelle dans le pire cas de O(n^3 · |G|), où n est la longueur de la chaîne d'entrée et |G| est la taille de la grammaire CNF. Cela en fait l'un des algorithmes d'analyse les plus efficaces en termes de comportement asymptotique dans le pire cas, bien que d'autres algorithmes puissent avoir de meilleurs temps d'exécution moyens dans des scénarios pratiques.
Aperçu de l'algorithme
L'algorithme fonctionne en remplissant un tableau tridimensionnel P[l, s, v], où chaque entrée est une valeur booléenne indiquant si la sous-chaîne de longueur l commençant à la position s peut être générée à partir du non-terminal R_v. Le tableau est rempli par ordre croissant de longueur de sous-chaîne, en commençant par les sous-chaînes de longueur 1.
Pour chaque symbole terminal de l'entrée, l'algorithme vérifie toutes les productions unitaires de la forme R_v → a_s et marque les entrées correspondantes du tableau comme vraies. Pour les sous-chaînes plus longues, il considère chaque partition possible de la sous-chaîne en deux parties et vérifie s'il existe une production A → BC telle que B génère la première partie et C génère la seconde partie. Si une telle production existe, l'entrée pour A est définie sur vrai.
Pseudo-code
soit l'entrée une chaîne I composée de n caractères : a1 ... an.
soit la grammaire contenant r symboles non-terminaux R1 ... Rr, avec le symbole de départ R1.
soit P[n,n,r] un tableau de booléens. Initialiser tous les éléments de P à faux.
soit back[n,n,r] un tableau de listes de triplets de retour. Initialiser tous les éléments de back à la liste vide.
pour chaque s = 1 à n
pour chaque production unitaire Rv → as
définir P[1,s,v] = vrai
pour chaque l = 2 à n -- Longueur de la portée
pour chaque s = 1 à n-l+1 -- Début de la portée
pour chaque p = 1 à l-1 -- Partition de la portée
pour chaque production Ra → Rb Rc
si P[p,s,b] et P[l-p,s+p,c] alors
définir P[l,s,a] = vrai,
ajouter <p,b,c> à back[l,s,a]
si P[n,1,1] est vrai alors
I est membre du langage
retourner back -- en retraçant les étapes à travers back, on peut facilement construire tous les arbres d'analyse possibles de la chaîne.
sinon
retourner "pas membre du langage"
Exemple
Considérons la grammaire suivante en CNF :
S → NP VP
VP → VP PP
VP → V NP
VP → eats
PP → P NP
NP → Det N
NP → she
V → eats
P → with
Det → the
N → fish
Pour analyser la chaîne "she eats the fish with the fish", l'algorithme marque d'abord toutes les sous-chaînes de longueur 1. Par exemple, P[1,1,NP] est défini sur vrai car NP → she, et P[1,2,VP] est défini sur vrai car VP → eats. Ensuite, il traite les sous-chaînes de longueur 2, comme "she eats", qui peut être dérivée comme S → NP VP, donc P[2,1,S] devient vrai. Le processus continue pour les sous-chaînes plus longues, en considérant toutes les partitions. À la fin, si P[n,1,S] est vrai, la chaîne est reconnue comme faisant partie du langage, et les pointeurs de retour permettent la reconstruction de l'arbre d'analyse.
Applications et variantes
L'analyse CKY est largement utilisée dans le traitement du langage naturel et la linguistique computationnelle, en particulier pour l'analyse avec des grammaires hors contexte probabilistes. Des variantes de l'algorithme ont été développées pour gérer les grammaires pondérées et améliorer les performances en moyenne. L'approche de programmation dynamique de l'algorithme le relie également à d'autres méthodes d'analyse, comme l'analyseur Earley, qui gère les grammaires hors contexte arbitraires sans conversion CNF mais a une complexité dans le pire cas similaire.
Dans les systèmes modernes d'Artificial intelligence, l'analyse CKY a été largement supplantée par des approches basées sur les Neural network, en particulier les modèles Transformer (architecture) utilisés dans les Large language model. Cependant, l'algorithme reste une technique fondamentale importante dans la théorie des langages formels et est toujours enseigné dans les programmes d'informatique. Ses principes de programmation dynamique et d'analyse ascendante apparaissent également dans d'autres domaines, comme les modèles Sequence-to-Sequence (Seq2Seq) et le décodage Beam Search.
L'efficacité et la clarté de l'algorithme en ont fait un exemple standard dans les manuels sur l'analyse syntaxique et le Machine learning. Des institutions de recherche comme MIT CSAIL et Stanford AI Lab ont contribué à son étude et à son application, et il reste pertinent dans les domaines qui nécessitent une analyse exacte de données structurées, comme la bioinformatique et la conception de compilateurs.
Limitations
L'analyse CKY nécessite que la grammaire soit en forme normale de Chomsky, ce qui peut augmenter le nombre de règles de production et la taille de la grammaire. La complexité temporelle dans le pire cas de O(n^3) peut être prohibitive pour des chaînes d'entrée très longues, surtout dans les applications en temps réel. De plus, la complexité spatiale de l'algorithme est O(n^2 · r), ce qui peut être important pour les grammaires avec de nombreux non-terminaux. Malgré ces limitations, l'analyse CKY reste une référence pour les algorithmes d'analyse exacte et un concept clé dans l'étude des langages hors contexte.