开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算：行程编码与词典编码】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：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。
从图中的输入和输出可以看出，输出相比输入而言减少许多。当编码数据量增大时，效果更加明显。
