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

Answer 1

Antwort mit KI erzeugt

Generelles Konzept zur Überprüfung, ob ein Baum in einem anderen enthalten ist

Um zu prüfen, ob ein Baum \(S\) in einem anderen Baum \(T\) enthalten ist, muss man im Wesentlichen zwei Dinge tun:

1. Bestimmen, ob zwei Bäume exakt identisch sind.
2. Für jeden Knoten in Baum \(T\) überprüfen, ob ein Teilbaum, der mit diesem Knoten als Wurzel beginnt, identisch mit Baum \(S\) ist.

Diese Überprüfung kann rekursiv erfolgen, wobei beide Schritte kombiniert werden. Der Basisalgorithmus funktioniert gut für Binärbäume, muss aber angepasst werden, um mit allgemeineren Bäumen, die mehr als zwei Kinder haben können, zu funktionieren.

Anpassung des Algorithmus für allgemeine Bäume

Die übergebenen Code-Schnipsel sind hauptsächlich für Binärbäume konzipiert. Für allgemeine Bäume, wie in deinem Beispiel die WordTree-Klasse, die potenziell viele Kinder haben kann, müssen Anpassungen vorgenommen werden. Ich werde eine allgemeine Version des Algorithmus skizzieren, die die Eigenschaften der WordTree-Klasse berücksichtigt:

python
class WordTree:
    # Annahme: Die Klasse wurde wie in der Frage beschrieben implementiert

def areIdentical(root1, root2):
    # Überprüfen Sie, ob zwei Bäume identisch sind
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False
    
    # Überprüfen, ob der aktuelle Datenpunkt und die Anzahl der Kinder übereinstimmen
    if root1.data != root2.data or len(root1.children) != len(root2.children):
        return False

    # Rekursive Überprüfung für alle Kinder
    for child1, child2 in zip(root1.children, root2.children):
        if not areIdentical(child1, child2):
            return False
    
    return True

def isSubtree(T, S):
    # Prüfen, ob S ein Unterbaum von T ist
    if S is None:
        return True
    if T is None:
        return False
    if areIdentical(T, S):
        return True
    for child in T.children:
        if isSubtree(child, S):
            return True
    return False

Zu Beachten:

- Die Funktion areIdentical() wurde angepasst, um mit den allgemeinen Bäumen zu arbeiten, indem sie die Daten jedes Knotens und deren Kinder vergleicht.
- Die Funktion isSubtree() durchläuft nun rekursiv alle Kinder des Baumes, anstatt nur links und rechts, wie es bei einem Binärbaum der Fall wäre.
- Die Konstruktion der Bäume und der Vergleichsprozess zwischen den zwei Bäumen bleibt unverändert.

Diese Überarbeitung des ursprünglichen Algorithmus erhöht die Flexibilität und erlaubt es, Bäume mit beliebig vielen Kindern zu behandeln.