非连续上下文建模及其在可执行文件压缩中的应用

摘要

数据压缩技术在过去的20年中迅速发展，并且广泛地应用于文本、语音、图像、视频以及可执行文件等领域。数据压缩的过程一般严格地分为两步：建模过程和编码过程。在编码算法得到的码长已经十分接近香农极限的今天，建模过程对于数据压缩中效率的提升起到了决定性的作用。迄今为止研究人员对于上下文建模进行了大量工作，并且提出了一系列经典的建模方法。 可执行文件压缩作为数据压缩的一个分支，随着网络设施和手持终端的普及，各种网络程序分发和手持设备驱动程序存储等应用要求的出现，逐渐显现出其重要的意义。然而经典的建模方法一般仅考虑连续的上下文模型，虽然在诸如文本压缩中取得良好的效果，但在可执行文件压缩中则不尽如人意。 本文首先回顾了经典的基于连续上下文建模的算法及其冗余的估计。在此基础上，通过对于连续上下文限制条件的松弛，考虑采用已预测子序列中字符的任意组合而非之前的后缀来构成非连续上下文，从而延伸出更广泛的非连续上下文及其模型的定义，并就此讨论基于非连续上下文的建模。对于非连续上下文建模，讨论的主要内容包括三点：第一，通过引入模型树来为非连续上下文建立一系列的上下文加权树，从而可以得出基于非连续上下文模型的加权概率估计；其二，针对所得到的加权概率估计，讨论它的模型估计冗余并与经典的连续上下文建模方法中的相应结果进行比较，体现出其对具有非连续相关性数据估计时得优势；最后对于存在或不存在训练数据的情况，分别建立对于指定数据的上下文模型选择的方法：当不存在训练数据时可以通过本文提出的方法，用已预测数据快速近似判断上下文模型；而当存在训练数据时可以依据最小描述长度准则，通过贪心算法选定一系列最优的模型。 对于可执行文件压缩，本文考虑同时采用连续上下文模型和非连续上下文模型来进行估计，并由这些估计最终给出加权概率估计。在总结了可执行文件，尤其是IA-32 指令集中的连续和非连续相关性后，将非连续建模方法结合其中的相关性应用到IA-32 指令集中，并通过训练数据采用前述的贪心算法依据最小描述长度准则选择出一组最优估计的上下文模型。在具体的实现中，本文提出一个可执行文件压缩的框架，包括对于可执行文件特有相关性建模以及指令语法分析的预处理、对于指令以选定的模型得出基于连续上下文或非连续上下文的概率模型估计，以及采用一族考虑p阶范数的归一化最小均方误差算法对所得出的概率估计进行混合，渐近地得到最优加权概率估计。