[PetersWerkWiki] [TitleIndex] [WordIndex] 

Werkoverleg met GvN.

Taken:

  1. EarleyParser

Artikelen:

Pierre Boullier & Benoît Sagot (2010)

Are Very Large Context-Free Grammars Tractable?

Vóór het parsen van een zin, eerst de grammatica filteren, daarna pas Earley-parsing toepassen. Resultaat hetzelfde als met ongefilterde grammatica.
Vergelijking van snelheden met verschillende filtermethodes. Onderlingen verschillen zijn minimaal. Een vergelijking met ongefilterd parsen ontbreekt, dus wat de winst van deze methode zou zijn is niet uit het artikel op te maken.
De beschreven basic filter verwijdert regels van een type die in onze data niet voorkomt: regels met meer dan één terminal aan de rechter kant. Andere filters zijn verbeteringen van dit filter, maar leveren niet of nauwelijks winst op, dus zijn waarschijnlijk voor ons ook niet nuttig.
John Aycock and R. Nigel Horspool (2002)

Practical Earley Parsing

Behandelt een manier hoe in een Earley-parser met lege categorieën omgegaan kan worden. Door deze te compileren zou de parser ongeveer twee keer zo snel worden. Alleen getest op het parsen van Java source-code, niet op natuurlijke taal.
Philippe McLean & R. Nigel Horspool (1996)

A Faster Earley Parser

Combineert Earley met een LR-parser.
10 tot 15 keer zo snel als gewone Earley-parser, maar alleen getest op het parsen van C source-code, niet op natuurlijke taal.

Mogelijk interessant:

Hermann Ney (1992)

Stochastic Grammars and Pattern Recognition

Ted Briscoe, John Carroll (1993)

Generalized Probabilistic LR Parsing of Natural Language

Madeleine Bates (1978)

The theory and practice of augmented transition network grammars

Ideeën:

Parses vanuit Alpino eerst minimaliseren voordat de regels voor de Earley-parser eruit worden afgeleid.

Parse door Alpino: 

[ "robust"
  [ "top_cat"
    [ "start(punt)"
      [ "max(punt)"
        [ "root(punt)"
          [ "modifier(nwh,[])"
            [ "pp([],nwh,[],in)"
              [ "p([np(obl,sg&de&def,thi,norm,nwh,[],_)],[],nwh,in)" In ]
              [ "optpunct(no,punct(dubb_punt))" ϵ ]
              [ "np(obl,sg&de&def,thi,norm,nwh,[],_)"
                [ "det(obl,sg&de&def,[],norm,nwh,[],none)" de ]
                [ "n(obl,sg&de&def,norm,nwh,[],_)" nieuwjaarsnacht ] ] ] ]
          [ "optpunct(no,punct((schuin_streep;komma)))" ϵ ]
          [ "sv1([modifier(nwh,[])])"
            [ "v([],fin,[vc([],psp,_,[modifier(nwh,[])],_,_)|_],[modifier(nwh,[])],_,[])" zijn ]
            [ "v2_vp(v(_,fin,[vc([],psp,[],[modifier(nwh,[])],[],[]),np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[],[]),[modifier(nwh,[])])"
              [ "vpx(v(_,fin,[vc([],psp,[],[modifier(nwh,[])],[],[]),np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[],[]),fin,[modifier(nwh,[])],[])"
                [ "vproj(v(_,fin,[vc([],psp,[],[modifier(nwh,[])],[],[]),np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[],[]),fin,[],[modifier(nwh,[])],[])"
                  [ "np(nom,pl&de&indef,thi,norm,nwh,[],_)"
                    [ "n(nom,pl&de&indef,norm,nwh,[],_)"
                      [ "num(pl&de&indef)" vier ]
                      [ "n(nom,pl&de&indef,norm,nwh,[],_)" doden ] ] ]
                  [ "vproj(v(_,fin,[vc([],psp,[],[modifier(nwh,[])],[],[]),np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[],[]),fin,[np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[])"
                    [ "vc(v(_,fin,[vc([],psp,[],[modifier(nwh,[])],[],[]),np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[],[]),fin,[np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[],[])"
                      [ "v(v(_,fin,[vc([],psp,[],[modifier(nwh,[])],[],[]),np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[],[]),fin,[vc([],psp,[],[modifier(nwh,[])],[],[]),np(nom,pl&de&indef,thi,norm,nwh,[],_)],[modifier(nwh,[])],[],[])" ϵ ]
                      [ "vc([],psp,[],[modifier(nwh,[])],[],[])"
                        [ "vb([],psp,[],[modifier(nwh,[])],[],[])"
                          [ "v([],psp,[],[modifier(nwh,[])],[],[])" gevallen ] ] ] ] ] ] ] ] ] ] ] ]
    [ "optpunct(yes,punct(punt))"
      [ "punct(punt)" . ] ] ] ]

Geminimaliseerd: 

[ "robust"
  [ "root(punt)"
    [ "pp([],nwh,[],in)"
      [ "p([np(obl,sg&de&def,thi,norm,nwh,[],_)],[],nwh,in)" In ]
      [ "np(obl,sg&de&def,thi,norm,nwh,[],_)"
        [ "det(obl,sg&de&def,[],norm,nwh,[],none)" de ]
        [ "n(obl,sg&de&def,norm,nwh,[],_)" nieuwjaarsnacht ] ] ]
    [ "sv1([modifier(nwh,[])])"
      [ "v([],fin,[vc([],psp,_,[modifier(nwh,[])],_,_)|_],[modifier(nwh,[])],_,[])" zijn ]
      [ "n(nom,pl&de&indef,norm,nwh,[],_)"
        [ "num(pl&de&indef)" vier ]
        [ "n(nom,pl&de&indef,norm,nwh,[],_)" doden ] ]
      [ "v([],psp,[],[modifier(nwh,[])],[],[])" gevallen ] ] ]
  [ "punct(punt)" . ] ]

Ongelijke data:

Zin in clef_part0001: 

Dat was vooral opvallend in Den Haag , waar " slechts ' 35 aanhoudingen werden verricht .

Volgens clef_part0001.rules werden deze regels gebruikt voor de substring Den Haag:

np(obl,indef,thi,norm,nwh,[],LOC) → np(obl,indef,thi,norm,nwh,[],LOC) punct(komma) adv(agr,nwh,[]) optpunct(no,punct((schuin_streep;komma)))
np(obl,indef,thi,norm,nwh,[],LOC) → n(obl,indef,norm,nwh,[],LOC)
n(obl,indef,norm,nwh,[],LOC) → pn(indef,LOC)

Volgens clef_part0001.trees werden op dezelfde plaats deze regels gebruikt:

np → n
n → n optpunct rel optpunct
n → pn

Dit houdt in dat de vergelijkingen tussen de resultaten met de Earley-parser en de uitvoer van Alpino niet klopt.

CategoryParsing CategoryLiteratuur