MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Jez, Arturdblp
Editor(s):
Fischer, Johannes
Sanders, Peter		dblp
dblp
Not MPII Editor(s):
Fischer, Johannes
Sanders, Peter
BibTeX cite key*:
Jez2013CPM
Title, Booktitle
Title*:
Approximation of Grammar-Based Compression via Recompression
Booktitle*:
24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013)
Event, URLs
Conference URL::
http://www.cpm2013.de/
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-38905-4_17
Event Address*:
Bad Herrenalb, Germany
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
17 June 2013
Event End Date:
19 June 2013
Publisher
Name*:
Springer
URL:
http://link.springer.com/
Address*:
Heidelberg, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
7922
Number:
Month:
June
Pages:
165-176
Year*:
2013
VG Wort Pages:
ISBN/ISSN:
978-3-642-38904-7; 978-3-642-38905-4
Sequence Number:
DOI:
10.1007/978-3-642-38905-4_17
Note, Abstract, ©
Note:
Full version at http://arxiv.org/abs/1301.5842
(LaTeX) Abstract:
We present a simple linear-time algorithm constructing a~context-free grammar of size $O(g \log (N/g))$
for the input string of size $N$, where
$g$ the size of the optimal grammar generating this string.
The algorithm works for arbitrary size alphabets,
but the running time is linear assuming that the alphabet $\Sigma$ of the input string
is a subset of $\{1,\ldots , N^c \}$ for some constant $c$.
Algorithms with such an approximation guarantees and running time are known,
the novelty of this paper is the particular simplicity of the algorithm
as well as the analysis of the algorithm, which uses a general
technique of recompression recently introduced by the author.
Furthermore, contrary to the previous results, this work does not use the LZ representation
of the input string in the construction, nor in the analysis.
Keywords:
Grammar-based compression, Construction of the smallest grammar, SLP
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Jez2013CPM,
AUTHOR = {Jez, Artur},
 EDITOR = {Fischer, Johannes and Sanders, Peter},
 TITLE = {Approximation of Grammar-Based Compression via Recompression},
 BOOKTITLE = {24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013)},
 PUBLISHER = {Springer},
 YEAR = {2013},
 VOLUME = {7922},
 PAGES = {165--176},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Bad Herrenalb, Germany},
 MONTH = {June},
 ISBN = {978-3-642-38904-7},
; ISBN = {978-3-642-38905-4},
 DOI = {10.1007/978-3-642-38905-4_17},
 NOTE = {Full version at http://arxiv.org/abs/1301.5842},
}

Entry last modified by Artur Jez, 02/17/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
01/21/2014 03:15:16 PM
Revision
1.
0.


Editor
Artur Jez
Artur Jez


Edit Date
01/21/2014 03:43:00 PM
01/21/2014 03:15:16 PM