The Library
Less redundant codes for variable size dictionaries
Tools
Yao, Zhen and Rajpoot, Nasir M. (2002) Less redundant codes for variable size dictionaries. In: IEEE Data Compression Conference (DCC 2002), Utah, US, 2-4 Apr 2002. Published in: Proceedings DCC 2002 : data compression conference p. 481. ISBN 0769514774. ISSN 1068-0314.
|
PDF
WRAP_dcc02_full.pdf - Requires a PDF viewer. Download (434Kb) | Preview |
Official URL: http://dx.doi.org/10.1109/DCC.2002.1000024
Abstract
We report on a family of variable-length codes with less redundancy than the flat code used in most of the variable size dictionary-based compression methods. The length of codes belonging to this family is still bounded above by [log_2/ |D|] where |D| denotes the dictionary size. We describe three of these codes, namely, the balanced code, the phase-in-binary code (PB), and the depth-span code (DS). As the name implies, the balanced code is constructed by a height balanced tree, so it has the shortest average codeword length. The corresponding coding tree for the PB code has an interesting property that it is made of full binary phases, and thus the code can be computed efficiently using simple binary shifting operations. The DS coding tree is maintained in such a way that the coder always finds the longest extendable codeword and extends it until it reaches the maximum length. It is optimal with respect to the code-length contrast. The PB and balanced codes have almost similar improvements, around 3% to 7% which is very close to the relative redundancy in flat code. The DS code is particularly good in dealing with files with a large amount of redundancy, such as a running sequence of one symbol. We also did some empirical study on the codeword distribution in the LZW dictionary and proposed a scheme called dynamic block shifting (DBS) to further improve the codes' performance. Experiments suggest that the DBS is helpful in compressing random sequences. From an application point of view, PB code with DBS is recommended for general practical usage.
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 DCC 2002 : data compression conference | ||||
Publisher: | Institute of Electrical and Electronics Engineers | ||||
ISBN: | 0769514774 | ||||
ISSN: | 1068-0314 | ||||
Official Date: | 2002 | ||||
Dates: |
|
||||
Page Range: | p. 481 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | IEEE Data Compression Conference (DCC 2002) | ||||
Type of Event: | Conference | ||||
Location of Event: | Utah, US | ||||
Date(s) of Event: | 2-4 Apr 2002 | ||||
Related URLs: |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year