句法分析的幾種主要方法:
Deterministic parsing(specifically : Transition-based parsing)
Dynamic programming(specifically : Graph-based parsing)
Constraint satisfaction
這裡主要介紹一下Transition-based parsing
首先他所采取的資料結構是一個棧和一個隊列。
Data structure:
Stack [… , wi ]S of partially processed tokens
Queue [wj , …]Q of remaining input tokens
然後還定義了一些列action
Parsing actions built from atomic actions:
Shift
Reduce
這種方法的優點是
Efficiency
Simplicity
其操作流程就是,根據棧和隊列的狀态,每次執行一個action,然後根據這個action就能改變棧和隊列的狀态,再根據現在棧和隊列的狀态來選取下一個action。如此循環下去就會得到一棵句法樹。
Transition-based Dependency Parsing
input : Sentence:w1w2w3…..wn
output : Dependency parsed tree (三元組)
比如下面的樹就可以用這樣的三元組表示;:
(I,subj,like)
(fish,dobj,eating)
……
一般情況下:定義的action有下面這3個:
Shift
Left_arc
Right_arc
首先下圖是其中的configuration,初始狀态棧為空,隊列儲存了n個詞。
來看看選擇shift action後執行怎樣的操作。
Push another word onto the top of the stack, i.e. shifting one token from the buffer to the stack.
做shift就是把隊列的第一個詞(booked)給放到棧中去,現在booked是棧頂,而 I 是棧頂下面的那個元素。
再來看看left-arc。
Pop the top two words from the stack. Attach the second to the first, creating an arc pointing to the left. Push the first word back on the stack.
形象點的看就是把棧頂的第2個元素依賴到棧頂的第一個元素上去,使他們隻在棧中占一個位置。
用更好了解的說法就是,把棧頂的兩個元素pop出去,然後把加一條booked指向I的邊,這樣表示I 依附于 booked,然後把booked push到棧中去。
right-arc是一個道理,加一條I指向booked的邊,這樣表示booked依附于I,然後把I push到棧中去。
HEN顯然left-arc和right-arc隻會操作棧頂的兩個元素,加一條邊,并留下其中的一個。
下面是完整的流程。
給一個更加詳細的例子
來自Chen and Manning (2014)
下面說說成分
同樣也是一個棧和一個隊列。
幾種action
SHIFT
REDUCE –unary–X (把棧頂節點歸約成一個label為X的節點,并重新壓入棧)
REDUCE –binary–{L/R}–X,(把棧頂的兩個節點歸約成一個label為X的節點,并入棧)
來自Global Discriminative Model (2009)