A Simple Algorithm for Computing the Lempel Ziv Factorization

March 25-March 27

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/DCC.2008.36

Data Compression Conference (dcc 2008)

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Maxime Crochemore Articles by Lucian Ilie Articles by W. F. Smyth

	ASCII Text	x
	Maxime Crochemore, Lucian Ilie, W. F. Smyth, "A Simple Algorithm for Computing the Lempel Ziv Factorization," Data Compression Conference, pp. 482-488, Data Compression Conference (dcc 2008), 2008.

	BibTex	x
	@article{ 10.1109/DCC.2008.36, author = {Maxime Crochemore and Lucian Ilie and W. F. Smyth}, title = {A Simple Algorithm for Computing the Lempel Ziv Factorization}, journal ={Data Compression Conference}, volume = {0}, year = {2008}, issn = {1068-0314}, pages = {482-488}, doi = {http://doi.ieeecomputersociety.org/10.1109/DCC.2008.36}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Data Compression Conference TI - A Simple Algorithm for Computing the Lempel Ziv Factorization SN - 1068-0314 SP482 EP488 A1 - Maxime Crochemore, A1 - Lucian Ilie, A1 - W. F. Smyth, PY - 2008 KW - algorithms design KW - strings KW - suffix array KW - longest common prefix KW - longest previous factor KW - Lempel--Ziv factorization KW - repetitions KW - runs VL - 0 JA - Data Compression Conference ER -

Maxime Crochemore

Lucian Ilie

W. F. Smyth

We give a space-efficient simple algorithm for computing the Lempel--Ziv factorization of a string. For a string of length n over an integer alphabet, it runs in O(n) time independently of alphabet size and uses o(n) additional space.

Index Terms:

algorithms design, strings, suffix array, longest common prefix, longest previous factor, Lempel--Ziv factorization, repetitions, runs

Citation:

Maxime Crochemore, Lucian Ilie, W. F. Smyth, "A Simple Algorithm for Computing the Lempel Ziv Factorization," dcc, pp.482-488, Data Compression Conference (dcc 2008), 2008

Peer Review Notice | Give Us Feedback

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