Paper Info
Title
Fibonacci Based Compressed Suffix Array
Abstract
We suggest the usage of Fibonacci Codes instead of Elias' C γ code. The implementation requires 1.44 n H <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> +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.
Year
DOI
Venue
2018
10.1109/DCC.2018.00068
2018 Data Compression Conference
Keywords
Field
DocType
Compressed suffix array,Elias Code,Fibonacci Code
Integer,Discrete mathematics,Computer science,Theoretical computer science,Code word,Decoding methods,Data compression,Compressed suffix array,Encoding (memory),Fibonacci number
Conference
ISSN
ISBN
Citations 
1068-0314
978-1-5386-4884-1
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Shmuel T. Klein143477.80
Dana Shapira214432.15