数据压缩算法-LZ77
2021-01-19 09:24:36 
阿炯
LZ77与LZ78是Abraham Lempel与Jacob Ziv在1977年以及1978年发表的论文中的两个无损数据压缩算法。这两个算法是大多数LZ算法变体如LZW、LZSS以及其它一些压缩算法的基础。与最小冗余编码器或者行程长度编码器不同，这两个都是基于字典的编码器。LZ77是“滑动窗”压缩算法，这个算法后来被证明等同于LZ78中首次出现的显式字典编码技术。
其所使用的算法是采用字典做数据压缩的算法，由以色列的两位大神Jacob Ziv与Abraham Lempel在1977年发表的论文《A Universal Algorithm for Sequential Data Compression》中提出。基于统计的数据压缩编码，比如Huffman编码，需要得到先验知识——信源的字符频率，然后进行压缩。但是在大多数情况下，这种先验知识是很难预先获得。因此，设计一种更为通用的数据压缩编码显得尤为重要。LZ77数据压缩算法应运而生，其核心思想：利用数据的重复结构信息来进行数据压缩。
LZ77
LZ77算法通过使用编码器或者解码器中已经出现过的相应匹配数据信息替换当前数据从而实现压缩功能。这个匹配信息使用称为长度-距离对的一对数据进行编码，它等同于“每个给定长度个字符都等于后面特定距离字符位置上的未压缩数据流。”(“距离”有时也称作“偏移”。)
编码器和解码器都必须保存一定数量的最近的数据，如最近2 KB、4 KB或者32 KB的数据。保存这些数据的结构叫作滑动窗口，因为这样所以LZ77有时也称作滑动窗口压缩。编码器需要保存这个数据查找匹配数据，解码器保存这个数据解释编码器所指代的匹配数据。所以编码器可以使用一个比解码器更小的滑动窗口，但是反过来却不行。
许多关于LZ77算法的文档都将长度距离对描述为从滑动窗“复制”数据的命令：“在缓冲区中回退距离个字符然后从那点开始复制长度个字符。”尽管对于习惯于指令式编程的人们来说很直观，但是它仍然使得人们很难理解LZ77编码的一个特点：也就是说，长度距离对中的长度超过距离这样一种情况不仅是可接受的而且还是经常出现的情况。作为一个复制命令，就会让人费解：“回退一个字符然后从那点开始复制七个字符。”但是如果缓冲区中只有一个字符的话那该如何复制七个字符呢？然而将长度距离对看作对于特性的描述就可以避免这种混淆：后面的七个字符与前面的七个完全相同。这就意味着每个字符都可以通过在缓冲区找到确定下来：即使在当前数据对解码开始的时候所要查找的字符并不在缓冲区中也可以。通过这个定义，这样的数据对将是距离字符序列的多次重复，也就是说LZ77成了一个灵活容易的行程长度编码形式。
尽管所有的LZ77算法都是根据同样的基本原理工作，但是如何输出编码后的数据可能会大不一样，例如长度与距离的取值范围是多少以及如何区分长度距离对和字面符号(即直接用字符本身，而不是用长度距离对表示)。下面是一些实例：
1、在Lempel与Ziv最初1977年论文中描述的算法每次将数据输出成三个数值：在缓冲区中找到的最大匹配长度与位置以及紧随这个匹配的字面符号。如果输入流中的两个相邻字符只能编码成字面符号的话，那么长度就是0。
2、在PalmDoc格式中，长度距离对经常用两字节序列进行编码，在这两字节的16位中，11位表示距离，3位表示长度，剩余的两位用来表示第一个字节是这样一个两个字节序列的开头。
3、直到2004年，最流行的基于LZ77的压缩方法是同时使用了LZ77与哈夫曼编码的DEFLATE。字面符号、长度以及用于指示当前数据块结束的符号都放到一个字母表中。距离可以安全地放到一个单独的字母表中，由于距离只会出现在一个长度后面，所以它不可能与其它类型的符号混淆。
LZ78
LZ77算法针对过去的数据进行处理，而LZ78算法却是针对后来的数据进行处理。LZ78通过对输入缓存数据进行预先扫描与它维护的字典中的数据进行匹配来实现这个功能，在找到字典中不能匹配的数据之前它扫描进所有的数据，这时它将输出数据在字典中的位置、匹配的长度以及找不到匹配的数据，并且将结果数据添加到字典中。
尽管在最初得到流行，但是后来LZ78的普及逐渐衰减，这可能是由于在刚LZ78出现的一些年份，一部分LZ78算法获得了美国专利保护。最流行的LZ78压缩形式是LZW算法，这个算法是Terry Welch所开发的一个LZ78变体。
2021年1月18日，IEEE 终身研究员 Jacob Ziv 将获得今年的 IEEE 荣誉勋章，主要原因是他对信息论和数据压缩技术的重要贡献以及杰出的研究领导能力。 Jacob Ziv 被称为数据压缩先驱是因为他和 Abraham Lempel 在 1977 年发布的 Lempel-Ziv 算法(LZ77)及之后的系列贡献。
LZ77 是许多无损压缩算法的基础，是第一个使用字典来压缩数据的算法。LZ77 管理一个叫做 slidingwindow 的动态字典，算法的工作原理是将一串字符替换为单个代码，并标记为“tokens”。当算法识别出一个新的字符串时，它就输出这个字符串，然后将其添加到字典中，下次再遇到这个字符串时，输出单个代码，这意味着数据被“压缩”了，以便更有效地传输。
一个简单的例子：
"I am an engineer therefore I am an engineer, and only if I am an engineer"
变成
"I am an engineer* there&fo& *, and only if *.
第一次出现"I am an engineer"后，指定了"*"值，之后再出现该短语由"*"表示。同样，＆ 是已被指定了"re"值。
1978 年，二人又发布了通过解析输入数据生成静态字典的 LZ78 算法。这两个算法能够从压缩数据中完美实现数据解压重构，并且比以往的算法效率更高，它们也可以用在 GIF，PNG，ZIP 文件的压缩中。
"LZ 算法是第一个成功的通用压缩算法"，一位支持 Jacob Ziv 获奖的工程师说道，"这些算算法以及 Jacob Ziv 对它们的分析已经构成了后续大多数通用算法的基础。"
此外，Jacob Ziv 还有很多成就，并获得多项殊荣，包括 1995 年的 Marconi Prize，2008 年的 BBVA Foundation Frontiers of Knowledge Award，2017 年的 EMET Prize。
Jacob Ziv 出生在以色列，1955 年开始其工程师生涯，在以色列国防部任职，负责通信系统的开发。1962 年获得麻省理工学院的电气工程博士学位，后重新加入以色列国防部领导通信系统部门。自 1970 年以来，他一直任以色列理工学院电气工程教授，并在 1974 年至 1976 年担任电气工程学院院长，1978 年至 1982 年担任学院教务处副院长。
无损压缩鼻祖Abraham Lempel离世，享年86岁
来自以色列的科学家的他正是因为他和同事发明的LZ77/LZ78压缩算法，才有了Zip、GIF、PNG、TIFF、MP3、PDF等直到今天还在流行的文件格式。他生前曾就职的的以色列理工学院评价他为“学院成立100年来最伟大的研究员之一”，并称很少有科学家“像他一样在技术发展以及我们的日常生活领域中都产生了如此大的影响”。
无数网友为他的离世哀悼。有人还表示：我的研究生论文主题是HTML压缩，里面都还写有他的名字呢。
共同发明LZ77/LZ78，彻底改写数据压缩领域
Lempel教授于1936年出生于波兰。23岁的时候他进入以色列理工学院，经过八年的学习，拿到博士学位。在毕业十年之际，41岁的他成为母校的全职教授，负责电气工程和计算机科学专业的教学（随后又担任了三年计算机学院院长）。这一年他和同事Jacob Ziv发明LZ77算法的那一年，也就是1977年（下图左为Ziv，右为Lempel）。
正如其名，“LZ77”中的“L”代表Lempel教授，“Z”代表他的同事Ziv教授，“77”则是发明年份。
如果你是计算机专业的学生，LZ77算法一定出现过你的课本之上。其特点包括简单、易于实现，可以针对任何数据格式进行无损压缩，完全区别于此前已经诞生的各种有损压缩算法。它主要采用的是基于字典的方式进行压缩。简单来说，就是把数据中可以组成“短语”的一串字符加入“字典”，然后再有匹配的字符出现就采用标记来代替，由此就能实现压缩的目的。
在具体操作中，该算法会将数据分为“滑动窗口”和“数据缓冲区”。每次处理数据的时候，先把一部分数据预载入缓冲区，然后依次载入滑动窗口区（有长度限制）。如果后进入的字符在滑动窗口里面出现匹配的时候，就记进当前的短语字典中。随着滑动窗口的不断向前，字典会不断变化，不停地滑动字符向前，寻找到更多与字典中的短语匹配的选项，然后用带有含义的标记符进行标记，最终就可以得到一段压缩好的表示结果。
例子如下图所示，粉色为滑动窗口区，蓝色为缓冲区。
从上面的原理我们可以看出，LZ77的压缩比比较高，但由于要不停地找匹配选项，压缩过程有一些耗时，但又由于解压速度又非常快（标记会说明匹配项的明确位置），总体还是算得上非常高效的。
两位教授就以论文的形式将他们这一成果公布了出来。很快在1978年，他们又对77算法进行了更新，诞生了同样著名的LZ78，也就是LZ77的第二个版本。
不管后来大家如何“修修补补”，衍生出更加高效和完善的LZSS、LZW、LZH等新算法，它们的原理都和Lempel教授和Ziv教授的思想没有什么差别。因此在这些算法上诞生的TIFF、PNG、ZIP、MP3等广为流传的压缩文件格式，都得感谢这两位老爷子的贡献。
2004年，IEEE就宣布LZ77和LZ78算法成为电气和电子工程的“历史里程碑”。
Lempel教授也因为所作贡献，拿了不少奖项，包括IEEE信息理论学会技术创新金禧奖和2007年的IEEE Richard W. Hamming奖章，后者主要表彰他在“数据压缩方面的开创性工作”。
57岁被惠普聘用，贡献了8项专利
在改写数据压缩领域之后，Lempel教授并没有“闲着”。1993年，已经57岁的他被惠普公司聘用。仅过了一年，他就出来创立了惠普以色列实验室（HP Labs Israel），并担任其董事长直到71岁。在此期间，惠普以Lempel教授的名义注册了8项专利。如今，Lempel教授已于2023年2月5日辞世，离87岁生日就还差一周时间。
讣告地址。
其所使用的算法是采用字典做数据压缩的算法，由以色列的两位大神Jacob Ziv与Abraham Lempel在1977年发表的论文《A Universal Algorithm for Sequential Data Compression》中提出。基于统计的数据压缩编码，比如Huffman编码，需要得到先验知识——信源的字符频率，然后进行压缩。但是在大多数情况下，这种先验知识是很难预先获得。因此，设计一种更为通用的数据压缩编码显得尤为重要。LZ77数据压缩算法应运而生，其核心思想：利用数据的重复结构信息来进行数据压缩。
LZ77
LZ77算法通过使用编码器或者解码器中已经出现过的相应匹配数据信息替换当前数据从而实现压缩功能。这个匹配信息使用称为长度-距离对的一对数据进行编码，它等同于“每个给定长度个字符都等于后面特定距离字符位置上的未压缩数据流。”(“距离”有时也称作“偏移”。)
编码器和解码器都必须保存一定数量的最近的数据，如最近2 KB、4 KB或者32 KB的数据。保存这些数据的结构叫作滑动窗口，因为这样所以LZ77有时也称作滑动窗口压缩。编码器需要保存这个数据查找匹配数据，解码器保存这个数据解释编码器所指代的匹配数据。所以编码器可以使用一个比解码器更小的滑动窗口，但是反过来却不行。
许多关于LZ77算法的文档都将长度距离对描述为从滑动窗“复制”数据的命令：“在缓冲区中回退距离个字符然后从那点开始复制长度个字符。”尽管对于习惯于指令式编程的人们来说很直观，但是它仍然使得人们很难理解LZ77编码的一个特点：也就是说，长度距离对中的长度超过距离这样一种情况不仅是可接受的而且还是经常出现的情况。作为一个复制命令，就会让人费解：“回退一个字符然后从那点开始复制七个字符。”但是如果缓冲区中只有一个字符的话那该如何复制七个字符呢？然而将长度距离对看作对于特性的描述就可以避免这种混淆：后面的七个字符与前面的七个完全相同。这就意味着每个字符都可以通过在缓冲区找到确定下来：即使在当前数据对解码开始的时候所要查找的字符并不在缓冲区中也可以。通过这个定义，这样的数据对将是距离字符序列的多次重复，也就是说LZ77成了一个灵活容易的行程长度编码形式。
尽管所有的LZ77算法都是根据同样的基本原理工作，但是如何输出编码后的数据可能会大不一样，例如长度与距离的取值范围是多少以及如何区分长度距离对和字面符号(即直接用字符本身，而不是用长度距离对表示)。下面是一些实例：
1、在Lempel与Ziv最初1977年论文中描述的算法每次将数据输出成三个数值：在缓冲区中找到的最大匹配长度与位置以及紧随这个匹配的字面符号。如果输入流中的两个相邻字符只能编码成字面符号的话，那么长度就是0。
2、在PalmDoc格式中，长度距离对经常用两字节序列进行编码，在这两字节的16位中，11位表示距离，3位表示长度，剩余的两位用来表示第一个字节是这样一个两个字节序列的开头。
3、直到2004年，最流行的基于LZ77的压缩方法是同时使用了LZ77与哈夫曼编码的DEFLATE。字面符号、长度以及用于指示当前数据块结束的符号都放到一个字母表中。距离可以安全地放到一个单独的字母表中，由于距离只会出现在一个长度后面，所以它不可能与其它类型的符号混淆。
LZ78
LZ77算法针对过去的数据进行处理，而LZ78算法却是针对后来的数据进行处理。LZ78通过对输入缓存数据进行预先扫描与它维护的字典中的数据进行匹配来实现这个功能，在找到字典中不能匹配的数据之前它扫描进所有的数据，这时它将输出数据在字典中的位置、匹配的长度以及找不到匹配的数据，并且将结果数据添加到字典中。
尽管在最初得到流行，但是后来LZ78的普及逐渐衰减，这可能是由于在刚LZ78出现的一些年份，一部分LZ78算法获得了美国专利保护。最流行的LZ78压缩形式是LZW算法，这个算法是Terry Welch所开发的一个LZ78变体。
2021年1月18日，IEEE 终身研究员 Jacob Ziv 将获得今年的 IEEE 荣誉勋章，主要原因是他对信息论和数据压缩技术的重要贡献以及杰出的研究领导能力。 Jacob Ziv 被称为数据压缩先驱是因为他和 Abraham Lempel 在 1977 年发布的 Lempel-Ziv 算法(LZ77)及之后的系列贡献。
LZ77 是许多无损压缩算法的基础，是第一个使用字典来压缩数据的算法。LZ77 管理一个叫做 slidingwindow 的动态字典，算法的工作原理是将一串字符替换为单个代码，并标记为“tokens”。当算法识别出一个新的字符串时，它就输出这个字符串，然后将其添加到字典中，下次再遇到这个字符串时，输出单个代码，这意味着数据被“压缩”了，以便更有效地传输。
一个简单的例子：
"I am an engineer therefore I am an engineer, and only if I am an engineer"
变成
"I am an engineer* there&fo& *, and only if *.
第一次出现"I am an engineer"后，指定了"*"值，之后再出现该短语由"*"表示。同样，＆ 是已被指定了"re"值。
1978 年，二人又发布了通过解析输入数据生成静态字典的 LZ78 算法。这两个算法能够从压缩数据中完美实现数据解压重构，并且比以往的算法效率更高，它们也可以用在 GIF，PNG，ZIP 文件的压缩中。
"LZ 算法是第一个成功的通用压缩算法"，一位支持 Jacob Ziv 获奖的工程师说道，"这些算算法以及 Jacob Ziv 对它们的分析已经构成了后续大多数通用算法的基础。"
此外，Jacob Ziv 还有很多成就，并获得多项殊荣，包括 1995 年的 Marconi Prize，2008 年的 BBVA Foundation Frontiers of Knowledge Award，2017 年的 EMET Prize。
Jacob Ziv 出生在以色列，1955 年开始其工程师生涯，在以色列国防部任职，负责通信系统的开发。1962 年获得麻省理工学院的电气工程博士学位，后重新加入以色列国防部领导通信系统部门。自 1970 年以来，他一直任以色列理工学院电气工程教授，并在 1974 年至 1976 年担任电气工程学院院长，1978 年至 1982 年担任学院教务处副院长。
无损压缩鼻祖Abraham Lempel离世，享年86岁
来自以色列的科学家的他正是因为他和同事发明的LZ77/LZ78压缩算法，才有了Zip、GIF、PNG、TIFF、MP3、PDF等直到今天还在流行的文件格式。他生前曾就职的的以色列理工学院评价他为“学院成立100年来最伟大的研究员之一”，并称很少有科学家“像他一样在技术发展以及我们的日常生活领域中都产生了如此大的影响”。
无数网友为他的离世哀悼。有人还表示：我的研究生论文主题是HTML压缩，里面都还写有他的名字呢。
共同发明LZ77/LZ78，彻底改写数据压缩领域
Lempel教授于1936年出生于波兰。23岁的时候他进入以色列理工学院，经过八年的学习，拿到博士学位。在毕业十年之际，41岁的他成为母校的全职教授，负责电气工程和计算机科学专业的教学（随后又担任了三年计算机学院院长）。这一年他和同事Jacob Ziv发明LZ77算法的那一年，也就是1977年（下图左为Ziv，右为Lempel）。
正如其名，“LZ77”中的“L”代表Lempel教授，“Z”代表他的同事Ziv教授，“77”则是发明年份。
如果你是计算机专业的学生，LZ77算法一定出现过你的课本之上。其特点包括简单、易于实现，可以针对任何数据格式进行无损压缩，完全区别于此前已经诞生的各种有损压缩算法。它主要采用的是基于字典的方式进行压缩。简单来说，就是把数据中可以组成“短语”的一串字符加入“字典”，然后再有匹配的字符出现就采用标记来代替，由此就能实现压缩的目的。
在具体操作中，该算法会将数据分为“滑动窗口”和“数据缓冲区”。每次处理数据的时候，先把一部分数据预载入缓冲区，然后依次载入滑动窗口区（有长度限制）。如果后进入的字符在滑动窗口里面出现匹配的时候，就记进当前的短语字典中。随着滑动窗口的不断向前，字典会不断变化，不停地滑动字符向前，寻找到更多与字典中的短语匹配的选项，然后用带有含义的标记符进行标记，最终就可以得到一段压缩好的表示结果。
例子如下图所示，粉色为滑动窗口区，蓝色为缓冲区。
从上面的原理我们可以看出，LZ77的压缩比比较高，但由于要不停地找匹配选项，压缩过程有一些耗时，但又由于解压速度又非常快（标记会说明匹配项的明确位置），总体还是算得上非常高效的。
两位教授就以论文的形式将他们这一成果公布了出来。很快在1978年，他们又对77算法进行了更新，诞生了同样著名的LZ78，也就是LZ77的第二个版本。
不管后来大家如何“修修补补”，衍生出更加高效和完善的LZSS、LZW、LZH等新算法，它们的原理都和Lempel教授和Ziv教授的思想没有什么差别。因此在这些算法上诞生的TIFF、PNG、ZIP、MP3等广为流传的压缩文件格式，都得感谢这两位老爷子的贡献。
2004年，IEEE就宣布LZ77和LZ78算法成为电气和电子工程的“历史里程碑”。
Lempel教授也因为所作贡献，拿了不少奖项，包括IEEE信息理论学会技术创新金禧奖和2007年的IEEE Richard W. Hamming奖章，后者主要表彰他在“数据压缩方面的开创性工作”。
57岁被惠普聘用，贡献了8项专利
在改写数据压缩领域之后，Lempel教授并没有“闲着”。1993年，已经57岁的他被惠普公司聘用。仅过了一年，他就出来创立了惠普以色列实验室（HP Labs Israel），并担任其董事长直到71岁。在此期间，惠普以Lempel教授的名义注册了8项专利。如今，Lempel教授已于2023年2月5日辞世，离87岁生日就还差一周时间。
讣告地址。