Prague Stringology Conference 2023
A Worst Case Analysis of the LZ2 Compression Algorithm with Bounded Size Dictionaries
| Abstract: |
| We make a worst case analysis of practical implementations of LZ2 compression, where the work space remains constant with the increase of the data size and the optimal solution must work with the same on-line decoder. The memory bound implies an off-line standard polynomial time optimal solution with huge multiplicative constants and we show that an on-line approach approximates with a large factor, leaving the design of an effective and more efficient off-line coding as an open problem in this context. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |