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.

Crochemore, M., Giambruno, L., Langiu, A., Mignosi, F., Restivo, A. (2012). Dictionary-symbolwise flexible parsing. JOURNAL OF DISCRETE ALGORITHMS, Journal of Discrete Algorithms 14 (2012)(14 (2012)), 74-90 [10.1016/j.jda.2011.12.021].

Dictionary-symbolwise flexible parsing

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

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.
2012
Settore INF/01 - Informatica
Crochemore, M., Giambruno, L., Langiu, A., Mignosi, F., Restivo, A. (2012). Dictionary-symbolwise flexible parsing. JOURNAL OF DISCRETE ALGORITHMS, Journal of Discrete Algorithms 14 (2012)(14 (2012)), 74-90 [10.1016/j.jda.2011.12.021].
File in questo prodotto:
File Dimensione Formato  
JDA423.pdf

Solo gestori archvio

Descrizione: Articolo
Dimensione 463.88 kB
Formato Adobe PDF
463.88 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/63122
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 7
social impact