Suffix Arrays in Theory and Practice: Combinatorics of and.

The suffix array of a string is a permutation of all starting positions of the string's suffixes in lexicographical order. In this book, we investigate mathematical and algorithmical aspects of suffix arrays.The first part mainly deals with combinatorial properties of suffix arrays and their enumeration. For a fixed alphabet size and string length, we divide the set of all strings into equivalence classes of strings that share the same suffix array. For each such equivalence class, we count the number of strings contained in it and enumerate those strings. We also give exact formulas for computing the number of equivalence classes and efficient algorithms for enumerating them. The second part of the book deals with suffix array construction. We first present a new classification of suffix array construction algorithms and provide an in-depth review of the classified algorithms. After the survey of the previous algorithms, we present our practical algorithm for suffix array construction. We finally present an experimental study that compares our algorithm to other fast suffix array construction algorithms.

Dr. Klaus-Bernd Schürmann, Dipl.-Inform.: Studies of Mathematics and Computer Science at the Free University of Berlin and at the University of Massachusetts Dartmouth. Post-graduate studies of Bioinformatics at the University of Bielefeld. Consultant at IDS Scheer AG, Saarbrücken.Title