Prague Stringology Conference 2018
Ekaterina Benza, Shmuel Tomi Klein and Dana Shapira
Fibonacci Based Compressed Suffix Array
| Abstract: |
| 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: |  |
 |
 |
| PostScript | BibTeX reference |