Dictionary-Symbolwise Flexible Parsing

Antonio Restivo, Laura Giambruno, Alessio Langiu, Filippo Mignosi, Maxime Crochemore, Alessio Langiu

Research output: Contribution to conferencePaper

6 Citations (Scopus)

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.
Original languageEnglish
Publication statusPublished - 2011

Fingerprint

Parsing
Glossaries
Compressor
Alike
Prefix
Compressors
Linear Time
Closed
Data Compression
Costs
Encoding
Branch
Data compression
Dictionary

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Restivo, A., Giambruno, L., Langiu, A., Mignosi, F., Crochemore, M., & Langiu, A. (2011). Dictionary-Symbolwise Flexible Parsing.

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

2011.

Research output: Contribution to conferencePaper

Restivo, A, Giambruno, L, Langiu, A, Mignosi, F, Crochemore, M & Langiu, A 2011, 'Dictionary-Symbolwise Flexible Parsing'.
Restivo, Antonio ; Giambruno, Laura ; Langiu, Alessio ; Mignosi, Filippo ; Crochemore, Maxime ; Langiu, Alessio. / Dictionary-Symbolwise Flexible Parsing.
@conference{047ccefb84674b378f8bf220f1b130b2,
title = "Dictionary-Symbolwise Flexible Parsing",
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.",
keywords = "Optimal Parsing, Lossless Data Compression, DAG",
author = "Antonio Restivo and Laura Giambruno and Alessio Langiu and Filippo Mignosi and Maxime Crochemore and Alessio Langiu",
year = "2011",
language = "English",

}

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 -