Abstract
Linear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) that works when the dictionary is prefix closed and the encoding of dictionary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionaries and any symbolwise compressor under some natural hypothesis. In the case of LZ78-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbolwise compressor our algorithm can be implemented in time. We further present some experimental results that show the effectiveness of the dictionary-symbolwise approach.
Lingua originale | English |
---|---|
pagine (da-a) | 74-90 |
Numero di pagine | 17 |
Rivista | Journal of Discrete Algorithms |
Volume | Journal of Discrete Algorithms 14 (2012) |
Stato di pubblicazione | Published - 2012 |
All Science Journal Classification (ASJC) codes
- ???subjectarea.asjc.2600.2614???
- ???subjectarea.asjc.2600.2607???
- ???subjectarea.asjc.1700.1703???