lz4是目前綜合來看效率最高的壓縮演算法，更加側重壓縮解壓速度，壓縮比並不是第一。在當前的安卓和蘋果操作系統中，內存壓縮技術就使用的是lz4演算法，及時壓縮手機內存以帶來更多的內存空間。本質上是時間換空間。
lz4壓縮演算法其實很簡單，舉個壓縮的栗子
其中兩個括弧內的便代表的是壓縮時檢測到的重復項，(5,4) 代表向前5個byte，匹配到的內容長度有4，即"bcde"是一個重復。當然也可以說"cde"是個重復項，但是根據演算法實現的輸入流掃描順序，我們取到的是第一個匹配到的，並且長度最長的作為匹配。
壓縮後的數據是下面的格式
其他情況也可能有連續的匹配：
Literals 指沒有重復、首次出現的位元組流，即不可壓縮的部分
Match 指重復項，可以壓縮的部分
Token 記錄literal長度，match長度。作為解壓時候memcpy的參數
可以想到，如果重復項越多或者越長，壓縮率就會越高。上述例子中"bcde"在壓縮後，用(5,4)表示，即從4個bytes壓縮成了3個bytes來表示，其中offset 2bytes, match length 1byte，能節省1個byte。
大致流程，壓縮過程以至少4個bytes為掃描窗口查找匹配，每次移動1byte進行掃描，遇到重復的就進行壓縮。
由於offset用2bytes表示，只能查找到到2^16(64kb)距離的匹配，對於壓縮4Kb的內核頁，只需要用到12位。
掃描的步長1byte是可以調整的，即對應LZ4_compress_fast機制，步長變長可以提高壓縮解壓速度，減少壓縮率。
我們來看下 apple的lz4實現
壓縮理解了其實解壓也很簡單
根據解壓前的數據流，取出token內的length，literals直接復制到輸出，即memcpy(src,dst,length)
遇到match，在從前面已經拷貝的literals復制到後面即可
⑵ 演算法解析：哈夫曼（huffman）壓縮演算法
本篇將介紹 哈夫曼壓縮演算法（Huffman compression）
眾所周知，計算機存儲數據時，實際上存儲的是一堆0和1（二進制）。
如果我們存儲一段字元：ABRACADABRA!
那麼計算機會把它們逐一翻譯成二進制，如A：01000001；B: 01000010; !: 00001010.
每個字元佔8個bits, 這一整段字元則至少佔12*8=96 bits。
但如果我們用一些特殊的值來代表這些字元，如：
圖中，0代表A; 1111代表B；等等。此時，存儲這段字元只需30bits，比96bits小多了，達到了壓縮的目的。
我們需要這么一個表格來把原數據翻譯成特別的、占空間較少的數據。同時，我們也可以用這個表格，把特別的數據還原成原數據。
首先，為了避免翻譯歧義，這個表格需滿足一個條件： 任何一個字元用的值都不能是其它字元的前綴 。
我們舉個反例：A: 0; B: 01;這里，A的值是B的值的前綴。如果壓縮後的數據為01xxxxxx,x為0或者1，那麼這個數據應該翻譯成A1xxxxxx, 還是Bxxxxxxx?這樣就會造成歧義。
然後，不同的表格會有不同的壓縮效果，如：
這個表格的壓縮效果更好。
那麼我們如何找到 最好的表格 呢？這個我們稍後再講。
為了方便閱讀，這個表格是可以寫成一棵樹的：
這棵樹的節點左邊是0，右邊是1。任何含有字元的節點都沒有非空子節點。（即上文提及的前綴問題。）
這棵樹是在壓縮的過程中建成的，這個表格是在樹形成後建成的。用這個表格，我們可以很簡單地把一段字元變成壓縮後的數據，如：
原數據：ABRACADABRA!
表格如上圖。
令壓縮後的數據為S；
第一個字元是A，根據表格，A：11，故S=11;
第二個字元是B，根據表格，B：00，故S=1100;
第三個字元是R，根據表格，R：011，故S=1100011;
如此類推，讀完所有字元為止。
壓縮搞定了，那解壓呢？很簡單，跟著這棵樹讀就行了：
壓縮後的數據S=11000111101011100110001111101
記住，讀到1時，往右走，讀到0時，往左走。
令解壓後的字元串為D；
從根節點出發，第一個數是1，往右走：
第二個數是1，往右走：
讀到有字元的節點，返回此字元，加到字元串D里。D:A;
返回根節點，繼續讀。
第三個數是0，往左走：
第四個數是0，往左走：
讀到有字元的節點，返回此字元，加到字元串D里。D:AB;
返回根節點，繼續讀。
第五個數是0，往左走：
第六個數是1，往右走：
第七個數是1，往右走：
讀到有字元的節點，返回此字元，加到字元串D里。D:ABR;
返回根節點，繼續讀。
如此類推，直到讀完所有壓縮後的數據S為止。
壓縮與解壓都搞定了之後 我們需要先把原數據讀一遍，並把每個字元出現的次數記錄下來。如：
ABRACADABRA!中，A出現了5次;B出現了2次;C出現了1次;D出現了1次;R出現了2次;!出現了1次。
理論上，出現頻率越高的字元，我們給它一個佔用空間越小的值，這樣，我們就可以有最佳的壓縮率
由於哈夫曼壓縮演算法這塊涉及內容較多 ，文章篇幅很長；全文全方面講解了Compose布局的各方面知識。更多Android前言技術進階，我自薦一套《 完整的Android的資料，以及一些視頻課講解 》 現在私信發送「進階」或者「筆記」即可免費獲取
最後我想說：
對於程序員來說，要學習的知識內容、技術有太多太多，要想不被環境淘汰就只有不斷提升自己，從來都是我們去適應環境，而不是環境來適應我們
技術是無止境的，你需要對自己提交的每一行代碼、使用的每一個工具負責，不斷挖掘其底層原理，才能使自己的技術升華到更高的層面
Android 架構師之路還很漫長，與君共勉
⑶ 求C++簡單文件壓縮程序，用基本演算法實現
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
void main()
{
ifstream infile("c:\\1.txt");//自己改文件名
ofstream outfile("c:\\2.txt");
char cCurrent,cPre;
int iCount=0;
cPre=-1;
while(infile>>cCurrent)
{
if(cCurrent=='\n') continue;
if(cPre==-1) cPre=cCurrent;
if(cPre==cCurrent)
{
iCount++;
}
else
{
if(cPre>='0'&&cPre<='9')
outfile<<iCount<<'*'<<cPre<<' ';
else
outfile<<iCount<<cPre<<' ';
cPre=cCurrent;
iCount=1;
}
}
if(cPre>='0'&&cPre<='9')
outfile<<iCount<<'*'<<cPre<<' ';
else
outfile<<iCount<<cPre<<' ';
infile.close();
outfile.close();
}
⑷ 二進制壓縮演算法有哪些
二進制數據壓縮演算法二進制是計算技術中廣泛採用的一種數制。二進制數據是用0和1兩個數碼來表示的數。它的基數為2，進位規則是「逢二進一」，借位規則是「借一當二」，由18世紀德國數理哲學大師萊布尼茲發現。當前的計算機系統使用的基本上是二進制系統，數據在計算機中主要是以補碼的形式存儲的。計算機中的二進制則是一個非常微小的開關，用「開」來表示1，「關」來表示0。
20世紀被稱作第三次科技革命的重要標志之一的計算機的發明與應用，因為數字計算機只能識別和處理由『0』。『1』符號串組成的代碼。其運算模式正是二進制。19世紀愛爾蘭邏輯學家喬治布爾對邏輯命題的思考過程轉化為對符號「0『』。『』1『』的某種代數演算，二進制是逢2進位的進位制。0、1是基本算符。因為它只使用0、1兩個數字元號，非常簡單方便，易於用電子方式實現。
二進制壓縮
在編程時遇到每個數據只有兩種狀態，且 dfs 或者 bfs 時遍歷時間復雜度高時，可以採用二進制壓縮數據，尤其是二維數組。LZFSE
1，zlib和gzip都對deflate進行了封裝，比deflate多了數據頭和尾
1，蘋果開源了新的無損壓縮演算法 LZFSE ，該演算法是去年在iOS 9和OS X 10.10中 引入 的。按照蘋果公司的說法，LZFE的壓縮增益和ZLib level 5相同，但速度要快2~3倍，能源效率也更高。
LZFSE基於Lempel-Ziv，並使用了 有限狀態熵編碼，後者基於Jarek Duda在
非對稱數字系統（ANS）方面所做的熵編碼工作。簡單地講，ANS旨在「終結速度和比率的平衡」，既可以用於精確編碼，又可以用於快速編碼，並且具有數據加密功能。使用ANS代替更為傳統的
Huffman和 算術編碼方法的壓縮庫 越來越多，LZFSE就位列其中。
顯然，LZFSE的目標不是成為最好或最快的演算法。事實上，蘋果公司指出，
LZ4的壓縮速度比LZFSE快，而 LZMA提供了更高的壓縮率，但代價是比Apple
SDK提供的其他選項要慢一個數量級。當壓縮率和速度幾乎同等重要，而你又希望降低能源效率時，LZFSE是蘋果推薦的選項。
GitHub上提供了LZFSE的參考實現。在MacOS上構建和運行一樣簡單：
$ xcodebuild install DSTROOT=/tmp/lzfse.dst
如果希望針對當前的iOS設備構建LZFSE，可以執行：
xcodebuild -configuration 「Release」 -arch armv7 install DSTROOT=/tmp/lzfse.dst
除了 API文檔之外，蘋果去年還提供了一個 示例項目，展示如何使用LZFSE 進行塊和流壓縮，這是一個實用的LZFSE入門資源。
LZFSE是在谷歌 brotli之後發布的，後者在去年開源。與LZFSE相比，brotli 似乎是針對一個不同的應用場景進行了優化，比如壓縮靜態Web資產和Android APK，在這些情況下，壓縮率是最重要的。
⑸ 數據流壓縮原理和數據壓縮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在函數調用之前千萬不能為零。應用程序可以隨時消耗被壓縮的輸出數據
⑹ 壓縮采樣的演算法是怎麼描述的
ADPCM(Adaptive
Differential
Pulse
Code
Molation)，是一種針對
16bits(
或8bits或者更高)
聲音波形數據的一種有損壓縮演算法,它將聲音流中每次采樣的
16bit
數據以
4bit
存儲,所以壓縮比
1:4.
而且壓縮/解壓縮演算法非常簡單,所以是一種低空間消耗，高質量高效率聲音獲得的好途徑。保存聲音的數據文件後綴名為
.AUD
的大多用ADPCM
壓縮。
ADPCM
主要是針對連續的波形數據的，保存的是波形的變化情況，以達到描述整個波形的目的，由於它的編碼和解碼的過程卻很簡潔，列在後面，相信大家能夠看懂。
8bits采樣的聲音人耳是可以勉強接受的，而
16bit
采樣的聲音可以算是高音質了。ADPCM
演算法卻可以將每次采樣得到的
16bit
數據壓縮到
4bit
。需要注意的是，如果要壓縮/解壓縮得是立體聲信號，采樣時，聲音信號是放在一起的，需要將兩個聲道分別處理。
PCM是脈沖編碼調制的意思。AD是自適應增量的意思。
嚴格說來，ADPCM不是壓縮方法。他的主要思想是，用差值替代絕對值。舉個例子，全班同學平均身高175CM：其中，我的身高170CM，這就是PCM方法；我的身高和平均值相比為-5cm，這就是DPCM，我的身高跟前一位同學相比為-10CM，前一位同學有多高我不知道他多高，你問他，這是ADPCM。比方不是太准確，大概就是這個意思。
在大多數情況下，數據值與平均值相差不大，所以用差值替代絕對值可以節省空間。
很高興回答樓主的問題
如有錯誤請見諒
⑺ 壓縮文件的演算法
主要是看文件格式，像rmvb等格式都是已經壓縮過的了，再壓空間不大，還有就是獨立格式文件，一般系統無法識別，並且文件名比較怪的都是別人獨立開發的格式，這些也沒什麼壓縮空間，演算法你要看那格式種了，系統常見的文件壓縮演算法都是
ZIP文件的總體格式
分文件頭信息+文件壓縮數據
中心目錄+中心目錄記錄結束符
1.分文件頭信息:
位元組數 描述
4 分文件頭信息標志(0x04034b50)
2 解壓縮所需版本
2 通用比特標志位(置比特0位=加密;置比特1位=使用壓
縮方式6,並使用8k變化目錄,否則使用4k變化目錄;置比特2位=使用壓
縮方式6,並使用3個ShannonFano樹對變化目錄輸出編碼,否則使用2個
ShannonFano樹對變化目錄輸出編碼,其它比特位未用)
2 壓縮方式(0=不壓縮,1=縮小,2=以壓縮因素1縮小,3=以
壓縮因素2縮小,4=以壓縮因素3縮小,5=以壓縮因素4縮小,6=自展)
2 文件最後修改時間
2 文件最後修改日期
4 32位校驗碼
4 壓縮文件大小
4 未壓縮文件大小
2 文件名長
2 擴展段長
? 文件名(不定長)
? 擴展段(不定長)
2.中心目錄結構
文件頭信息...中心目錄記錄結束符
文件頭:
位元組數 描述
4 中心文件頭信息標志(0x02014b50)
2 主機操作系統(高位位元組表示主機操作系統,低位字
節表示ZIP壓縮軟體版本號,其值除以10表示主版本號,其值模10表示
次版本號。0=MS-DOS,OS/2 FAT文件系統,1=Ami ga,2=VMS,3=Unix及
變種,4=VM/CMS,5=AtariST,6=OS/2 HPFS,7=Macintosh,8=Z-System,9
=C P/M,10-255未用)
2 解壓縮所需版本
2 通用比特標志
2 壓縮方式
2 文件最後修改時間(用標準的MS-DOS時間日 期格式
編碼)
2 文件最後修改日期
4 32位校驗碼(使用David Schwaderer的CRC-32演算法產
生)
4 壓縮文件大小
4 未壓縮文件大小
2 文件名長
2 擴展段長
2 文件注釋長(分別為文件名長,擴展段,注釋 段,小於
64K)
2 磁碟起始號(本文件在磁碟中的起始號)
2 內部文件屬性(最低位若置1,表示為ASC文本,否則為
二進制數據,其它位未用)
4 外部文件屬性(依賴於主機操作系統)
4 分文件頭相對位移
? 文件名(不定長)
? 擴展段(不定長,用於未來擴展,低版本為0長)
? 文件注釋(不定長)
3.中心目錄記錄結束符
位元組數 描述
4 中心目錄標記結束符(0x06054b50)
2 磁碟號(其中包括中心目錄結束記錄)
2 磁碟中心目錄起始號
2 磁碟中心目錄入口總數
2 中心目錄入口總數(ZIP文件中的文件總數)
2 整個中心目錄大小
4 關於起始磁碟號的中心目錄初始偏移
2 ZIP文件注釋長度
? ZIP文件注釋(不定長)
加密方法
PKZIP中使用的加密方法由Roger Schlafly提供。ZIP文件在解壓
縮前必須先解密。每個加密文件具有一個12位元組的加密文件頭擴展信
息,存儲於數據區的起始位置,加密前先設置一個起始值,然後被三個3
2位的密鑰加密。密鑰被使用者提供的口令初始化。12個位元組加密之
後,由PKZIP的偽隨機數產生方法,結合PKZIP中使用CRC-32演算法對密鑰
進行更新。
具體實施分為三步:
1.用口令對三個32位密鑰初始化。
K(0)=305419896,K(1)=591751049,K(2)=878082192
循環 for i=0 to length(password)-1
調用更新密鑰函數 update_keys(password(i))
結束循環(循環口令長度次)
其中更新密鑰函數為:
update_keys(char):
Key(0)=crc32(key(0),char)
Key(1)=Key(1)+(Key(0)& 000000ffH)
Key(1)=Key(1)*134775813+1
Key(2)=crc32(Key(2),Key(1)〉〉24)
end update_keys
CRC32函數中,給定一個4位元組的CRC值和一個字元,返回一個由CRC
-32演算法更新的CRC。具體為:
crc32(c,b)=crc32tab[(c^b)&0xff]^(c>>8),crc32tab[256]的值
為固定的256個4位元組數。
2.讀取並加密12位元組的加密頭,再次對密鑰進行初始化。
將12個位元組的加密頭讀入緩沖區buffer(0)至buffer(11),循環fo
r i=0 to 11
C=buffer(i)^decrypt_byte()
update_keys(C)
buffer(i)=C
結束循環(循環12次)
其中的decrypt_byte()函數為:
unsigned char decrypt_byte()
local unsigned short temp
temp=Key(2)¦2
decrypt_byte=((temp*(temp^1))>>8)&0xff
end decrypt_byte
該步結束後,緩沖區中最後的二個位元組buffer(10)和buffer(11)
將成為加密文件校驗碼的二個最高位(按低至高順序存放)。對ZIP加
密文件進行解壓縮前,PKUNZIP軟體將使用者提供的口令按上述二個步
驟進行處理,得到的結果與校驗碼的二個高位位元組進行比較,只有當提
供了正確的口令時,結果一致,才能進行後續的解壓縮過程,否則,PKZI
P報告錯誤信息,程序自動結束。
3.讀取壓縮的數據流並以加密密鑰對其進行加密。
壓縮數據流按下述過程加密:
循環 直至數據流結束
C=數據流的一個位元組
temp=C^decrypt_byte()
update_keys(temp)
輸出temp
結束循環
⑻ 常用的數據壓縮演算法有哪些
基本的分為兩大類：有損和無損。
有損壓縮：主要是一些量化演算法，比如a率，u率，lloyds最優量化。
無損壓縮：主要是一些編碼演算法，比如子帶編碼，差分編碼，哈夫曼編碼等。
另外時頻變換雖然沒壓縮效果，但是是很好的壓縮工具，比如fft，dct等。
最後就是壓縮感知稀疏重建等。