[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki


[ Back to the navigation ]

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)


[ Back to the navigation ] [ Back to the content ]