基于动态词典的文本压缩研究

摘要

近年来，数据压缩的理论得到了相当充分的发展，相关的产品在各个领域被广泛应用。从数据还原的角度来看，数据压缩可以分为有损压缩和无损压缩两大领域…。 本文的压缩研究属于无损压缩领域。在第一章中，对无损压缩领域中基于统计和基于字典的两大主流方法进行了回顾，并阐述了其中主要压缩方法的原理和特点，指出了其适用范围和局限性。本文进一步从基于字典的压缩方法出发，针对相关字典内容的特点进行了具体分析：一般基于字典压缩方法中的字典，仅与源码流的字符顺序相关，而不与其具体内容的意义相关。本文着重针对文本文件尤其是中文文本文件进行了分析，指出文本文件的字符比一般文件的字符有更强的关联性，字符之间的搭配也有较强的稳定性。据此，本文在压缩方法中建立了内容关联性较强的词典，而不是一般的字典，并提出了一种崭新的数据压缩方法一动态词典压缩法。 动态词典压缩法，克服了传统字典压缩方法的某些不足。传统的字典压缩方法中，当字典饱和或压缩率降低时，要么保持字典不变继续使用，要么将字典完全废弃[2]。此时的字典或不能很好的反映历史数据特点，或不能反应现实数据特点，不能发挥它的最大作用，字典的管理存在明显的局限性。本文的动态词典由保持独立的词典单元组成。在压缩和解压过程中，使用散列法对词典单元进行定位，并使用线性搜索查找词典单元的内容，使对整个字典的操作能很快进行。同时，本文对词典的管理采用了一种全新的方法一冲突率法，并用冲突率对词典单元的有效性进行及时检查。当冲突率超过某一设定值时，本词典单元立即废弃不用并需重新建立，但其它的单元保持不变，这样既能使符合要求的词典单元保留下来继续使用，又能将不满足条件的词典单元及时废弃，从而保证整个字典的高效性。本文把这种及时更新内容的词典称为动态词典，由此建立的压缩法称为动态词典压缩法，并简称为“QQQ。 词典重用法是本文采取的另一种重要方法，它主要用于对文件夹进行词典的高效管理。一般而言，处于文件夹中的文件在内容方面有较强的关联性，因而建立的词典也应有相似的部分。为了进一步体现动态词典的高效性，本文不是为每一个文件建立一个独立的词典，而是将同一词典在各个文件中重复使用一这就叫词典重用。通过词典的重用，不仅提高了处理文件夹的速度，而且还提高了文件夹的压缩率。 实现本算法的软件已成功开发。实验表明，本算法在文本压缩方面有较好的综合性能；作为一个独立的压缩方法，它有较快的速度和较高的压缩率。

目录

文摘

英文文摘

声明

第一章 概述

第二章 词典压缩的基本原理

第三章 压缩过程

第四章 解压过程

第五章 动态词典与词典重用

第六章 性能分析

第七章 软件介绍

第八章 总结

参考文献

致谢