Skuteczna kompresja nieoznakowanych drzew

Rozważ nieoznakowane, ukorzenione drzewa binarne. Możemy skompresować takich drzew: gdy istnieją wskaźniki do poddrzew i T ' z T = T ' (ustne = jak równość strukturalne), możemy zapisać (wlog) T i zastąpić wszystkie wskaźniki do T ' z wskazówki dla T . Zobacz odpowiedź uli na przykład.$T$$T'$$T = T'$$=$$T$$T'$$T$

Podaj algorytm, który przyjmuje drzewo w powyższym sensie jako dane wejściowe i oblicza (minimalną) liczbę węzłów pozostałych po kompresji. Algorytm powinien działać w czasie (w modelu kosztu jednolitego) z n liczbą węzłów na wejściu.$\cal{O}(n\log n)$$n$

To było pytanie egzaminacyjne i nie byłem w stanie znaleźć dobrego rozwiązania, ani go nie widziałem.

Tak, możesz wykonać tę kompresję w czasie , ale nie jest to łatwe :) Najpierw dokonamy pewnych obserwacji, a następnie przedstawimy algorytm. Zakładamy, że drzewo początkowo nie jest skompresowane - nie jest to tak naprawdę potrzebne, ale ułatwia analizę.$O(n \log n)$

Po pierwsze, charakteryzujemy indukcyjnie „równość strukturalną”. Niech i T ' będą dwoma (pod) drzewami. Jeśli zarówno T, jak i T ' są zerowymi drzewami (w ogóle nie mają wierzchołków), są one strukturalnie równoważne. Jeśli oba T i T ' nie są zerowymi drzewami, to są one strukturalnie równoważne, jeśli ich lewe dzieci są strukturalnie równoważne, a ich prawe dzieci są strukturalnie równoważne. „Równoważność strukturalna” to minimalny stały punkt nad tymi definicjami.$T$$T'$$T$$T'$$T$$T'$

Na przykład dowolne dwa węzły liścia są strukturalnie równoważne, ponieważ oba mają drzewa zerowe jako oba swoje dzieci, które są strukturalnie równoważne.

Ponieważ denerwujące jest stwierdzenie „ich lewe dzieci są strukturalnie równoważne, podobnie jak ich prawe dzieci”, często mówimy „ich dzieci są strukturalnie równoważne” i zamierzamy to samo. Zauważ też, że czasami mówimy „ten wierzchołek”, gdy mamy na myśli „poddrzew zakorzeniony w tym wierzchołku”.

$d$$d+1$$O(n^2)$

$\{ 1, 2, 3, \dots, n \}$

$n$$O(n)$

Najpierw kompresujemy wszystkie liście (możemy je znaleźć na liście z wierzchołkami o głębokości 0) w jednym wierzchołku. Przypisujemy temu wierzchołkowi identyfikator. Kompresja dwóch wierzchołków odbywa się poprzez przekierowanie elementu nadrzędnego jednego z wierzchołków, tak aby wskazywał na drugi wierzchołek.

$d$$d$

Iterujemy wszystkie listy z węzłami o jednakowej głębokości od małej głębokości do dużej głębokości. Dla każdego poziomu tworzymy listę par liczb całkowitych, gdzie każda para odpowiada identyfikatorom potomków niektórych wierzchołków na tym poziomie. Mamy dwa wierzchołki na tym poziomie, które są strukturalnie równoważne, jeśli ich odpowiadające sobie pary liczb całkowitych są równe. Korzystając z porządku leksykograficznego, możemy je posortować i uzyskać zestawy równych par liczb całkowitych. Kompresujemy te zestawy do pojedynczych wierzchołków jak wyżej i nadamy im identyfikatory.

$O(n)$$n$$O(n \log n)$

Kompresowanie niemodyfikowalnej struktury danych, aby nie powielała żadnego strukturalnie równego podtermu, znane jest jako sumowanie skrótów . Jest to ważna technika zarządzania pamięcią w programowaniu funkcjonalnym. Hash Consing to rodzaj systematycznego zapamiętywania struktur danych.

$n$$O(n\:\mathrm{lg}(n))$

Rozważę drzewa jako mające następującą strukturę (zapisaną tutaj w składni Haskell):

data Tree = Leaf
          | Node Tree Tree

$\mathtt{nodes} : T \times T \to N$$T$$N$$T = N \uplus \{\ell\}$$\ell$

Możemy wykorzystać strukturę danych w czasie logarytmicznym nodes, na przykład zrównoważone drzewo wyszukiwania binarnego. Poniżej wywołam lookup nodesoperację, która wyszukuje klucz w nodesstrukturze danych, oraz insert nodesoperację, która dodaje wartość do nowego klucza i zwraca ten klucz.

Teraz przechodzimy przez drzewo i dodajemy węzły. Chociaż piszę w pseudokodzie podobnym do Haskella, będę traktować nodesjako zmienną globalną zmienną; będziemy tylko do niego dodawać, ale wstawki muszą być w całości gwintowane. addFunkcja recurses na drzewie, dodając do jego poddrzewa na nodesmapie i zwraca identyfikator korzenia.

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

Liczba insertwywołań, która jest również ostatecznym rozmiarem nodesstruktury danych, to liczba węzłów po maksymalnej kompresji. (W razie potrzeby dodaj jedno puste drzewo).

Oto kolejny pomysł, który ma na celu (iniekcyjne) kodowanie struktury drzew w liczbach, a nie tylko ich arbitralne oznaczanie. W tym celu wykorzystujemy fakt, że faktoryzacja pierwsza dowolnej liczby jest wyjątkowa.

$E$$N(l,r)$$l$$r$$N(E,E)$

$\qquad \displaystyle \begin{align*} f(E) &= 0 \\ f(N(l,r)) &= 2^{f(l)}\cdot 3^{f(r)} \end{align*}$

$f$

To ostatnie założenie dotyczy różnych maszyn; w takim przypadku wolałoby się zastosować coś podobnego do funkcji parowania Cantora zamiast potęgowania.

$\cal{O}(n \log n)$$\cal{O}(n \log n)$

Ponieważ zdjęcia nie są dozwolone w komentarzach:

w lewym górnym rogu: drzewo wejściowe

u góry po prawej: poddrzewa zakorzenione w węzłach 5 i 7 są również izomorficzne.

dolny lewy i prawy: skompresowane drzewa nie są jednoznacznie zdefiniowane.

$7+5|T|$$6+|T|$

Edycja: Czytam pytanie, ponieważ T i T 'były dziećmi tego samego rodzica. Użyłem również definicji kompresji jako rekurencyjnej, co oznacza, że ​​można skompresować dwa wcześniej poddane kompresji poddrzewa. Jeśli to nie jest prawdziwe pytanie, moja odpowiedź może nie działać.

$O(n \log n)$$T(n) = 2T(n/2) + cn$

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    

Gdzie hasSameStructure()jest funkcja, która porównuje dwa już skompresowane poddrzewa w czasie liniowym, aby sprawdzić, czy mają dokładnie taką samą strukturę. Pisanie liniowej funkcji rekurencyjnej w czasie, która przechodzi przez każdą i sprawdza, czy jedno poddrzewo ma pozostawione dziecko za każdym razem, gdy robi to drugie itd., Nie powinno być trudne.

$n_\ell$$n_r$