Efficient Inverted Index Compression Algorithm Characterized by Faster Decompression Compared with the Golomb-Rice...

Area of Science:

• Information Theory
• Computer Science
• Data Compression

Background:

• Binary sequences with a fixed number of ones are common in data storage and retrieval.
• Existing compression methods like Golomb-Rice coding can be slow for decompression, especially in database applications.

Purpose of the Study:

• To propose a novel compression algorithm for binary sequences with a disproportionate number of zeros and ones.
• To develop a method that prioritizes decompression speed over maximal compression ratio.

Main Methods:

• Derivation of entropy bounds for binary sequences with a fixed number of ones: k log2(0.48·n/k) < H < k log2(2.72·n/k).
• Development of a simple fixed-length word coding scheme based on the derived entropy bounds.

Main Results:

• The proposed coding method achieves efficient compression for binary sequences with a high number of zeros.
• Decompression speed is significantly improved compared to Golomb-Rice coding.
• A minor reduction in compression efficiency is observed, which is acceptable for specific applications.

Conclusions:

• The developed algorithm provides a practical solution for compressing sparse binary data.
• This method is particularly beneficial for database applications where rapid data retrieval is critical.