The Performance of Linear Time Suffix Sorting Algorithms

	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/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

Data Compression Conference (DCC'05)

Snowbird, Utah

March 29-March 31

ISBN: 0-7695-2309-9

	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

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

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.