Fibonacci Based Compressed Suffix Array
Shmuel T. Klein, Dana Shapira · 2018
We suggest the usage of Fibonacci Codes instead of Elias' C γ code. The implementation requires 1.44 n Hk+n+o(n) bits of space, while retaining the searching functionalities. We used a less common variant of the Fibonacci code which was found to be often preferable for the encoding. This variant is constructed from the traditional Fibonacci code by omitting the rightmost 1-bit of every codeword and dropping those codewords that start with 0. As a result, every codeword now starts and ends with a 1-bit, so codeword boundaries may still be detected by the occurrence of the string 11. In order to obtain Φ[i], i mod b codewords need to be decoded. The traditional approach is to decode each codeword and add the decoded values. One of the advantages of using a Fibonacci based representation of the integers is that it is possible to perform this addition directly on the compressed form, without individually decoding each summand.