Dictionary-Symbolwise Flexible Parsing

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

Research output: Contribution to conferenceOther

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
Number of pages14
Publication statusPublished - 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Dictionary-Symbolwise Flexible Parsing'. Together they form a unique fingerprint.

  • Cite this

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