Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings
| Autor: | Carl Philipp Reh, Danny Hucke |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
lcsh:T55.4-60.8
Unary operation media_common.quotation_subject addition chain 02 engineering and technology Upper and lower bounds lcsh:QA75.5-76.95 Theoretical Computer Science Combinatorics 020204 information systems 0202 electrical engineering electronic engineering information engineering lcsh:Industrial engineering. Management engineering grammar-based compression data compression approximation algorithm Mathematics media_common Numerical Analysis Grammar Addition chain Approximation algorithm Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Computational Mathematics Computational Theory and Mathematics 020201 artificial intelligence & image processing lcsh:Electronic computers. Computer science Symbol (formal) Word (computer architecture) Computer Science::Formal Languages and Automata Theory Data compression |
| Zdroj: | Algorithms Volume 14 Issue 2 Algorithms, Vol 14, Iss 65, p 65 (2021) |
| ISSN: | 1999-4893 |
| DOI: | 10.3390/a14020065 |
| Popis: | 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 a smallest grammar for this word. The worst-case approximation ratio of a grammar-based compressor for a given word length is the largest approximation ratio over all input words of that length. In this work, we study the worst-case approximation ratio of the algorithms error, error and error on unary strings, i.e., strings that only make use of a single symbol. Our main contribution is to show the improved upper bound of error((logn)8·(loglogn)3) for the worst-case approximation ratio of error. In addition, we also show the lower bound of 1.34847194⋯ for the worst-case approximation ratio of error, and that error and error have a worst-case approximation ratio of log2(3). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|