开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算:行程编码与词典编码】学习笔记,与课程紧密联系,让用户快速学习知识。
课程地址:https://developer.aliyun.com/learning/course/811/detail/15685
行程编码与词典编码
内容介绍
一.行程编码(Run Length Encoding)
二、词典编码(Dictionary Encoding )
一、行程编码(Run Length Encoding)
1.概念
行程编码(RLE)在部分教材中,又被称为游程编码。R是Run表示行程和游程;L是 Length;E是 Encoding。
RLE 编码的概念
2.乘法代替加法
①使用场景
该算法表示在讲述图像的空间冗余中发现,有大量冗余的区域,两者颜色值接近,通过差分脉冲调制等方法,进行编码后会产生许多相同连续的数字。
②举例
如:全为同一颜色时,经过差分后则全为0或连续若干个8,此时是不采用将单独的0挨个保存,而采用将连续的0看作一个0去保存,另外再将个数存储起来,因为可以解决将加法变为乘法,连续的个数越多,方法效率越高。Eg:此时需要50个8,一个8占3位,采用按个保存则需要150位,而使用将个数单独保存的形式,只需要一个8占3位,一个50占6位,只需要9位。
③好处
此种使用乘法代替加法减少行程长度的方式,可以大幅度降低占用的空间。同时行程长度(Run)的颜色,长度和样本值重复次数越多,编码越有用,压缩比也越高。
二、词典编码(Dictionary Encoding )
1.概念
词典编码类似于查字典的方式。词典编码是根据数据本身包含很多重复的特性,如:在字典中有大量词,不再重复存储相同的词,而采用将其是第几个词的索引存储下来即可。如:“中华人民共和国”在第15页第2条索引,要将15页第2条这个索引记下,而非中华人民共和国”这个词。
词典编码(Dictionary Encoding )的根据是数据本身包含有重复
代码这个特性
例如,文本文件和光栅图像就具有这种特性
2.分类
词典编码法的种类很多,归纳起来大致有两类
①第一类
查找正在压缩的文本,字符或是光栅图像,看其编码的数据是否
在之前输入的数据中出现过。
若出现过,用已经出现过的字符串代替重复的部分,不再重复编
码,只保留字符串的指针。
它的输出仅仅是指针早期出现过的字符串的“指针”
如:输入流为 ABCDXABCM....从第一个开始 A 为第一次出现,则输出 A,B 同理之前并未变过,也为第一次出现,输出 B,之后 CDX 同理输出。但到 ABCM 时,其中连续的 ABC 都曾出现过,此时不再存储ABC而存储P,P表示指向之前出现过的 ABC 字符串的指针。
该算法核心思想:
编译当前字符时,要考虑之前是否出现过。
②第二类
经过统计后发现其中有许多为经常出现的数据
采用从输入的数据中提前创建一个“短语词典(dictionary of the
phrases)”
这种短语不一定具有具体含义的短语,它可以是任意字符的组合。
如:图像一段连续的颜色值或灰度值、任意数字的组合、文本数据字符串等。
遇到已经在词典中出现的短语后,编码器在输出这个词典中的索引号相当于指针,而非短语数据本身。
案例
将经常出现的短语,颜色创建一个词典。ac 由索引号1表示;ax 由索引号2表示;ec由索引号3表示;axx 由索引号4表示;cax 由索引号5表示。
12345分别表示不同的词和短语,共同组成一个词典。开始编译输入数据流时,遇到a在词典中没有,无反应。编译到 ac 发现在词典中有对应,输出索引1。
编译至 acb 词典中并没有,因而将 ac 作为一个词,b 作为一个词分开查找,由ac找到词典中的索引1,b 在词典中未找到,输出 b。而后 axx 在词典中存在,因而输出对应索引4,之后的 a、d、y 在词典中都无法查到,对应输出 a、d、y。
从图中的输入和输出可以看出,输出相比输入而言减少许多。当编码数据量增大时,效果更加明显。