Am 2.12.2014 besucht uns Markus Lohrey von der Universität Siegen und hält um 16:15 einen Vortrag über “Grammar-based tree compression”. Ort: OH12, Raum 1.055.
Grammar-based string compression has emerged to an active research topic in data compression and string algorithmics. The idea is to code a long text by a context-free grammar that only generates the text. This allows to share repeated subpatterns in texts and leads in the best case to an exponential compression ratio.
One of the attractive features of grammar-based compression is that it can be generalized from strings to other data structures assuming suitable grammatical formalisms exist for the specific data structures. For trees, one can use context-free tree grammars for compression, which are natural generalization of context-free string grammars to trees. In the talk, I will give a survey on recent results on grammar-based tree compression. We will see (i) theoretical bounds on the compression ratio achievable by grammar-based tree compression, (ii) algorithms working on grammar-compressed trees, and (iii) applications in the area of XML compression.