Differences
This shows you the differences between two versions of the page.
news:markus_lohrey_uni_siegen_gast_am_lehrstuhl [2015-09-08 15:53] |
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. | ||
+ | |||