LZW壓縮演算法的基本概念：LZW壓縮有三個重要的對象：數據流(CharStream)、編碼流(CodeStream)和編譯表(String Table)。在編碼時，數據流是輸入對象（文本文件的據序列），編碼流就是輸出對象（經過壓縮運算的編碼數據）；在解碼時，編碼流則是輸入對象，數據流是輸出對象；而編譯表是在編碼和解碼時都須要用藉助的對象。字元(Character)：最基礎的數據元素，在文本文件中就是一個位元組，在光柵數據中就是一個像素的顏色在指定的顏色列表中的索引值；字元串(String)：由幾個連續的字元組成； 前綴(Prefix)：也是一個字元串，不過通常用在另一個字元的前面，而且它的長度可以為0；根(Root)：一個長度的字元串；編碼(Code)：一個數字，按照固定長度（編碼長度）從編碼流中取出，編譯表的映射值；圖案：一個字元串，按不定長度從數據流中讀出,映射到編譯表條目. LZW壓縮演算法的基本原理：提取原始文本文件數據中的不同字元，基於這些字元創建一個編譯表，然後用編譯表中的字元的索引來替代原始文本文件數據中的相應字元，減少原始數據大小。看起來和調色板圖象的實現原理差不多，但是應該注意到的是，我們這里的編譯表不是事先創建好的，而是根據原始文件數據動態創建的，解碼時還要從已編碼的數據中還原出原來的編譯表.
B. 如何把16位數據壓縮為8位
我給你講一下壓縮的基本原理吧：
所謂數據壓縮，實際上指的是把相似的數據用另外一種方式表達。舉個例子："aaaaaaaaaa",如果直接儲存，要佔10個位元組，但是通過觀察發現，其實這個字元串里全是"a",那麼就可以這樣儲存："10a"，這樣就減短了存儲的長度，達到了所謂的「壓縮」的要求。再舉個例子，"aaaaaaaaaab","aaaaaaaaaac","aaaaaaaaaad","aaaaaaaaaae"，如果直接儲存，那麼就要佔44個位元組，但是通過觀察我們發現，其實這四個字元串的前10個字母都是a，那麼就可以這樣儲存"10ab","10ac","10ad","10ae"。
當然，做這種變換是需要額外的空間來解釋10a到底是什麼的意思的，不然就會混淆。
所以，單純的把一個16位數壓縮成8位的演算法是不存在的，一定要根據上下文來發掘規律。
常見的壓縮演算法有：LZW，LZ77等，他們的思想和我上面說的是類似的。
C. 數據壓縮比計算方法
數據壓縮比計算方法
舉例：65536=2的16次方，所以要16位二進制存儲，就是2個位元組即2B，像點1024*1024，則一張不壓縮的圖片要容量=1024*1024*2/1024*1024MB=2M,所以2*40=80M所以壓縮比=80：20=4：1
D. 深入淺出lz4壓縮演算法
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復制到後面即可
E. 壓縮演算法原理
哈夫曼
哈夫曼編碼是無損壓縮當中最好的方法。它使用預先二進制描述來替換每個符號，長度由特殊符號出現的頻率決定。常見的符號需要很少的位來表示，而不常見的符號需要很多為來表示。
哈夫曼演算法在改變任何符號二進制編碼引起少量密集表現方面是最佳的。然而，它並不處理符號的順序和重復或序號的序列。
2.1 原理
我不打算探究哈夫曼編碼的所有實際的細節，但基本的原理是為每個符號找到新的二進製表示，從而通常符號使用很少的位，不常見的符號使用較多的位。
簡短的說，這個問題的解決方案是為了查找每個符號的通用程度，我們建立一個未壓縮數據的柱狀圖；通過遞歸拆分這個柱狀圖為兩部分來創建一個二叉樹，每個遞歸的一半應該和另一半具有同樣的權（權是 ∑ N K =1 符號數 k , N 是分之中符號的數量，符號數 k 是符號 k出現的次數 ）
這棵樹有兩個目的：
1． 編碼器使用這棵樹來找到每個符號最優的表示方法
2． 解碼器使用這棵樹唯一的標識在壓縮流中每個編碼的開始和結束，其通過在讀壓縮數據位的時候自頂向底的遍歷樹，選擇基於數據流中的每個獨立位的分支，一旦一個到達葉子節點，解碼器知道一個完整的編碼已經讀出來了。
壓縮後的數據流是 24 位（三個位元組），原來是 80 位（ 10 個位元組）。當然，我應該存儲哈夫曼樹，這樣解碼器就能夠解碼出對應的壓縮流了，這就使得該例子中的真正數據流比輸入的流數據量大。這是相對較短的數據上的副作用。對於大數據量來說，上面的哈夫曼樹就不佔太多比例了。
解碼的時候，從上到下遍歷樹，為壓縮的流選擇從左 / 右分支，每次碰到一個葉子節點的時候，就可以將對應的位元組寫到解壓輸出流中，然後再從根開始遍歷。
2.2 實現
哈夫曼編碼器可以在基本壓縮庫中找到，其是非常直接的實現。
這個實現的基本缺陷是：
1． 慢位流實現
2． 相當慢的解碼（比編碼慢）
3． 最大的樹深度是 32 （編碼器在任何超過 32 位大小的時候退出）。如果我不是搞錯的話，這是不可能的，除非輸出的數據大於 2 32位元組。
另一方面，這個實現有幾個優點：
1． 哈夫曼樹以一個緊密的形式每個符號要求 12 位（對於 8 位的符號）的方式存儲，這意味著最大的頭為 384 。
2． 編碼相當容易理解
哈夫曼編碼在數據有噪音的情況（不是有規律的，例如 RLE ）下非常好，這中情況下大多數基於字典方式的編碼器都有問題。
F. 壓縮文件的演算法
主要是看文件格式，像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
結束循環
G. C++對一長度為22的數字字元串，無損壓縮為16位字元串，並且可逆。有什麼好的演算法
長度22的數字字元串表示的應該是0至10^23-1
即0到9999....9 （22個9）
一個字元串佔一個位元組8位，理論上最多表示2^8-1,0~255個狀態，
或者說一個位元組無符號整數范圍是0~255
要無損壓縮0至10^23-1范圍內的整數，至少需要二進制77位（23/log10(2)）
你所說的16位字元串是只16個字元串把，也就是16位元組，128位吧，
如果是的話，壓縮還是很有冗餘的，要是小於77為二進制數，就不可能無損壓縮了
最簡單的就是用4位二進制碼表示1個十進制數
4位二進制碼有16中可能，取其中的10中可能表示十進制0~1
那麼每兩位十進制數就用一個位元組表示，22位，只需要11個位元組就夠了
數字字元0~9的ascii碼是48~57（十六進制30~39），只保留低四位就是0~9
兩個10進制數給佔4位，佔一個位元組
壓縮編碼的時候，從十進制低位起，每兩個數字一組（個位和十位，百位和千位.....)
（低位的ascii-48） +（高位的ascii-48）*16 獲得一個位元組
22位的數字，能夠獲得11個位元組的數據，如果要16個位元組的話，就有5個位元組的冗餘
解碼的時候，從低到高獲得每個位元組
位元組數據/16的商+48 就是高位的ascii碼
位元組數據/16的余數+48 就是地位的ascii碼
當然乘除可以用移位運算代替，速度更快
H. 二進制壓縮演算法有哪些
二進制數據壓縮演算法二進制是計算技術中廣泛採用的一種數制。二進制數據是用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，在這些情況下，壓縮率是最重要的。
I. 位元組壓縮10000100當中最左邊的一參與運算嗎
參與運算。
位元組壓縮演算法，採用一個位元組來表示連續的一串0(或1)。位元組最左邊的一位是0，則表示該位元組代表一串0，否則，代表一串1，其餘位代表0(或1)的數量，因此參與運算。
J. zip 的壓縮原理與實現
文件壓縮原理
我們使用計算機所做的事情大多都是對文件進行處理。每個文件都會佔用一定的磁碟空間，我們希望一些文件，尤其是暫時不用但又比較重要不能刪除的文件（如備份文件，有點像雞肋呀），盡可能少的佔用磁碟空間。但是，許多文件的存儲格式是比較鬆散的，這樣就浪費了一些寶貴的計算機存儲資源。這時，我們可以藉助壓縮工具解決這個問題，通過對原來的文件進行壓縮處理，使之用更少的磁碟空間保存起來，當需要使用時再進行解壓縮操作，這樣就大大節省了磁碟空間。當你要拷貝許多小文件時，通過壓縮處理可以提高執行效率。如果小文件很多，操作系統要執行頻繁的文件定位操作，需要花費很多的時間。如果先把這些小文件壓縮，變成一個壓縮文件後，再拷貝時就很方便了。由於計算機處理的信息是以二進制數的形式表示的，因此壓縮軟體就是把二進制信息中相同的字元串以特殊字元標記來達到壓縮的目的。為了有助於理解文件壓縮，請您在腦海里想像一幅藍天白雲的圖片。對於成千上萬單調重復的藍色像點而言，與其一個一個定義「藍、藍、藍……」長長的一串顏色，還不如告訴電腦：「從這個位置開始存儲1117個藍色像點」來得簡潔，而且還能大大節約存儲空間。這是一個非常簡單的圖像壓縮的例子。其實，所有的計算機文件歸根結底都是以「1」和「0」的形式存儲的，和藍色像點一樣，只要通過合理的數學計算公式，文件的體積都能夠被大大壓縮以達到「數據無損稠密」的效果。總的來說，壓縮可以分為有損和無損壓縮兩種。如果丟失個別的數據不會造成太大的影響，這時忽略它們是個好主意，這就是有損壓縮。有損壓縮廣泛應用於動畫、聲音和圖像文件中，典型的代表就是影碟文件格式mpeg、音樂文件格式mp3和圖像文件格式jpg。但是更多情況下壓縮數據必須准確無誤，人們便設計出了無損壓縮格式，比如常見的zip、rar等。壓縮軟體（compression software）自然就是利用壓縮原理壓縮數據的工具，壓縮後所生成的文件稱為壓縮包（archive），體積只有原來的幾分之一甚至更小。當然，壓縮包已經是另一種文件格式了，如果你想使用其中的數據，首先得用壓縮軟體把數據還原，這個過程稱作解壓縮。常見的壓縮軟體有winzip、winrar等