[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki


[ Back to the navigation ]

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

user:ptacek:eugene-charniak-recent-advances-in-nl-parsing-a-mt [2006/03/28 16:18]
user:ptacek:eugene-charniak-recent-advances-in-nl-parsing-a-mt [2006/03/28 16:18] (current)
Line 1: Line 1:
 +====== 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:
 +<​code>​
 +1 2 3 4 ?
 +        1
 +        2
 +        3
 +        4
 +</​code>​
 +
 +slozitost θ(|G|N<​sup>​3</​sup>​)
 +
 +===== 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 ]