学位论文 > 优秀研究生学位论文题录展示

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

作　者: 戴文睿
导　师: 支琤
学　校: 上海交通大学
专　业: 通信与信息系统
关键词: 非连续上下文建模 可执行文件压缩 上下文加权 模型估计冗余
分类号: TP391.1
类　型: 硕士论文
年　份: 2008年
下　载: 52次
引　用: 1次
阅　读: 论文下载
 

内容摘要


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

全文目录


摘要  3-5
ABSTRACT  5-11
第一章 绪论  11-21
  1.1 本文的主要内容和创新点  11-12
  1.2 经典数据压缩系统  12-13
  1.3 信源编码及其冗余  13-17
    1.3.1 信源  13
    1.3.2 信源编码及其性质  13-15
    1.3.3 编码冗余  15
    1.3.4 算术编码  15-17
  1.4 基于上下文建模及其冗余  17-20
    1.4.1 参数估计冗余  17-19
    1.4.2 模型估计冗余  19-20
    1.4.3 Rissanen冗余下限  20
  1.5 本章小结  20-21
第二章 基于连续上下文的建模  21-32
  2.1 连续上下文集  21
  2.2 可变阶数的连续上下文建模  21-29
    2.2.1 CTW  22-24
    2.2.2 PPM  24-27
    2.2.3 PST  27-29
  2.3 多方向连续上下文建模  29-31
  2.4 本章小结  31-32
第三章 基于非连续上下文的建模  32-45
  3.1 非连续上下文  32-33
  3.2 非连续上下文集  33
  3.3 模型树  33-35
  3.4 非连续建模和上下文加权  35-38
    3.4.1 对于未知数据源的非连续建模  35-36
    3.4.2 非连续模型的模型估计冗余  36-38
  3.5 非连续上下文模型的选择  38-44
    3.5.1 非连续上下文模型的单独判决  39-42
    3.5.2 最大后验概率模型  42
    3.5.3 定制最佳估计模型集  42-44
  3.6 本章小结  44-45
第四章 可执行文件压缩  45-61
  4.1 可执行文件中的相关性  45-51
    4.1.1 IA-32 指令的构成  46
    4.1.2 IA-32 指令的相关性  46-51
  4.2 基于IA-32 指令集上下文的建模  51-52
  4.3 基于非连续上下文建模的可执行压缩实现  52-58
    4.3.1 预处理  53-54
    4.3.2 模型预测及更新  54-58
  4.4 实验结果  58-60
  4.5 本章小结  60-61
第五章 工作总结及展望  61-63
  5.1 全文总结  61-62
  5.2 工作展望  62-63
参考文献  63-68
附录一 KT估计性质  68-70
致谢  70-71
攻读硕士学位期间已发表或录用的论文  71

相似论文

  1. 基于FPGA的数字图像处理基本算法研究与实现,TP391.41
  2. 用于检索的人脸特征提取与匹配算法研究,TP391.41
  3. 基于FPGA的高速图像预处理技术的研究,TP391.41
  4. 2D人脸模板保护算法研究,TP391.41
  5. 导弹虚拟试验可视化技术研究,TP391.9
  6. 基于用户兴趣特征的图像检索研究与实现,TP391.41
  7. 图像拼接技术研究,TP391.41
  8. 高效精确字符串匹配算法的研究与实现,TP391.41
  9. 基于词义及语义分析的问答技术研究,TP391.1
  10. 基于三维重建的焊点质量分类方法研究,TP391.41
  11. 舌体特征的提取及融合分类方法研究,TP391.41
  12. 统计机器翻译中结构转换技术的研究,TP391.2
  13. 基于人眼检测的驾驶员疲劳状态识别技术,TP391.41
  14. 基于句法特征的代词消解方法研究,TP391.1
  15. 空中目标与背景的红外图像仿真技术研究,TP391.41
  16. 基于EPC C1G2协议的超高频RFID系统设计及仿真,TP391.44
  17. 基于智能学习的多传感器目标识别与跟踪系统研究,TP391.41
  18. 基于TMS320C6713的SPIHT图像压缩算法研究及实现,TP391.41
  19. 双传感器图像联合目标检测及系统实现研究,TP391.41
  20. 雾天或背光条件下图像清晰化算法研究及硬件实现,TP391.41
  21. 多邮件自动文摘的关键技术研究,TP391.1

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理（信息加工） > 文字信息处理
© 2012 www.xueweilunwen.com