lz77压缩

‘壹’ 求7z算法的原理,详细

7z算法的原理：

简单地说也就是把文件中的重复数据用更简洁的方法表示，例如一个文件中有1000个字母A，那么这将占用1KB的数据空间，如果用压缩算法就可以用1000A来表示，那么它只需要5个字节的数据空间，压缩比达到了200倍。

7z简介：

7z 是一种主流高效的压缩格式，它拥有极高的压缩比。在计算机科学中，7z是一种可以使用多种压缩算法进行数据压缩的档案格式。该格式最初被7-Zip实现并采用，但是这种档案格式是公有的，并且7-Zip软件本身亦在GNU宽通用公共许可证 (GNU LGPL)协议下开放源代码。目前LZMA软件开发工具包的最新版本为V9.34。7z格式的MIME类型为application/x-7z-compressed。

‘贰’ 数据流压缩原理和数据压缩Zlib的实现

压缩的本质就是去冗余，去除信息冗余，使用最短的编码保存最完整的数据信息。所以对于不同的场景，压缩采用的算法也因时制宜，比如视频和图片可以采用有损压缩，而文本数据采用无损压缩。压缩率又取决于信息的冗余度，也就是内容中重复的比例。那些均匀分布的随机字符串，压缩率会降到最低，即香农限

deflate是zip文件的默认算法。它更是一种数据流压缩算法。

LZ77压缩算法采用字典的方式进行压缩，是一种简单但是很高效的数据压缩算法。其方式就是把数据中一些可以组织成短语的字符加入字典。维护三个概念： 短语字典、滑动窗口、向前缓冲区

压缩的逆过程，通过解码标记和保持滑动窗口中的符号来更新解压数据。当解码字符被标记:将标记编码成字符拷贝到滑动窗口中，一步一步直到全部翻译完成

在流式传输中，不定长编码数据的解码想要保持唯一性，必须满足唯一可以码的条件。而异前缀码就是一种唯一可译码的候选，当然这样会增加编码的长度，却可以简化解码。

huffman编码是一种基于概率分布的贪心策略最优前缀码。huffman编码可以有效的压缩数据，压缩率取决于数据本身的信息冗余度

计算数据中各符号出现的概率，根据概率从小到大，从下往上反向构建构造码树，这样最终得到的编码的平均长度是最短的。同时也是唯一可译的

解读：在一开始，每一个字符已经按照出现概率的大小排好顺序，在后续的步骤中，每一次将概率最低的两棵树合并，然后用合并后的结果再次排序（为了找出最小的两棵树）。在gzip源码中并没有专门去排序，而是使用专门的数据结构（比如最小堆或者红黑树）。

使用优先队列实现huffman树，最后基于Huffman树最终实现文件压缩。
具体步骤：

gzip = gzip 头 + deflate 编码的实际内容 + gzip 尾

zlib = zlib 头 + deflate 编码的实际内容 + zlib 尾

压缩之前：初始化各种输入输出缓冲区；
压缩：我们可以不断往这些缓冲区中填充内容，然后由deflate函数进行压缩或者indeflate函数进行解压

总结：在调用deflate函数之前，应用程序必须保证至少一个动作被执行（avail_in或者avail_out被设置），用提供更多数据或者消耗更多的数据的方式。avail_out在函数调用之前千万不能为零。应用程序可以随时消耗被压缩的输出数据

‘叁’ PNG图片是无损压缩的吗为什么还有大小分别

PNG图片是有压缩的。

PNG图片主要有三个类型，分别为 PNG 8/ PNG 24 / PNG 32。

PNG8：PNG 8中的8，其实指的是8bits（一个字节），相当于用2^8（2的8次方）大小来存储一张图片的颜色种类，2^8等于256，也就是说PNG 8能存储256种颜色，一张图片如果颜色种类很少，将它设置成PNG 8得图片类型是非常适合的。

PNG24：PNG 24中的24，相当于3乘以8 等于 24，就是用三个8bits分别去表示 R（红）、G（绿）、B（蓝）。

R(0~255)，G(0~255)，B(0~255)，可以表达256乘以256乘以256=16777216种颜色的图片，这样PNG 24就能比PNG 8表示色彩更丰富的图片。但是所占用的空间相对就更大了。

PNG32：PNG 32中的32，相当于PNG 24 加上 8bits的透明颜色通道，就相当于R（红）、G（绿）、B（蓝）、A（透明）。

R(0~255),G(0~255),B(0~255),A(0~255)。比PNG 24多了一个A（透明），也就是说PNG 32能表示跟PNG 24一样多的色彩，并且还支持256种透明的颜色，能表示更加丰富的图片颜色类型。

(3)lz77压缩扩展阅读

PNG图片的压缩，分两个阶段：

预解析（Prediction）：这个阶段就是对png图片进行一个预处理，处理后让它更方便后续的压缩。比如就是一个女神，在化妆前，会先打底，先涂乳液和精华，方便后续上妆、美白、眼影、打光等等。

压缩（Compression）：执行Deflate压缩，该算法结合了 LZ77 算法和 Huffman 算法对图片进行编码。

压缩阶段会将预处理阶段得到的结果进行Deflate压缩，它由 Huffman 编码 和 LZ77压缩构成。

如前面所说，Deflate压缩会标记图片所有的重复数据，并记录数据特征和结构，会得到一个压缩比最大的png图片 编码数据。

Deflate是一种压缩数据流的算法. 任何需要流式压缩的地方都可以用。

还有就是我们前面说过，一个png图片，是由很多的数据块构成的，但是数据块里面的一些信息其实是没有用的，比如用Photoshop保存了一张png图片。

图片里就会有一个区块记录“这张图片是由photshop创建的”，很多类似这些信息都是无用的，如果用photoshop的“导出web格式”就能去掉这些无用信息。

‘肆’ ps存png压缩无/快最小/慢选什么

1、如果对图片质量要求比较高，就选择，压缩无/快。

2、如果对图片质量要求不太高，就选择，最小/慢。

两者最主要的区别是图片的大小和质量。

(4)lz77压缩扩展阅读：

PNG格式的存储优势

体积小网络通讯中因受带宽制约，在保证图片清晰、逼真的前提下，网页中不可能大范围的使用文件较大的bmp格式文件。

无损压缩PNG文件采用LZ77算法的派生算法进行压缩，其结果是获得高的压缩比，不损失数据。它利用特殊的编码方法标记重复出现的数据，因而对图像的颜色没有影响，也不可能产生颜色的损失，这样就可以重复保存而不降低图像质量。

索引彩色模式PNG-8格式与GIF图像类似，同样采用8位调色板将RGB彩色图像转换为索引彩色图像。图像中保存的不再是各个像素的彩色信息，而是从图像中挑选出来的具有代表性的颜色编号，每一编号对应一种颜色，图像的数据量也因此减少，这对彩色图像的传播非常有利。

更优化的网络传输显示PNG图像在浏览器上采用流式浏览，即使经过交错处理的图像会在完全下载之前提供浏览者一个基本的图像内容，然后再逐渐清晰起来。它允许连续读出和写入图像数据，这个特性很适合于在通信过程中显示和生成图像。

支持透明效果PNG可以为原图像定义256个透明层次，使得彩色图像的边缘能与任何背景平滑地融合，从而彻底地消除锯齿边缘。这种功能是GIF和JPEG没有的。

PNG同时还支持真彩和灰度级图像的Alpha通道透明度。最高支持24位真彩色图像以及8位灰度图像。支持Alpha通道的透明/半透明特性。支持图像亮度的Gamma校准信息。支持存储附加文本信息，以保留图像名称、作者、版权、创作时间、注释等信息。

PNG格式有8位、24位、32位三种形式，其中8位PNG支持两种不同的透明形式（索引透明和alpha透明），24位PNG不支持透明，32位PNG在24位基础上增加了8位透明通道，因此可展现256级透明程度。

PNG8和PNG24后面的数字则是代表这种PNG格式最多可以索引和存储的颜色值。8代表2的8次方也就是256色，而24则代表2的24次方大概有1600多万色。

参考资料来源：网络-png

‘伍’ LZ77和LZW编码是同一个东西吗

不是，但它们有关系。
Ziv和Lempel于1977年发表的算法被后人称为LZ77算法。
1978年，二人又发表了续篇，被命名为LZ78的压缩算法。
1984年，Welch这个人研究了LZ78算法的变种，因为是W在Z和L两人之后研究出来的，因此叫LZW算法。

LZW申请了专利，但专利在2003年过期了。
现在的几乎所有压缩算法，都是从LZ77发展而来的。
而所谓LZ77编码和LZW编码，就是利用各自的压缩算法，对原字符序列压缩后产生的新的编码。

‘陆’ 需要 用 javaScript 解压 通过lz77压缩的字符串

我看lz77要操纵字节，javascript现在没这个能力，所以估计实现不了lz77解压吧，你是否要考虑下使用不压缩的字符串呢

‘柒’ 用python编写一个字符串压缩程序(要求为自适应模型替代法)

你好，并掘下面是LZ777自适应压缩算法的一个简单实现，你可以看看
import math
from bitarray import bitarray
class LZ77Compressor:
"""
A simplified implementation of the LZ77 Compression Algorithm
"""
MAX_WINDOW_SIZE = 400
def __init__(self, window_size=20):
self.window_size = min(window_size, self.MAX_WINDOW_SIZE)
self.lookahead_buffer_size = 15 # length of match is at most 4 bits
def compress(self, input_file_path, output_file_path=None, verbose=False):
"""
Given the path of an input file, its content is compressed by applying a simple
LZ77 compression algorithm.
The compressed format is:
0 bit followed by 8 bits (1 byte character) when there are no previous matches
within window
1 bit followed by 12 bits pointer (distance to the start of the match from the
current position) and 4 bits (length of the match)

If a path to the output file is provided, the compressed data is written into
a binary file. Otherwise, it is returned as a bitarray
if verbose is enabled, the compression description is printed to standard output
"""
data = None
i = 0
output_buffer = bitarray(endian='big'指唤)
# read the input file
try:
with open(input_file_path, 'rb') as input_file:
data = input_file.read()
except IOError:
print 'Could not open input file ...'
raise
while i < len(data):
#print i
match = self.findLongestMatch(data, i)
if match:
# Add 1 bit flag, followed by 12 bit for distance, and 4 bit for the length
# of the match
(bestMatchDistance, bestMatchLength) = match
output_buffer.append(True)
output_buffer.frombytes(chr(bestMatchDistance >> 4))
output_buffer.frombytes(chr(((bestMatchDistance & 0xf) << 4) | bestMatchLength))
if verbose:
print "<1, %i, %i>"绝逗核 % (bestMatchDistance, bestMatchLength),
i += bestMatchLength
else:
# No useful match was found. Add 0 bit flag, followed by 8 bit for the character
output_buffer.append(False)
output_buffer.frombytes(data[i])

if verbose:
print "<0, %s>" % data[i],
i += 1
# fill the buffer with zeros if the number of bits is not a multiple of 8
output_buffer.fill()
# write the compressed data into a binary file if a path is provided
if output_file_path:
try:
with open(output_file_path, 'wb') as output_file:
output_file.write(output_buffer.tobytes())
print "File was compressed successfully and saved to output path ..."
return None
except IOError:
print 'Could not write to output file path. Please check if the path is correct ...'
raise
# an output file path was not provided, return the compressed data
return output_buffer

def decompress(self, input_file_path, output_file_path=None):
"""
Given a string of the compressed file path, the data is decompressed back to its
original form, and written into the output file path if provided. If no output
file path is provided, the decompressed data is returned as a string
"""
data = bitarray(endian='big')
output_buffer = []
# read the input file
try:
with open(input_file_path, 'rb') as input_file:
data.fromfile(input_file)
except IOError:
print 'Could not open input file ...'
raise
while len(data) >= 9:
flag = data.pop(0)
if not flag:
byte = data[0:8].tobytes()
output_buffer.append(byte)
del data[0:8]
else:
byte1 = ord(data[0:8].tobytes())
byte2 = ord(data[8:16].tobytes())
del data[0:16]
distance = (byte1 << 4) | (byte2 >> 4)
length = (byte2 & 0xf)
for i in range(length):
output_buffer.append(output_buffer[-distance])
out_data = ''.join(output_buffer)
if output_file_path:
try:
with open(output_file_path, 'wb') as output_file:
output_file.write(out_data)
print 'File was decompressed successfully and saved to output path ...'
return None
except IOError:
print 'Could not write to output file path. Please check if the path is correct ...'
raise
return out_data

def findLongestMatch(self, data, current_position):
"""
Finds the longest match to a substring starting at the current_position
in the lookahead buffer from the history window
"""
end_of_buffer = min(current_position + self.lookahead_buffer_size, len(data) + 1)
best_match_distance = -1
best_match_length = -1
# Optimization: Only consider substrings of length 2 and greater, and just
# output any substring of length 1 (8 bits uncompressed is better than 13 bits
# for the flag, distance, and length)
for j in range(current_position + 2, end_of_buffer):
start_index = max(0, current_position - self.window_size)
substring = data[current_position:j]
for i in range(start_index, current_position):
repetitions = len(substring) / (current_position - i)
last = len(substring) % (current_position - i)
matched_string = data[i:current_position] * repetitions + data[i:i+last]
if matched_string == substring and len(substring) > best_match_length:
best_match_distance = current_position - i
best_match_length = len(substring)
if best_match_distance > 0 and best_match_length > 0:
return (best_match_distance, best_match_length)
return None

‘捌’ 7Z的压缩算法

7z 已公开了结构编辑功能，所以它可以支持任何一种新的压缩算法。
到目前为止，下列压缩算法已被整合到了 7z 中： 7z压缩格式的算法压缩算法 备注 LZMA 改良与优化后的 LZ77 算法 LZMA2 改良的 LZMA 算法 PPMD 基于 Dmitry Shkarin 的 PPMdH 算法 BCJ 32 位 x86 可执行文件转换程序 BCJ2 32 位 x86 可执行文件转换程序 BZip2 标准 BWT 算法 Deflate 标准 LZ77-based 算法