Algorytm Cocke-Younger-Kasami

W teoretycznej informatyki i teorii języka The algorytm Cocke-Younger-Kasami ( cyk ) jest algorytm do analizowania dla gramatyk bezkontekstowych , opublikowane przez Itiroo Sakai w 1961 roku w celu ustalenia, czy słowo jest generowane przez gramatyki, a jeżeli tak, aby dać drzewo składni . Algorytm został nazwany na cześć trzech osób, które niezależnie go odkryły, J. Cocke, którego artykuł nigdy nie został opublikowany, DH Youngera i T. Kasami, którzy opublikowali wewnętrzny raport w US-AirForce.

Algorytm działa na zasadzie analizy oddolnej i wykorzystuje programowanie dynamiczne . Algorytm zakłada, że ​​gramatyka jest w normalnej postaci Chomsky'ego . To ograniczenie nie stanowi problemu, ponieważ każda gramatyka niekontekstowa dopuszcza równoważną gramatykę postaci normalnej Chomsky'ego. Czas obliczania tego algorytmu jest w , gdzie jest długością słowa do analizy i jest rozmiarem gramatyki. O(|m|3⋅|sol|){\ Displaystyle O (| m | ^ {3} \ cdot | G |)}|m|{\ displaystyle | m |}m{\ displaystyle m}|sol|{\ displaystyle | G |}

Zasada

Bez utraty ogólności zakładamy, że gramatyka nie generuje pustego słowa . Zatem możemy założyć, że gramatyka jest w normalnej formie Chomsky'ego i nie zawiera żadnych reguł dotyczących formy (mówimy o gramatyce właściwej, patrz gramatyka bezkontekstowa ). sol{\ displaystyle G}ϵ{\ displaystyle \ epsilon}sol{\ displaystyle G}NIE→ϵ{\ Displaystyle N \ rightarrow \ epsilon}

Lub niepuste słowo do analizy. Algorytm wykorzystuje programowanie dynamiczne. Podproblemy to: jest zbiorem nieterminali, które generują słowo dla wszystkich takich, gdzie gdzie jest długością słowa . m{\ displaystyle m}P.[ja,jot]{\ displaystyle P [i, j]}m[ja..jot]{\ Displaystyle m [i..j]}ja,jot{\ displaystyle i, j}1≤ja≤jot≤|m|{\ Displaystyle 1 \ równoważnik ja \ równoważnik j \ równoważnik | m |}|m|{\ displaystyle | m |}m{\ displaystyle m}

Możemy obliczyć zbiory przez indukcję . P.[ja,jot]{\ displaystyle P [i, j]}|jot-ja|{\ displaystyle | ji |}

• Przypadek bazowy: jest zbiorem nieterminali , czyli regułą gramatyczną.P.[ja,ja]{\ displaystyle P [i, i]}NIE{\ displaystyle N}NIE→m[ja]{\ Displaystyle N \ rightarrow m [i]}
• Przypadek rekurencyjny: Jeśli , jest zbiorem nieterminali, takich, że istnieje reguła, w której i są nieterminalami oraz liczbą całkowitą, taką, która jest w i jest w .ja<jot{\ displaystyle i <j}P.[ja,jot]{\ displaystyle P [i, j]}NIE{\ displaystyle N}NIE→bVS{\ displaystyle N \ rightarrow BC}b{\ displaystyle B}VS{\ displaystyle C}k∈{ja,...,jot-1}.{\ Displaystyle k \ in \ {i, \ kropki, j-1 \}.}b{\ displaystyle B}P.[ja,k]{\ displaystyle P [i, k]}VS{\ displaystyle C}P.[k+1,jot]{\ displaystyle P [k + 1, j]}

Rysunek po prawej stronie przedstawia przypadek podstawowy i przypadek rekurencyjny.

Wyprowadzamy algorytm programowania dynamicznego, który oblicza wszystkie zestawy . Słowo jest generowane przez gramatykę wtedy i tylko wtedy, gdy jest tam, gdzie jest aksjomatem gramatyki i jest długością słowa . P.[ja,jot]{\ 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}

Przykład

Rozważ następującą gramatykę w normalnej formie Chomsky'ego:

S→solNIEsolVsolV→solVVSsolV→VsolNIEsolV→jeśćVS→P.solNIEsolNIE→remitNIEsolNIE→toV→jeśćP.→zNIE→rybaNIE→widelecremit→zremit→za.{\ displaystyle {\ begin {tablica} {lcl} {\ mathit {S}} i \ do & {\ mathit {GN}} \; {\ mathit {GV}} \\ {\ mathit {GV}} & \ do & {\ 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 {with}} \\ {\ mathit {N}} & \ to & {\ textit {ryba}} \\ {\ mathit {N}} & \ to & {\ textit {fork}} \\ {\ mathit {Det}} & \ to & {\ textit {du}} \\ {\ mathit {Det}} & \ to & {\ textit {a}} \ end {tablica}}.}

gdzie jest zbiór nieterminali i zestaw terminali (liter) . Tutaj „ona” nazywana jest literą (chociaż jest to słowo), a wyrażenie takie jak „ona je widelcem” nazywa się słowem. {S,solV,VS,solNIE,V,P.,NIE,remit}.{\ Displaystyle \ {S, GV, C, GN, V, P, N, Det \}.}{millmi,pojassonie,faourvsgodzmittmi,mwniesolmi,reu,wvmivs,uniemi}.{\ Displaystyle \ {ona, ryba, widelec, zjada, z, za \}.}

Teraz przeanalizujmy słowo, które jest frazą „zjada rybę widelcem” za pomocą algorytmu CYK. W poniższej tabeli wskazujemy wartości  : m{\ displaystyle m}P.[ja,jot]{\ 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}
to	jeść	z	ryba	z	za	widelec

Słowo „zjada rybę widelcem” jest rozpoznawane, ponieważ aksjomat jest w środku . S{\ displaystyle S}P.[1,7]{\ displaystyle P [1,7]}

Pseudo kod

Oto pseudokod zainspirowany analizą z poprzedniej sekcji:

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.

Możemy podać pseudokod, który pokazuje sześcienną złożoność poprzez  : |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.

Dyskusje

Gramatyki ważone

Jeśli gramatyka jest ważona , algorytm CYK umożliwia wygenerowanie najcięższego drzewa, które generuje zdanie.

Zainteresowanie normalnym formatowaniem Chomsky'ego

Ograniczenie gramatyki w normalnej formie Chomsky'ego jest przede wszystkim estetyczne, a Lange i Leiß omawiają wariant algorytmu CYK ze słabszymi ograniczeniami.

Powiązanie z mnożeniem macierzy

Algorytm CYK jest w , gdzie jest długością słowa do analizy i jest rozmiarem gramatyki postaci normalnej Chomsky'ego. Valiant daje przedłużenie algorytm cyk poprzez dostosowanie STRASSEN „s algorytm na macierzach . Θ(|m|3⋅|sol|){\ Displaystyle \ Theta (| m | ^ {3} \ cdot | G |)}|m|{\ displaystyle | m |}|sol|{\ displaystyle | G |}O(|m|2,81⋅|sol|){\ Displaystyle O (| m | ^ {2.81} \ cdot | G |)}

Używając algorytmu Coppersmitha-Winograda do pomnożenia macierzy, osiągamy asymptotyczną złożoność równą . Ale stała ukryta w dużym zapisie O oznacza, że ​​algorytm nie jest interesujący w praktyce. Zależności od wydajnego algorytmu mnożenia macierzy nie można uniknąć w następującym sensie: Lee pokazał, że można zbudować algorytm mnożący w czasie macierze o wielkości 0-1 z analizatora dla gramatyk bezkontekstowych w formacie . O(|m|2,38⋅|sol|){\ Displaystyle O (| m | ^ {2,38} \ cdot | G |)}(nie×nie){\ Displaystyle (n \ razy n)}O(nie3-ε/3){\ Displaystyle O (n ^ {3- \ varepsilon / 3})}O(|m|3-ε⋅|sol|){\ Displaystyle O (| m | ^ {3- \ varepsilon} \ cdot | G |)}

Demonstracje

• Demonstracja algorytmu CYK w Javascript
• Kolejna demonstracja algorytmu CYK w JavaScript
• Aplet Uniwersytetu w Lipsku (strona w języku niemieckim)
• Ćwiczenie do generowania przykładów dla algorytmu CYK
• Przykład implementacji w Pythonie

Uwagi i odniesienia

1. (w) Itiroo Sakai, „Składnia w tłumaczeniu uniwersalnym” w 1961 r. Międzynarodowa konferencja na temat tłumaczenia maszynowego języków i stosowanej analizy językowej, Teddington, Anglia , t.  II, Londyn, Her Majesty's Stationery Office,1962, s.  593-608.
2. (w) Dick Grune, analiza techniczna: praktyczny przewodnik , Nowy Jork, Springer,2008, 2 II  wyd. ( ISBN  978-0-387-20248-8 ) , s.  579.
3. Według Hopcrofta, Motwaniego i Ullmana praca J. Cocke, mimo iż była rozpowszechniana prywatnie, nigdy nie została opublikowana.
4. DH Younger, „  Rozpoznawanie i analizowanie języków bezkontekstowych w czasie n 3  ”, Informacje i kontrola , t.  10 N O  21967, s.  189-208.
5. T. Kasami, „  Efektywny algorytm rozpoznawania i analizy składni dla języków bezkontekstowych  ”, Raport naukowy AFCRL-65-758 , Bedford, Mass., Air Force Cambridge Research Laboratory,1965.
6. (w) Sipser, Michael, Wprowadzenie do teorii obliczeń (wyd. 1) ,1997( ISBN  978-0-534-94728-6 ).
7. Víctor M. Jiménez i Andrés Marzal, „  Computation of the N Best Parse Trees for Weighted and Stochastic Context-Free Grammars  ”, Advances in Pattern Recognition , 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 , czytaj online ).
8. Xian Chen, „  Weighted-CYK-Probabilistic-Context-Free-Grammar  ”, na GitHub ,marzec 2015.
9. Martin Lange, Hans Leiß, „  Do CNF czy nie do CNF? Efektywna, ale prezentowalna wersja algorytmu CYK  ”, Informatica Didactica 8, 2009.
10. „  Ogólne bezkontekstowe rozpoznawanie w czasie krótszym niż sześcienny  ” , na stronie www.sciencedirect.com ( DOI  10.1016 / S0022-0000 (75) 80046-8 , dostęp: 29 grudnia 2015 ) .
11. Don Coppersmith i Shmuel Winograd . Mnożenie macierzy przez progresje arytmetyczne. Materiały z XIX dorocznego sympozjum ACM na temat teorii informatyki , strony 1–6, 1987.
12. (w) Donald Knuth, The Art of Computer Programming Tom 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley Professional. p. 501. , Reading (Mass.), Addison-Wesley, 762  str. ( ISBN  978-0-201-89684-8 , uwaga BnF n o  FRBNF37532795 ).
13. Lillian Lee , „  Szybka analiza gramatyki bez kontekstu wymaga szybkiego mnożenia macierzy boolowskiej  ”, J. ACM , vol.  49,1 st styczeń 2002, s.  1-15 ( ISSN  0004-5411 , DOI  10.1145 / 505241.505242 , czytaj online , dostęp: 29 grudnia 2015 ).

Bibliografia

Algorytm jest eksponowany w pracach teoretycznych dotyczących języków formalnych.

• Alfred Aho, Monica Lam, Ravi Sethi i Jeffrey Ullman, kompilatorzy: zasady, techniki i narzędzia: z ponad 200 ćwiczeniami , Paryż, Pearson,2007, 2 II  wyd. , 928  s. ( ISBN  978-2-7440-7037-2 i 2744070378 , uwaga BnF n o  FRBNF41172860 ) - Ćwiczenie 4.4.9 z książki Dragon .
• (de) Katrin Erk and 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, Wprowadzenie do teorii języka formalnego , Reading, Mass. ua, Addison-Wesley,1978, 594,  str. ( ISBN  978-0-201-02955-0 , OCLC  266962302 ) - Część 12.4 Algorytm Cocke-Kasami-Youngera, s.  430-442 .
• (en) John E. Hopcroft, Rajeev Motwani i Jeffrey D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń , Addison Wesley,2001, 2 II  wyd. , 521  str. ( ISBN  978-0-201-44124-6 oraz 0201441241 ) - Punkt 7.4.4 Testowanie członkostwa w CFL, s.  298-304 .
• (en) Peter Linz, Wprowadzenie do języków formalnych i automatów , Jones & Bartlett Learning,2001, 410  s. ( ISBN  978-0-7637-1422-2 i 0763714224 ) - Część 6.3 Algorytm członkostwa dla gramatyk bezkontekstowych, s.  172-174 .
• (en) Jeffrey Shallit, Drugi kurs języków formalnych i teorii automatów , Cambridge University Press,2009, 240  pkt. ( ISBN  978-0-521-86572-2 i 0521865727 ) - Część 5.1 Rozpoznawanie i analiza w gramatykach ogólnych s.   141-144

Zobacz też

• Analiza Earley
• Ukryty model Markowa
• Gotowy automat
• Teoria automatów
• Gramatyka algebraiczna probabilistyczna
• Algorytm Viterbiego
• Programowanie dynamiczne
• Bioinformatyka
• Automatyczne rozpoznawanie mowy

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