Dictionary-Symbolwise Flexible Parsing

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

Research output: Contribution to conferenceOtherpeer-review

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
  • General Computer Science

Fingerprint

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

Cite this