《老子到此一游系列》之 老子为什么是老子 ——综述视角解读压缩编码 第四章 LZ77 压缩算法（转发）
ELT.ZIP是谁？
ELT<=>Elite(精英)，.ZIP为压缩格式，ELT.ZIP即压缩精英。
成员：
上海工程技术大学大二在校生 闫旭
合肥师范学院大二在校生 楚一凡
清华大学大二在校生 赵宏博
成都信息工程大学大一在校生 高云帆
黑龙江大学大一在校生 高鸿萱
山东大学大三在校生 张智腾
ELT.ZIP是来自6个地方的同学，在OpenHarmony成长计划啃论文俱乐部里，与来自华为、软通动力、润和软件、拓维信息、深开鸿等公司的高手一起，学习、研究、切磋操作系统技术…
本文的梳理来自其中的四名同学：闫旭、楚一凡、赵宏博和高云帆。
前期回顾
第一章：轻松上手——《伟大的计算原理》和《数据压缩技术调查：从数据质量、编码方案、数据类型和应用的角度》
第二章：小波变换（Wavelet Transform）——嵌入式零树小波编码EZW、无损加密后压缩(ETC)技术
第四章 LZ77 压缩算法
4.1 LZ77 编码简介
LZ 编码由以色列研究者 Jacob Ziv 和 Abraham Lempel 提出，是无损压缩的核心思想。LZ 是一个系列的算法，而其中最基本的就是两人在 1977年所发表的论文《A Universal Algorithm for Sequential Compression》 中提出的 LZ77 算法。
LZ77 压缩是一种基于字典及滑动窗口的无损压缩技术，广泛应用于通信传输。
LZ77 算法不同于 Huffman 编码等基于统计的数据压缩编码，需要得到先验知识——信源的字符频率，然后进行压缩。
LZ77的核心思想：利用数据的重复结构信息来进行数据压缩。
4.1 LZ77 的基本原理
LZ77 以经常出现的字母组合（或较长的字符串）构建字典中的数据项，并且使用较短的数字（或符号）编码来代替比较复杂的数据项。数据压缩时，将从待压缩数据中读入的源数据与字典中的数据项进行匹配，从中检索出相应的代码并输出。从而实现数据的压缩。
在 LZ77 方法中，词典就是先前已编码序列的一部分。编码器通过一个滑动窗口来查看输入序列，如下图所示：
这个滑动窗口包括两个部分：查找缓冲区(Search Buffer) 和 先行缓冲区(Look Ahead Buffer)
- 查找缓冲区：包含了最近已编码序列的一部分
- 先行缓冲区：包含待编码序列的下一部分
这里查找缓冲区包含了 8 个符号，先行缓冲区包含 7 个符号。但在实际情况中，缓冲区要大很多。
LZ77 中的相关参数解释：
- 匹配指针 先在 查找缓冲区 中找到移动指针，知道找到与先行缓冲区第一个字符a相匹配字符a。此时该指针与先行缓冲区的距离称为 偏移量(off) 。这里的 偏移量off 就是7。
- 编码器之后查看指针位置之后的符号，查看其是否与先行缓冲区的符号相匹配。从第一个符号（匹配指针以开始所指向的位置）开始，与先行缓冲区的符号匹配，匹配到的连续符号的长度称为 匹配长度(len)。例如这里，从匹配指针所指的位置开始的符号串 abra 与 先行缓冲区中的符号串 abra 相匹配，下一位查找缓冲区的 x 与 先行缓冲区 a 不匹配，所以这里的 匹配长度len 是 4.。
- 编码器在查找缓冲区中搜素最长匹配串。找到最长的匹配串后，编码器即可用三元组 <off,len,c> 对其进行编码。这里 off 是偏移量 ，len 是匹配长度，c 是先行缓冲区中跟在该匹配项串之后的符号的码字。例如这里 匹配串 是 abra，则先行缓冲区匹配串后的码字是 r。
4.1 LZ77 的算法
LZ77 算法执行流程如下：
- 步骤 1：从输入的待压缩数据的起始位置，读取未编码的源数据，从滑动窗口的字典数据项中查找最长的匹配字符串。若结果为 T，则执行步骤 2，若结果为 F，则执行步骤 3；
- 步骤 2：输出函数 F（off，len，c）。然后将窗口向后滑动到 len++，继续步骤 1；
- 步骤 3：输出函数 F（0，0，c），其中 c 为下一个字符。并且窗口向后滑动（len + 1）个字符，执行步骤 1。
下面是代码实现：
参考文献
[1] Universal Lossless Data Compression Algorithms
[2]一种改进的 LZ77 无损数据压缩算法设计
[3] 无损数据压缩、算法比较和实现
[4] LZ77 Parsing, et c.
https://www.cs.helsinki.fi/u/puglisi/dct2017
缩略语列表
| 缩写 | 英文 | 中文 |
| AC | Alternating Current | 交流 |
| ASWDR | Adaptively Scanned Wavelet Difference Reduction | 自适应扫描小波差约简 |
| ATM | Asynchronous Transfer Mode | 异步传输模式 |
| CR | Compression Ratio | 压缩比 |
| CREW | Compression with Reversible Embedded Wavelets | 可逆嵌入小波压缩 |
| CSS | Cascading Style Sheets | 层叠样式表 |
| DC | Data Compression | 数据压缩 |
| DCT | Discrete Cosine Transform | 离散余弦变换 |
| DWT | Discrete Wavelet Transform | 离散小波变换 |
| EBCOT | Embedded Block Coding with Optimised Truncation | 优化截断的嵌入式块 |
| EC | Embedded Coding | 嵌入式编码 |
| EPWIC | Embedded Predictive Wavelet Image Coder | 嵌入式预测小波图像 |
| ETC | Encryption Then Compression | 加密后压缩 |
| EZW | Embedded Zerotree Wavelets | 嵌入式零树小波 |
| GW | Geometric Wavelet | 几何小波 |
| HVS | Human Visual System | 人类视觉系统 |
| JPEG | Joint Photographic Experts Group | 联合图像专家组 |
| LIP | List of Insignificant Pixels | 不重要像素列表 |
| LIS | List of Insignificant Sets | 不重要集合列表 |
| LSP | List of Significant Pixels | 重要像素列表 |
| LZW | Lempel-Ziv-Welch | 蓝波-立夫-卫曲编码法 |
| LZMA | Lempel-Ziv-Markov chain-Algorithm | |
| MSE | Mean Square Error | 均方误差 |
| MPEG | Motion Pictures Expert Group | 动态图像专家组 |
| PSNR | Peak SignaN-to-noise Ratio | 峰值信噪比 |
| RLE | Run Length Encoding | 游程编码 |
| ROI | Region Of Interest | 感兴趣区域 |
| SB | Sub Bands | 子带 |
| SFQ | Space Frequency Quantization | 空频量化 |
| SPECK | Set Partitioned Embedded bloCK | 设置分区嵌入式块 |
| SPIHT | SetPartitioning in Hierarchical Trees | 多级树集合分裂 |
| SR | Stack Run | 堆栈运行 |
| SVD | Singular Value Decomposition | 奇异值分解 |
| VQ | Vector Quantization | 向量量化 |
| WDR | Wavelet Difference Reduction | 小波差约简 |
| WMSN | Wireless Multimedia Sensor Network | 无线多媒体传感器网络 |
| WSN | Wireless Sensor Networks | 无线传感器网络 |
写在最后：
OpenHarmony 成长计划—“啃论文俱乐部”（以下简称“啃论文俱乐部”）是在 2022年 1 月 11 日的一次日常活动中诞生的。截至 3 月 31 日，啃论文俱乐部已有 87 名师生和企业导师参与，目前共有十二个技术方向并行探索，每个方向都有专业的技术老师带领同学们通过啃综述论文制定技术地图，按“降龙十八掌”的学习方法编排技术开发内容，并通过专业推广培养高校开发者成为软件技术学术级人才。
啃论文俱乐部的宗旨是希望同学们在开源活动中得到软件技术能力提升、得到技术写作能力提升、得到讲解技术能力提升。大学一年级新生〇门槛参与，已有俱乐部来自多所高校的大一同学写出高居榜首的技术文章。
如今，搜索“啃论文”，人们不禁想到、而且看到的都是我们——OpenHarmony 成长计划—“啃论文俱乐部”的产出。
OpenHarmony开源与开发者成长计划—“啃论文俱乐部”学习资料合集
1）入门资料：啃论文可以有怎样的体验
https://docs.qq.com/slide/DY0RXWElBTVlHaXhi?u=4e311e072cbf4f93968e09c44294987d
2）操作办法：怎么从啃论文到开源提交以及深度技术文章输出https://docs.qq.com/slide/DY05kbGtsYVFmcUhU
3）企业/学校/老师/学生为什么要参与 & 啃论文俱乐部的运营办法https://docs.qq.com/slide/DY2JkS2ZEb2FWckhq
4）往期啃论文俱乐部同学分享会精彩回顾：
同学分享会No1.成长计划啃论文分享会纪要（2022/02/18） https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY
同学分享会No.2 成长计划啃论文分享会纪要（2022/03/11） https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF
同学们分享会No.3 成长计划啃论文分享会纪要（2022/03/25）
https://docs.qq.com/doc/DUm5pUEF3ck1VcG92?u=4e311e072cbf4f93968e09c44294987d
现在，你是不是也热血沸腾，摩拳擦掌地准备加入这个俱乐部呢？当然欢迎啦！啃论文俱乐部向任何对开源技术感兴趣的大学生开发者敞开大门。
后续，我们会在服务中心公众号陆续分享一些 OpenHarmony 开源与开发者成长计划—“啃论文俱乐部”学习心得体会和总结资料。记得呼朋引伴来看哦。
扫码添加 OpenHarmony 高校小助手，加入“啃论文俱乐部”微信群