基于分区的正整数序列压缩方法

摘要

本发明提供了一种基于分区的正整数序列压缩方法。该方法主要包括：通过正整数序列X构造单调递增正整数序列S；构造所述单调递增正整数序列S的有向无环图G；使用迪杰斯特拉算法计算所述有向无环图G中从源点到汇点的最短路径；根据上述最短路径，得到单调递增正整数序列S的最优划分；计算最优划分中每一个区块的元素个数和每一个区块采用Golomb‑Rice编码时需要的参数b；采用Elias Gamma编码对元素个数进行编码和参数b进行编码，采用Golomb‑Rice编码对每一个区块内所有元素进行编码，根据编码结果得到单调递增正整数序列S的压缩结果。本发明综合了序列分区编码利用正整数序列的局部“聚集”性质与Golomb‑Rice编码的高效性等优点，提高了正整数序列的压缩性能。