### Abstract

Lingua originale | English |
---|---|

Stato di pubblicazione | Published - 2011 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cita questo

*Dictionary-Symbolwise Flexible Parsing*.

**Dictionary-Symbolwise Flexible Parsing.** / Restivo, Antonio; Giambruno, Laura; Langiu, Alessio; Mignosi, Filippo; Crochemore, Maxime; Langiu, Alessio.

Risultato della ricerca: Paper

}

TY - CONF

T1 - Dictionary-Symbolwise Flexible Parsing

AU - Restivo, Antonio

AU - Giambruno, Laura

AU - Langiu, Alessio

AU - Mignosi, Filippo

AU - Crochemore, Maxime

AU - Langiu, Alessio

PY - 2011

Y1 - 2011

N2 - Linear time optimal parsing algorithms are very rare in the dictionary based branch of the data compression theory. The most re- cent is the Flexible Parsing algorithm of Mathias and Shainalp that works when the dictionary is prefix closed and the encoding of dictio- nary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionar- ies and any symbolwise compressor under some natural hypothesis. In the case of LZ78-alike algorithms with variable costs and any, linear as usual, symbolwise compressor can be implemented in linear time. In the case of LZ77-alike dictionaries and any symbolwise compressor it can be implemented in O(nlog(n)) time. We further present some experi- mental results that show the effectiveness of the dictionary-symbolwise approach.

AB - Linear time optimal parsing algorithms are very rare in the dictionary based branch of the data compression theory. The most re- cent is the Flexible Parsing algorithm of Mathias and Shainalp that works when the dictionary is prefix closed and the encoding of dictio- nary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionar- ies and any symbolwise compressor under some natural hypothesis. In the case of LZ78-alike algorithms with variable costs and any, linear as usual, symbolwise compressor can be implemented in linear time. In the case of LZ77-alike dictionaries and any symbolwise compressor it can be implemented in O(nlog(n)) time. We further present some experi- mental results that show the effectiveness of the dictionary-symbolwise approach.

KW - Optimal Parsing, Lossless Data Compression, DAG

UR - http://hdl.handle.net/10447/53245

M3 - Paper

ER -