Struktura danych dla zbiorów drzew.

Próby pozwalają na efektywne przechowywanie list elementów. Prefiksy są wspólne, więc zajmuje mało miejsca.

Szukam podobnego sposobu skutecznego przechowywania drzew. Chciałbym móc sprawdzać członkostwo i dodawać elementy, wiedząc, czy dane drzewo jest poddrzewem niektórych przechowywanych drzew, czy też istnieje drzewo przechowywane, które jest poddrzewem danego drzewa.

Zazwyczaj przechowywałem około 500 niezrównoważonych drzew podwójnych o wysokości mniejszej niż 50.

EDYTOWAĆ

Moja aplikacja jest rodzajem sprawdzania modelu przy użyciu pewnego rodzaju zapamiętywania. Wyobrazić, że mają stan i z następujących wzorów: i z będący złożoną podstruktura i sobie wyobrazić, że najpierw chce wiedzieć, posiada w s . Sprawdzam, czy ϕ się utrzymuje i po długim procesie stwierdzam, że tak jest. Teraz chcę wiedzieć, czy g trzyma si . Chciałbym przypomnieć fakt, że f posiada i zauważyć, że g ⇒ f tak, że może pochodzić g w s prawie natychmiast.f = ϕ g = ( ϕ ∨ ψ ) ϕ $s$$f = \phi$$g = (\phi \vee \psi)$$\phi$$f$$s$$\phi$$g$$s$$f$$g \Rightarrow f$$g$$s$
I odwrotnie, jeśli udowodniłem, że nie utrzymuje wt , to chcę powiedzieć, że f nie utrzymuje wt prawie natychmiast.$g$$t$$f$$t$

Możemy budować częściowe porządki na formułach i mieć iff g ⇒ f . Dla każdego stanu s , możemy przechowywać dwa zestawy wzorów; L ( s ) przechowuje maksymalne formuły, które przechowują, a l ( s ) przechowuje minimalne formuły, które nie przechowują. Teraz biorąc pod uwagę stan si formułę g , widzę, czy ∃ f ∈ L ( s ) , f ⇒ g , czy czy ∃ f ∈ l ( s $g \geq f$$g \Rightarrow f$$s$$L(s)$$l(s)$$s$$g$$\exists f \in L(s), f \Rightarrow g$ w którym to przypadku skończę i wiem bezpośrednio, czy g trzyma w s .$\exists f \in l(s), g \Rightarrow f$$g$$s$

Obecnie i l są implementowane jako listy i nie jest to oczywiście optymalne, ponieważ muszę iterować wszystkie zapisane formuły osobno. Gdyby moje formuły były sekwencjami, a jeśli częściowa kolejność była „jest przedrostkiem”, wtedy trie mogłaby okazać się znacznie szybsza. Niestety moje formuły mają strukturę drzewiastą opartą na ¬ , ∧ , operatorze modalnym i twierdzeniach atomowych.$L$$l$$\neg, \wedge$

Jak wskazują @Raphael i @Jack, mógłbym sekwencjonować drzewa, ale obawiam się, że to nie rozwiąże problemu, ponieważ interesująca mnie cząstkowa kolejność nie odpowiada „przedrostkowi”.

Może chcesz wypróbować g-try . Jest to zasadniczo struktura danych, której szukasz, ale zaprojektowana do użytku z ogólnymi wykresami zamiast tylko z drzewami. Jako taki, nie jestem pewien, czy próby mają dobre gwarancje teoretyczne - myślę, że wykorzystują algorytm kanonizacji grafów jako podprogram - ale w praktyce wydają się działać dobrze.

(Nie bój się, że połączony artykuł dotyczy „motywów sieciowych w sieciach biologicznych”: g-trie to doskonale dobra abstrakcyjna struktura danych dla grafów.)

Szczególną formą tego jest wytrwałość : patrz artykuły Tworzenie struktur danych trwałych przez Driscoll, Sarnak, Sleator i Tarjan oraz Planarna lokalizacja punktu za pomocą drzew ciągłego wyszukiwania Sarnak i Tarjan, które przechowują rodziny powiązanych drzew.

Brzmi to trochę jak las ( rozrzucone lasy ) ...

Amortyzuje koszt wstawienia za pomocą techniki zwanej zgrupowaniem według rangi i operacji wyszukiwania z użyciem kompresji ścieżki . Wiem, że istnieje również trwała wersja tej struktury opracowana przez Sylvaina Conchona i Jean-Christophe Filliâtre, ale nie mam pojęcia, czy jest to ta sama, o której wspomina Jack ...

Co z minimalnymi automatami drzewa ?

W „Purely Functional Data Structures” (1998) Chris Okasaki proponuje próby drzew binarnych z wykorzystaniem agregacji typów (10.3.2).

Nie wiem, czy to natychmiast pomaga; podane tam rozwiązanie może nie być możliwe do wdrożenia bezpośrednio.

W języku programowania: jeśli utworzysz drzewa z typowych podwyrażeń / drzew / DAG, uzyskasz ładny kompaktowy model. Tak ukierunkowane wykresy acykliczne. Wtedy wystarczyłby zestaw drzew.

drzewo klasy publicznej {Operacja na łańcuchach znaków; Drzewo [] poddrzewa;

public int compareTo(Tree rhs) {
    if (rhs == null) return false;
    int cmp = operation.compareTo(rhs.operation);
    if (cmp == 0) {
        cmp = Arrays.compareTo(subtrees, rhs.subtrees);
    }
    return cmp;
}

...}

Map commonSubExpressions = new HashMap ();

Tree get (String expressionSyntax) {Tree t = new Tree (); t.operacja = ...; t.subtrees = ... wywołanie rekurencyjne w celu uzyskania podwyrażeń; Drzewo t2 = commonSubExpressions.get (t); if (t2 == null) {t2 = t; commonSubExpressions.put (t2, t2); } zwróć t2; }}