logo资料库

lz78压缩编码论文及源代码.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.96M 资料格式：doc 举报 版权申诉
第1页 / 共48页
第2页 / 共48页
第3页 / 共48页
第4页 / 共48页
第5页 / 共48页
第6页 / 共48页
第7页 / 共48页
第8页 / 共48页
资料共48页，剩余部分请下载后查看
    BACHELOR'S DEGREE THESIS
    OF WUHAN UNIVERSITY
    ABSTRACT
    Key words: LZ78；data compression；dictionary theor
    compression rate
    1.1 论文研究的目的及意义 …………………………………………………………1
    1.2.2 LZ词典编码概述及其应用和地位………………………………………4
    1.2 数据压缩领域的研究现状及发展趋势
    1.1.2 LZ词典编码概述及应用地位
    1.2 论文研究背景及内容安排
    2.1 LZ词典编码系列算法介绍
    2.1.1 LZ编码若干种算法的介绍及评价
    2.2 LZ78编译码算法的设计与理论分析
    2.2.1 LZ78算法设计与分析
    LZ78编码实质上使用了一种分析算法称为贪婪分析算法。在贪婪分析算法中，每一次分析都要串行地
    学号 200631200225 密级____________ 武汉大学本科毕业论文 基于 LZ78 词典编码的数据压缩算法 研究及其 C 实现 院（系）名 称：电子信息学院 专 业 名 称 ：通信工程 学 生 姓 名 ：陈武 指 导 教 师 ：周建国 副教授 二○一○年五月
    BACHELOR'S DEGREE THESIS OF WUHAN UNIVERSITY Analyzing and Programming In C of LZ78 Data Compression Algorithm College ： Electronic Information School Subject ： Telecommunication Engineering Name ： Chen Wu Directed by ： Zhou Jianguo Professor May 2010
    郑 重 声 明 本人呈交的学位论文，是在导师的指导下，独立进行研究工作所 取得的成果，所有数据、图片资料真实可靠。尽我所知，除文中已经 注明引用的内容外，本学位论文的研究成果不包含他人享有著作权的 内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已 在文中以明确的方式标明。本学位论文的知识产权归属于培养单位。 本人签名： 日期：
    摘 要 本文主要论述和设计基于 LZ78 词典编码的压缩算法及其 C 实现。以色列科 学家 Ziv 和 Lemple 提出的 LZ 算法是当今数据压缩领域最为流行的压缩算法，LZ 算法通过不断改进已形成一个算法系列，但基本原理都是基于 LZ77 和 LZ78 算法。 在 LZ 算法之前出现的 Huffman 编码和算术编码都要已知信源分布，而 LZ 算法不必已知信源统计特性也能实现高效编码。LZ 算法在信源足够长时可无限 逼近信息熵，达到最佳编码效果。 LZ78 词典编码实现文本数据压缩的基本原理是，在编码过程中一边编码一 边自适应建立词典,为新字符串(即短语)建立索引。将当前短语用已出现的与之 相同的短语索引号代替，从而压缩冗余，若不存在匹配串，则新建索引。解压时 将索引对应的短语输出即可得到正确原文。压缩率和压缩时间是评价压缩效果的 指标，压缩率越高，所用时间越少，压缩算法效果越好。 本文在实现短语查询匹配的算法中采用链表建立一级索引，将具有相同首字 母的短语用一个链表连接起来，提高了查找速度。本文程序可实现包含英文和汉 语字符的文本文件的压缩，通过几个实例的统计，该程序压缩率在 1.3-3.0 之间。 关键词：数据压缩；LZ78；词典编码；索引链表；压缩率
    ABSTRACT This essay researches on LZ78 dictionary compression algorithm and its C programming. Two scientists Ziv and Lemple found LZ compression algorithm and then it became the most popular and efficient algorithm. There are a series of LZ algorithms based on LZ77 and LZ78. Before LZ algorithm there were Huffman algorithm and Mathematic algorithm. But both of them should know the statistic characteristics of message source before compression. LZ can make effective data compression without know it. The longer the source message is, the better the LZ78 compressing result is. LZ algorithm is based on dictionary theory. It makes an index directory when compressing data. By replacing the repeated strings with indexes, it compresses data efficiently. If the current string never existed, then it is numbered with an index. By replacing the index with corresponding string, it decompresses data successfully. Compressing rate and time are evaluating indicators of data compression algorithm. Higher rate or less time consuming means better compressing result. This essay uses chain table to speed the string matching process. The chain links the lemma which has the same head alphabet. This program can compress English and Chinese mixed text. Compressing rate is about 1.3-3.0. Key words: LZ78；data compression；dictionary theory；index chain； compression rate
    目 录 第 1 章 引言…………………………………………………………………………………1 1.1 论文研究的目的及意义 …………………………………………………………1 1.2 数据压缩领域的研究现状与发展趋势………………………………………1 1.2.1 Huffman 编码、算术编码简介……………………………………………2 1.2.2 LZ 词典编码概述及其应用和地位………………………………………4 1.3 本文内容结构安排…………………………………………………………………4 第 2 章 LZ78 词典编码算法……………………………………………………………6 2.1 LZ 词典编码系列算法介绍………………………………………………………6 2.1.1 LZ 编码若干种算法的介绍及评价……………………………………6 2.1.2 LZ78 词典编码算法描述及评价………………………………………7 2.2 LZ78 编译码算法的设计与理论分析…………………………………………9 2.2.1 LZ78 算法分析与设计……………………………………………………9 2.2.2 LZ78 算法的理论分析…………………………………………………11 第 3 章 基于 LZ78 的文本压缩算法 C 程序设计……………………………14 3.1 文本文件的特征及相应的压缩算法…………………………………………14 3.2 程序设计思路及流程……………………………………………………………15 3.2.1 编程环境、C 语言及程序设计要点…………………………………15 3.2.2 程序设计思路及流程图…………………………………………………16 3.3 本程序的文本压缩效率及效果分析…………………………………………22 3.3.1 文本压缩效率的评价指标……………………………………………22 3.3.2 程序的运行情况介绍及分析…………………………………………22 3.3.3 程序的改进建议…………………………………………………………23 第 4 章 总结……………………………………………………………………………25 4.1 论文的研究设计过程及体会………………………………………………25 4.2 设计的改进方案及进一步研究方向………………………………………26
    参考文献 …………………………………………………………………………………… 27 致谢 …………………………………………………………………………………………28 附录 A …………………………………………………………………………………………29 附录 B …………………………………………………………………………………………40
    第 1 章 引言 1.1 论文研究目的及意义 本文的研究对象是数据压缩算法中最为流行的 LZ 词典压缩算法，它独特的 编码方法和优异的性能使之获得广泛的用途，对该算法的研究自问世起从未间 断，现今流行的许多数据压缩软件都是采用 LZ 系列算法及其各种改进算法。对 于我们通信工程专业的学生，了解和研究数据压缩领域的流行趋势十分必要，这 也是选择 LZ78 压缩算法及程序设计作为毕业设计的初衷。通过算法理论的研究 提高对数据压缩理论的认识，通过程序设计提高编程能力，同时也培养自己独立 分析问题和解决问题的能力。 1.2 数据压缩领域的研究现状及发展趋势 信息处理技术在计算机网络、通信设备、影音多媒体的使用中都起着至关重 要的作用。自 1948 年 Shannon 发表了他的划时代的《通信的数学理论》之后， 信息论开始了它飞速的发展，它描述了信源和信道编码定理，为人们指出了实现 有限而可靠通信的必由之路是数字化和编码。经过数字化和编码的信息才能通过 通信系统进行传输和接收。通信系统模型如图 1.1[1]所示。 信源 信源 编码器 纠错 编码器 调制器 信 道 干扰源 信宿 信 源 译 码 纠错 译码器 解调器 图 1.1 通信系统模型 数据的可压缩性建立在数据的重复性上, 只有重复性的数据才有可能被压 缩。数字化信息之所以要压缩，是由于它们存在大量的数据冗余，只有除去这些 不必要保留的冗余，才能实现通信的有效性。一份文档由有限个不同字符的重复 1
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料