The Library
Implementation and experimental evaluation of flexible parsing for dynamic dictionary based data compression
Tools
Matias, Yossi, Rajpoot, Nasir M. (Nasir Mahmood) and Sahinalp, Suleyman Cenk (2008) Implementation and experimental evaluation of flexible parsing for dynamic dictionary based data compression. In: 2nd Workshop on Algorithm Engineering (WAE 1998), Saarbrucken, Germany, 20-22 Aug 2008. Published in: Proceedings WAE’98
|
PDF
WRAP_Rajpoot_wae98.pdf - Published Version - Requires a PDF viewer. Download (237Kb) | Preview |
Abstract
We report on the implementation and performance evaluation of greedy parsing with lookaheads for dynamic dictionary compression. Specifically, we consider the greedy parsing with a single step lookahead which we call Flexible Parsing (FP) as an alternative to the commonly used greedy parsing (with no-lookaheads) scheme. Greedy parsing is the basis of most popular compression programs including unix compress and gzip, however it does not necessarily achieve optimality with regard to the dictionary construction scheme in use. Flexible parsing, however, is optimal, i.e., partitions any given input to the smallest number of phrases possible, for dictionary construction schemes which satisfy the prefix property throughout their execution.
There is an on-line linear time and space implementation of the FP scheme via the trie-reverse-trie pair data structure [MS98]. In this paper, we introduce a more practical, randomized data structure to implement FP scheme whose expected theoretical performance matches the worst case performance of the trie-reverse-trie-pair. We then report on the compression ratios achieved by two FP based compression programs we implemented. We test our programs against compress and gzip on various types of data on some of which we obtain up to 35% improvement.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Data compression (Computer science) | ||||
Journal or Publication Title: | Proceedings WAE’98 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Date of first compliant deposit: | 28 July 2016 | ||||
Date of first compliant Open Access: | 28 July 2016 | ||||
Funder: | North Atlantic Treaty Organization (NATO), European Commission (EC) | ||||
Grant number: | CRG-972175 (NATO), ESPRIT LTR Project no. 20244 - ALCOM IT (EC) | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 2nd Workshop on Algorithm Engineering (WAE 1998) | ||||
Type of Event: | Workshop | ||||
Location of Event: | Saarbrucken, Germany | ||||
Date(s) of Event: | 20-22 Aug 2008 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year