New Compression Schemes for Natural Number Sequences

Elias and Fano independently proposed a quasi-succinct representation for monotonic integer sequences. In case the standard deviation is high, we suggest using the well known C_γ code instead of the Unary code used by their solution. In case the integers are similar, not necessarily forming a monotonic sequence, we propose to apply the Haar transform as a preprocessing stage, to achieve additional savings. Experimental results support the additional savings carried out by using our method.