Space efficient suffix trees

We give first the representation of a suffix tree that uses n lg n + O(n) bits of space and supports searching for a pattern string in the given text (from a fixed size alphabet) in O(m) time, where n is the size of the text and m is the length of the pattern. The structure is quite simple and answers a question raised by Muthukrishnan (in Proceedings of the FST and TCS Preconference Workshop on Randomization, 1997, pp. 23-27). Previous compact representations of suffix trees had either a higher lower order term in space and had some expectation assumption or required more time for searching. When the size of the alphabet k is not viewed as a constant, this structure can be modified to use the same space but take O(rn Ig k) time for string searching or to use an additional O(n Ig k) hits but take the same O(m) time for searching. We then give several index structures for binary texts, with less space including . a structure that uses a suffix array (n inverted right perpendicular lg n inverted left perpendicular bits) and an additional o(n) bits, . an indexing structure that takes n/2 lg n + O(n) bits of space, and . an o(n lg n) bit structure which answers in O(m) time, the decision question of whether a given pattern of length nr occurs in the text. Each of these structures uses a different technique, either in the storage scheme or in the search algorithm, in reducing the space requirement. The first one uses a suffix array, a sparse suffix tree, and a table structure. Finding all the occurrences of a pattern using this structure takes O(m + s) time, where s is the number of occurrences of the pattern in the test. The second structure constructs a sparse suffix tree for all the suffixes that start with the bit that occurs more times in the given binary text. The last structure uses an iterative algorithm to search for the pattern. This structure is the first o(n lg n) bit index to support the decision version of indexing queries in time linens in the length of the pattern. But this does not support the general indexing queries where we want to find the position of the occurrence of the pattern. Our main contribution is the development of techniques to use the succinct tree representation through balanced parentheses for suffix trees. (C) 2001 Academic Press.