Parallel algorithms for the static dictionary compression Conference Paper

abstract

• We study 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(n2) processors, or in O(L+log2 n) time using O(n) processors. The other is the longest fragment first (LFF) dictionary compression, for which our algorithm requires O(L+log n) time and O(nL) processors, while 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 on-line with the lookahead of length O(L2).

name of conference

• Proceedings DCC '95 Data Compression Conference

authors

• Lu, Mi
• Watson, Karan

published proceedings

• Proceedings DCC '98 Data Compression Conference (Cat No98TB100225)

author list (cited authors)

• Nagumo, H., Lu, M. i., & Watson, K.

citation count

• 11

complete list of authors

• Nagumo, H||Lu, Mi||Watson, K

publication date

• January 1995

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• Data Compression Conference Proceedings  Journal

Digital Object Identifier (DOI)

• 10.1109/dcc.1995.515506

start page

• 162

end page

• 171

URL

• http://dx.doi.org/10.1109/dcc.1995.515506