Optimal Trade-Off for Succinct String Indexes

Roberto Grossi, Alessio Orlandi, Rajeev Raman

Let s be a string whose symbols are solely available through access(i), a read-only operation that probes s and returns the symbol at position i in s. Many compressed data structur…