Шаги для генерации дерева синтаксиса из алгоритма CYK (обработка естественного языка)

Question

В настоящее время я работаю над проектом с участием НЛП. Я реализовал идентификатор CKY, как указано в Jurafsky and Martin (алгоритм на стр. 450). Созданная таблица фактически хранит нетерминалы в таблице (вместо обычных булевых значений). Однако единственной проблемой, которую я получаю, является извлечение дерева синтаксического анализа.

Вот иллюстрация того, что делает мой CKY идентификатор:

Это моя грамматика

  S -> NP VP 
      S -> VP 
      NP -> MODAL PRON | DET NP | NOUN VF | NOUN | DET NOUN | DET FILENAME 
      MODAL -> 'MD' 
      PRON -> 'PPSS' | 'PPO' 
      VP -> VERB NP 
      VP -> VERB VP 
      VP -> ADVERB VP 
      VP -> VF 
      VERB -> 'VB' | 'VBN' 
      NOUN -> 'NN' | 'NP' 
      VF -> VERB FILENAME 
      FILENAME -> 'NN' | 'NP' 
      ADVERB -> 'RB' 
      DET -> 'AT' 

И это алгоритм:

for j from i to LENGTH(words) do 
    table[j-1,j] = A where A -> POS(word[j]) 
    for i from j-2 downto 0 
     for k from i+1 to j-1 
      table[i,j] = Union(table[i,j], A such that A->BC) 
      where B is in table[i,k] and C is in table[k,j] 

И это то, что мой разборе стол выглядит следующим образом:

Теперь, когда я знаю, что, поскольку S находится в [0,5], строка была проанализирована, а для k = 1 (согласно алгоритму, указанному в Мартине и Юрафском), мы имеем S -> таблицу [ 0] [2] таблица [2] [5] ie S -> NP VP

Единственная проблема, которую я получаю, заключается в том, что я смог получить используемые правила, но затем они находятся в смешанном формате, т.е. не на основе их появления в дереве разбора. Может ли кто-нибудь предложить алгоритм для получения правильного дерева синтаксического анализа?

Thankyou.

Answer 1

Вы должны посетить рекурсивно ячейки вашей таблицы и развернуть их так же, как и для узла S, пока все не станет терминалом (так что вам нечего открывать). В вашем примере вы сначала переходите к ячейке [0] [2]; это терминал, вам не нужно ничего делать. Затем вы переходите к [2] [5], это не терминал, сделанный [2] [3] и [3] [5]. Вы посещаете [2] [3], это терминал. [3] [5] - не терминал, выполненный двумя терминалами. Вы сделали. Вот демо в Python:

class Node: 
    '''Think this as a cell in your table''' 
    def __init__(self, left, right, type, word): 
     self.left = left 
     self.right = right 
     self.type = type 
     self.word = word 

# Declare terminals 
t1 = Node(None,None,'MOD','can') 
t2 = Node(None,None,'PRON','you') 
t3 = Node(None,None,'VERB', 'eat') 
t4 = Node(None,None,'DET', 'a') 
t5 = Node(None,None,'NOUN','flower') 

# Declare non-terminals 
nt1 = Node(t1,t2, 'NP', None) 
nt2 = Node(t4,t5, 'NP', None) 
nt3 = Node(t3,nt2,'VP', None) 
nt4 = Node(nt1,nt3,'S', None) 

def unfold(node): 
    # Check for a terminal 
    if node.left == None and node.right == None: 
     return node.word+"_"+node.type 

    return "["+unfold(node.left)+" "+unfold(node.right)+"]_"+node.type 

print unfold(nt4) 

И выход:

[[can_MOD you_PRON]_NP [eat_VERB [a_DET flower_NOUN]_NP]_VP]_S