Zobrazeno 1 - 8
of 8
pro vyhledávání: '"Carl Philipp Reh"'
Autor:
Danny Hucke, Carl Philipp Reh
Publikováno v:
Algorithms, Vol 14, Iss 2, p 65 (2021)
A grammar-based compressor is an algorithm that receives a word and outputs a context-free grammar that only produces this word. The approximation ratio for a single input word is the size of the grammar produced for this word divided by the size of
Externí odkaz:
https://doaj.org/article/4008000827fd4605befdf45daf149383
Publikováno v:
Information Processing Letters. 147:27-31
It is shown that for a given ordered node-labelled tree of size n and with s different node labels, one can construct in linear time a top dag of height O ( log n ) and size bounded by O ( n / log σ n ) and O ( d ⋅ log n ) , where σ =
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::517ec6ece248c30f6782165a3b50e0f1
https://doi.org/10.1016/j.ipl.2019.03.001
https://doi.org/10.1016/j.ipl.2019.03.001
Autor:
Carl Philipp Reh, Danny Hucke
Publikováno v:
Algorithms
Volume 14
Issue 2
Algorithms, Vol 14, Iss 65, p 65 (2021)
Volume 14
Issue 2
Algorithms, Vol 14, Iss 65, p 65 (2021)
A grammar-based compressor is an algorithm that receives a word and outputs a context-free grammar that only produces this word. The approximation ratio for a single input word is the size of the grammar produced for this word divided by the size of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::84ea3be5df09846fd2973acad39487c5
Autor:
Carl Philipp Reh, Kurt Sieber
Publikováno v:
String Processing and Information Retrieval ISBN: 9783030592110
SPIRE
SPIRE
We present a data structure of linear size that allows to perform navigation steps and subtree equality checks in grammar-compressed forests in constant time. Navigation steps include going to the parent, to the left/right neighbor or to the first/la
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::096a8bd2239fa850310c8a1e74a5ec8c
https://doi.org/10.1007/978-3-030-59212-7_2
https://doi.org/10.1007/978-3-030-59212-7_2
Autor:
Artur Jeż, Danny Hucke, Hideo Bannai, Carl Philipp Reh, Markus Lohrey, Momoko Hirayama, Shunsuke Inenaga
In a seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Her
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::465a1382023f1235cd31b4aa0326c1d8
http://arxiv.org/abs/1908.06428
http://arxiv.org/abs/1908.06428
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783319905297
CSR
CSR
We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b29e3c3f0d552a91add0a753fd72ca44
https://doi.org/10.1007/978-3-319-90530-3_11
https://doi.org/10.1007/978-3-319-90530-3_11
Publikováno v:
String Processing and Information Retrieval ISBN: 9783319460482
SPIRE
SPIRE
In a seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Her
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ed4f321f0a11fcb82ec94451c2c94263
https://doi.org/10.1007/978-3-319-46049-9_4
https://doi.org/10.1007/978-3-319-46049-9_4
Publikováno v:
DCC
Lohrey, M, Maneth, S & Reh, C P 2016, Traversing Grammar-Compressed Trees with Constant Delay . in 2016 Data Compression Conference . 2016 Data Compression Conference, Snowbird, United States, 29/03/16 . < http://arxiv.org/abs/1511.02141 >
Lohrey, M, Maneth, S & Reh, C P 2016, Traversing Grammar-Compressed Trees with Constant Delay . in 2016 Data Compression Conference . 2016 Data Compression Conference, Snowbird, United States, 29/03/16 . < http://arxiv.org/abs/1511.02141 >
A grammar-compressed ranked tree is represented with a linear space overhead so that a single traversal step, i.e., the move to the parent or the i-th child, can be carried out in constant time. Moreover, we extend our data structure such that equali
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0e7c062ca685937ab6c51448a5328b85
http://arxiv.org/abs/1511.02141
http://arxiv.org/abs/1511.02141