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.

CROCHEMORE, M., GIAMBRUNO, L., LANGIU, A., MIGNOSI, F., RESTIVO, A. (2011). Dictionary-Symbolwise Flexible Parsing. In Combinatorial Algorithms - 21st International Workshop, IWOCA 2010. Iliopoulos, Costas S. [10.1007/978-3-642-19222-7_38].

Dictionary-Symbolwise Flexible Parsing

GIAMBRUNO, Laura;LANGIU, Alessio;RESTIVO, Antonio
2011-01-01

Abstract

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.
lug-2010
21st International Workshop on Combinatorial Algorithms
London
26-28 July 2010
21
2011
14
CROCHEMORE, M., GIAMBRUNO, L., LANGIU, A., MIGNOSI, F., RESTIVO, A. (2011). Dictionary-Symbolwise Flexible Parsing. In Combinatorial Algorithms - 21st International Workshop, IWOCA 2010. Iliopoulos, Costas S. [10.1007/978-3-642-19222-7_38].
Proceedings (atti dei congressi)
CROCHEMORE, M; GIAMBRUNO, L; LANGIU, A; MIGNOSI, F; RESTIVO, A
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/53245
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact