Algoritmus CYK - CYK algorithm

v počítačová věda, Algoritmus Cocke – Younger – Kasami (alternativně nazývané CYKnebo CKY) je analýza algoritmus pro bezkontextové gramatiky vynalezl Ichirō Sakai.^[1] Algoritmus je pojmenován po některých svých nově objevitelích: John Cocke, Daniel Younger a Tadao Kasami. Zaměstnává to analýza zdola nahoru a dynamické programování.

Standardní verze CYK funguje pouze na bezkontextových gramatikách uvedených v Chomsky normální forma (CNF). Libovolná bezkontextová gramatika však může být transformována (po konvenci) na gramatiku CNF vyjadřující stejný jazyk (Sipser 1997 ).

Důležitost algoritmu CYK vyplývá z jeho vysoké účinnosti v určitých situacích. Použitím Velká O notace, nejhorší doba provozu CYK je ${ displaystyle { mathcal {O}} vlevo (n ^ {3} cdot vlevo | G vpravo | vpravo)}$ , kde ${ displaystyle n}$ je délka analyzovaného řetězce a ${ displaystyle left | G right |}$ je velikost gramatiky CNF ${ displaystyle G}$ (Hopcroft & Ullman 1979, str. 140). Díky tomu je jedním z nejúčinnějších algoritmů syntaktické analýzy, pokud jde o nejhorší případ asymptotická složitost, ačkoli v mnoha praktických scénářích existují jiné algoritmy s lepší průměrnou dobou chodu.

Standardní forma

The dynamické programování Algoritmus vyžaduje vykreslení bezkontextové gramatiky Chomsky normální forma (CNF), protože testuje možnosti rozdělení aktuální sekvence na dvě menší sekvence. Libovolnou bezkontextovou gramatiku, která negeneruje prázdný řetězec, lze v CNF reprezentovat pouze pomocí výrobní pravidla formulářů ${ displaystyle A rightarrow alpha}$ a ${ displaystyle A rightarrow BC}$ .

Algoritmus

Jako pseudokód

Algoritmus v pseudo kód je následující:

nechat vstup je řetězec Já skládající se z n postavy: A₁ ... A_n.nechat gramatika obsahuje r neterminální symboly R₁ ... R_r, se symbolem zahájení R₁.nechat P[n,n,r] být pole booleovců. Inicializujte všechny prvky P na falešný.pro každého s = 1 až n    pro každého jednotková výroba R_proti → A_s        soubor P[1,s,proti] = pravdapro každého l = 2 až n - Délka rozpětí    pro každého s = 1 až n-l+1 - Začátek rozpětí        pro každého str = 1 až l-1 - Rozdělení rozpětí            pro každého Výroba R_A    → R_b R_C                -li P[str,s,b] a P[l-str,s+str,C] pak soubor P[l,s,A] = pravda-li P[n,1,1] je pravda pak    Já je členem jazykajiný    Já není členem jazyka

Pravděpodobnostní CYK (pro nalezení nejpravděpodobnější analýzy)

Umožňuje obnovit nejpravděpodobnější analýzu s ohledem na pravděpodobnosti všech produkcí.

nechat vstup bude řetězec Já skládající se z n postavy: A₁ ... A_n.nechat gramatika obsahuje r neterminální symboly R₁ ... R_r, se symbolem zahájení R₁.nechat P[n,n,r] být pole reálných čísel. Inicializujte všechny prvky P na nulu.nechat zadní[n,n,r] být pole zpětně ukazujících trojic.pro každého s = 1 až n  pro každého jednotková výroba R_proti →A_s    soubor P[1,s,proti] = Pr (R_proti →A_s)pro každého l = 2 až n - Délka rozpětí  pro každého s = 1 až n-l+1 - Začátek rozpětí    pro každého str = 1 až l-1 - Rozdělení rozpětí             pro každého Výroba R_A → R_b R_C        prob_splitting = Pr (R_A →R_b R_C) * P[str,s,b] * P[l-str,s+str,C]        -li P[str,s,b]> 0 a P[l-str,s+str,C]> 0 a P[l,s,A] pak           soubor P[l,s,A] = prob_splitting soubor zadní[l,s,A] =

Jako próza

Neformálně tento algoritmus zohledňuje všechny možné podřetězce vstupního řetězce a sad ${ displaystyle P [l, s, v]}$ být pravdivý, pokud je podřetězec délky ${ displaystyle l}$ začínající od ${ displaystyle s}$ lze generovat z neterminální proměnné ${ displaystyle R_ {v}}$ . Jakmile vezme v úvahu podřetězce délky 1, přejde k podřetězcům délky 2 atd. U podřetězců délky 2 a větší zvažuje každé možné rozdělení podřetězce na dvě části a kontroluje, zda existuje nějaká výroba ${ displaystyle P až Q ; R}$ takhle ${ displaystyle Q}$ odpovídá první části a ${ displaystyle R}$ odpovídá druhé části. Pokud ano, zaznamená ${ displaystyle P}$ jako shoda s celým podřetězcem. Jakmile je tento proces dokončen, věta je gramatikou rozpoznána, pokud je podřetězec obsahující celý vstupní řetězec uzavřen počátečním symbolem.

Příklad

Analýza věty pomocí algoritmu CYK

Toto je příklad gramatiky:

{ displaystyle { begin {aligned} { ce {S}} & { ce {-> NP VP}} { ce {VP}} & { ce {-> VP PP} } { ce {VP}} & { ce {-> V NP}} { ce {VP}} & { ce {-> jí}} { ce {PP }} & { ce {-> P NP}} { ce {NP}} & { ce {-> Det N}} { ce {NP}} & { ce {-> ona}} { ce {V}} & { ce {-> jí}} { ce {P}} & { ce {-> s}} { ce {N}} & { ce {-> ryby}} { ce {N}} & { ce {-> vidlice}} { ce {Det}} & { ce {-> a}} end {zarovnáno}}}

Nyní ta věta jí vidličkou rybu je analyzována pomocí algoritmu CYK. V následující tabulce v ${ displaystyle P [i, j, k]}$ , $i$ je číslo řádku (počínaje spodní částí číslem 1) a $j$ je číslo sloupce (počínaje vlevo od 1).

CYK stůl
S
	VP

S
	VP			PP
S		NP			NP
NP	V, VP	Det.	N	P	Det	N
ona	jí	A	Ryba	s	A	Vidlička

Pro čitelnost tabulka CYK pro P je zde znázorněna jako 2-rozměrná matice M obsahující sadu neterminálních symbolů $R k$ je v ${ displaystyle M [i, j]}$ pokud, a pouze pokud, ${ displaystyle P [i, j, k]}$ .Ve výše uvedeném příkladu, protože počáteční symbol S je v ${ displaystyle M [7,1]}$ , věta může být generována gramatikou.

Rozšíření

Generování stromu analýzy

Výše uvedený algoritmus je a rozpoznávač to určí pouze to, zda je věta v jazyce. Je jednoduché jej rozšířit na a analyzátor který také konstruuje a analyzovat strom, uložením uzlů parse stromu jako prvků pole, namísto booleovské 1. Uzel je propojen s prvky pole, které byly použity k jeho vytvoření, aby se vytvořila stromová struktura. Pokud má být vytvořen pouze jeden analyzovaný strom, je v každém prvku pole potřeba pouze jeden takový uzel. Pokud však mají být zachovány všechny parsovací stromy nejednoznačné věty, je nutné uložit do prvku pole seznam všech způsobů, jak lze získat odpovídající uzel v procesu syntaktické analýzy. To se někdy děje s druhou tabulkou B [n, n, r] tzv zpětné ukazateleKonečným výsledkem je pak sdílený les možných analyzovaných stromů, kde se mezi různé analýzy analyzují společné části stromů. Tuto sdílenou doménovou strukturu lze pohodlně číst jako nejednoznačná gramatika generování pouze rozebrané věty, ale se stejnou nejednoznačností jako původní gramatika a se stejnými parsovacími stromy až po velmi jednoduché přejmenování jiných než terminálů, jak ukazuje Lang (1994).

Analýza gramatik bez kontextu bez CNF

Jak zdůraznil Lange & Leiß (2009) Nevýhodou všech známých transformací do Chomského normální formy je, že mohou vést k nežádoucímu nafouknutí ve velikosti gramatiky. Velikost gramatiky je součtem velikostí jejích produkčních pravidel, kde velikost pravidla je jedna plus délka jeho pravé strany. Použitím ${ displaystyle g}$ pro označení velikosti původní gramatiky se může v nejhorším případě zvětšit velikost ${ displaystyle g ^ {2}}$ na ${ displaystyle 2 ^ {2g}}$ , v závislosti na použitém transformačním algoritmu. Pro použití ve výuce navrhují Lange a Leiß mírné zobecnění algoritmu CYK, „aniž by byla ohrožena účinnost algoritmu, jasnost jeho prezentace nebo jednoduchost důkazů“ (Lange & Leiß 2009 ).

Analýza vážených gramatik bez kontextu

Je také možné rozšířit algoritmus CYK tak, aby analyzoval řetězce pomocí vážený a stochastické bezkontextové gramatiky. Váhy (pravděpodobnosti) jsou poté uloženy v tabulce P namísto booleanů, takže P [i, j, A] bude obsahovat minimální váhu (maximální pravděpodobnost), kterou lze podřetězec z i do j odvodit z A. Další rozšíření Algoritmus umožňuje výčet všech analýz řetězce od nejnižší po nejvyšší váhu (nejvyšší po nejnižší pravděpodobnost).

Valiantův algoritmus

The nejhorší doba provozu CYK je ${ displaystyle Theta (n ^ {3} cdot | G |)}$ , kde n je délka analyzovaného řetězce a |G| je velikost gramatiky CNF G. Díky tomu je v praxi jedním z nejúčinnějších algoritmů pro rozpoznávání obecných bezkontextových jazyků. Valiant (1975) dal rozšíření algoritmu CYK. Jeho algoritmus vypočítává stejnou analýzu jako algoritmus CYK; přesto to ukázal algoritmy pro efektivní množení z matice s 0-1 vstupy lze použít k provedení tohoto výpočtu.

Za použití Coppersmith – Winogradův algoritmus pro vynásobení těchto matic to dává asymptotickou nejhorší dobu běhu ${ displaystyle O (n ^ {2.38} cdot | G |)}$ . Konstantní výraz skrytý v Velká O notace je tak velký, že algoritmus Coppersmith – Winograd je vhodný pouze pro matice, které jsou příliš velké na to, aby je bylo možné zpracovat na současných počítačích (Knuth 1997 ), a tento přístup vyžaduje odečtení, a proto je vhodný pouze pro rozpoznávání. Nelze se zcela vyhnout závislosti na účinném násobení matic: Lee (2002) prokázal, že jakýkoli analyzátor pro bezkontextové gramatiky pracující v čase ${ displaystyle O (n ^ {3- varepsilon} cdot | G |)}$ lze efektivně převést na algoritmus počítající produkt produktu ${ displaystyle (n krát n)}$ -matrice s 0-1 vstupy v čase ${ displaystyle O (n ^ {3- varepsilon / 3})}$ .

Viz také

Reference

^ Grune, Dick (2008). Techniky analýzy: praktický průvodce (2. vyd.). New York: Springer. ISBN 978-0-387-20248-8.

Zdroje

Cocke, Johne; Schwartz, Jacob T. (duben 1970). Programovací jazyky a jejich překladače: Úvodní poznámky (PDF) (Technická zpráva) (2. přepracované vydání). CIMS, NYU.
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočtu. Čtení / MA: Addison-Wesley. ISBN 0-201-02988-X.CS1 maint: ref = harv (odkaz)
Kasami, T. (1965). Efektivní algoritmus rozpoznávání a analýzy syntaxe pro bezkontextové jazyky (Technická zpráva). AFCRL. 65-758.
Knuth, Donald E. (14. listopadu 1997). The Art of Computer Programming Volume 2: Seminumerical Algorithms (3. vyd.). Addison-Wesley Professional. p. 501. ISBN 0-201-89684-2.CS1 maint: ref = harv (odkaz)
Lang, Bernard (1994). "Rozpoznání může být těžší než analýza". Comput. Intell. 10 (4): 486–494. CiteSeerX 10.1.1.50.6982. doi:10.1111 / j.1467-8640.1994.tb00011.x.CS1 maint: ref = harv (odkaz)
Lange, Martin; Leiß, Hans (2009). „Do CNF nebo ne do CNF? Efektivní, přesto prezentovatelná verze algoritmu CYK“. Informatica Didactica. 8.CS1 maint: ref = harv (odkaz)
Lee, Lillian (2002). "Rychlá analýza gramatiky bez kontextu vyžaduje rychlé násobení booleovských matic". J. ACM. 49 (1): 1–15. arXiv:cs / 0112018. doi:10.1145/505241.505242.CS1 maint: ref = harv (odkaz)
Sipser, Michael (1997). Úvod do teorie výpočtu (1. vyd.). IPS. p.99. ISBN 0-534-94728-X.CS1 maint: ref = harv (odkaz)
Valiant, Leslie G. (1975). "Obecné bezkontextové rozpoznávání za méně než kubický čas". J. Comput. Syst. Sci. 10 (2): 308–314. doi:10.1016 / s0022-0000 (75) 80046-8.CS1 maint: ref = harv (odkaz)
Mladší, Daniel H. (únor 1967). "Rozpoznávání a analýza bezkontextových jazyků v čase n³". Informovat. Řízení. 10 (2): 189–208. doi:10.1016 / s0019-9958 (67) 80007-x.

externí odkazy

[1] Grune, Dick (2008). Techniky analýzy: praktický průvodce (2. vyd.). New York: Springer. ISBN 978-0-387-20248-8.

[1]

Algoritmy analýzy
Vzhůru nohama	LL Rekurzivní sestup Ocas rekurzivní Analyzátor Pratt
Zdola nahoru	Přednost Jednoduchý Operátor Posunovací dvůr Ohraničený kontext LR Jednoduchý Dívat se dopředu Kanonický Zobecněný CYK Rekurzivní výstup Shift-snížit
Smíšené, jiné	Kombinátor Schéma Earley
související témata	KOLÍK Gramatika určité věty Deterministická analýza Dynamické programování Memoizace Analyzátor generátoru LALR Analyzovat strom AST Analýza bez skeneru Historie konstrukce překladače Porovnání generátorů syntaktických analyzátorů