二進制數據壓縮算法二進制是計算技術中廣泛采用的一種數制。二進制數據是用0和1兩個數碼來表示的數。它的基數為2，進位規則是“逢二進一”，借位規則是“借一當二”，由18世紀德國數理哲學大師萊布尼茲發現。當前的計算機系統使用的基本上是二進制系統，數據在計算機中主要是以補碼的形式存儲的。計算機中的二進制則是一個非常微小的開關，用“開”來表示1，“關”來表示0。

20世紀被稱作第三次科技革命的重要標志之一的計算機的發明與應用，因為數字計算機只能識別和處理由‘0’?！?’符號串組成的代碼。其運算模式正是二進制。19世紀愛爾蘭邏輯學家喬治布爾對邏輯命題的思考過程轉化為對符號“0‘’。‘’1‘’的某種代數演算，二進制是逢2進位的進位制。0、1是基本算符。因為它只使用0、1兩個數字符號，非常簡單方便，易于用電子方式實現。

二進制壓縮 - 算法

二進制壓縮

在編程時遇到每個數據只有兩種狀態，且 dfs 或者 bfs 時遍歷時間復雜度高時，可以采用二進制壓縮數據，尤其是二維數組。

1.二進制壓縮一個二位數組

例如：

-+--

----

----

-+--

正常保存數據回使用二位數組，‘+’ -》 1，‘-’ -》 0，即

0100

0000

0000

010012345678910

如果我們采用二進制壓縮為一個 int 類型的數據，正好用 16 位來表示。

這里有兩種表示方法，其實都一樣，一種先從上到下變為從高位到低位，一種是從上到下變為從低位到高位。

從低位到高位

int input = 0;

int［］［］ data = new int［4］［4］;

Scanner sc = new Scanner（System.in）;

String line = “”;

for （int i = 0; i 《 4; i++） {

line = sc.next（）;

for （int j = 0; j 《 4; j++） {

data［dataIn++］ = line.charAt（j）;

}

}

for （int i = 0; i 《 16; i++） {

if （data［i］ == ‘+’） {

input |= （1 《《 i）;

// System.out.println（Integer.toBinaryString（input））;

}

}1234567891011121314151617

從高位到低位

int input = 0;

Scanner sc = new Scanner（System.in）;

String line = “”;

for （int i = 0; i 《 4; i++） {

line = sc.next（）;

for （int j = 0; j 《 4; j++） {

input = input 《《 1;

input = line.charAt（i） == ‘+’ ？ input + 1 ： input;

}

}

二進制數據壓縮算法

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/l***se.dst

如果希望針對當前的iOS設備構建LZFSE，可以執行：

xcodebuild -configuration “Release” -arch armv7 install DSTROOT=/tmp/l***se.dst

除了 API文檔之外，蘋果去年還提供了一個 示例項目，展示如何使用LZFSE 進行塊和流壓縮，這是一個實用的LZFSE入門資源。

LZFSE是在谷歌 brotli之后發布的，后者在去年開源。與LZFSE相比，brotli 似乎是針對一個不同的應用場景進行了優化，比如壓縮靜態Web資產和Android APK，在這些情況下，壓縮率是最重要的。