LZ77 压缩算法编码原理详解(结合图片和简单代码) - 文章 - 伯乐在线
& LZ77 压缩算法编码原理详解(结合图片和简单代码)
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 lookAheadB
output a (position, length, char());
shift the window length+1
while( lookAheadBuffer not empty ){get a pointer (position, match) to the longest matchin 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):
print("Step
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)
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 len(searchStr) - findIndex
#设置下一次窗口需要滑动的步数
def setMoveSteps(self, matchLen):
if matchLen == 0:
self.move = 1
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):
%s" % touple)
if __name__ == "__main__":
lz77 = Lz77("AABCBBABC")
lz77.encoding()
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
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原理的，大家有兴趣的可以参考下。由于国内介绍该算法的比较少，故这些英文文章帮助还是挺大的。
可能感兴趣的话题
文章写的很简单易懂，赞。还应该介绍一下压缩跟编码之间的关系，不是很明白。
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2017 伯乐在线LZ77算法是采用字典做数据压缩的算法，由以色列的两位大神Jacob Ziv与Abraham Lempel在1977年发表的论文《A Universal Algorithm for Sequential Data Compression》中提出。
基于统计的数据压缩编码，比如Huffman编码，需要得到先验知识——信源的字符频率，然后进行压缩。但是在大多数情况下，这种先验知识是很难预先获得。因此，设计一种更为通用的数据压缩编码显得尤为重要。LZ77数据压缩算法应运而生，其核心思想：利用数据的重复结构信息来进行数据压缩。举个简单的例子，比如
取之以仁义，守之以仁义者，周也。取之以诈力，守之以诈力者，秦也。
取之以、仁义、，、者、守之以、也、诈力、。均重复出现过，只需指出其之前出现的位置，便可表示这些词。为了指明出现位置，我们定义一个相对位置，如图
相对位置之后的消息串为取之以诈力，守之以诈力者，秦也。，若能匹配相对位置之前的消息串，则编码为以其匹配的消息串的起始与末端index；若未能匹配上，则以原字符编码。相对位置之后的消息串可编码为：[(1-3),(诈力),(6),(7-9),(诈力),(12),(6),(秦),(15-16)]，如图所示：
上面的例子展示如何利用索引值来表示词，以达到数据压缩的目的。LZ77算法的核心思想亦是如此，其具体的压缩过程不过比上述例子稍显复杂而已。
本文讲主要讨论LZ77算法如何做压缩及解压缩，关于LZ77算法的唯一可译、无损压缩（即解压可以不丢失地还原信息）的性质，其数学证明参看原论文[1]。
至于如何描述重复结构信息，LZ77算法给出了更为确切的数学解释。首先，定义字符串\(S\)的长度为\(N\)，字符串\(S\)的子串\(S_{i,j},\ 1\le i,j \le N\)。对于前缀子串\(S_{1,j}\)，记\(L_i^j\)为首字符\(S_{i}\)的子串与首字符\(S_{j+1}\)的子串最大匹配的长度，即：
L_i^j = \max \{ l | S_{i,i+l-1} = S_{j+1,j+l} \} \quad \text{subject to} \quad l \le N-j
我们称字符串\(S_{j+1,j+l}\)匹配了字符串\(S_{i,i+l-1}\)，且匹配长度为\(l\)。如图所示，存在两类情况：
定义\(p^j\)为所有情况下的最长匹配的\(i\)值，即
p^j = \mathop {\arg \max }\limits_{i} \{ L_i^j \} \quad \text{subject to} \quad 1 \le i \le j
比如，字符串\(S=\)且\(j=3\)，则有
\(L_1^j=1\)，因为\(S_{j+1,j+1}=S_{1,1}\), \(S_{j+1,j+2} \ne S_{1,2}\);
\(L_2^j=4\)，因为\(S_{j+1,j+1}=S_{2,2}\), \(S_{j+1,j+2} = S_{2,3}\)，\(S_{j+1,j+3} = S_{2,4}\)，\(S_{j+1,j+4} = S_{2,5}\)，\(S_{j+1,j+5} \ne S_{2,6}\)；
\(L_3^j = 0\)，因为\(S_{j+1,j+1} \ne S_{3,3}\)。
因此，\(p^j = 2\)且最长匹配的长度\(l^j=4\). 从上面的例子中可以看出：子串\(S_{j+1,j+p}\)是可以由\(S_{1,j}\)生成，因而称之为\(S_{1,j}\)的再生扩展（reproducible extension）。LZ77算法的核心思想便源于此——用历史出现过的字符串做词典，编码未来出现的字符，以达到数据压缩的目的。在具体实现中，用滑动窗口（Sliding Window）字典存储历史字符，Lookahead Buffer存储待压缩的字符，Cursor作为两者之间的分隔，如图所示：
并且字典与Lookahead Buffer的长度是固定的。
用\((p,l,c)\)表示Lookahead Buffer中字符串的最长匹配结果，其中
\(p\)表示最长匹配时，字典中字符开始时的位置（相对于Cursor位置），
\(l\)为最长匹配字符串的长度，
\(c\)指Lookahead Buffer最长匹配结束时的下一字符
压缩的过程，就是重复输出\((p,l,c)\)，并将Cursor移动至\(l+1\)，伪代码如下：
Output (p,l,c),
Cursor --& l+1
Until to the end of string
压缩示例如图所示：
为了能保证正确解码，解压缩时的滑动窗口长度与压缩时一样。在解压缩，遇到\((p,l,c)\)大致分为三类情况：
\(p==0\)且\(l==0\)，即初始情况，直接解码\(c\)；
\(p&=l\)，解码为字典dict[p:p+l+1]；
\(p&l\)，即出现循环编码，需要从左至右循环拼接，伪代码如下：
for(i = p, k = 0; k & i++, k++)
out[cursor+k] = dict[i%cursor]
比如，dict=abcd，编码为(2,9,e)，则解压缩为output=abcdcdcdcdcdce。
bitarray的实现请参看，下面给出简单的python实现。
# coding=utf-8
class LZ77:
A simplified implementation of LZ77 algorithm
def __init__(self, window_size):
self.window_size = window_size
self.buffer_size = 4
def longest_match(self, data, cursor):
find the longest match between in dictionary and lookahead-buffer
end_buffer = min(cursor + self.buffer_size, len(data))
c = ''
for j in range(cursor+1, end_buffer+1):
start_index = max(0, cursor - self.window_size + 1)
substring = data[cursor + 1:j + 1]
for i in range(start_index, cursor+1):
repetition = len(substring) / (cursor - i + 1)
last = len(substring) % (cursor - i + 1)
matchedstring = data[i:cursor + 1] * repetition + data[i:i + last]
if matchedstring == substring and len(substring) & l:
p = cursor - i + 1
l = len(substring)
c = data[j+1]
# unmatched string between the two
if p == -1 and l == -1:
return 0, 0, data[cursor + 1]
return p, l, c
def compress(self, message):
compress message
:return: tuples (p, l, c)
# the cursor move until it reaches the end of message
while i & len(message)-1:
(p, l, c) = self.longest_match(message, i)
out.append((p, l, c))
i += (l+1)
return out
def decompress(self, compressed):
decompress the compressed message
:param compressed: tuples (p, l, c)
:return: decompressed message
cursor = -1
out = ''
for (p, l, c) in compressed:
# the initialization
if p == 0 and l == 0:
elif p &= l:
out += (out[cursor-p+1:cursor+1] + c)
# the repetition of dictionary
elif p & l:
repetition = l / p
last = l % p
out += (out[cursor-p+1:cursor+1] * repetition + out[cursor-p+1:last] + c)
cursor += (l + 1)
return out
if __name__ == '__main__':
compressor = LZ77(6)
origin = list('aacaacabcabaaac')
pack = press(origin)
unpack = compressor.decompress(pack)
print pack
print unpack
print unpack == 'aacaacabcabaaac'
4. 参考资料
[1] Ziv, Jacob, and Abraham Lempel. &A universal algorithm for sequential data compression.& IEEE Transactions on information theory 23.3 (1977): 337-343.
[2] guyb, .
阅读(...) 评论()lzss_ 是一个比较著名的压缩算法，改进了lz77。此源代码希望对大家有用。 Compress-De algrithms 解压 240万源代码下载-
&文件名称: lzss_
& & & & &&]
&&所属分类:
&&开发工具: Visual C++
&&文件大小: 27 KB
&&上传时间:
&&下载次数: 552
&&提 供 者:
&详细说明：lzss是一个比较著名的压缩算法，改进了lz77。此源代码希望对大家有用。-lzss is one of the more well-known compression algorithms, improved lz77. This source of hope may be useful.
文件列表(日期：~)(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&&&lzss.exe
&近期下载过的用户:
&相关搜索:
&&&&&&&&&&
&输入关键字，在本站240万海量源码库中尽情搜索：
&[] - 分形算法 图形特效，可随音乐变化，完整VC代码
&[] - 几个压缩算法程序（改进包括lzw、lz77、compress、huffeman）
&[] - 此算法是一个压缩算法，lwz在lz77,lz78的基础上改进的一种算法。
&[] - 一个对lzss压缩算法的深入应用的例子，有兴趣的可以下载看一看
&[] - LZW程序源代码，c语言实现。可能不是很全，我有好的版本，会继续给大家。
&[] - 本文提出了lzss压缩算法在进行文本压缩时存在的问题，并给出了解决方法。改进后的算法具有较高的压缩率，实验结果令人满意。
关键词：LZSS；数据压缩
&[] - 压缩解压算法LZ77算法有许多派生算法(这里面包括 lzss算法)。它们的算法原理上基本都相同，无论是哪种派生算法，LZ77算法总会包含一个动态窗口（Sliding Window）和一个预读缓冲器（Read Ahead Buffer）。动态窗口是个历史缓冲器，它被用来存放输入流的前n个字节的有关信息
&[] - 双基地雷达空间定位精度分析，针对双基地雷达空间定位时的数据冗余提出了一种相关数据压缩算法。
&[] - 使用LZ77算法压缩文件的C代码，一般来说，现在流行的winzip，winrar以及unix下的compress使用的都是该算法
&[] - LZ77压缩算法是一种无损数据压缩算法。该算法是大多数 LZ 算法变体如 LZW、lzss 以及其它一些压缩算法的基础。是基于字典的编码器。LZ77 算法的JS实现 - 网页制作 - 蓝色理想
您的位置：　 &
& LZ77 算法的JS实现
　LZ77 算法的JS实现
作者：　时间： 　文档类型：原创　来自：
JS操作二进制很麻烦，而且一直没有一个好的无损压缩工具来实现纯文本的压缩。
所以钻研了一段时间的gzip，后来发现还是仅用 LZ77 比较容易实现，gzip中的 haffman 压缩部分对于JS来说太难搞了。
代码如下，注释的非常完整，所以就不多说了，有兴趣的可以仔细研究下：
运行代码框&html&
&title&LZ77&/title&
* { font-size:12 }
body { overflow: background-color: }
textarea { width:100%; height:240 overflow: }
#btn1 { width:100 }
window.onload =
function $(s){ return document.getElementById(s); }
function init()
$("txtS").focus();
$("btn1").onclick =
$("txtS").onkeydown = function ()
if (event.keyCode == 13 && event.ctrlKey)
function run()
var str = $("txtS").
$("txtS").value = "";
var lzc = new Lz77CompressDefer(str);
var t = new Date();
lzc.start(function (result)
$("txtR").value = Lz77SelfExtract(result);
var tc = new Date() -
$("txtS").value = eval($("txtR").value.substring(4));
var td = new Date() - t -
alert("压缩完毕\r\n压缩比："+($("txtR").value.length/str.length*100).toFixed(2)+"%\r\n压缩用时："+tc+"ms\r\n解压用时："+td+"ms\r\n校验："+(str==$("txtS").value?"OK":"failed"));
function showProgress(){
var p = lzc.status();
if (p & 1)
$("txtS").value = "压缩中 ... " + (p*100).toFixed(2) + "%";
setTimeout(showProgress, 300);
showProgress();
$("txtR").value = Lz77Compress(str);
var tc = new Date() -
$("txtS").value = Lz77Decompress($("txtR").value);
var td = new Date() - t -
alert($("txtR").value.length/$("txtS").value.length+":"+tc+":"+td+":"+(str==$("txtS").value));
* 以 LZ77 原理实现的JS文本压缩算法
* Author: Hutia
LZ77基本原理：
1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。
2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。
3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。
1. 将匹配串和不能匹配的单个字符分别编码、分别输出，输出匹配串时不同时输出后续字符。
本算法变种：
1. 采用出现概率很低的前导字符P来区分匹配串输出和非匹配串。对于匹配串，输出 ( P, off, len )，对于非匹配串，输出 c。
非匹配串中出现字符P时，输出PP来代替，以示和匹配串的区别。
因此匹配串的输出 ( off, len ) 结果中，不可以出现字符P，以免产生混淆。
本例中，取 (`) 作为前导字符。
2. 对于匹配串，输出为：
前导字符 (`) + 偏移量 (3位，92进制 = 778688) + 匹配长度 (2位，92进制 = 8464)
因此滑动窗大小为778688，最小的匹配长度为 7。
3. 本算法针对JS文件，为简化算法暂不考虑窗口滑动情况（JS文件通常不会大于700K）。对于文件大于778688字节的情况使用本算法会出错。将来可以实现滑动窗口或分段压缩。
4. 本例中为简化算法，将 off 与 len 转换为 92 进制的字符串，并且将低位放在左侧，高位放在右侧。
作者：Hutia
转载请注明出处
var NC = [], CN = [];
NC = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz~!@#$%^&*()-=[]\;',./_+{}|:\"&&?".split("");
for (var i=0; i&NC. i++) CN[NC[i]] =
function Lz77Compress(input)
/*LZ77压缩算法 - Hutia - JS版*/
/*变量声明*/
var p = 0; //扫描指针
var lp = 0; //链表查询指针
var len = input. //输入字符串的长度
var output = []; //输出
var index = ""; //索引
var head = []; //索引头信息
var prev = []; //位置链表
var match_off = 0; //匹配位置的偏移量
var match_len = 0; //发生匹配的长度
var last_match_off = 0; //上一次匹配位置的偏移量
var last_match_len = 0; //上一次发生匹配的长度
var j = 0; //循环变量
/*循环扫描*/
for (p=0; p& p++)
index = input.substring(p, p+7); //取当前字符开始的7个字符作为索引
/*链表维护*/
prev[p] = head[index]; //当前头位置进链表
head[index] = //保存现在位置进头信息
lp = //初始化链表查询指针
match_len = 0; //初始化匹配长度
match_off = 0; //初始化匹配位置
if (prev[lp]) //如果链表上存在上一个匹配
/*匹配查询*/
while (prev[lp]) //依次查看链表上的每个位置
lp = prev[lp]; //取出链表上的前一个位置到链表查询指针
for (j=1; j&8464 && lp+j&p; j++) //寻找此位置的最长匹配，匹配长度不能超过8464 (92进制的2个字节长度)，也不能超过当前指针位置
if (input.substring(lp, lp + j) != input.substring(p, p + j))
j--; //计算最长匹配
if (j & 7 && j & match_len) //如果此匹配比已发现的匹配长
match_len = //记录匹配长度
match_off = //记录匹配位置
/*匹配处理*/
if (match_len & 7) //如果找到了符合要求的匹配
if (last_match_len != 0 && last_match_len & match_len) //如果上次匹配存在，且长度没有这次匹配的长度大
/*懒惰模式*/
output_unmatch(input.charAt(p - 1)); //放弃上次匹配，将字符直接输出
last_match_off = match_ //记录此次的匹配位置
last_match_len = match_ //记录此次的匹配长度
else if (last_match_len != 0) //如果上次匹配存在，且长度比这次匹配的长度大
/*处理上次的懒惰模式*/
output_match(); //输出上次的匹配
else //如果上次匹配不存在
/*懒惰模式*/
last_match_off = match_ //记录此次的匹配位置
last_match_len = match_ //记录此次的匹配长度
else //如果找不到符合要求的匹配（例如匹配超出当前指针）
if (last_match_len != 0) //如果上次匹配存在
/*处理上次的懒惰模式*/
output_match(); //输出上次的匹配
output_unmatch(input.charAt(p)); //直接输出当前的字符
else //如果当前不存在匹配
if (last_match_len != 0) //如果之前发生了匹配
/*处理上次的懒惰模式*/
output_match(); //输出匹配
output_unmatch(input.charAt(p)); //直接输出当前的字符
} //循环扫描结束
/*边界处理*/
if (last_match_len != 0) //如果之前发生了匹配
/*处理上次的懒惰模式*/
output_match(); //输出匹配
return output.join("");
function output_match()
output.push("`"); //输出前缀符
output.push(N2C(last_match_off, 3)); //输出3字节偏移量
output.push(N2C(last_match_len, 2)); //输出2字节匹配长度
p += last_match_len - 2; //移动当前指针到匹配串的末尾（因为懒惰模式，此时 p 指向 last_match_off + 1 的位置，所以应 -2 ）
last_match_off = 0; //清空匹配位置
last_match_len = 0; //清空匹配长度
function output_unmatch(c)
output.push(c == "`" ? "``" : c); //输出未匹配的字符
function Lz77Decompress(input)
/*LZ77解压缩算法 - Hutia - JS版*/
/*变量声明*/
var p = 0; //扫描指针
var len = input. //输入字符串的长度
var output = []; //输出
var match_off = 0; //匹配位置的偏移量
var match_len = 0; //发生匹配的长度
/*循环扫描*/
for (p=0; p& p++)
if (input.charAt(p) == "`") //如果发现前缀标记
if (input.charAt(p + 1) == "`") //如果是转义前缀
output.push("`"); //直接输出字符 "`"
p++; //指针后移，跳过下一个字符
else //如果是压缩编码
match_off = C2N(input.substring(p+1, p+4)); //取出其 1-3 个字符，算出偏移量
match_len = C2N(input.substring(p+4, p+6)); //取出其 4-5 字符，算出匹配长度
output = [].concat(output.join("")); //整理输出内容
output.push(output[0].substring(match_off, match_off + match_len)); //自输出内容的相应偏移量位置取出编码所代表的字符串
p += 5; //指针后移，跳过下5个字符
else //如果没有发现前缀标记
output.push(input.charAt(p)); //直接输出相应的字符
return output.join("");
/*LZ77解压缩算法 - Hutia - JS / mini 版*/
hutia = function(s){var A="charAt",p=-1,l=s.length,o=[],m,a="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz~!@#$%^&*()-=[]\;',./_+{}|:\"&&?".split(""),_=[];while(++p&92)_[a[p]]=p;function $(c){var l=c.length,r=0,i=-1;while(++i&l)r+=_[c[A](i)]*Math.pow(92,i);}p=-1;while(++p&l){if(s[A](p)=="`"){if(s[A](p+1)=="`")p++,o.push("`");else{m=$(s.substring(p+1,p+4));o=[].concat(o.join(""));o.push(o[0].substring(m,m+$(s.substring(p+4,p+6))));p+=5;}}else o.push(s.charAt(p));}return o.join("");}
function Lz77SelfExtract(s)
return "eval(("+String(hutia)+")(\""+s.replace(/\\/g,"\\\\").replace(/\r/g,"\\r").replace(/\n/g,"\\n").replace(/\"/g,"\\\"")+"\"));";
function Lz77CompressDefer(input)
/*LZ77压缩算法 - Hutia - JS / Defer 版*/
/*变量声明*/
var p = 0; //扫描指针
var lp = 0; //链表查询指针
var len = input. //输入字符串的长度
var output = []; //输出
var index = ""; //索引
var head = []; //索引头信息
var prev = []; //位置链表
var match_off = 0; //匹配位置的偏移量
var match_len = 0; //发生匹配的长度
var last_match_off = 0; //上一次匹配位置的偏移量
var last_match_len = 0; //上一次发生匹配的长度
var j = 0; //循环变量
//回调函数
this.start = function(fn)
this.start = function(){}
callback =
this.status = function ()
return p /
function run()
var inner_i = 0;
/*循环扫描*/
for (; p& p++)
if (++inner_i & 400)
return setTimeout(run);
index = input.substring(p, p+7); //取当前字符开始的7个字符作为索引
/*链表维护*/
prev[p] = head[index]; //当前头位置进链表
head[index] = //保存现在位置进头信息
lp = //初始化链表查询指针
match_len = 0; //初始化匹配长度
match_off = 0; //初始化匹配位置
if (prev[lp]) //如果链表上存在上一个匹配
/*匹配查询*/
while (prev[lp]) //依次查看链表上的每个位置
lp = prev[lp]; //取出链表上的前一个位置到链表查询指针
for (j=1; j&8464 && lp+j&p; j++) //寻找此位置的最长匹配，匹配长度不能超过8464 (92进制的2个字节长度)，也不能超过当前指针位置
if (input.substring(lp, lp + j) != input.substring(p, p + j))
j--; //计算最长匹配
if (j & 7 && j & match_len) //如果此匹配比已发现的匹配长
match_len = //记录匹配长度
match_off = //记录匹配位置
/*匹配处理*/
if (match_len & 7) //如果找到了符合要求的匹配
if (last_match_len != 0 && last_match_len & match_len) //如果上次匹配存在，且长度没有这次匹配的长度大
/*懒惰模式*/
output_unmatch(input.charAt(p - 1)); //放弃上次匹配，将字符直接输出
last_match_off = match_ //记录此次的匹配位置
last_match_len = match_ //记录此次的匹配长度
else if (last_match_len != 0) //如果上次匹配存在，且长度比这次匹配的长度大
/*处理上次的懒惰模式*/
output_match(); //输出上次的匹配
else //如果上次匹配不存在
/*懒惰模式*/
last_match_off = match_ //记录此次的匹配位置
last_match_len = match_ //记录此次的匹配长度
else //如果找不到符合要求的匹配（例如匹配超出当前指针）
if (last_match_len != 0) //如果上次匹配存在
/*处理上次的懒惰模式*/
output_match(); //输出上次的匹配
output_unmatch(input.charAt(p)); //直接输出当前的字符
else //如果当前不存在匹配
if (last_match_len != 0) //如果之前发生了匹配
/*处理上次的懒惰模式*/
output_match(); //输出匹配
output_unmatch(input.charAt(p)); //直接输出当前的字符
} //循环扫描结束
/*边界处理*/
if (last_match_len != 0) //如果之前发生了匹配
/*处理上次的懒惰模式*/
output_match(); //输出匹配
/*回调输出*/
callback(output.join(""));
} //end of run
function output_match()
output.push("`"); //输出前缀符
output.push(N2C(last_match_off, 3)); //输出3字节偏移量
output.push(N2C(last_match_len, 2)); //输出2字节匹配长度
p += last_match_len - 2; //移动当前指针到匹配串的末尾（因为懒惰模式，此时 p 指向 last_match_off + 1 的位置，所以应 -2 ）
last_match_off = 0; //清空匹配位置
last_match_len = 0; //清空匹配长度
function output_unmatch(c)
output.push(c == "`" ? "``" : c); //输出未匹配的字符
function C2N(c) //将 92 进制字符串（高位在右）转换为 10 进制数字
var len = c.
var re = 0;
for (var i=0; i& i++)
re += CN[c.charAt(i)] * Math.pow(92, i);
function N2C(n, len) //将 10 进制数字转换为指定长度的 92 进制字符串，高位在右
var re = [];
for (var i=0; i& i++)
re[i] = NC[n % 92];
n = n / 92 | 0;
return re.join("");
&textarea id="txtS"&&/textarea&
&textarea id="txtR"&&/textarea&
&input type="button" value="Go" id="btn1"&
&/html& [Ctrl+A 全部选择 提示：你可先修改部分代码，再按运行]
经典论坛交流：
本文链接：　
责任编辑：
◎进入论坛、版块参加讨论，我还想。
蓝色理想版权申明：除部分特别声明不要转载，或者授权我站独家播发的文章外，大家可以自由转载我站点的原创文章，但原作者和来自我站的链接必须保留（非我站原创的，按照原来自一节，自行链接）。文章版权归我站和作者共有。
转载要求：转载之图片、文件，链接请不要盗链到本站，且不准打上各自站点的水印，亦不能抹去我站点水印。
特别注意：本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有，文章若有侵犯作者版权，请与我们，我们将立即删除修改。
说明：输入正确的用户名和密码才能参与评论。如果您不是本站会员，你可以 为本站会员。
注意：文章中的链接、内容等需要修改的错误，请用，以利文档及时修改。
注意：请不要在评论中含与内容无关的广告链接，违者封ID
请您注意：?不良评论请用，以利管理员及时删除。?尊重网上道德，遵守中华人民共和国的各项有关法律法规?承担一切因您的行为而直接或间接导致的民事或刑事法律责任?本站评论管理人员有权保留或删除其管辖评论中的任意内容
?您在本站发表的作品，本站有权在网站内转载或引用 ?参与本评论即表明您已经阅读并接受上述条款
专业书推荐
&1999-. 版权所有