dc.contributor.author Gupta, Ankur dc.contributor.author Grossi, Roberto dc.contributor.author Vitter, Jeffrey Scott dc.date.accessioned 2011-03-18T19:26:44Z dc.date.available 2011-03-18T19:26:44Z dc.date.issued 2008-01 dc.identifier.citation R. Grossi, A. Gupta, and J. S. Vitter. “Nearly Tight Bounds on the Encoding Length of the Burrows-Wheeler Transform,” in preparation. An extended abstract appears in Proceedings of the 5th Workshop on Analytical Algorithmics and Combinatorics (ANALCO ’08), San Francisco, CA, January 2008, 191–202 dc.identifier.uri http://hdl.handle.net/1808/7193 dc.description.abstract In this paper, we present a nearly tight analysis of the encoding length of the Burrows-Wheeler Transform (bwt) that is motivated by the text indexing setting.For a text T of n symbols drawn from an alphabet , our encoding scheme achieves bounds in terms of the hth-order empirical entropy Hh of the text, and takes linear time for encoding and decoding. We also describe a lower bound on the encoding length of the bwt that constructs an in nite (non-trivial) class of texts that are among the hardest to compress using the bwt. We then show that our upper bound encoding length is nearly tight with this lower bound for the class of texts we described. In designing our bwt encoding and its lower bound, we also address the t-subset problem; here, the goal is to store a subset of t items drawn from a universe [1 dc.language.iso en_US dc.publisher Society for Industrial and Applied Mathematics dc.relation.isversionof http://www.siam.org/proceedings/analco/2008/anl08_018guptaa.pdf dc.title Nearly Tight Bounds on the Encoding Length of the Burrows-Wheeler Transform (Extended Abstract) dc.type Article kusw.kuauthor Vitter, Jeffrey Scott kusw.oastatus fullparticipation kusw.oaversion Scholarly/refereed, publisher version kusw.oapolicy This item meets KU Open Access policy criteria. dc.rights.accessrights openAccess
﻿

### This item appears in the following Collection(s)

785-864-8983
KU Libraries
1425 Jayhawk Blvd
Lawrence, KS 66045
785-864-8983

KU Libraries
1425 Jayhawk Blvd
Lawrence, KS 66045