loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Data Compression Conference (DCC '95)
Parallel algorithms for the static dictionary compression
Snowbird, Utah
March 28-March 30
ISBN: 0-8186-7012-6
ASCII Text
x 
 
H. Nagumo, Mi Lu, K. Watson, "Parallel algorithms for the static dictionary compression," Data Compression Conference, pp. 162, Data Compression Conference (DCC '95), 1995.
 
 
BibTex
x
 
@article{ 10.1109/DCC.1995.515506,
author = {H. Nagumo and Mi Lu and K. Watson},
title = {Parallel algorithms for the static dictionary compression},
journal ={Data Compression Conference},
volume = {0},
year = {1995},
isbn = {0-8186-7012-6},
pages = {162},
doi = {http://doi.ieeecomputersociety.org/10.1109/DCC.1995.515506},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Data Compression Conference
TI - Parallel algorithms for the static dictionary compression
SN - 0-8186-7012-6
SP
EP
A1 - H. Nagumo,
A1 - Mi Lu,
A1 - K. Watson,
PY - 1995
KW - parallel algorithms; data compression; glossaries; computational complexity; parallel algorithms; static dictionary compression strategies; optimal compression; prefix property; maximum allowable entry length; longest-fragment-first compression; time performance; processor number; sequential LFF dictionary compression; online computation; lookahead length; computational complexity
VL - 0
JA - Data Compression Conference
ER -
 
H. Nagumo, Dept. of Electr. Eng., Texas A&M Univ., College Station, TX, USA
Mi Lu, Dept. of Electr. Eng., Texas A&M Univ., College Station, TX, USA
K. Watson, Dept. of Electr. Eng., Texas A&M Univ., College Station, TX, USA
Studies parallel algorithms for two static dictionary compression strategies. One is the optimal dictionary compression with dictionaries that have the prefix property, for which our algorithm requires O(L+log n) time and O(n) processors, where L is the maximum allowable length of the dictionary entries, while previous results run in O(L+log n) time using O(n/sup 2/) processors, or in O(L+log/sup 2/n) time using O(n) processors. The other algorithm is the longest-fragment-first (LFF) dictionary compression, for which our algorithm requires O(L+log n) time and O(nL) processors, while the previous result has O(L log n) time performance on O(n/log n) processors. We also show that the sequential LFF dictionary compression can be computed online with a lookahead of length O(L/sup 2/)
Index Terms:
parallel algorithms; data compression; glossaries; computational complexity; parallel algorithms; static dictionary compression strategies; optimal compression; prefix property; maximum allowable entry length; longest-fragment-first compression; time performance; processor number; sequential LFF dictionary compression; online computation; lookahead length; computational complexity
Citation:
H. Nagumo, Mi Lu, K. Watson, "Parallel algorithms for the static dictionary compression," dcc, pp.162, Data Compression Conference (DCC '95), 1995
Usage of this product signifies your acceptance of the Terms of Use.