Effiziente Komprimierung von unbeschrifteten Bäume

cs.stackexchange https://cs.stackexchange.com/questions/168

Frage

Betrachten unbeschrifteten verwurzelt ist, wie binäre Bäume.Wir können komprimieren solche Bäume werden:wenn es ein Zeiger auf Teilbäume $T$ und $T'$ mit $T = T'$ (Dolmetschen $=$ strukturelle Gleichheit), speichern wir (w.l.o.g.) $T$ und ersetzen Sie alle Verweise auf $T'$ mit Zeigern zu $T$.Finden uli ' s Antwort für ein Beispiel.

Geben Sie einen Algorithmus, nimmt einem Baum im obigen Sinne als Eingabe und berechnet die (minimale) Anzahl von Knoten, die bleiben nach der Komprimierung.Der Algorithmus ausgeführt werden soll in der Zeit $\cal{O}(n\log n)$ (in der uniform-cost-Modell) mit $n$ die Anzahl der Knoten in der Eingabe.

Dies war eine Prüfung der Frage, und ich habe nicht in der Lage zu kommen mit einem schönen Lösung, noch habe ich einen gesehen.

War es hilfreich?

Lösung

Ja, Sie können führen Sie diese Komprimierung in $O(n \log n)$ - Zeit, aber es ist nicht einfach :) Wir machen zunächst einige Beobachtungen und dann den Algorithmus.Nehmen wir an, der Baum ist zunächst nicht komprimiert werden - dies ist nicht wirklich notwendig, aber macht die Analyse zu erleichtern.

Erstens haben wir charakterisieren "strukturelle Chancengleichheit", die induktiv.Lassen Sie $T$ und $T'$ zwei (sub -) Bäume.Wenn $T$ und $T'$ sind beide der null-Bäume (ohne Scheitelpunkten aller), Sie sind strukturell äquivalent.Wenn $T$ und $T'$ sind beide nicht null Bäumen, dann sind Sie strukturell äquivalent iff, Ihre linke Kinder sind strukturell vergleichbar und Ihr Recht, Kinder sind strukturell äquivalent."Strukturelle äquivalenz" ist die minimale festen Punkt über diesen Definitionen.

Für Beispiel, zwei Blattknoten sind strukturell äquivalent, weil Sie beide schon die null-Bäume als Ihre beiden Kinder, die sind strukturell äquivalent.

Wie ist es ziemlich ärgerlich, zu sagen: 'Ihre linke Kinder sind strukturell äquivalent und so sind Ihre richtigen Kinder", werden wir oft sagen, "Ihre Kinder sind strukturell gleichwertig' und wollen das gleiche.Beachten Sie auch manchmal sagen wir auch 'in diesem vertex", wenn wir meinen 'Teilbaum verwurzelt in dieser Scheitelpunkt'.

Die obige definition gibt sofort einen Hinweis darauf, wie die Kompression:wenn wir wissen, dass die strukturelle Gleichwertigkeit aller Teilbäume mit der Tiefe von höchstens $d$, dann können wir leicht berechnen die strukturelle Gleichwertigkeit der Teilbäume mit der Tiefe $d+1$.Wir haben diese Berechnung in eine intelligente Art und Weise zu vermeiden, eine $O(n^2)$ Laufzeit.

Der Algorithmus zuweisen von IDS zu jedem vertex während seiner Ausführung.Ein Bezeichner ist eine Zahl in der Menge $\{ 1, 2, 3, \dots, n \}$.IDS eindeutig sind und sich niemals ändern:wir übernehmen daher legen wir einige (Globale) variable um 1 zu Beginn des Algorithmus, und jedes mal, wenn wir das zuweisen einer id zu einigen von vertex, wir weisen Sie dem aktuellen Wert dieser Variablen, die vertex-und Inkrement den Wert der variable.

Wir erste Transformation der input-Struktur in (höchstens $n$) listet die Scheitelpunkte der gleichen Tiefe, zusammen mit einem Zeiger auf das übergeordnete Element.Dies ist leicht getan, in $O(n)$ time.

Wir zuerst komprimieren alle Blätter (wir finden diese Blätter werden in der Liste mit den Eckpunkten Tiefe 0) in einem einzigen Scheitelpunkt.Wir weisen Sie diesem Knoten eine id ein.Kompression von zwei Eckpunkte erfolgt durch Umleitung der Elternteil entweder vertex-zu-Punkt, um den anderen Eckpunkt statt.

Wir machen zwei Beobachtungen:Erstens, jeder Scheitelpunkt hat die Kinder in streng kleineren Tiefe, und zweitens, wenn wir durchgeführt haben, die Komprimierung auf alle Scheitelpunkte der Tiefe, die kleiner als $d$ (und haben Sie identifiers), dann zwei Knoten Tiefe $d$ sind strukturell äquivalent und können komprimiert werden, iff die Kennungen Ihrer Kinder übereinstimmen.Diese Letzte Beobachtung folgt aus dem folgenden argument:zwei Eckpunkte sind strukturell äquivalent iff Ihre Kinder sind strukturell äquivalent, und nach der Kompression bedeutet dies, dass Ihre Zeiger zeigen auf die gleichen Kinder, was wiederum bedeutet, dass die Bezeichner der Ihre Kinder sind gleich.

Wir Durchlaufen alle Listen mit Knoten gleicher Tiefe von geringer Tiefe zu großer Tiefe.Für jede Ebene erstellen wir eine Liste von integer-Paaren, wobei jedes paar entspricht dem Identifier der Kinder von einigen von vertex, die auf diesem Niveau.Wir haben zwei Scheitelpunkte in dieser Ebene sind strukturell äquivalent iff Ihren entsprechenden integer-Paare gleich sind.Mit lexicographic ordering, können wir Sortieren diese und erhalten die sets von integer-Paare, die gleich sind.Komprimieren wir diese Sätze auf einzelne Punkte, wie oben, und geben Sie IDS.

Die obigen Beobachtungen zeigen, dass dieser Ansatz funktioniert und die Ergebnisse in komprimierter Baum.Die Gesamt-Laufzeit ist $O(n)$ plus die Zeit, die benötigt wird, um die Sortierung der Listen, die wir schaffen.Als die gesamte Anzahl von integer-Paaren, die wir erstellen, ist $n$, das gibt uns, dass die Gesamt-Laufzeit ist $O(n \log n)$, wie gewünscht.Zählen, wie viele Knoten haben wir Links am Ende der Prozedur ist trivial (nur anschauen, wie viele IDS haben wir uns ausgehändigt).

Andere Tipps

Komprimieren einer nicht begehrbaren Datenstruktur so, dass sie nicht strukturell gleicher Subterm doppelt Hash. Dies ist eine wichtige Technik in der Speicherverwaltung in der funktionalen Programmierung. Hash -Konflikt ist eine Art systematische Memoisierung für Datenstrukturen.

Wir gehen nach Hash-Konsum in den Baum und zählen die Knoten nach dem Hash-Gegenteil. Hash, der eine Datenstruktur der Größe $ n $ verfolgt, kann immer in $ o (n : mathrm {lg} (n)) $ operations durchgeführt werden; Das Zählen der Anzahl der Knoten am Ende ist in der Anzahl der Knoten linear.

Ich werde Bäume als die folgende Struktur betrachten (hier in Haskell -Syntax geschrieben):

data Tree = Leaf
          | Node Tree Tree

Für jeden Konstruktor müssen wir eine Zuordnung von seinen möglichen Argumenten auf das Ergebnis der Anwendung des Konstruktors auf diese Argumente beibehalten. Blätter sind trivial. Für Knoten behalten wir eine endliche Teilkarte $ mathtt {Knoten}: t mal t bis n $, wobei $ t $ der Satz von Baumkennungen und $ n $ der Satz von Knotenkennungen ist; $ T = n uplus { ell } $ wobei $ ell $ die einzige Blattkennung ist. (In konkreter Begriffen ist ein Kennung ein Zeiger auf einen Speicherblock.)

Wir können eine logarithmische Zeitdatenstruktur für verwenden nodes, wie ein ausgewogener binärer Suchbaum. Unten werde ich anrufen lookup nodes Die Operation, die einen Schlüssel in der nodes Datenstruktur und insert nodes Die Operation, die einen Wert unter einem frischen Schlüssel hinzufügt und diesen Schlüssel zurückgibt.

Jetzt durchqueren wir den Baum und fügen die Knoten hinzu, während wir weitergehen. Obwohl ich in Haskell-ähnlicher Pseudocode schreibe, werde ich behandeln nodes als globale veränderliche Variable; Wir werden es immer nur hinzufügen, aber die Einfügungen müssen überall eingefädelt werden. Das add Die Funktion tritt auf einem Baum zurück und addiert ihre Unterbälde zu der nodes Karte und gibt die Kennung der Wurzel 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 insert Anrufe, was auch die endgültige Größe der ist nodes Datenstruktur ist die Anzahl der Knoten nach maximaler Komprimierung. (Fügen Sie bei Bedarf einen für den leeren Baum hinzu.)

Hier ist eine weitere Idee, die darauf abzielt, die Struktur von Bäumen in Zahlen zu kodieren, anstatt sie nur willkürlich zu kennzeichnen. Dafür verwenden wir, dass die Primfaktorisierung einer beliebigen Zahl einzigartig ist.

Für unsere Zwecke bezeichnen $ e $ eine leere Position im Baum und $ n (l, r) $ einen Knoten mit linksem Subtree $ l $ und rechter Subtree $ R $. $ N (e, e) $ wäre ein Blatt. Nun lass

$ qquad displaystyle begin {align*} f (e) & = 0 f (n (l)) & = 2^{f (l)} cdot 3^{f (r)} Ende {Align*} $

Mit $ F $ können wir die Menge aller Teilbälle in einem Baum-Bottom-up berechnen. In jedem Knoten verschmelzen wir die von den Kindern erhaltenen Codierssätze und fügen eine neue Zahl hinzu (die in konstanter Zeit aus den Kindercodierungen berechnet werden kann).

Diese letzte Annahme ist eine Strecke für echte Maschinen; In diesem Fall würde man lieber etwas Ähnliches verwenden Cantors Paarungsfunktion anstelle von Exponentiation.

Die Laufzeit dieses Algorithmus hängt von der Struktur des Baumes ab (auf ausgewogenen Bäumen $ cal {o} (N log n) $ mit jeder festgelegten Implementierung, die die Vereinigung in der linearen Zeit ermöglicht). Für allgemeine Bäume würden wir eine logarithmische Zeit mit einer einfachen Analyse benötigen. Vielleicht kann eine ausgefeilte Analyse jedoch helfen. Beachten Sie, dass der übliche Worst-Case-Baum, die lineare Liste, $ cal {o} (n log n) $ Zeit hier zulässt, sodass es nicht so klar ist, was der schlimmste Fall sein kann.

Als Bilder sind nicht erlaubt in den Kommentaren:

enter image description here

oben Links:ein input-Baum

oben rechts:die Teilbäume verwurzelt in Knoten 5 und 7 sind isomorph zu.

unten Links und rechts:die komprimierte Bäume sind nicht eindeutig definiert.

Beachten Sie, dass in diesem Fall die Größe des Baumes nach unten gegangen von $7+5|T|$ zu $6+|T|$.

Bearbeiten: Ich habe die Frage gelesen, da T und T 'Kinder desselben Elternteils waren. Ich nahm die Definition der Komprimierung auch als rekursiv an, was bedeutet, dass Sie zwei zuvor komprimierte Teilbäume komprimieren können. Wenn dies nicht die tatsächliche Frage ist, funktioniert meine Antwort möglicherweise nicht.

$ O (n log n) $ bettelt für a $ t (n) = 2T (n/2) + cn $ Divide und Erobererlösung. Komprimieren Sie die Knoten rekursiv und berechnen Sie die Anzahl der Nachkommen in jedem Unterbaum nach der Komprimierung. Hier ist ein Python-ähnlicher 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 Subträume in der linearen Zeit vergleicht, um festzustellen, ob sie genau die gleiche Struktur haben. Schreiben einer linearen Zeitrekursivfunktion, die jeweils durchquert und überprüft, ob das eine Subtree jedes Mal, wenn das andere tut, ein linkes Kind hat. Es sollte nicht schwierig sein.

Sei $ n_ ell $ und $ n_r $ die Größen der linken bzw. rechten Teilbälle (nach Komprimierung). Dann ist die Laufzeit $$ t (n) = t (n_1) + t (n_2) + o (1) mbox {if $ n_ ell neq n_r $} $$ und $$ 2T (n/2) + O (n) mbox {sonst} $$

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top