Efficient Algorithm and Coding for Higher-Order Compression

Higher-order compression is a scheme for compressing data in the form of functional programs that generate the data. This compression scheme can be viewed a generalization of grammar-based compression, and retains its advantage that compressed data can be manipulated without decompression. Furthermore, the higher-order compression can achieve a high compression ratio and also discover patterns that cannot be found by traditional grammar-based compression. In this paper, we propose an efficient algorithm and a bit-coding scheme for higher-order compression and evaluate their effectiveness through experiments.