2015 , Volume 20, № 3, p.75-98

Purpose. A principle for construction of algorithms for fast lossless compression of integer data values, which are distributed mainly near zero, is considered. Such data come from, e.g., differential encoding of integer sequences, which represent gradually varying quantities (the quantities, which take similar values in neighboring points). According to the degree of compression for the given kind of data, the algorithms considered are of superior performance compared to ZLib [1] in its strongest compression mode Z_BEST_COMPRESSION, but they take considerably less time for both compression and unpacking, since the proposed compression algorithm is characterized by a linear computational complexity in terms of the processed data size.

Design/methodology/approach. To find the best (most compact) representation of an integer sequence by series of intervals for values of constant bit depth we use the dynamic programming approach. The dynamic programming scheme used is of the VSEncoding algorithm [4] type. A concrete compression algorithm is defined by specifying a particular method for the interval header representation.

Findings. The VSEopt algorithm - an optimized version of VSEncoding algorithm is proposed, which allows to find the true minimum of compressed size without limiting the depth of the interval length search by the max K parameter. A theoretical justification of the VSEopt algorithm is presented. The performed tests have demonstrated that VSEopt works as fast as VSEncoding with impractically small max K=16, but even with max K=1024 (and a lot of time spent) the VSEncoding algorithm can`t achieve the optimal compression found by VSEopt. Another theoretical inference eliminates the use of the VSEopt compression in order to employ the buffer of limited size without losing the capability of finding the true optimal solution. The performed tests show that the algorithm still be capable to find the best solution even when the buffer may be as small as 2000 items (when compressing much larger blocks of 160000 values). Some particular methods of interval header encoding were considered and tested. The best results were obtained for encodings, which use the static Huffman codes obtained with the help of statistics for interval depths and lengths distribution. For the test performed, the process of finding the header encoding which matches the statistics resulting from its usage have converged to the smallest of all the tests executed compressed data size.

Originality/value. The VSEncoding algorithm is the well known tool for compression of document indexes. The optimized version of the algorithm -- VSEopt is a new result. Our formulation and solution addresses the problem how to use a buffer of limited capacity but still find the best compression. The methods used for the algorithms of compression of differential integer sequences are also new and extend the field of the algorithm usage.