Reducing space for index implementation

This article considers several strategies to implement efficiently full indexes on raw textual data. Indexes are based on representations of all the suffixes of the original text, for which we describe three types of implementations aimed at reducing the memory space. The first method is a combination of compaction and minimization that leads to the compact suffix automaton. As a second method we show that considering a complement language can be useful especially when it is related to data compression. Finally, approximation of the set of suffixes is the third technique used to reduce the space of the implementation. (C) 2002 Elsevier Science B.V. All rights reserved.