Regular Expression Search with Suffix Arrays

The suffix array is already very small. It doesn't store the full suffixes, just the numbers. It's basically a list of pointers with one pointer for each character in the input data. The characters aren't duplicated, unlike a suffix tree. In fact, the suffix array is just the leaf nodes of a suffix tree in depth-first order. The internal nodes are omitted. Further, you can store it as an array instead of a linked list, meaning you halve the number of pointers to store.