Wie kann man wissen, ob ein Baum in einem anderen enthalten ist?

Question

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])