Structures of String Matching and Data Compression

This doctoral dissertation presents a range of results concerning efficient algorithms and data structures for string processing, including several schemes contributing to sequential data compression. It comprises both theoretic results and practical implementations. We study the suffix tree data structure, presenting an efficient representation and several generalizations. This includes augmenting the suffix tree to fully support sliding window indexing (including a practical implementation) in linear time. Furthermore, we consider a variant that indexes naturally word-partitioned data, and present a linear-time construction algorithm for a tree that represents only suffixes starting at word boundaries, requiring space linear in the number of words. By applying our sliding window indexing techniques, we achieve an efficient implementation for dictionary-based compression based on the LZ-77 algorithm. Furthermore, considering predictive source modelling, we show that a PPM* style model can be maintained in linear time using arbitrarily bounded storage space. We also consider the related problem of suffix sorting , applicable to suffix array construction and block sorting compression . We present an algorithm that eliminates superfluous processing of previous solutions while maintaining robust worst-case behaviour. We experimentally show favourable performance for a wide range of natural and degenerate inputs, and present a complete implementation. Block sorting compression using BWT , the Burrows-Wheeler transform , has implicit structure closely related to context trees used in predictive modelling. We show how an explicit BWT context tree can be efficiently generated as a subset of the corresponding suffix tree and explore the central problems in using this structure. We experimentally evaluate prediction capabilities of the tree and consider representing it explicitly as part of the compressed data, arguing that a conscious treatment of the context tree can combine the compression performance of predictive modelling with the computational efficiency of BWT. Finally, we explore offline dictionary-based compression , and present a semi-static source modelling scheme that obtains excellent compression, yet is also capable of high decoding rates. The amount of memory used by the decoder is flexible, and the compressed data has the potential of supporting direct search operations