依存関係ツリーの出力を平坦な構造に解析する方法

Question

さて、私は完全に迷っています。

(S 
    (NP 
     (PRP It) 
    ) 
    (VP 
     (VBD said) 
     (CLAUSE 
      (S 
       (NP 
        (DT the) 
        (NN figure) 
       ) 
       (VP 
        (VBD was) 
        (VBN rounded) 
       ) 
      ) 
     ) 
    ) 
    (PUNC .) 
) 

これらの解析の出力はプレーンテキストとして保存されています。私は、次のような依存関係ツリー解析ツールからいくつかの出力を持っています。出力は基本的に私が知る限りバイナリツリーです。私が望むのは、各単語が新しい行にあり、各単語にその単語に関連するすべてのラベルが含まれている出力ファイルを持つことです。例：

It S NP PRP 
said S VP 
the S VP CLAUSE S NP DT 
figure S VP CLAUSE S NP NN 
was S VP CLAUSE S VP VBD 
rounded S VP CLAUSE S VP VBN 
. PUNC S 

私はこの出力をどのように解析して私が探している出力にすることができますか？私はpyparsingライブラリを使用しようとしましたが、文字列をリストの階層リストに解析することができましたが、これは出力ニーズにあまり合わないものです。

私は再帰はおそらくここでは良い候補ツールだと思いますが、この問題にどのように適用するかはわかりません。これについての助けになるでしょう - 実装のアイディアを得るための疑似コードさえ。

Answer 1

まず、出力遷移に間違いがあります。

ソリューションにアプローチするには、再帰が必要です。しかし、あなたは車輪を発明する必要はありません。このようなタスクのためだけに、pyparsingという素敵な小さなモジュールがあります。

from pyparsing import nestedExpr 

astring = '''(S 
    (NP 
     (PRP It) 
    ) 
    (VP 
     (VBD said) 
     (CLAUSE 
      (S 
       (NP 
        (DT the) 
        (NN figure) 
       ) 
       (VP 
        (VBD was) 
        (VBN rounded) 
       ) 
      ) 
     ) 
    ) 
    (PUNC .) 
)''' 

expr = nestedExpr('(', ')') 
result = expr.parseString(astring).asList()[0] 

print(result) 

これはアウト出力します：私たちは、再帰的な正規表現を使用してリストのネストされたリストに、その文字列を変換することができ

['S', 
['NP', ['PRP', 'It']], 
['VP', 
    ['VBD', 'said'], 
    ['CLAUSE', 
    ['S', 
    ['NP', ['DT', 'the'], ['NN', 'figure']], 
    ['VP', ['VBD', 'was'], ['VBN', 'rounded']]]]], 
['PUNC', '.']] 

次は、私たちは、からの移行を構築することができます関数を記述する必要があります与えられた解析木。残念ながら、これを行う簡単な方法はありません。自分でハードコアの再帰的なサブルーチンを書く必要があります。 1つのアプローチがあります。 n番目のシンボルを使用してn + 1個のシンボルのすべてのトランジションを取得し、n番目のシンボルをトランジションに追加してトランジションの新しいリストを作成します。

は少し複雑に聞こえるが、多分コードは、あなたが理解するのに役立ちます：

def get_rules(rule_list): 
    transitions = [] 

    if len(rule_list) == 2 and isinstance(rule_list[1], str): 
     return [rule_list] 


    for rule in rule_list[1:]: 
     for r in get_rules(rule): 
      transitions.append([rule_list[0]] + r) 

    return transitions 

それはかなり簡単です。あなたが端末に到達した場合にシングルトンの移行を返すベースケースがあります。それ以外の場合は、再帰的に遷移を構築します。

この関数を呼び出すと結果が次回実行され、印刷：

for r in get_rules(result): 
    print(r[-1] + '\t' + '\t'.join(r[:-1])) 

出力：

私はあなたの遷移が誤って表されたことを先に述べた

It S NP PRP 
said S VP VBD 
the S VP CLAUSE S NP DT 
figure S VP CLAUSE S NP NN 
was S VP CLAUSE S VP VBD 
rounded S VP CLAUSE S VP VBN 
. S PUNC 

。あなたはこれで十字チェックすることができます、これは正しい答えです。