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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.