The Performance of Linear Time Suffix Sorting Algorithms

Snowbird, Utah March 29-March 31

DOI Bookmark:

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

Data Compression Conference (DCC'05)

	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 Simon J. Puglisi Articles by William F. Smyth Articles by Andrew Turpin

	ASCII Text	x
	Simon J. Puglisi, William F. Smyth, Andrew Turpin, "The Performance of Linear Time Suffix Sorting Algorithms," Data Compression Conference, pp. 358-367, Data Compression Conference (DCC'05), 2005.

	BibTex	x
	@article{ 10.1109/DCC.2005.87, author = {Simon J. Puglisi and William F. Smyth and Andrew Turpin}, title = {The Performance of Linear Time Suffix Sorting Algorithms}, journal ={Data Compression Conference}, volume = {0}, year = {2005}, issn = {1068-0314}, pages = {358-367}, doi = {http://doi.ieeecomputersociety.org/10.1109/DCC.2005.87}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Data Compression Conference TI - The Performance of Linear Time Suffix Sorting Algorithms SN - 1068-0314 SP358 EP367 A1 - Simon J. Puglisi, A1 - William F. Smyth, A1 - Andrew Turpin, PY - 2005 KW - null VL - 0 JA - Data Compression Conference ER -

Simon J. Puglisi, Curtin University of Technology, Perth, Australia

William F. Smyth, McMaster University, Hamilton, Canada

Andrew Turpin, University of Melbourne, Australia

Sorting all the suffixes of a string x = x[1..n] into lexicographical order is the most computationally expensive step in the Burrows-Wheeler Transformation for lossless compression. One tool for achieving a suffix sort is the suffix array. Suffix arrays are also the basis for a variety of compressed text indexing systems that allow arbitrary queries, for example the scheme of Grossi and Vitter.

Citation:

Simon J. Puglisi, William F. Smyth, Andrew Turpin, "The Performance of Linear Time Suffix Sorting Algorithms," dcc, pp.358-367, Data Compression Conference (DCC'05), 2005

Peer Review Notice | Give Us Feedback

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