字典码的信源编码编码端
字典编解码算法是一类重要的无损数据压缩和解压缩算法,在当前众多软件和数据处理中得到了广泛应用。分析和了解字典编解码算法在教学、设计和科研中都有很重要的意义。本论文以基于字典的编解码算法为主要研究对象。首先提出数据压缩技术的背景、本课题的目的和研究意义以及与课题相关的一些技术理论;然后进一步探究字典编解码算法主要内容、历史发展和研究现状;接着,本文详细介绍了字典码算法的具体实现过程,它是本课题完成的关键所在,也就是说字典码算法的实现就是软件压缩解压缩功能模块的实现,并且本文着重介绍了算法的难点——数据结构方面的实现。
关键词:数据压缩技术,字典编解码算法,LZSS
目 录
1 引言 1
1.1研究背景 1
1.2研究目的 2
1.3系统设计基本内容 3
2字典码编码种类及基本理论介绍 4
2.1字典码编码的起源和发展 4
2.2各类基于字典的编解码算法的基本原理 5
2.2.1 LZ77 5
2.2.2 LZSS 7
2.2.3 LZ78 9
2.3.4 LZW 10
3字典码编码软件设计 11
3.1系统功能与性能需求 11
3.2算法实现 11
总 结 19
致 谢..........................................................................................................................20
1 引言
1.1研究背景 *好棒文|www.hbsrm.com +Q: ^3^5^1^9^1^6^0^7^2^*
/> 多媒体技术是结合了计算机技术、视频技术、音频技术以及通信技术的综合体。在庞大的多媒体系统中,有很多要处理、传送、保存的信息,这些信息一般以数字、文本、语音、音乐、图形、视频等形式存在,这么多形式的媒体在计算机系统中占用很大的内存。所以髙效的传输这些数据和压缩这些数据的功能就成为多媒体系统中一项关键的功能,如何压缩这些数据直接影响到多媒体计算机的使用和改进。这些多媒体数据能被正常读取的条件是进行有效的压缩,现今功能强大的计算机在面对如此大的数据量时也显得有些短板,假如我们不处理这些庞然大物而是直接进行读取或是存储,那么就会对多媒体信息的传输、存取甚至是读出带来影响。所以我们压缩处理这些视频、图像多媒体数据就很必要了，借此来让我们释放计算机的数据传输速率让我们享受更高的传送速度，同时让我们的存储器存储更多的文件,让和数据处理能力得到质的飞跃,与此同时我们还可以花更少的时间获得更优质的多媒体数据，获得视听上的升级。
多媒体数据会面临体型庞大这个问题是存在一些原因的,因为多多少少会存在一些冗余，我们喜欢把这些冗余分为两种:主观冗余以及客观冗余。客观冗余主要是指因为在原始数据表示上固有的冗余,主要是由于数据处理上的不完善而产生的;而主观冗余则是指我们人类的感官功能不是完美的，存在一定的限制，这些冗余到达且被我们接受的时候,这些数据的全部信息不能被我们一点没有遗漏的接受,那些被我们遗漏的信息部分就被我们称作主观冗余。这些数据冗余又以空间冗余、时间冗余、编码冗余、结构冗余、知识冗余、信息结构冗余这些形式出现,这时候压缩就以一种必要的技术出现了，这些冗余迫切的需要通过编码实现数据的压缩来缩小它们的体型。所以说以上说到的数据压缩的过程,简而言之就是消去多媒体数据冗余性的方法。
实现信息从一种储存方式改变成另外一种储存方式的过程的叫做编码它就是一段功能为压缩的计算机编程代码，简称编码。需要处理文字、数字或其它对象时提前制定一种方法将对象编成数码，电脉冲信号也可以成为信息、数据转换的目标。编码涉及到电脑、播放器、远程控制和远程通话很多领域。在整个信息传输过程中，可以在不同阶段对对象进行编码，在信源和信道都可以进行编码，分别成为信源编码和信道编码，在此次设计的目中就实现信源编码。
1.2研究目的
信源编码的目的是为了提高通讯的有效性，在信源读取符号之后采用预定的转换，简而言之信源符号转换是为了削减或除去信源利余度所存在的。更确切一点说，信源编码就是针对在信源按照一点顺序传送出符号时，为了使用更短的码字来表示信源符号序列，通过采样信源符号的排列顺序特性来查找一种方式实现，使输出符号的码元载荷信息输出的时候，码元不仅荷载的信息平均量尽量加大，还能确保在后续的解码进程中符号的排列顺序不会产生失真来还原成符号改变之前。信源编码有两个作用，第一数据压缩时通过缩小码元数量以及下降码元速度；第二是实现信源从模拟信号到成数字信号的转变，从而达到用数字化传输的方式传送所需要的模拟信号的目的。摩尔斯电码可以说是信源编码历史上的起点，我们经常能接触到的ASCII码以及电报码都属于信源编码。但当今通信过程中常用的在信源端进行有两种可选择的编码方式，分为有损编码和无损编码，无损损编码包括：霍夫曼编码、算术编码、L-Z编码，也有其他编码方式是对所要编码的数据产生一定的损耗，叫做有损编码。信源编码改进的方向为使用更少的资源耗费更少的时间就能在信源减降低信息的冗余。本次设计的主要目的就是在信源进行编码实现数据压缩，说到数据压缩就不得不提到霍夫曼编码方式。霍夫曼编码之中拥有权路径长度最短的二叉树的霍夫曼树被称为最优二叉树，它常常出现在数据压缩的应用之中。
“霍夫曼编码”是一种一致性编码方法（也被称为熵编码方法），并能实现信息无损压缩。这种专业的名称是指利用所建立的特别的编码表将源字符（比如某文档中出现的某一符号）进行编码。这张编码表之所以会特别，是因为它计算每一个源字符出现的概率从而建立一张编码表（以高概率出现的字符就匹配较短的编码，相反的符号出现频率比较低的就匹配更长编码，它的作用就是在被编码的字符串的长度比预期的值更小，以实现数据的无损压缩。David.A.Huffman是这种编码方式的发源者，所以这种编码的方式就叫“霍夫曼编码”了。 比如，在英语单词中，a的出现频率非常高，x的出现频率就非常低。我们对一段英语文章利用霍夫曼编码压缩时，e分配一个位(bit)就够了，而x则分配25个位去表示。如果不对英语单词进行压缩而用一般的表示方式表达时，每一个英文字母都会占用8个位，即一个字节（byte）的容量。
对比两种表示方式，e占用的空间仅仅是一般编码的1/8，x占用的空间达到了一般的3倍以上。它可以提高对英语中的每一个字母的概率发生的概率，并能大大提高无损压缩的比例。
在现代通信中霍夫曼编码也被广泛的应用，在分组码方面它仍然存在着缺点。比如说概率特征必需获得精准的预测，如果它产生了变化那我们要做的就是更换码表，在对二元信源进行编码的时候，单一的符号不能编码，必须将多个符号组合进行编码获得更好的效果，如果对少量的符号编码编码效率能提升的空间就会很小，特别是在信源编码的结果难以达到预期结果，同时需要组合更多的鼓数，码表中寻在更多的码字，数据也变得繁杂更加难以操控。另外，在信源部分有存储部分时，靠单一的符号编码不可能使编码效能靠近1，所以一维熵H1就被设定为信息率所要接近的值，另外H肯定不会大于H1.这时候舍弃单一符号编码采用复合符号编码的方式提升编码效率就是必要的了，但这并不是完美的方法。它直接导致了码表过长，存储器压力过大。
图1 LZ77编码中缓冲区示意图
实现LZ77算法压缩的时候,一般把缓冲区的长度表示为N,M (M〈N)被用来表示缓冲区中用来存储前一步中被压缩的信息的长度,所以我们把M称作—正文窗口;用于存储待压缩的数据部分的长度我们则可以表示成N-M, N-M通常被称为超前查看缓冲区。实现压缩算法的实质是将所要处理的文件通过特定的顺序读取（一般为至右到左）,从而找出和超前查看缓冲区里即将被压缩数据存在一个具有最大长度的匹配字符串,然后我们假设起始位置值P，它表示数据被扫描之后所产生最大匹配字符串的位置,它还需要满足0
1 引言 1
1.1研究背景 1
1.2研究目的 2
1.3系统设计基本内容 3
2字典码编码种类及基本理论介绍 4
2.1字典码编码的起源和发展 4
2.2各类基于字典的编解码算法的基本原理 5
2.2.1 LZ77 5
2.2.2 LZSS 7
2.2.3 LZ78 9
2.3.4 LZW 10
3字典码编码软件设计 11
3.1系统功能与性能需求 11
3.2算法实现 11
总 结 19
致 谢..........................................................................................................................20
1 引言
1.1研究背景
/> 多媒体技术是结合了计算机技术、视频技术、音频技术以及通信技术的综合体。在庞大的多媒体系统中,有很多要处理、传送、保存的信息,这些信息一般以数字、文本、语音、音乐、图形、视频等形式存在,这么多形式的媒体在计算机系统中占用很大的内存。所以髙效的传输这些数据和压缩这些数据的功能就成为多媒体系统中一项关键的功能,如何压缩这些数据直接影响到多媒体计算机的使用和改进。这些多媒体数据能被正常读取的条件是进行有效的压缩,现今功能强大的计算机在面对如此大的数据量时也显得有些短板,假如我们不处理这些庞然大物而是直接进行读取或是存储,那么就会对多媒体信息的传输、存取甚至是读出带来影响。所以我们压缩处理这些视频、图像多媒体数据就很必要了，借此来让我们释放计算机的数据传输速率让我们享受更高的传送速度，同时让我们的存储器存储更多的文件,让和数据处理能力得到质的飞跃,与此同时我们还可以花更少的时间获得更优质的多媒体数据，获得视听上的升级。
多媒体数据会面临体型庞大这个问题是存在一些原因的,因为多多少少会存在一些冗余，我们喜欢把这些冗余分为两种:主观冗余以及客观冗余。客观冗余主要是指因为在原始数据表示上固有的冗余,主要是由于数据处理上的不完善而产生的;而主观冗余则是指我们人类的感官功能不是完美的，存在一定的限制，这些冗余到达且被我们接受的时候,这些数据的全部信息不能被我们一点没有遗漏的接受,那些被我们遗漏的信息部分就被我们称作主观冗余。这些数据冗余又以空间冗余、时间冗余、编码冗余、结构冗余、知识冗余、信息结构冗余这些形式出现,这时候压缩就以一种必要的技术出现了，这些冗余迫切的需要通过编码实现数据的压缩来缩小它们的体型。所以说以上说到的数据压缩的过程,简而言之就是消去多媒体数据冗余性的方法。
实现信息从一种储存方式改变成另外一种储存方式的过程的叫做编码它就是一段功能为压缩的计算机编程代码，简称编码。需要处理文字、数字或其它对象时提前制定一种方法将对象编成数码，电脉冲信号也可以成为信息、数据转换的目标。编码涉及到电脑、播放器、远程控制和远程通话很多领域。在整个信息传输过程中，可以在不同阶段对对象进行编码，在信源和信道都可以进行编码，分别成为信源编码和信道编码，在此次设计的目中就实现信源编码。
1.2研究目的
信源编码的目的是为了提高通讯的有效性，在信源读取符号之后采用预定的转换，简而言之信源符号转换是为了削减或除去信源利余度所存在的。更确切一点说，信源编码就是针对在信源按照一点顺序传送出符号时，为了使用更短的码字来表示信源符号序列，通过采样信源符号的排列顺序特性来查找一种方式实现，使输出符号的码元载荷信息输出的时候，码元不仅荷载的信息平均量尽量加大，还能确保在后续的解码进程中符号的排列顺序不会产生失真来还原成符号改变之前。信源编码有两个作用，第一数据压缩时通过缩小码元数量以及下降码元速度；第二是实现信源从模拟信号到成数字信号的转变，从而达到用数字化传输的方式传送所需要的模拟信号的目的。摩尔斯电码可以说是信源编码历史上的起点，我们经常能接触到的ASCII码以及电报码都属于信源编码。但当今通信过程中常用的在信源端进行有两种可选择的编码方式，分为有损编码和无损编码，无损损编码包括：霍夫曼编码、算术编码、L-Z编码，也有其他编码方式是对所要编码的数据产生一定的损耗，叫做有损编码。信源编码改进的方向为使用更少的资源耗费更少的时间就能在信源减降低信息的冗余。本次设计的主要目的就是在信源进行编码实现数据压缩，说到数据压缩就不得不提到霍夫曼编码方式。霍夫曼编码之中拥有权路径长度最短的二叉树的霍夫曼树被称为最优二叉树，它常常出现在数据压缩的应用之中。
“霍夫曼编码”是一种一致性编码方法（也被称为熵编码方法），并能实现信息无损压缩。这种专业的名称是指利用所建立的特别的编码表将源字符（比如某文档中出现的某一符号）进行编码。这张编码表之所以会特别，是因为它计算每一个源字符出现的概率从而建立一张编码表（以高概率出现的字符就匹配较短的编码，相反的符号出现频率比较低的就匹配更长编码，它的作用就是在被编码的字符串的长度比预期的值更小，以实现数据的无损压缩。David.A.Huffman是这种编码方式的发源者，所以这种编码的方式就叫“霍夫曼编码”了。 比如，在英语单词中，a的出现频率非常高，x的出现频率就非常低。我们对一段英语文章利用霍夫曼编码压缩时，e分配一个位(bit)就够了，而x则分配25个位去表示。如果不对英语单词进行压缩而用一般的表示方式表达时，每一个英文字母都会占用8个位，即一个字节（byte）的容量。
对比两种表示方式，e占用的空间仅仅是一般编码的1/8，x占用的空间达到了一般的3倍以上。它可以提高对英语中的每一个字母的概率发生的概率，并能大大提高无损压缩的比例。
在现代通信中霍夫曼编码也被广泛的应用，在分组码方面它仍然存在着缺点。比如说概率特征必需获得精准的预测，如果它产生了变化那我们要做的就是更换码表，在对二元信源进行编码的时候，单一的符号不能编码，必须将多个符号组合进行编码获得更好的效果，如果对少量的符号编码编码效率能提升的空间就会很小，特别是在信源编码的结果难以达到预期结果，同时需要组合更多的鼓数，码表中寻在更多的码字，数据也变得繁杂更加难以操控。另外，在信源部分有存储部分时，靠单一的符号编码不可能使编码效能靠近1，所以一维熵H1就被设定为信息率所要接近的值，另外H肯定不会大于H1.这时候舍弃单一符号编码采用复合符号编码的方式提升编码效率就是必要的了，但这并不是完美的方法。它直接导致了码表过长，存储器压力过大。
图1 LZ77编码中缓冲区示意图
实现LZ77算法压缩的时候,一般把缓冲区的长度表示为N,M (M〈N)被用来表示缓冲区中用来存储前一步中被压缩的信息的长度,所以我们把M称作—正文窗口;用于存储待压缩的数据部分的长度我们则可以表示成N-M, N-M通常被称为超前查看缓冲区。实现压缩算法的实质是将所要处理的文件通过特定的顺序读取（一般为至右到左）,从而找出和超前查看缓冲区里即将被压缩数据存在一个具有最大长度的匹配字符串,然后我们假设起始位置值P，它表示数据被扫描之后所产生最大匹配字符串的位置,它还需要满足0
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/dzxx/dzkxyjs/2020.html
