文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Python中实现一个LZ77压缩算法

2023-06-17 04:28

关注

这篇文章给大家介绍Python中实现一个LZ77压缩算法,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

原理介绍:

首先介绍几个专业术语。

lookahead buffer(不知道怎么用中文表述,暂时称为待编码区):

等待编码的区域

search buffer:

已经编码的区域,搜索缓冲区

滑动窗口:

指定大小的窗,包含“搜索缓冲区”(左) + “待编码区”(右)

接下来,介绍具体的编码过程:

为了编码待编码区,  编码器在滑动窗口的搜索缓冲区查找直到找到匹配的字符串。匹配字符串的开始字符串与待编码缓冲区的距离称为“偏移值”,匹配字符串的长度称为“匹配长度”。编码器在编码时,会一直在搜索区中搜索,直到找到***匹配字符串,并输出(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; }

主要步骤为:

设置编码位置为输入流的开始

在滑窗的待编码区查找搜索区中的***匹配字符串

如果找到字符串,输出(偏移值, 匹配长度), 窗口向前滑动“匹配长度”

如果没有找到,输出(0, 0, 待编码区的***个字符),窗口向前滑动一个单位

如果待编码区不为空,回到步骤2

描述实在是太复杂,还是结合实例来讲解吧

实例:

现在有字符串“AABCBBABC”,现在对其进行编码。

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

Python中实现一个LZ77压缩算法

由图可见,待编码缓冲区有“AAB”三个字符,此时搜索缓冲区还是空的。所以编码***个字符,由于搜索区为空,故找不到匹配串,输出(0,0, A),窗口右移一个单位,如下图

Python中实现一个LZ77压缩算法

此时待编码区有“ABC”。开始编码。***编码”A”,在搜索区找到”A”。由于没有超过待编码区,故开始编码”AB”,但在搜索区没有找到匹配字符串,故无法编码。因此只能编码”A”。

输出(1, 1)。即为相对于待编码区,偏移一个单位,匹配长度为1。窗口右滑动匹配长度,即移动1个单位。如下图

Python中实现一个LZ77压缩算法

一样,没找到,输出(0, 0, B),右移1个单号,如下图

Python中实现一个LZ77压缩算法

输出(0, 0, C),右移1个单位,如下图

Python中实现一个LZ77压缩算法

输出(2, 1),右移1个单位,如下图

Python中实现一个LZ77压缩算法

输出(3, 1), 右移1个单位,如下图

Python中实现一个LZ77压缩算法

开始编码”A”,在搜索缓冲区查找到匹配字符串。由于待编码缓冲区没有超过,继续编码。开始编码”AB”,也搜索到。不要停止,继续编码“ABC”,找到匹配字符串。由于继续编码,则超过了窗口,故只编码“ABC”,输出(5,  3),偏移5,长度3。右移3个单位,如下图

Python中实现一个LZ77压缩算法

此时待编码缓冲区为空,停止编码。

最终输出结果如下

Python中实现一个LZ77压缩算法

python代码实现:

class Lz77:def __init__(self, inputStr):self.inputStr = inputStr #输入流self.searchSize = 5    #搜索缓冲区(已编码区)大小self.aheadSize = 3     #lookAhead缓冲区(待编码区)大小 self.windSpiltIndex = 0 #lookHead缓冲区开始的索引self.move = 0self.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 Falsedef encoding(self):step = 0print("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 = 0offset = 0minEdge = 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  #每找到一个匹配串,加1return (offset, matchLen)#入参字符串是否存在于搜索缓冲区,如果存在,返回匹配字符串的起始索引def searchBufferOffest(self, i):searchStart = self.getWinStartIndex()        searchEnd = self.windSpiltIndex #下面几个if是处理开始时的特殊情况if searchEnd < 1:return self.notFindif searchStart < 0:            searchStart = 0if searchEnd == 0:                searchEnd = 1searchStr = self.inputStr[searchStart : searchEnd]  #搜索区字符串findIndex = searchStr.find(self.inputStr[self.windSpiltIndex : i])if findIndex == -1:return -1return len(searchStr) - findIndex#设置下一次窗口需要滑动的步数def setMoveSteps(self, matchLen):if matchLen == 0:            self.move = 1else:            self.move = matchLendef minEdge(self):return len(self.inputStr)  if len(self.inputStr) - 1 < self.getWinEndIndex() else self.getWinEndIndex() + 1def output(self, touple):print("%d      %d           %s     %s" % touple)if __name__ == "__main__":    lz77 = Lz77("AABCBBABC")    lz77.encoding()

关于Python中实现一个LZ77压缩算法就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯