9

私が取り組んでいるこのアルゴリズムの開発には助けが必要です。次の形式のツリーの入力があります。

( 根 ( AB ( ABC ) ( CBA ) ) ( CD ( CDE ) ( FGH ) ) )

これは次のツリーに見えます。

                   Root
                     |
                ____________
              AB           CD
              |             |  
       __________         ___________
      ABC      CBA        CDE      FGH

アルゴリズムが想定しているのは、括弧内の形式を読み取り、次の出力を与えることです。

Root -> AB CD
AB -> ABC CBA
CD -> CDE FGH

ルートとその子、および子を持つ他のすべての親が一覧表示されます。これを開始する方法を理解できません。誰かがヒントをくれたり、参考文献やリンクを教えてくれませんか?

4

4 に答える 4

4

解決策:Treeモジュールのクラスnltk

(別名自然言語ツールキット)

実際の解析を行う

これはあなたの入力です：

input = '( Root ( AB ( ABC ) ( CBA ) ) ( CD ( CDE ) ( FGH ) ) )'

そして、次のようにして非常に簡単に解析します。

from nltk import Tree
t = Tree.fromstring(input)

解析されたツリーで遊ぶ

>>> t.label()
'Root'
>>> len(t)
2
>>> t[0]
Tree('AB', [Tree('ABC', []), Tree('CBA', [])])
>>> t[1]
Tree('CD', [Tree('CDE', []), Tree('FGH', [])])
>>> t[0][0]
Tree('ABC', [])
>>> t[0][1]
Tree('CBA', [])
>>> t[1][0]
Tree('CDE', [])
>>> t[1][1]
Tree('FGH', [])

ご覧のとおり、各ノードをサブツリーのリストとして扱うことができます。

ツリーをプリティプリントするには 

>>> t.pretty_print()
            Root            
      _______|________       
     AB               CD    
  ___|___          ___|___   
ABC     CBA      CDE     FGH
 |       |        |       |  
...     ...      ...     ...

必要な出力を取得するには

from sys import stdout

def showtree(t):
    if (len(t) == 0):
        return
    stdout.write(t.label() + ' ->')
    for c in t:
        stdout.write(' ' + c.label())
    stdout.write('\n')
    for c in t:
        showtree(c)

使用法：

>>> showtree(t)
Root -> AB CD
AB -> ABC CBA
CD -> CDE FGH

モジュールをインストールするには

pip install nltk

(sudo必要に応じて使用)

于 2018-04-06T15:52:59.707 に答える
1

これを試して ：

def toTree(expression):
    tree = dict()
    msg =""
    stack = list()
    for char in expression:
        if(char == '('):
            stack.append(msg)
            msg = ""
        elif char == ')':
            parent = stack.pop()
            if parent not in tree:
                tree[parent] = list()
            tree[parent].append(msg)
            msg = parent
        else:
            msg += char
    return tree

expression = "(Root(AB(ABC)(CBA))(CD(CDE)(FGH)))"
print toTree(expression)

キー「」でルートにアクセスできる辞書を返します。その後、単純な BFS を実行して出力を印刷できます。

出力:

{
''    : ['Root'], 
'AB'  : ['ABC', 'CBA'], 
'Root': ['AB', 'CD'], 
'CD'  : ['CDE', 'FGH']
}

開始する前に Expression 内のすべての空白を削除するか、for ループの最初の行として次を追加して、式内の無関係な文字を無視する必要があります。

if char == <IRRELEVANT CHARACTER>:
    continue

上記のコードは O(n) 時間で実行されます。n は式の長さです。

編集

印刷機能は次のとおりです。

def printTree(tree, node):
    if node not in tree:
        return 
    print '%s -> %s' % (node, ' '.join(child for child in tree[node])) 
    for child in tree[node]:
        printTree(tree, child)

目的の出力は、次の方法で実現できます。

expression = "(Root(AB(ABC)(CBA))(CD(CDE)(FGH)))"
tree = toTree(expression)
printTree(tree, tree[''][0])

出力

Root -> AB CD
AB -> ABC CBA
CD -> CDE FGH

編集

ノード名が一意ではないと仮定すると、ノードに新しい名前を付けるだけで済みます。これは、次を使用して実行できます。

def parseExpression(expression):
    nodeMap = dict()
    counter = 1
    node = ""
    retExp =""
    for char in expression:
        if char == '(' or char == ')' :
            if (len(node) > 0):
                nodeMap[str(counter)] = node;
                retExp += str(counter)
                counter +=1
            retExp += char
            node =""
        elif char == ' ': continue
        else :
            node += char
    return retExp,nodeMap

print 関数は次のように変更されます。

def printTree(tree, node, nodeMap):
    if node not in tree:
        return 
    print '%s -> %s' % (nodeMap[node], ' '.join(nodeMap[child] for child in tree[node])) 
    for child in tree[node]:
        printTree(tree, child, nodeMap)

出力は次を使用して取得できます。

expression = " ( Root( SQ ( VBZ ) ( NP ( DT ) ( NN ) ) ( VP ( VB ) ( NP ( NN ) ) ) ))"
expression, nodeMap = parseExpression(expression)
tree = toTree(expression)
printTree(tree, tree[''][0], nodeMap)

出力:

Root -> SQ
SQ -> VBZ NP VP
NP -> DT NN
VP -> VB NP
NP -> NN
于 2013-11-03T14:14:05.490 に答える