Parallel algorithms for the static dictionary compression

D
DCC
1995
Data Compression Conference (DCC '95)
Abstract - Parallel algorithms for the static dictionary compression

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by H. Nagumo Articles by Mi Lu Articles by K. Watson

Data Compression Conference (DCC '95)

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

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.1995.515506

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.