The Smallest Grammar Problem Revisited
| Autor: | Markus Lohrey, Carl Philipp Reh, Danny Hucke |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Smallest grammar problem
Grammar Bisection media_common.quotation_subject Binary number 0102 computer and information sciences 02 engineering and technology Binary logarithm 01 natural sciences Upper and lower bounds Combinatorics 010201 computation theory & mathematics Compression (functional analysis) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Word (group theory) Mathematics media_common |
| Zdroj: | String Processing and Information Retrieval ISBN: 9783319460482 SPIRE |
| DOI: | 10.1007/978-3-319-46049-9_4 |
| Popis: | 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. Here we close the gaps for LZ78 and BISECTION by showing that the approximation ratio of LZ78 is \(\varTheta ( (n/\log n)^{2/3})\), whereas the approximation ratio of BISECTION is \(\varTheta ( (n/\log n)^{1/2})\). We also derive a lower bound for a smallest grammar for a word in terms of its number of LZ77-factors, which refines existing bounds of Rytter. Finally, we improve results of Arpe and Reischuk relating grammar-based compression for arbitrary alphabets and binary alphabets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|