Skip to Main content Skip to Navigation
Journal articles

Dictionary-Symbolwise Flexible Parsing

Abstract : Linear time optimal parsing algorithms are very rare in the dictionary based branch of the data compression theory. The most recent is the Flexible Parsing algorithm of Mathias and Shainalp 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-alike algorithms with variable costs and any, linear as usual, symbolwise compressor it can be implemented in linear time. In the case of LZ77-alike dictionaries and any symbolwise compressor it can be implemented in O(n log(n)) time. We further present some experimental results that show the effectiveness of the dictionary-symbolwise approach.
Document type :
Journal articles
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00742078
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 10:02:10 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:28 AM

File

Dictionary-Symbolwise_Flexible...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00742078, version 1

Citation

Maxime Crochemore, Laura Giambruno, Alessio Langiu, Filippo Mignosi, Antonio Restivo. Dictionary-Symbolwise Flexible Parsing. Journal of Discrete Algorithms, Elsevier, 2011, 14 (-), pp.74-90. ⟨hal-00742078⟩

Share

Metrics

Record views

316

Files downloads

449