+1 Punkt
38 Aufrufe

Ich möchte ein Alogrimmo erstellen, das mir erlaubt zu sagen, ob ein Baum in einem anderen enthalten ist. Dank dieser Seite habe ich einen Algorithmus verwaltet, der es mir ermöglicht, BinĂ€rbĂ€ume zu kennen, aber ich wĂŒrde es gerne verallgemeinern.

def isSubtree(T,S):
    '''
    Funktion, um zu sagen, ob ein Baum S ein Unterbaum eines anderen ist, T
    '''
    # Basisfall
    if S is None:
        return True

    if T is None:
        return True

    # ÜberprĂŒfen Sie den Baum mit root als aktuellen Knoten
    if (areIdentical(T, S)):
        return True

    # Wenn der Baum mit der Wurzel als aktueller Knoten nicht ĂŒbereinstimmt
    # dann probiere Kinder aus
    return isSubtree(T.children, S) or isSubtree(T.children, S) # wird nicht funktionieren, weil wir mehrere Kinder haben

def areIdentical(root1, root2):
    '''
    Funktion um zu sagen, ob zwei Wurzeln identisch sind
    '''
    # Basisfall
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False

    # ÜberprĂŒfen Sie, ob die Daten von beiden, ihren Wurzeln und Kindern, identisch sind
    return (root1.data == root2.data and
            areIdentical(root1.children, root2.children)) # Hier Problem, weil es nicht fĂŒr Kinder funktioniert


Erwartete Leistung
Zum Beispiel:


>>># erste Baumerstellung
>>>text = start becoming popular
>>>textSpacy = spacy_nlp(text1)
>>>treeText = nltk_spacy_tree(textSpacy)
>>>t = WordTree(treeText[0])

>>># zweite Baumbildung
>>>question = When did Beyonce start becoming popular?
>>>questionSpacy = spacy_nlp(question)
>>>treeQuestion = nltk_spacy_tree(questionSpacy)
>>>q = WordTree(treeQuestion[0])

>>># Baum comparison
>>>isSubtree(t,q)
True

---

Falls dies nĂŒtzlich sein sollte, hier ist die WordTree-Klasse, die ich verwendet habe:

class WordTree:
    '''Baum fĂŒr spaCy-abhĂ€ngiges Parsing-Array'''
    def __init__(self, tree, is_subtree=False):
        """
        Konstruieren Sie ein neues 'WordTree'-Objekt.

        :param array: Das Array, das die AbhĂ€ngigkeit enthĂ€lt
        :param parent: Das ĂŒbergeordnete Element des Arrays, falls vorhanden
        :return: gibt nichts zurĂŒck
        """
        self.parent = []
        self.children = []
        self.data = tree.label().split('_')[0] # das erste Element des Baumes # Wir werden auch die Synonyme hinzufĂŒgen.

        for subtree in tree:
            if type(subtree) == Tree:
                # Iteriere durch die Tiefe des Teilbaums.
                t = WordTree(subtree, True)
                t.parent=tree.label().split('_')[0]
            elif type(subtree) == str:
                surface_form = subtree.split('_')[0]
                self.children.append(surface_form)

Es funktioniert sehr gut mit BĂ€umen mit spaCy Phrasen :

question = "When did Beyonce start becoming popular?"
questionSpacy = spacy_nlp(question)
treeQuestion = nltk_spacy_tree(questionSpacy)
t = WordTree(treeQuestion[0])

Gefragt von

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...