Author Description

This dissertation, "On the Construction and Application of Compressed Text Indexes" by Wing-kai, Hon,, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled \On the Construction and Application of Compressed Text Indexes" submitted by Hon Wing Kai for the degree of Doctor of Philosophy at the University of Hong Kong in August 2004 Text indexing involves the preprocessing of a text to build a data structure which enables ecient matching of this text against any pattern afterwards. Tra- ditional indexes like sux trees and sux arrays oer superb matching perfor- mance in theory, and have found numerous applications in practice. However, they consume a lot of space. For a text of lengthn, they have a space requirement of O(n logn) bits, and this demanding space requirement has limited their use for indexing long texts such as DNA sequences. Recent developments, notably the Compressed Sux Arrays (CSA) of Grossi and Vitter, and the FM-index of Ferragina and Manzini, have oered hope of reducing the space requirements of traditional indexes. These two indexes re- quire space linear to the number of bits of the original text, and the matching performance is only slowed down by a polylog(n) factor. However, for such an index to be useful, it must have a space-ecient construction. In this study, we improve an existing construction algorithm for the CSA, and show that the CSA and FM-index can be constructed in O(n logn) time using optimal space. We also provide another construction algorithm, which runs in optimal time and optimal space when the text is over a constant-size alphabet. We also give