Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Jez, Artur

dblp



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

URL of the conference:

http://www.cpm2013.de/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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