字典码的信源压缩系统的设计译码端
目 录
1 绪论 1
2 编码的发展史 1
3 数据压缩与编码 2
3.1 编码的认识 2
3.2 编码方式分类 2
3.3 压缩技术分类 4
4 字典编码 5
4.1 字典编码的认识 5
4.2 字典编码的原理 5
4.3 字典编码方法分类与特点 5
5 编码的不足与改进 8
5. 1 编码的不足 8
5.2 编码的改进 8
5.3 编码长度改进 9
5.4 算法方法改进 9
6 算法的实现 9
6.1译码算法 10
6.2流程描述 10
6.3基础常量定义 10
6.4随机二进制文件的生成 11
7 改良算法与原始LZW算法对比 12
结论 13
致谢 14
参考文献15
附录A 译码数据结构 16
附录B 译码核心代码 18
1．绪论
从人们认识到信息的存在到现如今进入到信息社会，信息论已经发展了五十几年，而且也逐渐形成了一门独立的信息理论学科，人们对信息理论的认识伴随着社会的文明进步不断增强提高。信息论的发展，是由人们在通信生活实践中逐步认知并发展起来的，其被广大公众所认可的奠基人是美国当代数学家、科学家香农。半个世纪的发展，使采用通信理论作为核心理论的信息论的道理迅猛发展，到了21世纪，信息技术的发展已经有了非常大的进步，人们已经进入了信息时代。
随着信息时代的到来， 信息技术得到了迅速的推广与应用，而且信息产 *好棒文|www.hbsrm.com +Q: ￥3^5`1^9`1^6^0`7^2$
业已逐步成为我国的支柱产业，并已达到世界第二大规模。但我们不能仅仅看到我国信息产业的规模，更要发现我国信息产业规模虽大但实力不强。作为近代科技革命的一个重要的里程碑，信息技术一直伴随着我们国家的发展，在世界上已成为一个国家科学和技术的一个重要标识。这就要求我们加快我国信息核心产业的发展与创新，大力推动并发展信息科技产业的建设，从而提高我国信息理论的核心竞争力，才能在日新月异的世界之林上拥有不败之地。
2．编展码的发史
随着社会的进步，每天都有大量的信息相互传送着。科学家们发现，信息在传递过程中，容易丢失或产生冗余；许多信息在传输时都有其信息冗余度的存在，通过运用以下压缩编码的方式，能够有效地降低这种传输信息的冗余度，从而提升其传输效率与传输有效性，可靠性。
1948年，Shannon发表了Shannon编码方法，并建立了信息熵理论体系；1952年，R.M.Fano也随之发表了Fano编码，取得了一定的压缩效果；D.A.Huffman与1952年发表的“最小冗余度代码的构造方法”一文里，实现了第一种能够实用的编码方式，被称之为Huffman编码，但霍夫曼编码方式得到的编码长度不能完全靠近信息熵的极限值，所以，在1968年，P.Elias综合改进了Shannon编码与Fano编码，提出Shannon-Fano-Elias编码；1976年，J.Rissanen继续研究得出能够无限接近信息熵极限的编码方式，算术编码；1977年，科学家们打破了霍夫曼编码的统治，提出了字典编码；1979年，G.G.Langdon系统化了算术编码并于1981年提出了二进制编码。
3．数据压缩与编码
3．1编码的认识
在通信理论中，信息编码就是将原始信息数据按照一些特别的数学规则进行的转化。采用信息编码原因就是想将原始信息在确保信息传输质量的前提下，可以快速地传输到信宿中。我们常根据其功能的不同，可将其分为信源编码和信道编码以及加密编码。其中，信源编码就是把信息的源代码转化成为一个数字序列的方法。信源编码其根本任务就是通过降低数据率，减少数据信息中的冗余，提高数据信息传输效率；信道编码其根本任务就是提高信息体系的抗干扰能力，例如纠错码，卷积码之类的都属于此，它能够检查传输的信息是不是被传错；最后，加密编码主要是因为在信息传输过程中，为了防止信息被截取或者信息外泄从而对所传信息进行加密编码，用来提高信息的传输可靠性，被加密的信息只有特定的解密方法才能获得信息。
目前，有多种成熟的压缩技术，主要是无损和有损压缩。
无损压缩是对压缩数据本身的压缩，因为压缩文件可以完全恢复，所以不会影响该文件的内容；由于能够百分百的还原原始数据，所以通常被运用在文本文件的数据压缩中。
有损压缩常被称为破坏型压缩，是把需要处理的信息文件里一些不必要的数据压缩后，通过减少信息文件的质量，从而提高其压缩效率。这种压缩方法是对图像本身进行改变，减少了其中的信息量，从而提高了压缩比。根据其特性，有损压缩常常被运用在语音，图像以及视频信息的数据压缩过程中。其一个显著的特点即在图像压缩时，能使其颜色逐步变化，但在删除压缩图像时，颜色会突然进行转化。
3．2编码方式分类
本次设计要求对二进制文本数据进行压缩，为确保其压缩的可靠性，采用无损压缩来处理，从而保证文本数据信息不丢失。而在通常使用的无损压缩编码方式中，最常用的为游程编码，霍夫曼编码，算术编码以及字典编码。
游程编码又被称为“行程编码”，是一种根据符号出现概率的分布特性完成编码的统计编码。其编码的基本原理如下：拥有同样值的连续符号可以被构建成一个单独的符号值，或者用串长来替代，这些连续的符号组合在一起，被称为行程，这样就减少了原始数据的长度，从而达到压缩的目的。此编码算法较常用在降低由图像存储的存储空间，但假如此图像颜色很丰富，用此方式压缩后的文件会得到更大的信息量。所以，此编码算法一般不会单独使用，通常会由用户进行选择后，与其他的压缩编码算法结合起来共同使用。
霍夫曼方法是一种不定长的编码算法，其编码时码长可变，此算法全部都依据字符产生的频率创建平均长度最短的码字，所以常常被人们称作最佳编码算法。给定的信息源里，符号的概率高，对应的码就会短，反之，符号的概率低，所对的码就会长，这样就能用尽可能少的码表示源数据，又被称为熵编码方法法。霍夫曼编码算法具有以下特点：1.算法构造码不是唯一的。2.算法编码码字的字长不一。3.算法对不同的信息源编码的效率是不同的。4.译码码时要依照霍夫曼编码表才能有正确的译码结果。但是此编码算法也有其局限性：1.编码时的符号长度只可以是整数的形式，由于源符号集的概率分布没有形成2负n次方，因此没法达到熵极限。2.算法能够完成的编码表的大小会制约输入符号的数量。3.霍夫曼编码方式在译码时，过程相对繁杂。4.算法得先知道输入符号集的概率分布才能实现编码算法。5.在编码时没有错误保护功能；
6．算法的实现
本次设计采用的是Delphi7.0软件开发工具，在封装过程中定义了ExportData与Execute两个虚方法，设以上方法可修改或扩建算法的执行与数据输出过程。
算法的核心编码过程用Execute来表示，说明：在此方法中，Data为指针，待处理数据的首地址为其指针指向；DataSize用来代表要处理的数据大小；GetExportPointer方法在处理完数据后将把这些数据保存在内部，并记录此时的地址指针，再通过采用GetExportSize这个方法返回输出数据的大小。
1 绪论 1
2 编码的发展史 1
3 数据压缩与编码 2
3.1 编码的认识 2
3.2 编码方式分类 2
3.3 压缩技术分类 4
4 字典编码 5
4.1 字典编码的认识 5
4.2 字典编码的原理 5
4.3 字典编码方法分类与特点 5
5 编码的不足与改进 8
5. 1 编码的不足 8
5.2 编码的改进 8
5.3 编码长度改进 9
5.4 算法方法改进 9
6 算法的实现 9
6.1译码算法 10
6.2流程描述 10
6.3基础常量定义 10
6.4随机二进制文件的生成 11
7 改良算法与原始LZW算法对比 12
结论 13
致谢 14
参考文献15
附录A 译码数据结构 16
附录B 译码核心代码 18
1．绪论
从人们认识到信息的存在到现如今进入到信息社会，信息论已经发展了五十几年，而且也逐渐形成了一门独立的信息理论学科，人们对信息理论的认识伴随着社会的文明进步不断增强提高。信息论的发展，是由人们在通信生活实践中逐步认知并发展起来的，其被广大公众所认可的奠基人是美国当代数学家、科学家香农。半个世纪的发展，使采用通信理论作为核心理论的信息论的道理迅猛发展，到了21世纪，信息技术的发展已经有了非常大的进步，人们已经进入了信息时代。
随着信息时代的到来， 信息技术得到了迅速的推广与应用，而且信息产 *好棒文|www.hbsrm.com +Q: ￥3^5`1^9`1^6^0`7^2$
业已逐步成为我国的支柱产业，并已达到世界第二大规模。但我们不能仅仅看到我国信息产业的规模，更要发现我国信息产业规模虽大但实力不强。作为近代科技革命的一个重要的里程碑，信息技术一直伴随着我们国家的发展，在世界上已成为一个国家科学和技术的一个重要标识。这就要求我们加快我国信息核心产业的发展与创新，大力推动并发展信息科技产业的建设，从而提高我国信息理论的核心竞争力，才能在日新月异的世界之林上拥有不败之地。
2．编展码的发史
随着社会的进步，每天都有大量的信息相互传送着。科学家们发现，信息在传递过程中，容易丢失或产生冗余；许多信息在传输时都有其信息冗余度的存在，通过运用以下压缩编码的方式，能够有效地降低这种传输信息的冗余度，从而提升其传输效率与传输有效性，可靠性。
1948年，Shannon发表了Shannon编码方法，并建立了信息熵理论体系；1952年，R.M.Fano也随之发表了Fano编码，取得了一定的压缩效果；D.A.Huffman与1952年发表的“最小冗余度代码的构造方法”一文里，实现了第一种能够实用的编码方式，被称之为Huffman编码，但霍夫曼编码方式得到的编码长度不能完全靠近信息熵的极限值，所以，在1968年，P.Elias综合改进了Shannon编码与Fano编码，提出Shannon-Fano-Elias编码；1976年，J.Rissanen继续研究得出能够无限接近信息熵极限的编码方式，算术编码；1977年，科学家们打破了霍夫曼编码的统治，提出了字典编码；1979年，G.G.Langdon系统化了算术编码并于1981年提出了二进制编码。
3．数据压缩与编码
3．1编码的认识
在通信理论中，信息编码就是将原始信息数据按照一些特别的数学规则进行的转化。采用信息编码原因就是想将原始信息在确保信息传输质量的前提下，可以快速地传输到信宿中。我们常根据其功能的不同，可将其分为信源编码和信道编码以及加密编码。其中，信源编码就是把信息的源代码转化成为一个数字序列的方法。信源编码其根本任务就是通过降低数据率，减少数据信息中的冗余，提高数据信息传输效率；信道编码其根本任务就是提高信息体系的抗干扰能力，例如纠错码，卷积码之类的都属于此，它能够检查传输的信息是不是被传错；最后，加密编码主要是因为在信息传输过程中，为了防止信息被截取或者信息外泄从而对所传信息进行加密编码，用来提高信息的传输可靠性，被加密的信息只有特定的解密方法才能获得信息。
目前，有多种成熟的压缩技术，主要是无损和有损压缩。
无损压缩是对压缩数据本身的压缩，因为压缩文件可以完全恢复，所以不会影响该文件的内容；由于能够百分百的还原原始数据，所以通常被运用在文本文件的数据压缩中。
有损压缩常被称为破坏型压缩，是把需要处理的信息文件里一些不必要的数据压缩后，通过减少信息文件的质量，从而提高其压缩效率。这种压缩方法是对图像本身进行改变，减少了其中的信息量，从而提高了压缩比。根据其特性，有损压缩常常被运用在语音，图像以及视频信息的数据压缩过程中。其一个显著的特点即在图像压缩时，能使其颜色逐步变化，但在删除压缩图像时，颜色会突然进行转化。
3．2编码方式分类
本次设计要求对二进制文本数据进行压缩，为确保其压缩的可靠性，采用无损压缩来处理，从而保证文本数据信息不丢失。而在通常使用的无损压缩编码方式中，最常用的为游程编码，霍夫曼编码，算术编码以及字典编码。
游程编码又被称为“行程编码”，是一种根据符号出现概率的分布特性完成编码的统计编码。其编码的基本原理如下：拥有同样值的连续符号可以被构建成一个单独的符号值，或者用串长来替代，这些连续的符号组合在一起，被称为行程，这样就减少了原始数据的长度，从而达到压缩的目的。此编码算法较常用在降低由图像存储的存储空间，但假如此图像颜色很丰富，用此方式压缩后的文件会得到更大的信息量。所以，此编码算法一般不会单独使用，通常会由用户进行选择后，与其他的压缩编码算法结合起来共同使用。
霍夫曼方法是一种不定长的编码算法，其编码时码长可变，此算法全部都依据字符产生的频率创建平均长度最短的码字，所以常常被人们称作最佳编码算法。给定的信息源里，符号的概率高，对应的码就会短，反之，符号的概率低，所对的码就会长，这样就能用尽可能少的码表示源数据，又被称为熵编码方法法。霍夫曼编码算法具有以下特点：1.算法构造码不是唯一的。2.算法编码码字的字长不一。3.算法对不同的信息源编码的效率是不同的。4.译码码时要依照霍夫曼编码表才能有正确的译码结果。但是此编码算法也有其局限性：1.编码时的符号长度只可以是整数的形式，由于源符号集的概率分布没有形成2负n次方，因此没法达到熵极限。2.算法能够完成的编码表的大小会制约输入符号的数量。3.霍夫曼编码方式在译码时，过程相对繁杂。4.算法得先知道输入符号集的概率分布才能实现编码算法。5.在编码时没有错误保护功能；
6．算法的实现
本次设计采用的是Delphi7.0软件开发工具，在封装过程中定义了ExportData与Execute两个虚方法，设以上方法可修改或扩建算法的执行与数据输出过程。
算法的核心编码过程用Execute来表示，说明：在此方法中，Data为指针，待处理数据的首地址为其指针指向；DataSize用来代表要处理的数据大小；GetExportPointer方法在处理完数据后将把这些数据保存在内部，并记录此时的地址指针，再通过采用GetExportSize这个方法返回输出数据的大小。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/dzxx/gdxx/168.html
