Chart-Parsing Prolog Aufbaukurs SS 2000 Heinrich-Heine-Universität Düsseldorf Christof Rumpf

Chart-ParsingChart-ParsingProlog Aufbaukurs SS 2000

Heinrich-Heine-Universität Düsseldorf

Christof Rumpf

08.05.2000 Chart-Parsing 2

Chart-ParserChart-Parser

• Ein Chart-Parser speichert Information über bereits geparste Teilstrukturen in einer Tabelle (Chart).

• Bereits geleistete Arbeit kann beim Backtracking aus der Tabelle gelesen werden.


Motivation: Motivation: trashingtrashing

VP

V NP PP

D N P NP

D N

chased the cat into the garden

VP V NP

VP V NP PP


ChartChart

• In der Tabelle wird für jede Konstituente ein Eintrag gespeichert:– Name der Konstituente– wo sie beginnt– wo sie endet

• Beispielchart(np,[the,cat,into,the,garden],[into,the,garden]).


Top-Down-Chart-ParserTop-Down-Chart-Parser

parse(C,S1,S) :- chart(C,S1,S).

parse(C,[Word|S],S) :- word(C,Word).

parse(C,S1,S) :- rule(C,Cs), parse_list(Cs,S1,S), asserta(chart(C,S1,S)).

parse_list([C|Cs],S1,S) :- parse(C,S1,S2), parse_list(Cs,S2,S).

parse_list([],S,S).

clear_chart :- abolish(chart/3).


Numerische Repräsentation der PositionenNumerische Repräsentation der Positionen

chart(np,[the,cat,into,the,garden],[into,the,garden]).

chart(np,0,2).

?.- parse(s,0,8).yes

[the,dog,sees,the,cat,near,the,elephant]

c(the,0,1).c(dog,1,2).c(sees,2,3).c(the,3,4).

c(cat,4,5).c(near,5,6).c(the,6,7).c(elephant,7,8).

Chart

String Anfrage

kompaktere Repräsentation!


‚‚Numerischer‘ Chart-ParserNumerischer‘ Chart-Parser

parse(C,S1,S) :- chart(C,S1,S).

parse(C,S1,S) :- c(Word,S1,S), word(C,Word).

parse(C,S1,S) :- rule(C,Cs), parse_list(Cs,S1,S), asserta(chart(C,S1,S)).


parse_list([],S,S).

clear_chart :- abolish(chart/3).


VollständigkeitVollständigkeit

• Der bisherige Chart-Parser verschwendet mehr Ressourcen, als er einspart, weil Chart und Regeln konkurrieren.

• Lösung: Chart muss vollständig sein. Positive wie negative Information über Konstituenten muss vollständig gespeichert sein.


Chart-Parser mit Completeness-CheckChart-Parser mit Completeness-Check

parse(C,[Word|S],S) :- word(C,Word).

parse(C,S1,S) :- complete(C,S1), !, chart(C,S1,S).

parse(C,S1,S) :- rule(C,Cs), parse_list(Cs,S1,S2), asserta(chart(C,S1,S2)), S2 = S.

parse(C,S1,_) :- asserta(complete(C,S1)), fail.


parse_list([],S,S).

clear_chart :- abolish(chart/3), abolish(complete/2).


SubkategorisierungSubkategorisierungrule(vp,[verbal(0)]).rule(vp,[verbal(X),rest_of_vp(X)]).rule(rest_of_vp(1),[np]).rule(rest_of_vp(2),[np,np]).rule(verbal(X),[v(X)]).rule(np,[d,n]).

word(n,dog). word(n,dogs).word(n,cat). word(n,cats).word(n,elephant). word(n,elephants).word(v(0),sleep). word(d,the).word(v(1),see).word(v(2),give). ?- parse(vp,[see,the,dog],[]).

no

Problem: Komplexe Konstituenten mit

Argumenten stehen in einer Subsumptionshierarchie.


SubsumptionSubsumption

• Ein Term A subsumiert einen Term B gdw.– A und B sind unifizierbar.– B ist nach der Unifikation nicht spezifischer

als vorher.

• Beispiel:f(X, b) f(a, b) f(a, b) f(X, b)


Subsumptions-CheckSubsumptions-Check

parse(C,S1,S) :- complete(C0,S1), subsumes_chk(C0,C), !, C0 = C, chart(C,S1,S).

subsumes_chk(T1,T2) :- \+ ( varnames(T2), \+ (T1 = T2) ).

C muss spezifischer sein als C0

bzw. C0 muss genereller

sein als C.

(O´Keefe)


Earley´s AlgorithmusEarley´s Algorithmus

• Komplexität n3 (optimal).

• Behandelt leere Konstituenten.

• Loopt nicht bei Linksrekursion.

• Kombiniert top-down und bottom-up.

• Kein Backtracking: Nach dem Parse befinden sich alle Alternativen im Chart.

• Ist ein active chart parser.


Earley: Active Chart ParsingEarley: Active Chart Parsing

S NP VP 0 0S NP VP 0 2S NP VP 0 3

chart(s,[the,dog,barked],[np,vp],[the,dog,barked]).chart(s,[the,dog,barked],[vp],[barked]).chart(s,[the,dog,barked],[],[]).

parse(s,[the,dog,barked],[]).

Aktive Konstituenten sind solche, die an der aktuellen Position der Eingabekette als nächste geparst werden sollen.


Earley: Chart-EinträgeEarley: Chart-Einträge• Die gesuchte Konstituente.• Die Position, an der die gesuchte Konstituente

beginnt.• Die Subkonstituenten, die noch geparst werden

müssen. Die erste davon ist die aktive.• Die aktuelle Position im Input-String.

chart(s,[the,dog,barked],[np,vp],[the,dog,barked]).chart(s,[the,dog,barked],[vp],[barked]).chart(s,[the,dog,barked],[],[]).


Earley-Chart: Earley-Chart: the dog chases the catthe dog chases the catchart(start,[the,dog,chases,the,cat],[s], [the,dog,chases,the,cat]).chart(s, [the,dog,chases,the,cat],[np,vp],[the,dog,chases,the,cat]).chart(np, [the,dog,chases,the,cat],[d,n], [the,dog,chases,the,cat]).chart(np, [the,dog,chases,the,cat],[n], [dog,chases,the,cat]).chart(np, [the,dog,chases,the,cat],[], [chases,the,cat]).chart(s, [the,dog,chases,the,cat],[vp], [chases,the,cat]).chart(vp, [chases,the,cat],[v,np], [chases,the,cat]).chart(vp, [chases,the,cat],[v,np,pp], [chases,the,cat]).chart(vp, [chases,the,cat],[np], [the,cat]).chart(vp, [chases,the,cat],[np,pp], [the,cat]).chart(np, [the,cat],[d,n], [the,cat]).chart(np, [the,cat],[n], [cat]).chart(np, [the,cat],[], []).chart(vp, [chases,the,cat],[], []).chart(s, [the,dog,chases,the,cat],[], []).chart(start,[the,dog,chases,the,cat],[], []).chart(vp, [chases,the,cat],[pp], []).


Earley´s 3 KomponentenEarley´s 3 Komponenten

• Predictor– Sucht nach Regeln, die die aktiven Konstituenten

expandieren.

• Scanner– Akzeptiert Wörter der Eingabekette.

• Completer– Verwendet den Output des Scanners um übergeordnete

Konstituenten zu vervollständigen.


Earley-Parser: Das GerüstEarley-Parser: Das Gerüst% parse(+C,+S1,-S)% Parse a constituent of type C from input string S1,% leaving remainder of input in S.

parse(C,S1,S) :- clear_chart, store(chart(start,S1,[C],S1)), process(S1), chart(C,S1,[],S).

% process(+Position)% Starting with input string Position, work through% the Earley parsing process.

process([]) :- !.

process(Position) :- predictor(Position), scanner(Position,NewPosition), completer(NewPosition), process(NewPosition).


Predictor: BeschreibungPredictor: Beschreibung

• Für alle aktiven Konstituenten (1. Element in Chart-Spalte 3):– finde alle Syntaxregeln, die diese Konstituenten

expandieren und generiere entsprechende Chart-Einträge.

– Expandiere auch die so neu hinzugekommenen Konstituenten.


Predictor: CodePredictor: Code% predictor(+Position)% Creates new goals using syntax rules.

predictor(Position) :- chart(C,PC,[Goal|Goals],Position), % For every chart entry of this kind predict(Goal,Position), % do all possible predictions fail.

predictor(_). % then succeed with no further action.

predict(Goal,Position) :- rule(Goal,[H|T]), % For every rule expanding Goal store(chart(Goal,Position, [H|T],Position)), % make a new chart entry predict(H,Position), % and make predictions from it too fail.

predict(_,_). % then succeed with no further action.


Scanner: BeschreibungScanner: Beschreibung

• Akzeptiere das nächste Wort aus der Eingabekette und bestimme seine Kategorie.

• Für alle Chart-Einträge für die aktuelle Position: Wenn die aktive Kategorie der Wort-Kategorie entspricht, generiere neue Chart-Einträge:– entferne die aktive Kategorie

– entferne das aktuelle Wort


Scanner: CodeScanner: Code

% scanner(+Position,-NewPosition)% Accept a word and use it to satisfy goals.

scanner([W|Words],Words) :- chart(C,PC,[G|Goals],[W|Words]), % for each current goal at current pos. word(G,W), % if category of W matches it store(chart(C,PC,Goals,Words)), % make a new chart entry fail.

scanner([_|Words],Words). % then succeed with no further action.


CompleterCompleter

• Für alle vollständigen Konstituenten:– Kombiniere sie zu übergeordneten

Konstituenten und generiere entsprechende Chart-Einträge.

– Berücksichtige ebenso die auf diese Weise neu hinzugekommenen Konstituenten.


Completer: CodeCompleter: Code% completer(+Position)% Process all consituents that are ready to be completed. See text.

completer(Position) :- chart(C,PC,[],Position), % For every chart entry with no goals complete(C,PC,Position), % complete all possible higher constituents fail.

completer(_). % then succeed with no further action.

complete(C,PC,Position) :- chart(C0,PC0,[C|Goals],PC), % For every constituent that can be completed store(chart(C0,PC0, Goals,Position)), % make a new chart entry, Goals == [], % then fail here if Goals not empty, complete(C0,PC0,Position), % or process new entry the same way fail.

complete(_,_,_). % then succeed with no further action.


Leere KonstituentenLeere Konstituenten

predict(Goal,Position) :- rule(Goal,[]), store(chart(Goal,Position,[],Position)), complete(Goal,Position,Position), fail.

% rule(d,[])


Chart-EinträgeChart-EinträgeOhne Subsumption

store(chart(A,B,C,D)) :- \+ chart(_,B,_,D), asserta(chart(A,B,C,D)).

Mit Subsumption

store(chart(A,B,C,D)) :- \+ (chart(A1,B,C1,D), subsumes_chk(A1,A), subsumes_chk(C1,C)), asserta(chart(A,B,C,D)).


PerformancePerformanceParser ALS Prolog

20 MHz 80386Quintus PrologSparcstation 1+

DCG 3,4 0,3Top-Down 6,0 1,2Bottom-Up 38,3 8,4Left-Corner ohne Linking 12,7 2,6Left-Corner mit Linking 12,0 2,5Chart ohne Completeness-Check 47,2 20,5Chart mit Completeness-Check 59,3 27,3Chart mit Subsumptions-Check 71,3 32,2Earley ohne Subsumptions-Check 320,3 144,5Earley mit Subsumptions-Check 989,8 172,0


LiteraturLiteratur

• Covington, Michael A. (1994): Natural Language Processing for Prolog Programmers. Chap. 6: Parsing Algorithms. Prentice-Hall.

• Gazdar, Gerald & Chris Mellish (1989): Natural Language Processing in Prolog. Addison Wesley.

Documents

Chart-Parsing Prolog Aufbaukurs SS 2000 Heinrich-Heine-Universität Düsseldorf Christof Rumpf