LZ77无损压缩算法原理详解(结合图片和简单代码)
LZ77无损压缩算法原理详解(结合图片和简单代码)
算法无损压缩| 2016-09-28
LZ77算法是无损压缩算法，由以色列人Abraham Lempel发表于1977年。LZ77是典型的基于字典的压缩算法，现在很多压缩技术都是基于LZ77。鉴于其在数据压缩领域的地位，本文将结合图片和源码详细介绍其原理。
原理介绍：
首先介绍几个专业术语。
1.lookahead buffer(不知道怎么用中文表述，暂时称为待编码区):
等待编码的区域
2. search buffer：
已经编码的区域，搜索缓冲区
3.滑动窗口：
指定大小的窗，包含“搜索缓冲区”（左） + “待编码区”（右）
接下来，介绍具体的编码过程：
为了编码待编码区， 编码器在滑动窗口的搜索缓冲区查找直到找到匹配的字符串。匹配字符串的开始字符串与待编码缓冲区的距离称为“偏移值”，匹配字符串的长度称为“匹配长 度”。编码器在编码时，会一直在搜索区中搜索，直到找到最大匹配字符串，并输出(o, l )，其中o是偏移值， l是匹配长度。然后窗口滑动l，继续开始编码。如果没有找到匹配字符串，则输出(0, 0, c)，c为待编码区下一个等待编码的字符，窗口滑动“1”。算法实现将类似下面的：
while( lookAheadBuffer not empty )
{
get a pointer (position, match) to the longest match
in the window for the lookAheadBuffer;
output a (position, length, char());
shift the window length+1 characters along;
}
主要步骤为：
1.设置编码位置为输入流的开始
2.在滑窗的待编码区查找搜索区中的最大匹配字符串
3.如果找到字符串，输出(偏移值， 匹配长度)， 窗口向前滑动“匹配长度”
4.如果没有找到，输出(0, 0, 待编码区的第一个字符)，窗口向前滑动一个单位
5.如果待编码区不为空，回到步骤2
描述实在是太复杂，还是结合实例来讲解吧
实例：
现在有字符串“AABCBBABC”，现在对其进行编码。
一开始，窗口滑入如图位置
由图可见，待编码缓冲区有“AAB”三个字符，此时搜索缓冲区还是空的。所以编码第一个字符，由于搜索区为空，故找不到匹配串，输出(0,0, A),窗口右移一个单位，如下图
此时待编码区有“ABC”。开始编码。最先编码”A”，在搜索区找到”A”。由于没有超过待编码区，故开始编码”AB”，但在搜索区没有找到匹配字符串，故无法编码。因此只能编码”A”。
输出(1, 1)。即为相对于待编码区，偏移一个单位，匹配长度为1。窗口右滑动匹配长度，即移动1个单位。如下图
一样，没找到，输出(0, 0, B),右移1个单号，如下图
输出（0， 0， C）,右移1个单位，如下图
输出(2, 1),右移1个单位，如下图
输出(3, 1)， 右移1个单位，如下图
开始编码”A”，在搜索缓冲区查找到匹配字符串。由于待编码缓冲区没有超过，继续编码。 开始编码”AB”,也搜索到。不要停止，继续编码“ABC”，找到匹配字符串。由于继续编码，则超过了窗口，故只编码“ABC”，输出(5, 3),偏移5，长度3。右移3个单位，如下图
此时待编码缓冲区为空，停止编码。
最终输出结果如下
python代码实现：
class Lz77:
def __init__(self, inputStr):
self.inputStr = inputStr #输入流
self.searchSize = 5 #搜索缓冲区(已编码区)大小
self.aheadSize = 3 #lookAhead缓冲区（待编码区）大小
self.windSpiltIndex = 0 #lookHead缓冲区开始的索引
self.move = 0
self.notFind = -1 #没有找到匹配字符串
#得到滑动窗口的末端索引
def getWinEndIndex(self):
return self.windSpiltIndex + self.aheadSize
#得到滑动窗口的始端索引
def getWinStartIndex(self):
return self.windSpiltIndex - self.searchSize
#判断lookHead缓冲区是否为空
def isLookHeadEmpty(self):
return True if self.windSpiltIndex + self.move> len(self.inputStr) - 1 else False
def encoding(self):
step = 0
print("Step Position Match Output")
while not self.isLookHeadEmpty():
#1.滑动窗口
self.winMove()
#2. 得到最大匹配串的偏移值和长度
(offset, matchLen) = self.findMaxMatch()
#3.设置窗口下一步需要滑动的距离
self.setMoveSteps(matchLen)
if matchLen == 0:
#匹配为0，说明无字符串匹配，输出下一个需要编码的字母
nextChar = self.inputStr[self.windSpiltIndex]
result = (step, self.windSpiltIndex, '-', '(0,0)' + nextChar)
else:
result = (step, self.windSpiltIndex, self.inputStr[self.windSpiltIndex - offset: self.windSpiltIndex - offset + matchLen], '(' + str(offset) + ',' + str(matchLen) + ')')
#4.输出结果
self.output(result)
step = step + 1 #仅用来设置第几步
#滑动窗口(移动分界点)
def winMove(self):
self.windSpiltIndex = self.windSpiltIndex + self.move
#寻找最大匹配字符并返回相对于窗口分界点的偏移值和匹配长度
def findMaxMatch(self):
matchLen = 0
offset = 0
minEdge = self.minEdge() + 1 #得到编码区域的右边界
#遍历待编码区，寻找最大匹配串
for i in range(self.windSpiltIndex + 1, minEdge):
#print("i: %d" %i)
offsetTemp = self.searchBufferOffest(i)
if offsetTemp == self.notFind:
return (offset, matchLen)
offset = offsetTemp #偏移值
matchLen = matchLen + 1 #每找到一个匹配串，加1
return (offset, matchLen)
#入参字符串是否存在于搜索缓冲区，如果存在，返回匹配字符串的起始索引
def searchBufferOffest(self, i):
searchStart = self.getWinStartIndex()
searchEnd = self.windSpiltIndex
#下面几个if是处理开始时的特殊情况
if searchEnd < 1:
return self.notFind
if searchStart < 0:
searchStart = 0
if searchEnd == 0:
searchEnd = 1
searchStr = self.inputStr[searchStart : searchEnd] #搜索区字符串
findIndex = searchStr.find(self.inputStr[self.windSpiltIndex : i])
if findIndex == -1:
return -1
return len(searchStr) - findIndex
#设置下一次窗口需要滑动的步数
def setMoveSteps(self, matchLen):
if matchLen == 0:
self.move = 1
else:
self.move = matchLen
def minEdge(self):
return len(self.inputStr) if len(self.inputStr) - 1 < self.getWinEndIndex() else self.getWinEndIndex() + 1
def output(self, touple):
print("%d %d %s %s" % touple)
if __name__ == "__main__":
lz77 = Lz77("AABCBBABC")
lz77.encoding()
只是简单的写了下，没有过多考虑细节，请注意，这不是最终的代码，只是用来阐述原理，仅供参考。输出结果就是上面的输出。
参考文章：
https://msdn.microsoft.com/en-us/library/ee916854.aspx
https://en.wikipedia.org/wiki/LZ77_and_LZ78
https://cs.stanford.edu/people/eroberts/courses/soco/projects/2000-01/data-compression/lossless/lz77/algorithm.htm
以上几篇文章都是很好的讲解LZ77原理的，大家有兴趣的可以参考下。由于国内介绍该算法的比较少，故这些英文文章帮助还是挺大的。
本文文字及图片出自 博客园
你对本文的反应是：
0
俺的神呀 0
赞一个 0
飘过~ 0
强 0
很实用 0
好文 0
笑死了 0
mark 0
敬佩 0
垃圾 0
0
看样子你已经点过这个了！
抱歉，你最多只能点三个！
你也许感兴趣的：
1行代码生成随机迷宫，这个概率编程语言登GitHub热榜，作者曾开发著名WFC算法
为什么谷歌被骂上热搜一点也不冤，详解FLoC背后联邦计算
Google 工程师：如何看待程序员普遍缺乏数据结构和算法知识？
如何判断一个元素在亿级数据中是否存在？
阮一峰：彩票的数学知识
事情污，但算法不污
在美国入境被考算法，非洲程序员的亲身经历
写了六个相同功能的函数之后，我学到了这些
十大机器学习算法
算法是内功，程序员别冷落算法
共有 1 条讨论
大爷 对这篇文章的反应是俺的神呀
2024-10-22 21:34
发表回复 取消回复您的邮箱地址不会被公开。 必填项已用 * 标注
评论 *
显示名称 *
邮箱 *
网站