Ähnliche Zweige in mehreren Bäumen finden

Question

Sagen wir, wir haben N Bäume mit verschiedenen Größen und Strukturen. Was ist der beste Weg, um die ähnlichen Zweige zwischen all diesen Bäumen zu finden? Das ultimative Ziel ist es, alle ähnlichen Unterbäume zu finden und sie von den längsten ähnlichen Zweigen (Baumebenen) zu den kürzesten Zweigen zu sortieren.

Der Zweck der Frage ist das ähnlich zu finden schließt sich unter den mehreren Abfragen. Wenn wir jede Abfrage als eine Baumstruktur darstellen, werden die Zweige auf jeder Ebene durch die Joins erzeugt. Und ich versuche die ähnlichen Verknüpfungen zwischen allen Abfragen zu finden.

Answer 1

Beginnen Sie mit dem Erstellen einer Karte vom Tabellennamen zur Liste von (Baum, Position im Baum). Bei der Erstellung finden Sie, wo dieselbe Tabelle zweimal referenziert wird. Notieren Sie sich, wo beide Kinder eines Baumknotens Blätter sind.

Besuchen Sie die Orte, wo beide Kinder eines Knotens Blätter sind. Entfernen Sie diese untergeordneten Elemente und deren übergeordnete Elemente aus der Struktur, und ersetzen Sie sie durch einen neuen Tabellennamen. Verwenden Sie dabei denselben Tabellennamen, bei dem die beiden gerade entfernten Tabellen identisch sind. Beim Aktualisieren der Karte erfahren Sie, wo Teilbäume der maximalen Tiefe 1 im Baum zweimal referenziert werden. Notieren Sie Orte, an denen diese Bearbeitung neue Orte hervorgebracht hat, an denen beide untergeordneten Elemente eines Baumknotens Blätter sind.

Wiederholen Sie den vorherigen Absatz Orte zu erkennen, wo in der ursprünglichen Baum, wir identische Teilbäume der maximalen Tiefe haben 2.

Weiter, bis Sie alle Bäume in Nicht-Existenz bearbeitet haben. Sie haben nun alle Teilbaumübereinstimmungen in umgekehrter Reihenfolge der maximalen Tiefe gefunden.