L'algorithme de Cocke-Younger-Kasami (CYK, ou CKY) est un algorithme d'analyse syntaxique pour les grammaires hors contexte en informatique. 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 utilise une analyse ascendante et la programmation dynamique pour déterminer si une chaîne donnée peut être générée par une grammaire donnée, et il peut également construire des arbres syntaxiques. Sa complexité temporelle dans le pire des cas est O(n^3 · |G|), où n est la longueur de la chaîne d'entrée et |G| est la taille de la grammaire en forme normale de Chomsky, ce qui en fait l'un des algorithmes d'analyse les plus efficaces en termes de complexité asymptotique dans le pire des cas, bien que d'autres algorithmes puissent avoir de meilleures performances moyennes en pratique.
L'algorithme CYK est largement utilisé en traitement du langage naturel et dans la conception de compilateurs, où l'analyse syntaxique est une étape fondamentale. Il est particulièrement apprécié pour sa simplicité et son temps polynomial garanti, même pour les grammaires ambiguës. La dépendance de l'algorithme à la programmation dynamique lui permet de traiter systématiquement toutes les analyses possibles, ce qui est utile dans des applications telles que l'analyse syntaxique dans les langages de programmation et l'analyse syntaxique dans les systèmes d'intelligence artificielle.
Contexte historique
L'algorithme a été décrit pour la première fois par Itiroo Sakai en 1961, mais il a gagné en importance grâce à des redécouvertes indépendantes par John Cocke, Daniel Younger et Tadao Kasami à la fin des années 1960. Jacob T. Schwartz a également contribué à son développement. Le nom de l'algorithme reflète ces redécouvertes, l'acronyme CYK étant dérivé de Cocke, Younger et Kasami. L'algorithme est devenu un sujet standard dans l'enseignement de l'informatique, en particulier dans les cours sur les langages formels et la théorie des automates. Son développement précède les approches modernes d'analyse basées sur le apprentissage automatique et les réseaux de neurones, mais il reste pertinent en tant que technique fondamentale.
Forme standard : forme normale de Chomsky
La version standard de l'algorithme CYK exige que la grammaire hors contexte soit en forme normale de Chomsky (CNF). En CNF, toutes les règles de production sont de la forme A → BC (où B et C sont des non-terminaux) ou A → α (où α est un symbole terminal). De plus, le symbole de départ S peut avoir une production S → ε pour permettre la chaîne vide. Toute grammaire hors contexte qui ne génère pas la chaîne vide peut être transformée en une grammaire CNF équivalente, comme l'a montré Sipser en 1997. Cette transformation est algorithmique et préserve le langage généré par la grammaire. L'exigence de CNF simplifie le processus d'analyse car elle limite les façons dont une sous-chaîne peut être divisée en deux parties, permettant une programmation dynamique efficace.
Description de l'algorithme
L'algorithme CYK fonctionne en remplissant un tableau tridimensionnel P[l, s, v], où l est la longueur d'une sous-chaîne, s est la position de départ de cette sous-chaîne, et v est un non-terminal. L'entrée P[l, s, v] est définie sur vrai si la sous-chaîne de longueur l commençant à la position s peut être dérivée du non-terminal R_v. L'algorithme procède par ordre croissant de longueur de sous-chaîne, en commençant par la longueur 1.
Pour chaque sous-chaîne de longueur 1, l'algorithme vérifie les productions unitaires de la forme R_v → a_s, où a_s est le terminal à la position s. Pour les sous-chaînes de longueur 2 ou plus, il considère chaque partition possible de la sous-chaîne en deux parties, et pour chaque production A → BC, il vérifie si la première partie peut être dérivée de B et la seconde partie de C. Si c'est le cas, il marque la sous-chaîne comme dérivable de A. L'algorithme maintient également un tableau de pointeurs arrière pour permettre la reconstruction des arbres syntaxiques.
À la fin, la chaîne d'entrée est reconnue comme membre du langage si P[n, 1, 1] est vrai, ce qui signifie que le symbole de départ R_1 peut dériver la chaîne entière. Les pointeurs arrière peuvent ensuite être utilisés pour construire tous les arbres syntaxiques possibles.
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
- N → fish
- Det → the
Cette grammaire peut analyser des phrases comme "she eats the fish with the fork". L'algorithme CYK remplirait le tableau en marquant d'abord les sous-chaînes d'un seul mot : "she" comme NP, "eats" comme VP ou V, "the" comme Det, "fish" comme N, "with" comme P, et "fork" comme N. Ensuite, il combine les sous-chaînes : "the fish" comme NP (Det N), "eats the fish" comme VP (V NP), et ainsi de suite. Finalement, il détermine que la phrase entière peut être dérivée de S, et les pointeurs arrière révèlent la structure de l'arbre syntaxique.
Applications et importance
L'algorithme CYK est important dans la théorie et la pratique de l'analyse syntaxique. Il est utilisé en traitement du langage naturel pour l'analyse syntaxique, dans la conception de compilateurs pour analyser les langages de programmation, et en bioinformatique pour la prédiction de la structure secondaire de l'ARN. Sa complexité temporelle dans le pire des cas de O(n^3) est optimale pour l'analyse générale des grammaires hors contexte dans le pire des cas, bien que des algorithmes spécialisés comme l'algorithme d'Earley puissent être plus efficaces pour certaines grammaires. L'approche de programmation dynamique de l'algorithme le rend également adapté aux grammaires ambiguës, car il peut énumérer toutes les analyses possibles. Dans l'intelligence artificielle moderne, l'algorithme CYK a été adapté pour une utilisation avec des grammaires hors contexte probabilistes et l'analyse statistique, où il calcule l'arbre syntaxique le plus probable étant donné une distribution de probabilité sur les productions.
Limitations et extensions
Une limitation de l'algorithme CYK standard est son exigence de CNF, qui peut augmenter la taille de la grammaire et affecter l'efficacité. Des extensions existent pour les grammaires qui ne sont pas en CNF, comme l'algorithme d'Earley, qui gère directement les grammaires hors contexte arbitraires. De plus, l'algorithme CYK a été étendu pour gérer les grammaires pondérées et probabilistes, où chaque production a un poids ou une probabilité, et l'objectif est de trouver l'analyse avec le poids ou la probabilité maximale. Ces extensions sont utilisées en reconnaissance vocale et en traduction automatique. L'algorithme constitue également la base de techniques d'analyse plus avancées dans les modèles basés sur le apprentissage profond, bien que ceux-ci utilisent souvent des approches par réseaux de neurones plutôt que des règles grammaticales explicites.