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. | ||
| + | |||