前言
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()
只是简单的写了下,没有过多考虑细节,请注意,这不是最终的代码,只是用来阐述原理,仅供参考。输出结果就是上面的输出(格式由于坑爹的博客园固定样式,代码位置有偏移,请注意
Atas ialah kandungan terperinci 图文详解LZ77压缩算法编码Python实现原理. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Anda boleh mempelajari konsep pengaturcaraan asas dan kemahiran Python dalam masa 2 jam. 1. Belajar Pembolehubah dan Jenis Data, 2.

Python digunakan secara meluas dalam bidang pembangunan web, sains data, pembelajaran mesin, automasi dan skrip. 1) Dalam pembangunan web, kerangka Django dan Flask memudahkan proses pembangunan. 2) Dalam bidang sains data dan pembelajaran mesin, numpy, panda, scikit-learn dan perpustakaan tensorflow memberikan sokongan yang kuat. 3) Dari segi automasi dan skrip, Python sesuai untuk tugas -tugas seperti ujian automatik dan pengurusan sistem.

Anda boleh mempelajari asas -asas Python dalam masa dua jam. 1. Belajar pembolehubah dan jenis data, 2. Struktur kawalan induk seperti jika pernyataan dan gelung, 3 memahami definisi dan penggunaan fungsi. Ini akan membantu anda mula menulis program python mudah.

Bagaimana Mengajar Asas Pengaturcaraan Pemula Komputer Dalam masa 10 jam? Sekiranya anda hanya mempunyai 10 jam untuk mengajar pemula komputer beberapa pengetahuan pengaturcaraan, apa yang akan anda pilih untuk mengajar ...

Cara mengelakkan dikesan semasa menggunakan fiddlerevery di mana untuk bacaan lelaki-dalam-pertengahan apabila anda menggunakan fiddlerevery di mana ...

Memuatkan Fail Pickle di Python 3.6 Kesalahan Laporan Alam Sekitar: ModulenotFoundError: Nomodulenamed ...

Bagaimana untuk menyelesaikan masalah segmentasi kata Jieba dalam analisis komen tempat yang indah? Semasa kami mengadakan komen dan analisis tempat yang indah, kami sering menggunakan alat segmentasi perkataan jieba untuk memproses teks ...

Bagaimana cara menggunakan ungkapan biasa untuk memadankan tag tertutup pertama dan berhenti? Semasa berurusan dengan HTML atau bahasa markup lain, ungkapan biasa sering diperlukan untuk ...


Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Penyesuai Pelayan SAP NetWeaver untuk Eclipse
Integrasikan Eclipse dengan pelayan aplikasi SAP NetWeaver.

MinGW - GNU Minimalis untuk Windows
Projek ini dalam proses untuk dipindahkan ke osdn.net/projects/mingw, anda boleh terus mengikuti kami di sana. MinGW: Port Windows asli bagi GNU Compiler Collection (GCC), perpustakaan import yang boleh diedarkan secara bebas dan fail pengepala untuk membina aplikasi Windows asli termasuk sambungan kepada masa jalan MSVC untuk menyokong fungsi C99. Semua perisian MinGW boleh dijalankan pada platform Windows 64-bit.

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

VSCode Windows 64-bit Muat Turun
Editor IDE percuma dan berkuasa yang dilancarkan oleh Microsoft

SublimeText3 versi Inggeris
Disyorkan: Versi Win, menyokong gesaan kod!