Smaller Compressed Suffix Arrays. (13th April 2020) - Benza, Ekaterina; Klein, Shmuel T; Shapira, Dana
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.