Dictionary-symbolwise flexible parsing

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

Risultato della ricerca: Article

7 Citazioni (Scopus)

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.
Lingua originaleEnglish
pagine (da-a)74-90
Numero di pagine17
RivistaJournal of Discrete Algorithms
VolumeJournal of Discrete Algorithms 14 (2012)
Stato di pubblicazionePublished - 2012

Fingerprint

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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Cita questo

Restivo, A., Giambruno, L., Giambruno, L., Crochemore, M., Langiu, A., Mignosi, F., & Langiu, A. (2012). Dictionary-symbolwise flexible parsing. Journal of Discrete Algorithms, Journal of Discrete Algorithms 14 (2012), 74-90.

Dictionary-symbolwise flexible parsing. / Restivo, Antonio; Giambruno, Laura; Giambruno, Laura; Crochemore, Maxime; Langiu, Alessio; Mignosi, Filippo; Langiu, Alessio.

In: Journal of Discrete Algorithms, Vol. Journal of Discrete Algorithms 14 (2012), 2012, pag. 74-90.

Risultato della ricerca: Article

Restivo, A, Giambruno, L, Giambruno, L, Crochemore, M, Langiu, A, Mignosi, F & Langiu, A 2012, 'Dictionary-symbolwise flexible parsing', Journal of Discrete Algorithms, vol. Journal of Discrete Algorithms 14 (2012), pagg. 74-90.
Restivo A, Giambruno L, Giambruno L, Crochemore M, Langiu A, Mignosi F e altri. Dictionary-symbolwise flexible parsing. Journal of Discrete Algorithms. 2012;Journal of Discrete Algorithms 14 (2012):74-90.
Restivo, Antonio ; Giambruno, Laura ; Giambruno, Laura ; Crochemore, Maxime ; Langiu, Alessio ; Mignosi, Filippo ; Langiu, Alessio. / Dictionary-symbolwise flexible parsing. In: Journal of Discrete Algorithms. 2012 ; Vol. Journal of Discrete Algorithms 14 (2012). pagg. 74-90.
@article{f23659054458453a8fadad074ae39bf1,
title = "Dictionary-symbolwise flexible parsing",
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.",
keywords = "Dictionary-based compression, Directed acyclic graph, Optimal parsing, Stringology, Symbolwise text compression, Text compression",
author = "Antonio Restivo and Laura Giambruno and Laura Giambruno and Maxime Crochemore and Alessio Langiu and Filippo Mignosi and Alessio Langiu",
year = "2012",
language = "English",
volume = "Journal of Discrete Algorithms 14 (2012)",
pages = "74--90",
journal = "Journal of Discrete Algorithms",
issn = "1570-8667",
publisher = "Elsevier",

}

TY - JOUR

T1 - Dictionary-symbolwise flexible parsing

AU - Restivo, Antonio

AU - Giambruno, Laura

AU - Giambruno, Laura

AU - Crochemore, Maxime

AU - Langiu, Alessio

AU - Mignosi, Filippo

AU - Langiu, Alessio

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Dictionary-based compression

KW - Directed acyclic graph

KW - Optimal parsing

KW - Stringology

KW - Symbolwise text compression

KW - Text compression

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

UR - http://dx.doi.org/10.1016/j.jda.2011.12.021

M3 - Article

VL - Journal of Discrete Algorithms 14 (2012)

SP - 74

EP - 90

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

SN - 1570-8667

ER -

Accesso al documento