Table of Contents
Context Free Grammar
da se do CNF - Chomskeho normalni forma
A → BC
B → terminal
S1 → Λ
CKY
na diagonalu si napis posloupnost terminalu a preved je na neterminaly
potom postupuj po diagonalach vys a vys, do kazdeho policka prijdou vsechny moznosti, ktere jsou odvodit z dvojic policek:
1 2 3 4 ?
1
2
3
4
slozitost θ(|G|N3)
Chart parsing
taky horni trojuhelnik nad diagonalou. navic ?zasobnik Agenda, na pocatku v ni terminaly,
pak je supej do policek a pokud muzes pouzit nejaky pravidlo, tak ho uzi a vysledek zase supej do Agendy.
Resi problem CKY s unary rules (jako S→VP) a ani cykly v G nevadi (S→VP→NP→S) (do agendy supu jen kdyz tam jeste prvek neni) CKY vadily?
PCFG
Probabilistic, pro kazde rule na P(pravidla)
do cell si pisu soucin komponenty*P(pravidla)
pocitam nejpravdepodobnejsi parse, takze kdyz vice moznosti, tak si staci pamatovat tu vetsi pst
tahle pravdepodobnosti verze Chart parsingu se asi menuje VITERBI (nerozumnel jsem presne)