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.

Authors

• Maxime Crochemore

Keywords

• Data retrieval
• Suffix tree
• Suffix automaton
• DAWG
• Suffix oracle
• Index
• Text compression
• Pattern matching