Smaller Compressed Suffix Arrays†
Ekaterina Benza, Shmuel T. Klein, Dana Shapira · The Computer Journal · 2020
Abstract An alternative to compressed suffix arrays is introduced, based on representing a sequence of integers using Fibonacci encodings, thereby reducing the space requirements of state-of-the-art implementations of the suffix array, while retaining the searching functionalities. Empirical tests support the theoretical space complexity improvements and show that there is no deterioration in the processing times.