We introduce forest straight-line programs (FSLPs) as a compressed representation for unranked trees (forests). These are compared to other compression formalisms for forests, namely top dags and TSLPs (tree straight-line programs) for fcns (first-child next-sibling) encoding. We show that FSLPs are equally succinct to TSLPs for fcns encodings but converting them to top dags requires a blowup of the alphabet size. All of these formalisms are treated uniformly using an algebraic setting.

We then use FSLPs to implement various data structures and algorithms:

We can answer in polynomial time if two FSLPs produce equal forests modulo associativity and/or modulo commutativity. Allowing linear preprocessing time, we implement a data structure that allows navigation steps on FSLPs (go to the first/last child, the next/previous neighbor or to the parent, or print the symbol at the current location) to occur in constant time. Allowing polynomial time preprocessing, we extend this to include a subtree equality check that works in constant time.

We also study the effects of unorderedness on compression and derive various bounds. In the best case, compression using DAGs can be improved from $n$ to $log n$ when trees are allowed to be reordered, i.e. a ratio of $n / log n$.

For TSLPs/FSLPs instead of DAGs, we show a ratio of $n * log log n / log^2 n$.

We show how to evaluate a form of visibly one-counter automata on FSLPs in polynomial time by implementing them as an algebra.

Finally, we implement an algorithm that produces a top dag and is worst-case optimal, i.e. it always finds a top dag that compresses to at least $n/log n$, while also retaining other beneficial properties from previous top dag compressors.

Wir stellen Forest-Straight-Line-Programme vor, die ungerankte Bäume (Forests) komprimieren. Diese werden mit anderen komprimierten Darstellungen verglichen: Top-Dags und TSLPs (Tree-Straight-Line-Programme) für fcns (First-Child-Next-Sibling)-Kodierung. Wir zeigen, dass FSLPs und TSLPs für fcns gleich stark komprimieren. Beim Konvertieren von FSLPs zu Top-Dags ist allerdings ein Blowup der Alphabetgröße unvermeidbar. All diese Formalismen werden gleichermaßen in einem algebraischen Setting behandelt.

Wir implementieren verschiedene Algorithmen und Datenstrukturen auf FSLPs:

In Polynomialzeit können wir beantworten, ob zwei FSLPs die gleichen Forests modulo Assoziativität und/oder Kommutativität produzieren. Mit linearer Preprocessing-Zeit können wir eine Datenstruktur implementieren, die Navigationsschritte auf FSLPs (gehe zum ersten/letzten Kind, zum nächsten/vorherigen Nachbarn oder zum Elternknoten, oder gib das Symbol an der aktuellen Position aus) in konstanter Zeit durchführen. Mit polynomieller Preprocessing-Zeit können wir dies um einen Subtree-Equality-Check erweitern.

Wir untersuchen außerdem, wie sich Unorderedness auf Kompression auswirkt, wobei wir verschiedene Schranken zeigen. Im besten Fall kann die Kompression eines DAGs von $n$ zu $log n$ verbessert werden, wenn man Bäume umordnen darf, was einem Verhältnis von $n / log n$ entspricht. Im Falle von TSLPs/FSLPs zeigen wir ein Verhältnis von $n * log log n / log^2 n$.

Wir zeigen, wie man eine Art Visibly One-Counter-Automat auf FSLPs auswerten kann, indem wir diese als Algebra implementieren.

Zuletzt implementieren wir einen Algorithmus, der einen Top-Dag produziert, welcher worst-case-optimal ist, d.h. er findet immer einen Top-Dag, der mindestens zu $n / log n$ komprimiert. Außerdem erhält dieser andere nützliche Eigenschaften von vorher eingeführten Top-Dag-Kompressoren.