图文详解lz77压缩算法编码python实现原理

前言

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”,现在对其进行编码。

一开始,窗口滑入如图位置

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()

只是简单的写了下,没有过多考虑细节,请注意,这不是最终的代码,只是用来阐述原理,仅供参考。输出结果就是上面的输出(格式由于坑爹的博客园固定样式,代码位置有偏移,请注意

以上就是图文详解lz77压缩算法编码python实现原理的详细内容,更多请关注 第一php社区 其它相关文章!

Posted in 未分类