小张学算法之基础算法：2.游标编码算法

定义：

游标编码就是将一连串相同的字符或数据使用 次数+数据的方式进行压缩。属于熵编码的一种。

例子：
加入文本数据：
aaaaaabbbbbbbccc
就可以表示为
6a7b3c
原本存储需要16个byte存储，现在只需要6个byte了。
如何存储呢：
如果只是顺序的存储cnt+数据的存储方式，我们没法解决有数字的文本信息，当出现数字时没法知道到底是数字4还是cnt值为4。

存储结构

所以我们以这样的数据结构来存储：

struct{byte cnt；byte dat；
}

第一字节存cnt，第二字节存数据，当然这个数据可以是字符也可是一个字节的二进制数据。

适用条件

出现连续的重复序列的数据

例子

我们对一张色域256的图片进行压缩，（色域256色刚好一个像素对应一个字节，如果其他色域，一个像素不是一个字节那就可能没有一系列重复的字节），window 画图工具打开，进行艺术创造~，保存256色域 nihao.bmp

上代码进行压缩（python实现）

#-*- coding:utf-8 -*-def rle_compile(src_path, dest_path):with open(src_path, 'rb') as src_fd:with open(dest_path, 'wb') as dest_fd:cur_byt = src_fd.read(1)last_byt = Nonecnt = 0;while cur_byt:if cur_byt != last_byt:if last_byt is not None:write_pair(dest_fd, cnt, last_byt)last_byt = cur_bytcnt = 1else:cnt = cnt + 1if cnt > 255:write_pair(dest_fd, 255, last_byt)cnt=1cur_byt = src_fd.read(1)if cnt > 0:write_pair(dest_fd, cnt, last_byt)def write_pair(fd, cnt, dat_byt):fd.write(int.to_bytes(cnt, 1, byteorder='big'))fd.write(dat_byt)def rle_decompile(src_path, dest_path):with open(src_path, 'rb') as src_fd:with open(dest_path, 'wb') as dest_fd:cnt = src_fd.read(1)dat_byt = src_fd.read(1)while cnt and dat_byt:dest_fd.write(int.from_bytes(cnt,byteorder='big')*dat_byt)cnt = src_fd.read(1)dat_byt = src_fd.read(1)
def main():src_path = 'nihao.bmp'com_path = 'nihao_cmo.zfj'decom_path = 'nihao_decmo.bmp'rle_compile(src_path, com_path)rle_decompile(com_path, decom_path)
if __name__ == '__main__':main()

508KB的源文件压缩到11KB，压缩率达2.1%！！！