Prague Stringology Conference 2018

Ekaterina Benza, Shmuel Tomi Klein and Dana Shapira

Fibonacci Based Compressed Suffix Array

We propose Fibonacci based compressed suffix arrays, and show how repeated decompression can be avoided using our scheme. For a given file T of size n, the implementation requires 1.44 n Hk+n+o(n) bits of space, where Hk is the k-th order empirical entropy of T, while retaining the searching functionalities. Empirical results support this theoretical bound improvement, and show that on most files, our implementation saves space as compared to previous suggestions.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference