Efficient Finite-State Decoding of Rice Codes for Large Alphabets
Can Özbey, Özge Dinçsoy · 2020
In this paper, we present a finite-state approach to efficiently decode a sequence of Rice codes. The proposed method is capable of decoding a byte stream for any Golomb parameter for unboundedly large alphabets with constant space complexity. Performance of the approach is evaluated in comparison to the conventional bit-level decoding algorithm on compressed inverted indexes with respect to various parameter values. It is observed that decoding performance of the method increases with the mean value of encoded integers. Speed gains up to about a factor of 2 are empirically obtained in comparison with the conventional decoding from the point where the optimal value of the divisor is computed as 128. Results show that it is particularly effective for tasks in which a stream of large integers are encoded such as compression of document identifier gaps in inverted indexes.