Dictionary-Symbolwise Flexible Parsing

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

Risultato della ricerca: Other

6 Citazioni (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.
Lingua originaleEnglish
Numero di pagine14
Stato di pubblicazionePublished - 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Entra nei temi di ricerca di 'Dictionary-Symbolwise Flexible Parsing'. Insieme formano una fingerprint unica.

  • Cita questo

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