This shows you the differences between two versions of the page.

Link to this comparison view

news:markus_lohrey_uni_siegen_gast_am_lehrstuhl [2015-09-08 15:53] (current)
Line 1: Line 1:
 +====== Markus Lohrey (Uni Siegen) Gast am Lehrstuhl ======
 +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.
 +=== Zusammenfassung ===
 +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.
Last modified: 2015-09-08 15:53 (external edit)