Combinatorial and information-theoretic aspects of tree compression

Abstract

We analyze lossless tree compression algorithms under information-theoretic and combinatorial aspects. One of the most important and widely used compression methods for rooted trees is to represent a tree by its minimal directed acyclic graph, shortly referred to as minimal DAG. The size of the minimal DAG of the tree is the number of distinct fringe subtrees occurring in the tree, where a fringe subtree of a rooted tree is a subtree induced by one of the nodes and all its descendants. In the first part of this work, we study the average number of distinct fringe subtrees (i.e., the average size of the minimal DAG) in random trees. Specifically, we consider the random tree models of leaf-centric binary tree sources, simply generated families of trees and very simple families of increasing trees. In the second part of this work, we analyze grammar-based tree compression via tree straight-line programs (TSLPs) from an information-theoretic point of view. Specifically, we extend the notion of empirical entropy from stings to node-labeled binary trees and plane trees and show that a suitable binary encoding of TSLPs yields binary tree encodings of size bounded by the empirical entropy plus some lower order terms. This generalizes recent results from grammar-based string compression to grammar-based tree compression. In the third part of this work, we present a new compressed encoding of unlabeled binary and plane trees. We analyze this encoding under an information-theoretic point of view by proving that this encoding is universal und thus asymptotically optimal for a great variety of tree sources; this covers in particular the vast majority of tree sources, with respect to which previous tree sources codes were shown to be universal.

Wir analysieren verlustfreie Methoden der Baumkomprimierung unter informationstheoretischen und kombinatorischen Gesichtspunkten. Eine weit verbreitete Methode der Baumkomprimierung ist die sogenannte DAG-Komprimierung, bei der ein Baum durch seinen zugehörigen minimalen gerichteten azyklischen Graphen (engl. directed acyclic graph, kurz DAG) dargestellt wird. Die Größe dieses minimalen DAGs eines Baums ist die Anzahl der verschiedenen fringe subtrees des Baums. Ein fringe subtree eines gewurzelten Baums ist ein Teilbaum, der von einem der Knoten inklusive aller seiner Nachkommen induziert wird. Im ersten Teil dieser Arbeit analysieren wir die erwartete Anzahl der verschiedenen fringe subtrees (d.h., die durchschnittliche Größe des minimalen DAGs) bzgl. verschiedener Wahrscheinlichkeitsverteilungen auf verschiedenen Baumfamilien. Wir betrachten das Modell der leaf-centric tree sources, das Modell der simply generated families of trees und das Modell der increasing trees. Im zweiten Teil der Arbeit analysieren wir Grammatik-basierte Baumkompression durch sogenannte tree straight-line programs (TSLPs). Wir erweitern den Begriff der empirischen Entropie von Wörtern auf Bäume und zeigen, dass eine geeignete Binärkodierung von TSLPs binäre Baumkodierungen liefert, deren Größe in der empirischen Entropie (plus lower-order terms) beschränkt ist. Im dritten Teil der Arbeit stellen wir eine neue komprimierte Darstellung von Bäumen vor, die universal und daher optimal bezüglich einer großen Anzahl an Baumverteilungen ist; insbesondere gilt dies auch für die Mehrzahl der Verteilungen, bezüglich derer für bisherige Baumkodierungen Universalität nachgewiesen werden konnte.