Effiziente Komprimierung von unbeschrifteten Bäumen

20

Betrachten Sie unbeschriftete, verwurzelte Binärbäume. Wir können solche Bäume komprimieren : wenn es Zeiger auf Teilbäume T und mit (interpretieren T = T ' =TT=T= als strukturelle Gleichheit), speichern wir (oBdA) T und ersetzen Sie alle Verweise auf T mit Zeigern auf T . Siehe uli Antwort für ein Beispiel.

Geben Sie einen Algorithmus an, der einen Baum im obigen Sinne als Eingabe verwendet und die (minimale) Anzahl von Knoten berechnet, die nach der Komprimierung verbleiben. Der Algorithmus sollte in der Zeit O(nlogn) (im einheitlichen Kostenmodell) mit n der Anzahl der Knoten in der Eingabe ausgeführt werden.

Dies war eine Prüfungsfrage, und ich konnte weder eine schöne Lösung finden, noch habe ich eine gesehen.

Raphael
quelle
Und was ist hier „der Preis“, „die Zeit“, die elementare Operation? Die Anzahl der besuchten Knoten? Die Anzahl der überstrichenen Kanten? Und wie wird die Größe der Eingabe angegeben?
uli
Diese Baumkomprimierung ist eine Instanz von Hash-Consing . Nicht sicher, ob dies zu einer generischen Zählmethode führt.
Gilles 'SO- hör auf böse zu sein'
@uli Ich habe klargestellt, was n ist. Ich denke jedoch, dass "Zeit" spezifisch genug ist. In nicht gleichzeitigen Einstellungen entspricht dies der Zählung von Operationen, die in Landau der Zählung der am häufigsten vorkommenden Elementaroperation entspricht.
Raphael
@Raphael Natürlich kann ich mir vorstellen, wie die beabsichtigte elementare Operation aussehen soll und wie wahrscheinlich alle anderen auch. Aber und ich weiß, dass ich hier pedantisch bin, wenn „Zeitgrenzen“ vorgegeben sind, ist es wichtig anzugeben, was gezählt wird. Tauscht, vergleicht, ergänzt, greift auf den Speicher zu, überprüft Knoten, überquert Kanten, Sie nennen es. Es ist wie das Weglassen der Maßeinheit in der Physik. Ist es oder 1010kg ? Und ich nehme an, dass Speicherzugriffe fast immer die häufigste Operation sind. 10ms
uli
@uli Diese Art von Details soll das „einheitliche Kostenmodell“ vermitteln. Es ist schmerzhaft, genau zu definieren, welche Operationen elementar sind, aber in 99,99% der Fälle (einschließlich dieser) gibt es keine Mehrdeutigkeit. Komplexitätsklassen haben grundsätzlich keine Einheiten. Sie messen nicht die Zeit, die für die Ausführung einer Instanz benötigt wird, sondern die Art und Weise, wie diese Zeit variiert, wenn die Eingabe größer wird.
Gilles 'SO - hör auf böse zu sein'

Antworten:

10

Ja, Sie können diese Komprimierung in , aber es ist nicht einfach :) Wir machen zuerst einige Beobachtungen und stellen dann den Algorithmus vor. Wir gehen davon aus, dass der Baum zunächst nicht komprimiert ist - dies ist nicht wirklich erforderlich, erleichtert aber die Analyse.O(nlogn)

Erstens charakterisieren wir "strukturelle Gleichheit" induktiv. Sei und T ' zwei (Unter-) Bäume. Wenn T und T ' beide Nullbäume sind (überhaupt keine Eckpunkte haben), sind sie strukturell äquivalent. Wenn T und T ' beide keine Nullbäume sind, sind sie strukturell äquivalent, wenn ihre linken Kinder strukturell äquivalent sind und ihre rechten Kinder strukturell äquivalent sind. "Strukturelle Äquivalenz" ist der minimale Fixpunkt über diese Definitionen.TTTTTT

Beispielsweise sind zwei beliebige Blattknoten strukturell äquivalent, da beide die Nullbäume als ihre beiden untergeordneten Objekte haben, die strukturell äquivalent sind.

Da es ziemlich ärgerlich ist zu sagen, dass "ihre linken Kinder strukturell gleichwertig sind und ihre rechten Kinder", werden wir oft sagen, dass "ihre Kinder strukturell gleichwertig sind" und dasselbe beabsichtigen. Beachten Sie auch, dass wir manchmal "diesen Scheitelpunkt" sagen, wenn wir "den an diesem Scheitelpunkt verwurzelten Teilbaum" meinen.

Die obige Definition gibt uns sofort einen Hinweis, wie die Komprimierung durchzuführen ist: Wenn wir die strukturelle Äquivalenz aller Teilbäume mit einer Tiefe von höchstens , können wir die strukturelle Äquivalenz der Teilbäume mit einer Tiefe von d + 1 leicht berechnen . Wir müssen diese Berechnung auf intelligente Weise durchführen, um eine Laufzeit von O ( n 2 ) zu vermeiden .dd+1O(n2)

Der Algorithmus weist jedem Scheitelpunkt während seiner Ausführung Bezeichner zu. Ein Bezeichner ist eine Zahl in der Menge . Bezeichner sind eindeutig und ändern sich nie: Wir gehen daher davon aus, dass wir zu Beginn des Algorithmus eine (globale) Variable auf 1 setzen. Jedes Mal, wenn wir einem Scheitelpunkt einen Bezeichner zuweisen, weisen wir dem Scheitelpunkt und dem Inkrement den aktuellen Wert dieser Variablen zu der Wert dieser Variablen.{1,2,3,,n}

Wir transformieren zuerst den Eingabebaum in (höchstens ) Listen, die Scheitelpunkte gleicher Tiefe enthalten, zusammen mit einem Zeiger auf deren Eltern. Dies ist leicht in O ( n ) Zeit möglich.nO(n)

Wir komprimieren zuerst alle Blätter (wir können diese Blätter in der Liste mit Scheitelpunkten der Tiefe 0 finden) zu einem einzigen Scheitelpunkt. Wir weisen diesem Vertex einen Bezeichner zu. Die Komprimierung von zwei Scheitelpunkten erfolgt durch Umleiten des übergeordneten Scheitelpunkts auf den anderen Scheitelpunkt.

Wir machen zwei Beobachtungen: Erstens hat jeder Scheitelpunkt Kinder mit einer streng kleineren Tiefe, und zweitens, wenn wir alle Scheitelpunkte mit einer Tiefe kleiner als komprimiert haben (und ihnen Bezeichner gegeben haben), dann sind zwei Scheitelpunkte mit der Tiefe d strukturell gleich und kann komprimiert werden, wenn die Bezeichner ihrer Kinder übereinstimmen. Diese letzte Beobachtung ergibt sich aus dem folgenden Argument: Zwei Eckpunkte sind strukturell äquivalent, wenn ihre Kinder strukturell äquivalent sind, und nach der Komprimierung bedeuten dies, dass ihre Zeiger auf dieselben Kinder zeigen, was wiederum bedeutet, dass die Bezeichner ihrer Kinder gleich sind.dd

Wir durchlaufen alle Listen mit Knoten gleicher Tiefe von kleiner bis großer Tiefe. Für jede Ebene erstellen wir eine Liste von ganzzahligen Paaren, wobei jedes Paar den Bezeichnern der untergeordneten Elemente eines Scheitelpunkts auf dieser Ebene entspricht. Wir haben, dass zwei Eckpunkte in dieser Ebene strukturell äquivalent sind, wenn ihre entsprechenden ganzzahligen Paare gleich sind. Unter Verwendung der lexikografischen Reihenfolge können wir diese sortieren und die Mengen von ganzzahligen Paaren erhalten, die gleich sind. Wir komprimieren diese Mengen wie oben beschrieben zu einzelnen Eckpunkten und geben ihnen Bezeichner.

Die obigen Beobachtungen beweisen, dass dieser Ansatz funktioniert und zum komprimierten Baum führt. Die Gesamtlaufzeit beträgt plus der Zeit, die zum Sortieren der von uns erstellten Listen benötigt wird. Da die Gesamtzahl der von uns erstellten Ganzzahlpaare n ist , ergibt sich , wie erforderlich , eine Gesamtlaufzeit von O ( n log n ) . Es ist trivial, zu zählen, wie viele Knoten am Ende des Vorgangs noch übrig sind (sehen Sie sich nur an, wie viele Identifikatoren wir ausgegeben haben).O(n)nO(nlogn)

Alex ten Brink
quelle
Ich habe Ihre Antwort nicht im Detail gelesen, aber ich denke, Sie haben das Hash-Consing mit einer seltsamen problemspezifischen Art der Suche nach Knoten mehr oder weniger neu erfunden.
Gilles 'SO - hör auf böse zu sein'
@Alex "Kinder von streng kleinerem degree" Grad sollten wohl sein depth? Und obwohl CS-Bäume nach unten wachsen, finde ich "Höhe eines Baumes" weniger verwirrend als "Tiefe eines Baumes".
uli
Gute Antwort. Ich denke, es sollte eine Möglichkeit geben, das Sortieren zu umgehen. Mein zweiter Kommentar zu @Gilles Antwort gilt auch hier.
Raphael
@uli: yup, du hast recht, ich habe es korrigiert (nicht sicher, warum ich diese beiden Wörter verwechselt habe). Höhe und Tiefe sind zwei subtil unterschiedliche Konzepte, und ich brauchte das letztere :) Ich dachte, ich würde mich an die konventionelle "Tiefe" halten, anstatt alle durch den Austausch zu verwirren.
Alex ten Brink
4

Das Komprimieren einer nicht veränderlichen Datenstruktur, so dass keine strukturell gleiche Teilmenge dupliziert wird, wird als Hash-Consing bezeichnet . Dies ist eine wichtige Technik bei der Speicherverwaltung in der funktionalen Programmierung. Hash Consing ist eine Art systematisches Merken von Datenstrukturen.

Wir werden den Baum Hash-konservieren und die Knoten nach dem Hash-konservieren zählen. Hashes, die eine Datenstruktur der Größe können immer in O ( n) durchgeführt werdenn Operationen; Das Zählen der Anzahl der Knoten am Ende ist linear zur Anzahl der Knoten.O(nlg(n))

Ich werde Bäume mit der folgenden Struktur betrachten (hier in Haskell-Syntax geschrieben):

data Tree = Leaf
          | Node Tree Tree

Für jeden Konstruktor muss eine Zuordnung von den möglichen Argumenten zum Ergebnis der Anwendung des Konstruktors auf diese Argumente verwaltet werden. Blätter sind trivial. Bei Knoten, wir eine endliche Teil Karte aufrechtzuerhalten wobei T der Satz von Baum - Identifikatoren ist und N ist der Satz von Knotenkennungen; T = N { } wobei die einzige Blattkennung ist. (Konkret ist ein Bezeichner ein Zeiger auf einen Speicherblock.)nodes:T×TNTNT=N{}

Wir können eine logarithmisch-zeitliche Datenstruktur für nodesbeispielsweise einen ausgeglichenen binären Suchbaum verwenden. Im Folgenden werde ich lookup nodesdie Operation aufrufen, die einen Schlüssel in der nodesDatenstruktur sucht , und insert nodesdie Operation, die einen Wert unter einem neuen Schlüssel hinzufügt und diesen Schlüssel zurückgibt.

Jetzt überqueren wir den Baum und fügen die Knoten hinzu. Obwohl ich in Haskell-ähnlichem Pseudocode schreibe, werde ich nodesals globale veränderbare Variable behandeln; Wir werden immer nur hinzufügen, aber die Einfügungen müssen durchgehend eingefädelt werden. Die addFunktion rekursiert in einem Baum, fügt seine Unterbäume zur nodesKarte hinzu und gibt den Bezeichner des Stamms zurück.

insert (p1,p2) =
add Leaf = $\ell$
add (Node t1 t2) =
    let p1 = add t1
    let p2 = add t2
    case lookup nodes (p1,p2) of
      Nothing -> insert nodes (p1,p2)
      Just p -> p

Die Anzahl der insertAufrufe, die auch die endgültige Größe der nodesDatenstruktur darstellt, ist die Anzahl der Knoten nach maximaler Komprimierung. (Fügen Sie bei Bedarf eine für den leeren Baum hinzu.)

Gilles 'SO - hör auf böse zu sein'
quelle
Können Sie eine Referenz für "Hash-Verarbeitung einer Datenstruktur der Größe kann immer in O ( n l g ( n ) ) -Operationen durchgeführt werden" angeben ? Beachten Sie, dass Sie für ausgeglichene Bäume benötigen , um die gewünschte Laufzeit zu erreichen. nO(nlG(n))nodes
Raphael
Ich habe nur darüber nachgedacht, Unterstrukturen strukturiert in Zahlen zu zerlegen, damit die unabhängige Berechnung des Hash für denselben Baum immer das gleiche Ergebnis liefert. Ihre Lösung ist auch in Ordnung, vorausgesetzt, wir verfügen über veränderbare Datenstrukturen. Ich denke, es kann ein bisschen aufgeräumt werden; Die Verschachtelung von insertund addsollte explizit gemacht werden, und es sollte eine Funktion angegeben werden, die das Problem tatsächlich löst.
Raphael
1
@Raphael Hash basiert auf einer endlichen Kartenstruktur über Tupel von Zeigern / Bezeichnern. Sie können diese mit logarithmischer Zeit für das Nachschlagen und Hinzufügen implementieren (z. B. mit einem ausgeglichenen binären Suchbaum). Meine Lösung erfordert keine Veränderbarkeit. Ich mache nodesaus Bequemlichkeitsgründen eine veränderbare Variable, aber Sie können sie durchlaufen. Ich werde keinen vollständigen Code angeben, das ist nicht SO.
Gilles 'SO - hör auf böse zu sein'
1
@Raphael Hashing- Strukturen sind im Gegensatz zu der Zuweisung von willkürlichen Zahlen ein bisschen zweifelhaft. Im einheitlichen Kostenmodell können Sie alles in eine große Ganzzahl codieren und Operationen mit konstanter Zeit ausführen, was nicht realistisch ist. In der realen Welt können Sie kryptografische Hashes verwenden, um de facto eine Eins-zu-Eins-Zuordnung von unendlichen Mengen zu einem endlichen Bereich von Ganzzahlen vorzunehmen, aber diese sind langsam. Wenn Sie eine Nicht-Krypto-Prüfsumme als Hash verwenden, müssen Sie über Kollisionen nachdenken.
Gilles 'SO - hör auf böse zu sein'
3

Hier ist eine andere Idee, die darauf abzielt, die Struktur von Bäumen (injektiv) in Zahlen zu kodieren, anstatt sie nur willkürlich zu kennzeichnen. Dafür verwenden wir, dass die Primfaktorisierung jeder Zahl eindeutig ist.

EN(l,r)lrN(E,E)

f(E)=0f(N(l,r))=2f(l)3f(r)

f

Diese letzte Annahme betrifft echte Maschinen. In diesem Fall würde man es vorziehen, etwas Ähnliches wie die Cantor-Paarungsfunktion anstelle der Potenzierung zu verwenden.

O(nLogn)O(nLogn)

Raphael
quelle
1

Da Bilder in Kommentaren nicht erlaubt sind:

Bildbeschreibung hier eingeben

oben links: ein eingabebaum

oben rechts: Die in Knoten 5 und 7 verwurzelten Teilbäume sind ebenfalls isomorph.

Unten links und rechts: Die komprimierten Bäume sind nicht eindeutig definiert.

7+5|T|6+|T|

uli
quelle
Dies ist in der Tat ein Beispiel für die gewünschte Operation, danke. Beachten Sie, dass Ihre endgültigen Beispiele identisch sind, wenn Sie nicht zwischen Original- und hinzugefügten Referenzen unterscheiden.
Raphael
-1

Edit: Ich habe die Frage gelesen, als T und T ′ Kinder desselben Elternteils waren. Ich habe die Definition von Komprimierung auch als rekursiv angesehen, was bedeutet, dass Sie zwei zuvor komprimierte Unterbäume komprimieren können. Wenn das nicht die eigentliche Frage ist, funktioniert meine Antwort möglicherweise nicht.

O(nLogn) bittet um a T(n)=2T(n/2)+cnLösung teilen und erobern. Komprimieren Sie Knoten rekursiv und berechnen Sie die Anzahl der Nachkommen in jedem Teilbaum nach der Komprimierung. Hier ist ein pythonartiger Pseudocode.

def Comp(T):
   if T == null:
     return 0
   leftCount = Comp(T.left)
   rightCount = Comp(T.right)
   if leftCount == rightCount:
     if hasSameStructure(T.left, T.right):
       T.right = T.left
       return leftCount + 1
     else
       return leftCount + rightCount + 1    

Wo hasSameStructure()ist eine Funktion, die zwei bereits komprimierte Teilbäume in linearer Zeit vergleicht, um festzustellen, ob sie exakt die gleiche Struktur haben. Das Schreiben einer rekursiven linearen Zeitfunktion, die jede durchläuft und prüft, ob der eine Teilbaum jedes Mal ein linkes Kind hat, wenn der andere es tut, usw. sollte nicht schwierig sein.

Lassen n und nrSei die Größe des linken und rechten Teilbaums (nach der Komprimierung). Dann ist die Laufzeit

T(n)=T(n1)+T(n2)+O(1) ob nnr
und
2T(n/2)+O(n) Andernfalls
Joe
quelle
Was ist, wenn die Teilbäume keine Geschwister sind? Pflege für ((T1, T1), (T2, T1)) T1 kann zweimal gespeichert werden, indem beim dritten Auftreten ein Zeiger zwei verwendet wird.
uli
@uli Ich bin mir nicht sicher, was du sagst. Ich las die Frage alsT und Twaren Kinder desselben Elternteils. Wenn das nicht die eigentliche Frage ist, funktioniert meine Antwort möglicherweise nicht. Ich habe die Definition von Komprimierung auch als rekursiv angesehen, was bedeutet, dass Sie zwei zuvor komprimierte Unterbäume komprimieren können.
Joe
Die Fragen besagen lediglich, dass zwei Subressen als isomorph identifiziert werden. Es wird nichts darüber gesagt, dass sie die gleichen Eltern haben. Wenn ein Teilbaum T1 in einem Baum dreimal vorkommt, wie in meinem vorherigen Beispiel ((T1, T1), (T1, T2)), können zwei Vorkommen komprimiert werden, indem auf das dritte Vorkommen gezeigt wird.
uli