數據壓縮演算法教學

A. 數據流壓縮原理和數據壓縮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在函數調用之前千萬不能為零。應用程序可以隨時消耗被壓縮的輸出數據

B. 數據壓縮比計算方法

數據壓縮比計算方法
舉例：65536=2的16次方，所以要16位二進制存儲，就是2個位元組即2B，像點1024*1024，則一張不壓縮的圖片要容量=1024*1024*2/1024*1024MB=2M,所以2*40=80M所以壓縮比=80：20=4：1

C. 如何用C語言實現數據壓縮

首先選擇一個壓縮演算法

然後按照演算法實現壓縮代碼，調用介面就可以
常見的 可以使用哈夫曼編碼壓縮，或者使用開源的壓縮代碼，比如lzo, gzip, lzma等等。

D. 數據壓縮的兩種方法

數據壓縮的兩種方法是無損壓縮和有損壓縮。
數據壓縮是指在不丟失信息的前提下，縮減數據量以減少存儲空間，提高其傳輸、存儲和處理效率的一種技術方法。或按照一定的演算法對數據進行重新組織，減少數據的冗餘和存儲的空間。對於任何形式的通信來說，只有當信息的發送方和接受方都能夠理解編碼機制的時候壓縮數據通信才能夠工作。例如，只有當接受方知道這篇文章需要用英語字元解釋的時候這篇文章才有意義。同樣，只有當接受方知道編碼方法的時候他才能夠理解壓縮數據。一些壓縮演算法利用了這個特性，在壓縮過程中對數據進行加密，例如利用密碼加密，以保證只有得到授權的一方才能正確地得到數據。數據壓縮能夠實現是因為多數現實世界的數據都有統計冗餘。無損壓縮演算法通常利用了統計冗餘，這樣就能更加簡練地、但仍然是完整地表示發送方的數據。
更多關於數據壓縮的兩種方法，進入：https://m.abcgonglue.com/ask/a6d3301615837126.html?zd查看更多內容

E. 數據壓縮的流行演算法

Lempel-Ziv（LZ）壓縮方法是最流行的無損存儲演算法之一。DEFLATE是 LZ 的一個變體，它針對解壓速度與壓縮率進行了優化，雖然它的壓縮速度可能非常緩慢，PKZIP、gzip 以及 PNG 都在使用 DEFLATE。LZW （Lempel-Ziv-Welch）是 Unisys 的專利，直到2003年6月專利到期限，這種方法用於 GIF 圖像。另外值得一提的是 LZR (LZ-Renau) 方法，它是 Zip 方法的基礎。LZ 方法使用基於表格的壓縮模型，其中表格中的條目用重復的數據串替換。對於大多數的 LZ 方法來說，這個表格是從最初的輸入數據動態生成的。這個表格經常採用霍夫曼編碼維護（例如，SHRI、LZX）。 一個性能良好基於 LZ 的編碼機制是 LZX，它用於微軟公司的 CAB 格式。

F. 壓縮演算法原理

哈夫曼
哈夫曼編碼是無損壓縮當中最好的方法。它使用預先二進制描述來替換每個符號，長度由特殊符號出現的頻率決定。常見的符號需要很少的位來表示，而不常見的符號需要很多為來表示。

哈夫曼演算法在改變任何符號二進制編碼引起少量密集表現方面是最佳的。然而，它並不處理符號的順序和重復或序號的序列。

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 ）下非常好，這中情況下大多數基於字典方式的編碼器都有問題。

G. 二進制壓縮演算法有哪些

二進制數據壓縮演算法二進制是計算技術中廣泛採用的一種數制。二進制數據是用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，在這些情況下，壓縮率是最重要的。

H. 數據壓縮

數據壓縮技術主要研究數據的表示、傳輸和轉換方法，目的是減少數據所佔據的存儲空間和縮短數據傳輸時所需要的時間。

衡量數據壓縮的3個主要指標：一是壓縮前後所需的信息存儲量之比要大；二是實現壓縮的演算法要簡單，壓縮、解壓縮速度快，要盡可能做到實時壓縮和解壓縮；三是恢復效果要好，要盡可能完全恢復原始數據。

數據壓縮主要應用於兩個方面。一是傳輸：通過壓縮發送端的原始數據，並在接收端進行解壓恢復，可以有效地減少傳輸時間和增加信道帶寬。二是存儲：在存儲時壓縮原始數據，在使用時進行解壓，可大大提高存儲介質的存儲量。

數據壓縮按照壓縮的失真度分成兩種類型：一種叫作無損壓縮，另一種叫作有損壓縮。

無損壓縮是指使用壓縮後的數據進行重構（或者叫作還原、解壓縮），重構後的數據與原來的數據完全相同；無損壓縮用於要求重構的信號與原始信號完全一致的場合。一個很常見的例子是磁碟文件的壓縮。根據目前的技術水平，無損壓縮演算法一般可以把普通文件的數據壓縮到原來的1/4～1/2。一些常用的無損壓縮演算法有霍夫曼（Huffman）演算法、算術演算法、遊程演算法和LZW（Lenpel-Ziv ＆ Welch）壓縮演算法。

1）霍夫曼演算法屬於統計式壓縮方法，其原理是根據原始數據符號發生的概率進行編碼。在原始數據中出現概率越高的符合，相應的碼長越短，出現概率越少的符合，其碼長越長。從而達到用盡可能少的符號來表示原始數據，實現對數據的壓縮。

2）算術演算法是基於統計原理，無損壓縮效率最高的演算法。即將整段要壓縮的數據映射到一段實數半封閉的范圍［0，1）內的某一區段。該區段的范圍或寬度等於該段信息概率。即是所有使用在該信息內的符號出現概率全部相乘後的概率值。當要被編碼的信息越來越長時，用來代表該信息的區段就會越來越窄，用來表示這個區段的位就會增加。

3）遊程演算法是針對一些文本數據特點所設計的壓縮方法。主要是去除文本中的冗餘字元或位元組中的冗餘位，從而達到減少數據文件所佔的存儲空間。壓縮處理流程類似於空白壓縮，區別是在壓縮指示字元之後加上一個字元，用於表明壓縮對象，隨後是該字元的重復次數。本演算法具有局限性，很少單獨使用，多與其他演算法配合使用。

4）LZW演算法的原理是用字典詞條的編碼代替在壓縮數據中的字元串。因此字典中的詞條越多，壓縮率越高，加大字典的容量可以提高壓縮率。字典的容量受計算機的內存限制。

有損壓縮是指使用壓縮後的數據進行重構，重構後的數據與原來的數據有所不同，但不影響人對原始資料表達的信息造成誤解。有損壓縮適用於重構信號不一定非要和原始信號完全相同的場合。例如，圖像和聲音的壓縮就可以採用有損壓縮，因為其中包含的數據往往多於我們的視覺系統和聽覺系統所能接收的信息，丟掉一些數據而不至於對聲音或者圖像所表達的意思產生誤解，但可大大提高壓縮比。