Das deutsche Python-Forum

Seit 2002 Diskussionen rund um die Programmiersprache Python
https://www.python-forum.de/

Brauche Hilfe bei komplexer XML-Struktur

https://www.python-forum.de/viewtopic.php?t=27072

Seite 1 von 1

Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Donnerstag 4. August 2011, 19:26
von Dingels
Schönen guten Abend allerseits,

ich studiere Computerlinguistik und für ein Software-Projekt möchte ich mit einem morphologisch und syntaktisch annotierten Korpus arbeiten. Dieses Korpus liegt in XML vor. Die Struktur für einen Beispielsatz sieht folgendermaßen aus:

Code: Alles auswählen

<s id="s5">
  <graph root="s5_504">
    <terminals>
      <t id="s5_1" word="Die" pos="ART" morph="Def.Fem.Nom.Sg"/>
      <t id="s5_2" word="Tagung" pos="NN" morph="Fem.Nom.Sg.*"/>
      <t id="s5_3" word="hat" pos="VVFIN" morph="3.Sg.Pres.Ind"/>
      <t id="s5_4" word="mehr" pos="PIAT" morph="--"/>
      <t id="s5_5" word="Teilnehmer" pos="NN" morph="Masc.Akk.Pl.*"/>
      <t id="s5_6" word="als" pos="KOKOM" morph="--"/>
      <t id="s5_7" word="je" pos="ADV" morph="--"/>
      <t id="s5_8" word="zuvor" pos="ADV" morph="--"/>
    </terminals>
    <nonterminals>
      <nt id="s5_500" cat="NP">
        <edge label="NK" idref="s5_1"/>
        <edge label="NK" idref="s5_2"/>
      </nt>
      <nt id="s5_501" cat="AVP">
        <edge label="CM" idref="s5_6"/>
        <edge label="MO" idref="s5_7"/>
        <edge label="HD" idref="s5_8"/>
      </nt>
      <nt id="s5_502" cat="AP">
        <edge label="HD" idref="s5_4"/>
        <edge label="CC" idref="s5_501"/>
      </nt>
      <nt id="s5_503" cat="NP">
        <edge label="NK" idref="s5_502"/>
        <edge label="NK" idref="s5_5"/>
      </nt>
      <nt id="s5_504" cat="S">
        <edge label="SB" idref="s5_500"/>
        <edge label="HD" idref="s5_3"/>
        <edge label="OA" idref="s5_503"/>
      </nt>
    </nonterminals>
  </graph>
</s>
Ich möchte dieses XML nun in eine Python-Datenstruktur umwandeln, um damit leichter zu arbeiten. Als Output hab ich mir ungefähr folgendes vorgestellt:

Code: Alles auswählen

[ 'S',
    [ ('SB', 'NP'),
        [ ('NK', 'ART'), 'Die' ],
        [ ('NK', 'NN'), 'Tagung' ]
    ],
    [ ('HD', 'VVFIN'), 'hat' ],
    [ ('OA', 'NP'),
        [ ('NK', 'AP'),
            [ ('HD', 'PIAT'), 'mehr' ],
            [ ('CC', 'AVP'),
                [ ('CM', 'KOKOM'), 'als' ],
                [ ('MO', 'ADV'), 'je' ],
                [ ('HD', 'ADV'), 'zuvor' ]
            ]
        ],
        [ ('NK', 'NN'), 'Teilnehmer' ]
    ]
]
Mein Problem ist jetzt, dass ich genau daran bisher gescheitert bin. Ich weiß, dass ich hier eine rekursive Herangehensweise wählen muss, aber mein Gehirn tut sich leider äußerst schwer damit. :| Ich hab das XML schon mittels xml.etree.ElementTree geparst und ich weiß auch, wie ich auf die einzelnen Elemente zugreifen kann. Aber wie ich welche rekursiven Funktionen definieren muss, um mein Ziel zu erreichen, erschließt sich mir leider nicht so recht.

Grundsätzlich müsste man ja folgendes tun:
1. Identifiziere das root-Element im graph-Tag (hier 's5_504').
2. Suche nach demjenigen Nonterminal, dessen ID diesem root-Element entspricht.
3. Extrahiere die syntaktische Kategorie dieses Nonterminals (hier 'S') und initialisiere damit den neuen Baum.
4. Gehe rekursiv jeden Edge des Nonterminals entlang und finde mittels der idref-Tags die weiteren Subknoten.
5. Mache das so lange bis Du zu einem Terminal-Symbol kommst.

Also, in der Theorie ist mir das alles klar, aber mein Hirn kommt trotz vieler Versuche den ganzen Tag hindurch einfach nicht zu einer funktionierenden Lösung, da ich Schwierigkeiten mit rekursivem Denken habe. Ich habe bisher nur Erfahrung mit iterativer Programmierung.

Daher wende ich mich an euch: Könnt ihr mir einen Denkanstoß, ein Stück Code oder ähnlich Hilfreiches geben? Eine komplette Lösung kann ich von euch nicht verlangen, aber zumindest ein Grundgerüst, mit dem ich weitermachen kann, wäre sehr hilfreich für mich. Gibt es vielleicht sogar eine externe Bibliothek, die mir dabei helfen kann?

Herzlichen Dank im Voraus! :)

Beste Grüße und schönen Abend noch,
Dingels

Re: Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Donnerstag 4. August 2011, 19:33
von deets
Ich halte deine Struktur fuer nicht wirklich geeignet. Du baust einen Baum auf, aber sie ist ja schon selbst als Graph benannt. Und so einen wuerde ich auch bauen. Und dazu brauchst du auch keinen Rekursion. Einfach nur Objekte fuer Terminale, NichtTerminale und Kanten definieren, und dann stulle durchkonstruieren.

Darauf dann zu arbeiten mittels Graphen-Algorithmen mag durchaus intermediaere Baumstrukturen bedeuten, aber sowas wie semantische Netze sind ja auch Netze (Graphen), und nicht semantische Baeume :)

Re: Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Donnerstag 4. August 2011, 19:40
von Dingels
deets hat geschrieben:Ich halte deine Struktur fuer nicht wirklich geeignet. Du baust einen Baum auf, aber sie ist ja schon selbst als Graph benannt. Und so einen wuerde ich auch bauen. Und dazu brauchst du auch keinen Rekursion. Einfach nur Objekte fuer Terminale, NichtTerminale und Kanten definieren, und dann stulle durchkonstruieren.

Darauf dann zu arbeiten mittels Graphen-Algorithmen mag durchaus intermediaere Baumstrukturen bedeuten, aber sowas wie semantische Netze sind ja auch Netze (Graphen), und nicht semantische Baeume :)
Hallo deets, danke für deine Meinung. Leider verstehe ich nicht so recht, was Du meinst. Ja, die XML-Struktur ist im Grunde ein Graph, aber in der geparsten Struktur fehlen doch die Zusammenhänge zwischen den einzelnen (Nicht-)Terminalsymbolen. Das heißt, ich kann doch meines Wissens gar nicht mittels xml.etree.ElementTree den vollständigen Pfad vom root-Symbol bis zu einem Terminal-Symbol anzeigen lassen, oder? Aber ich vermute, ich stehe gerade auf dem Schlauch. :lol:

Kannst Du mir bitte mal an einem konkreten Beispiel zeigen, welche Struktur Du für sinnvoller hältst?

Re: Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Donnerstag 4. August 2011, 21:07
von deets
Na, es ist doch im Grunde ganz einfach: mittels etree parst du das Dokument. Dann suchst du dir mittels find erstmal alle Terminal-Elemente, und konstruierst fuer jedes davon ein Objekt - sinnvollerweise benannt Terminal oder so. Und das hat vor allem eine ID, und du steckst die Dinger zB in ein dictionary, welches die ID auf dasTerminal abbildet.

Danach suchst du die nicht-terminale, und baust ein Objekt NonTerminal damit. Ebenfalls wieder mit der ID (und allem anderen natuerlich, gilt auch fuer die Terminals). Auch das indizierst du ueber das ID-zu-Objekt-dict, denn der ID-Raum ist ja fuer alle gleich.

Und last but not least suchst du die edge-Elemente, und erzeugst Edge-Objekte. Und dann hast du diverse Moeglichkeiten, aber eine waere zB jedem Terminal/NonTerminal eine Liste mit Edge-Objekten angedeihen zu lassen, und da stopfst du die enstprechenden rein.

Re: Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Freitag 5. August 2011, 18:08
von Dingels
Hallo noch mal,

deets, ich glaube, ich weiß jetzt ungefähr, was Du meinst. Ich hab jetzt folgende Struktur herausbekommen:

Code: Alles auswählen

{'s5_500': {'cat': 'NP',
            'edges': {'s5_1': {'label': 'NK',
                               'morph': 'Def.Fem.Nom.Sg',
                               'pos': 'ART',
                               'word': 'Die'},
                      's5_2': {'label': 'NK',
                               'morph': 'Fem.Nom.Sg.*',
                               'pos': 'NN',
                               'word': 'Tagung'}}},
 's5_501': {'cat': 'AVP',
            'edges': {'s5_6': {'label': 'CM',
                               'morph': '--',
                               'pos': 'KOKOM',
                               'word': 'als'},
                      's5_7': {'label': 'MO',
                               'morph': '--',
                               'pos': 'ADV',
                               'word': 'je'},
                      's5_8': {'label': 'HD',
                               'morph': '--',
                               'pos': 'ADV',
                               'word': 'zuvor'}}},
 's5_502': {'cat': 'AP',
            'edges': {'s5_4': {'label': 'HD',
                               'morph': '--',
                               'pos': 'PIAT',
                               'word': 'mehr'},
                      's5_501': {'label': 'CC'}}},
 's5_503': {'cat': 'NP',
            'edges': {'s5_5': {'label': 'NK',
                               'morph': 'Masc.Akk.Pl.*',
                               'pos': 'NN',
                               'word': 'Teilnehmer'},
                      's5_502': {'label': 'NK'}}},
 's5_504': {'cat': 'S',
            'edges': {'s5_3': {'label': 'HD',
                               'morph': '3.Sg.Pres.Ind',
                               'pos': 'VVFIN',
                               'word': 'hat'},
                      's5_500': {'label': 'SB'},
                      's5_503': {'label': 'OA'}}}}
Was ich aber haben möchte, ist folgendes:

Code: Alles auswählen

 {'s5_504': {'cat': 'S',
            'edges': {'s5_3': {'label': 'HD',
                               'morph': '3.Sg.Pres.Ind',
                               'pos': 'VVFIN',
                               'word': 'hat'},
                      's5_500': {'label': 'SB',
                                 'cat': 'NP',
                                 'edges': {'s5_1': {'label': 'NK',
                                                    'morph': 'Def.Fem.Nom.Sg',
                                                    'pos': 'ART',
                                                    'word': 'Die'},
                                           's5_2': {'label': 'NK',
                                                    'morph': 'Fem.Nom.Sg.*',
                                                    'pos': 'NN',
                                                    'word': 'Tagung'},
                      's5_503': {'label': 'OA',
                                 'cat': 'NP',
                                 'edges': {'s5_5': {'label': 'NK',
                                                    'morph': 'Masc.Akk.Pl.*',
                                                    'pos': 'NN',
                                                    'word': 'Teilnehmer'},
                                           's5_502': {'label': 'NK',
                                                      'cat': 'AP',
                                                      'edges': {'s5_4': {'label': 'HD',
                                                                         'morph': '--',
                                                                         'pos': 'PIAT',
                                                                         'word': 'mehr'},
                                                                's5_501': {'label': 'CC',
                                                                           'cat': 'AVP',
                                                                           'edges': {'s5_6': {'label': 'CM',
                                                                                              'morph': '--',
                                                                                              'pos': 'KOKOM',
                                                                                              'word': 'als'},
                                                                                     's5_7': {'label': 'MO',
                                                                                              'morph': '--',
                                                                                              'pos': 'ADV',
                                                                                              'word': 'je'},
                                                                                     's5_8': {'label': 'HD',
                                                                                              'morph': '--',
                                                                                              'pos': 'ADV',
                                                                                              'word': 'zuvor'}}}}}}}}}}
Das heißt, ich möchte vom root-Symbol ausgehend rekursiv eine Art Baum erstellen. Wie mache ich das? Ich halte das für die sinnvollste Möglichkeit, syntaktische Abhängigkeiten darzustellen. Der Sinn des ganzen liegt übrigens darin, dass ich für Leute, die Deutsch als Fremdsprache lernen, Übungsaufgaben automatisch aus einem Korpus generieren möchte. Für diesen Zweck möchte ich auch Übungen zur Satzstellung im Deutschen generieren, daher die syntaktische Analyse. Wenn ihr meine Struktur nicht für sinnvoll haltet, dann zeigt mir bitte an einem konkreten(!) Beispiel, wie ihr es machen würdet. Sonst versteh ich es wahrscheinlich immer noch nicht.

Danke! :)

Re: Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Samstag 6. August 2011, 14:44
von Dingels
Kann mir denn niemand dabei helfen? :K

Re: Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Samstag 6. August 2011, 15:22
von BlackJack
@Dingels: Ich weiss nicht wie es anderen geht, aber ich sehe halt nicht auf Anhieb wie das was Du hast, mit dem zusammenhängt was Du haben möchtest. Und raten mag ich nicht. Andererseits: Wenn Du es Schritt für Schritt beschreiben würdest, hast Du höchstwahrscheinlich auch schon selbst die Antwort auf Deine Frage.

Re: Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Sonntag 7. August 2011, 01:42
von pillmuncher
@Dingels: grundsätzlich würde ich ungefähr sowas machen:

Code: Alles auswählen

from lxml import etree

xmlsatz = '''
<s id="s5">
  <graph root="s5_504">
    ...
  </graph>
</s>
'''

tree = etree.fromstring(xmlsatz)

def map_ids(elem):
    if 'id' in elem.attrib:
        yield elem.attrib['id'], elem
    for child in elem:
        for each in map_ids(child):
            yield each

nodes = dict(map_ids(tree))

def print_ast(node_id, indent=0):
    if 'word' in nodes[node_id].attrib:
        print '    ' * indent, node_id, ':', nodes[node_id].attrib['word']
    else:
        print '    ' * indent, node_id, ':', nodes[node_id].attrib['cat']
        for edge in nodes[node_id].xpath('edge'):
            print_ast(edge.attrib['idref'], indent + 1)

print_ast(tree.xpath('graph')[0].attrib['root'])
Ergebnis:

Code: Alles auswählen

 s5_504 : S
     s5_500 : NP
         s5_1 : Die
         s5_2 : Tagung
     s5_3 : hat
     s5_503 : NP
         s5_502 : AP
             s5_4 : mehr
             s5_501 : AVP
                 s5_6 : als
                 s5_7 : je
                 s5_8 : zuvor
         s5_5 : Teilnehmer
Die Feinarbeit überlass ich dir ;-).

Gruß,
Mick.

Re: Brauche Hilfe bei komplexer XML-Struktur

Verfasst: Dienstag 9. August 2011, 00:38
von pillmuncher
Mir war fad (Python 2.7):

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from lxml import etree

def filter_by_keys(adict, *keys):
    return {key:value for key, value in adict.iteritems() if key in keys}

def build_ast(nodes, node, attribs={}):
    if node.tag == 't':
        return filter_by_keys(attribs, 'label', 'morph', 'pos', 'word')
    elif node.tag == 'nt':
        result = filter_by_keys(attribs, 'label', 'cat')
        result['edges'] = {
            edge.attrib['idref']:build_ast(
                nodes,
                nodes[edge.attrib['idref']],
                dict(
                    attribs.items() +
                    edge.attrib.items() +
                    nodes[edge.attrib['idref']].attrib.items()
                )
            )
                for edge in node.xpath('edge')
        }
        return result
    else:
        raise ValueError('node muss ein XML-Tag vom Typ <t> oder <nt> sein!')

if __name__ == '__main__':

    import pprint

    xmltext = '''
        <s id="s5">
          <graph root="s5_504">
            ... (s.o.)
          </graph>
        </s>
    '''

    xmltree = etree.fromstring(xmltext)
    elems = {
        elem.attrib['id']:elem
            for elem in xmltree.getiterator()
                if 'id' in elem.attrib
    }
    root = xmltree.xpath('graph')[0].attrib['root']
    pprint.pprint({root:build_ast(elems, elems[root])})
Ergebnis:

Code: Alles auswählen

{'s5_504': {'cat': 'S',
            'edges': {'s5_3': {'label': 'HD',
                               'morph': '3.Sg.Pres.Ind',
                               'pos': 'VVFIN',
                               'word': 'hat'},
                      's5_500': {'cat': 'NP',
                                 'edges': {'s5_1': {'label': 'NK',
                                                    'morph': 'Def.Fem.Nom.Sg',
                                                    'pos': 'ART',
                                                    'word': 'Die'},
                                           's5_2': {'label': 'NK',
                                                    'morph': 'Fem.Nom.Sg.*',
                                                    'pos': 'NN',
                                                    'word': 'Tagung'}},
                                 'label': 'SB'},
                      's5_503': {'cat': 'NP',
                                 'edges': {'s5_5': {'label': 'NK',
                                                    'morph': 'Masc.Akk.Pl.*',
                                                    'pos': 'NN',
                                                    'word': 'Teilnehmer'},
                                           's5_502': {'cat': 'AP',
                                                      'edges': {'s5_4': {'label': 'HD',
                                                                         'morph': '--',
                                                                         'pos': 'PIAT',
                                                                         'word': 'mehr'},
                                                                's5_501': {'cat': 'AVP',
                                                                           'edges': {'s5_6': {'label': 'CM',
                                                                                              'morph': '--',
                                                                                              'pos': 'KOKOM',
                                                                                              'word': 'als'},
                                                                                     's5_7': {'label': 'MO',
                                                                                              'morph': '--',
                                                                                              'pos': 'ADV',
                                                                                              'word': 'je'},
                                                                                     's5_8': {'label': 'HD',
                                                                                              'morph': '--',
                                                                                              'pos': 'ADV',
                                                                                              'word': 'zuvor'}},
                                                                           'label': 'CC'}},
                                                      'label': 'NK'}},
                                 'label': 'OA'}}}}
Alle Zeiten sind UTC+01:00
Seite 1 von 1

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de