Cocke-Younger-Kasami algoritme

I teoretisk datalogi og sprogteori er algoritmen Cocke-Younger-Kasami ( CYK ) en algoritme til analyse af kontekstfri grammatik , udgivet af Itiroo Sakai i 1961 for at afgøre, om et ord genereres af en grammatik, og i bekræftende fald at give et syntaks træ . Algoritmen er opkaldt efter de tre personer, der uafhængigt genopdagede den, J. Cocke, hvis artikel aldrig blev offentliggjort, DH Younger og T. Kasami, der offentliggjorde en intern rapport hos US-AirForce.

Algoritmen fungerer ved bottom-up-analyse og anvender dynamisk programmering . Algoritmen antager, at grammatikken er i Chomsky normal form . Denne begrænsning er ikke et problem, da enhver ikke-kontekstuel grammatik indrømmer en ækvivalent Chomsky normal form grammatik. Den beregning tid af denne algoritme er i , hvor er længden af ordet , der skal analyseres, og er på størrelse med grammatikken. O(|m|3⋅|G|){\ displaystyle O (| m | ^ {3} \ cdot | G |)}|m|{\ displaystyle | m |}m{\ displaystyle m}|G|{\ displaystyle | G |}

Princip

Uden tab af generalitet antager vi, at grammatikken ikke genererer det tomme ord . Vi kan således antage, at grammatikken er i Chomsky-normalform, og at den ikke indeholder nogen formregler (vi taler om korrekt grammatik, se ikke-kontekstuel grammatik ). G{\ displaystyle G}ϵ{\ displaystyle \ epsilon}G{\ displaystyle G}IKKE→ϵ{\ displaystyle N \ rightarrow \ epsilon}

Eller et ord uden ord at analysere. Algoritmen anvender dynamisk programmering. Delproblemerne er: er det sæt ikke-terminaler, der genererer ordet for alle sådan, hvor hvor længden af ​​ordet er . m{\ displaystyle m}P[jeg,j]{\ displaystyle P [i, j]}m[jeg..j]{\ displaystyle m [i..j]}jeg,j{\ displaystyle i, j}1≤jeg≤j≤|m|{\ displaystyle 1 \ leq i \ leq j \ leq | m |}|m|{\ displaystyle | m |}m{\ displaystyle m}

Vi kan beregne sætene ved induktion på . P[jeg,j]{\ displaystyle P [i, j]}|j-jeg|{\ displaystyle | ji |}

• Basissag: er det sæt ikke-terminaler , der er en grammatikregel.P[jeg,jeg]{\ displaystyle P [i, i]}IKKE{\ displaystyle N}IKKE→m[jeg]{\ displaystyle N \ rightarrow m [i]}
• Rekursivt tilfælde: Hvis , er sættet af ikke-terminaler sådan, at der er en regel, hvor og er ikke-terminaler, og et helt tal , der er i og er i .jeg<j{\ displaystyle i <j}P[jeg,j]{\ displaystyle P [i, j]}IKKE{\ displaystyle N}IKKE→BVS{\ displaystyle N \ rightarrow BC}B{\ displaystyle B}VS{\ displaystyle C}k∈{jeg,...,j-1}.{\ displaystyle k \ in \ {i, \ prikker, j-1 \}.}B{\ displaystyle B}P[jeg,k]{\ displaystyle P [i, k]}VS{\ displaystyle C}P[k+1,j]{\ displaystyle P [k + 1, j]}

Figuren til højre viser basissagen og den rekursive sag.

Vi udleder en dynamisk programmeringsalgoritme, der beregner alle sætene . Ordet genereres af grammatikken, hvis og kun hvis det er i, hvor grammatikens aksiom er og er længden af ​​ordet . P[jeg,j]{\ displaystyle P [i, j]}m{\ displaystyle m}S{\ displaystyle S}P[1,|m|]{\ displaystyle P [1, | m |]}S{\ displaystyle S}|m|{\ displaystyle | m |}m{\ displaystyle m}

Eksempel

Overvej følgende grammatik i Chomsky normal form:

S→GIKKEGVGV→GVVSGV→VGIKKEGV→spiseVS→PGIKKEGIKKE→DetIKKEGIKKE→detV→spiseP→medIKKE→fiskIKKE→gaffelDet→afDet→-en.{\ displaystyle {\ begin {array} {lcl} {\ mathit {S}} & \ til & {\ mathit {GN}} \; {\ mathit {GV}} \\ {\ mathit {GV}} & \ til & {\ mathit {GV}} \; {\ mathit {C}} \\ {\ mathit {GV}} & \ til & {\ mathit {V}} \; {\ mathit {GN}} \\ { \ mathit {GV}} & \ til & {\ textit {mange}} \\ {\ mathit {C}} & \ til & {\ mathit {P}} \; {\ mathit {GN}} \\ {\ matematik {GN}} & \ til & {\ mathit {Det}} \; {\ mathit {N}} \\ {\ mathit {GN}} & \ til & {\ textit {elle}} \\ {\ mathit {V}} & \ til & {\ textit {mange}} \\ {\ mathit {P}} & \ til & {\ textit {med}} \\ {\ mathit {N}} & \ til & {\ textit {fish}} \\ {\ mathit {N}} & \ to & {\ textit {fork}} \\ {\ mathit {Det}} & \ to & {\ textit {du}} \\ {\ mathit {Det}} & \ to & {\ textit {a}} \ end {array}}.}

hvor sættet af ikke-terminaler er og sættet af terminaler (bogstaver) er . Her kaldes "hun" et bogstav (selvom det er et ord), og en sætning som "hun spiser fisk med en gaffel" kaldes et ord. {S,GV,VS,GIKKE,V,P,IKKE,Det}.{\ displaystyle \ {S, GV, C, GN, V, P, N, Det \}.}{elle,sojegssoikke,fourvs.hette,mpåikkege,du,påvevs.,uikkee}.{\ displaystyle \ {hun, fisk, gaffel, spiser, fra, med, en \}.}

Lad os nu analysere ordet, som er sætningen "hun spiser fisk med en gaffel" med CYK-algoritmen. I den følgende tabel angiver vi værdierne for  : m{\ displaystyle m}P[jeg,j]{\ displaystyle P [i, j]}

P [1, 7] = {S}
P [1, 6] = ø	P [2, 7] = {GV}
P [1, 5] = ø	P [2, 6] = ø	P [3, 7] = ø
P [1, 4] = S	P [2, 5] = ø	P [3, 6] = ø	P [4, 7] = ø
P [1, 3] = ø	P [2, 4] = {GV}	P [3, 5] = ø	P [4, 6] = ø	P [5, 7] = {C}
P [1, 2] = {S}	P [2, 3] = ø	P [3, 4] = {GN}	P [4, 5] = ø	P [5, 6] = ø	P [6, 7] = {GN}
P [1, 1] = {GN}	P [2, 2] = {V, GV}	P [3, 3] = {Det}	P [4, 4] = {N}	P [5, 5] = {P}	P [6, 6] = {Det}	P [7, 7] = {N}
det	spise	af	fisk	med	-en	gaffel

Ordet "hun spiser fisk med en gaffel" genkendes, fordi aksiomet er i . S{\ displaystyle S}P[1,7]{\ displaystyle P [1,7]}

Pseudokode

Her er en pseudokode inspireret af analysen i det foregående afsnit:

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

Vi kan give en pseudokode, der viser den kubiske kompleksitet ved at  : |m|{\ displaystyle | m |}

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

Diskussioner

Vægtede grammatikker

Hvis grammatikken vægtes , gør CYK-algoritmen det muligt at generere det tungeste træ, der genererer sætningen.

Interesse for Chomskys normale formatering

Begrænsningen af ​​at have en grammatik i Chomskys normale form er primært æstetisk, og Lange og Leiß diskuterer en variant af CYK-algoritmen med svagere begrænsninger.

Forbindelse med matrixmultiplikation

CYK-algoritmen er i , hvor er længden af ​​ordet, der skal analyseres, og er størrelsen på Chomskys normale formgrammatik. Valiant giver en udvidelse af CYK algoritme ved at tilpasse Strassen 's algoritme til de matricer . Θ(|m|3⋅|G|){\ displaystyle \ Theta (| m | ^ {3} \ cdot | G |)}|m|{\ displaystyle | m |}|G|{\ displaystyle | G |}O(|m|2,81⋅|G|){\ displaystyle O (| m | ^ {2.81} \ cdot | G |)}

Ved hjælp af Coppersmith-Winograd-algoritmen til at multiplicere matricerne når vi en asymptotisk kompleksitet af . Men konstanten skjult i den store O-notation betyder, at algoritmen ikke har nogen interesse i praksis. Afhængigheden af ​​en effektiv algoritme til at multiplicere matricer kan ikke undgås i følgende forstand: Lee viste, at man kan opbygge en algoritme til at multiplicere 0-1 matricer af størrelse i tid fra en analysator til ikke-kontekstuelle grammatikker i . O(|m|2,38⋅|G|){\ displaystyle O (| m | ^ {2,38} \ cdot | G |)}(ikke×ikke){\ displaystyle (n \ gange n)}O(ikke3-ε/3){\ displaystyle O (n ^ {3- \ varepsilon / 3})}O(|m|3-ε⋅|G|){\ displaystyle O (| m | ^ {3- \ varepsilon} \ cdot | G |)}

Demonstrationer

• En demonstration af CYK-algoritmen i Javascript
• Endnu en demonstration af CYK-algoritmen i JavaScript
• University of Leipzig applet (side på tysk)
• En træner til at generere eksempler til CYK-algoritmen
• Eksempel på implementering i Python

Noter og referencer

1. (i) Itiroo Sakai, "Syntaks i universel oversættelse" i 1961 International Conference on maskinoversættelse af sprog og Anvendt Sprog Analyse, Teddington, England , vol.  II, London, Hendes Majestæts Papir,1962, s.  593-608.
2. (i) Dick Grune, teknisk Parsing: en praktisk vejledning , New York, Springer,2008, 2 nd  ed. ( ISBN  978-0-387-20248-8 ) , s.  579.
3. Ifølge Hopcroft, Motwani og Ullman er J. Cockes arbejde, selvom det er blevet cirkuleret privat, aldrig blevet offentliggjort.
4. DH Yngre, “  Anerkendelse og parsing af kontekstfrie sprog i tid n 3  ”, Information and Control , bind.  10, nr .  21967, s.  189-208.
5. T. Kasami, “  En effektiv algoritme til anerkendelse og syntaksanalyse for kontekstfrie sprog  ”, Science Report AFCRL-65-758 , Bedford, Mass., Air Force Cambridge Research Laboratory,1965.
6. (in) Sipser, Michael, Introduction to Theory of Computation (1. udgave) ,1997( ISBN  978-0-534-94728-6 ).
7. Víctor M. Jiménez og Andrés Marzal, ”  Beregning af de N bedste parse-træer til vægtede og stokastiske kontekstfrie grammatikker  ”, fremskridt inden for mønstergenkendelse , Springer Science + Business Media,2000, s.  183-192 ( ISBN  978-3-540-67946-2 , ISSN  0302-9743 , DOI  10.1007 / 3-540-44522-6_19 , læs online ).
8. Xian Chen, "  Vægtet-CYK-probabilistisk-kontekst-fri-grammatik,  " på GitHub ,marts 2015.
9. Martin Lange, Hans Leiss, ”  At CNF eller ikke at CNF? En effektiv og alligevel præsentabel version af CYK-algoritmen  ”, Informatica Didactica 8, 2009.
10. “  Generel kontekstfri anerkendelse på mindre end kubisk tid  ” på www.sciencedirect.com ( DOI  10.1016 / S0022-0000 (75) 80046-8 , adgang 29. december 2015 ) .
11. Don Coppersmith og Shmuel Winograd . Matrixmultiplikation via aritmetiske progressioner. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing , side 1–6, 1987.
12. (i) Donald Knuth, The Art of Computer Programming Bind 2: Seminumerical Algoritmer (3rd ed.). Addison-Wesley Professional. s. 501. , Reading (Mass.), Addison-Wesley, 762  s. ( ISBN  978-0-201-89684-8 , note BNF n o  FRBNF37532795 ).
13. Lillian Lee , "  Hurtig kontekstfri grammatik-parsing kræver hurtig boolsk matrixmultiplikation,  " J. ACM , bind.  49,1 st januar 2002, s.  1–15 ( ISSN  0004-5411 , DOI  10.1145 / 505241.505242 , læst online , adgang 29. december 2015 ).

Bibliografi

Algoritmen eksponeres i de teoretiske værker om formelle sprog.

• Alfred Aho, Monica Lam, Ravi Sethi og Jeffrey Ullman, Compilers: principper, teknikker og værktøjer: med mere end 200 øvelser , Paris, Pearson,2007, 2 nd  ed. , 928  s. ( ISBN  978-2-7440-7037-2 og 2744070378 , meddelelse BNF n o  FRBNF41172860 ) - Øvelse 4.4.9 i Dragon book .
• (de) Katrin Erk og Lutz Priese, Theoretische Informatik: Eine umfassende Einführung , Berlin, Springer,2008, 485  s. ( ISBN  978-3-540-76319-2 , OCLC  244015158 ) - 6.8.1 Das Wortproblem, s.  154-159 .
• (en) Michael A. Harrison, Introduktion til formel sprogteori , læsning, masse. ua, Addison-Wesley,1978, 594  s. ( ISBN  978-0-201-02955-0 , OCLC  266962302 ) - Afsnit 12.4 Cocke-Kasami-Yngre algoritme, s.  430-442 .
• (en) John E. Hopcroft, Rajeev Motwani og Jeffrey D. Ullman, Introduktion til automatteori, sprog og beregning , Addison Wesley,2001, 2 nd  ed. , 521  s. ( ISBN  978-0-201-44124-6 og 0201441241 ) - Afsnit 7.4.4 Test af medlemskab i en CFL, s.  298-304 .
• (en) Peter Linz, en introduktion til formelle sprog og automatisering , Jones & Bartlett Learning,2001, 410  s. ( ISBN  978-0-7637-1422-2 og 0763714224 ) - Afsnit 6.3 En medlemsalgoritme for kontekstfri grammatikker, s.  172-174 .
• (en) Jeffrey Shallit, et andet kursus i formelle sprog og automatteori , Cambridge University Press,2009, 240  s. ( ISBN  978-0-521-86572-2 og 0521865727 ) - Afsnit 5.1 Anerkendelse og parsing i generelle grammatikker s.   141-144

Se også

• Earley analyse
• Skjult Markov-model
• Færdig automat
• Teori om automata
• Probabilistisk algebraisk grammatik
• Viterbi-algoritme
• Dynamisk programmering
• Bioinformatik
• Automatisk talegenkendelse

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">