Dictionary-symbolwise flexible parsing

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

Risultato della ricerca: Articlepeer review

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

All Science Journal Classification (ASJC) codes

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

Fingerprint Entra nei temi di ricerca di 'Dictionary-symbolwise flexible parsing'. Insieme formano una fingerprint unica.

Cita questo