Dictionary-Symbolwise Flexible Parsing

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

Risultato della ricerca: Otherpeer review

6 Citazioni (Scopus)


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

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???


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

Cita questo