Name
Abstract | ||
|---|---|---|
Linear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) 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-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbolwise compressor our algorithm can be implemented in O(nlogn) time. We further present some experimental results that show the effectiveness of the dictionary-symbolwise approach. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jda.2011.12.021 | Journal of Discrete Algorithms |
Keywords | Field | DocType |
flexible parsing algorithm,prefix-closed dictionary,parsing algorithm,lz77-like dictionary,symbolwise compressor,dictionary-symbolwise flexible parsing,linear time,linear-time optimal,dictionary-symbolwise flexible parsing algorithm,lz78-like algorithm,dictionary pointer | Pointer (computer programming),Computer science,Algorithm,Prefix,Compression ratio,Parsing,Time complexity,Data compression,Lossless compression,Encoding (memory) | Journal |
Volume | ISSN | Citations |
14, | 1570-8667 | 3 |
PageRank | References | Authors |
0.40 | 20 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Laura Giambruno | 2 | 22 | 5.35 |
| Alessio Langiu | 3 | 46 | 6.52 |
| Filippo Mignosi | 4 | 569 | 99.71 |
| Antonio Restivo | 5 | 697 | 107.05 |