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 演算法