二進(jìn)制數(shù)據(jù)壓縮算法二進(jìn)制是計(jì)算技術(shù)中廣泛采用的一種數(shù)制。二進(jìn)制數(shù)據(jù)是用0和1兩個(gè)數(shù)碼來表示的數(shù)。它的基數(shù)為2，進(jìn)位規(guī)則是“逢二進(jìn)一”，借位規(guī)則是“借一當(dāng)二”，由18世紀(jì)德國(guó)數(shù)理哲學(xué)大師萊布尼茲發(fā)現(xiàn)。當(dāng)前的計(jì)算機(jī)系統(tǒng)使用的基本上是二進(jìn)制系統(tǒng)，數(shù)據(jù)在計(jì)算機(jī)中主要是以補(bǔ)碼的形式存儲(chǔ)的。計(jì)算機(jī)中的二進(jìn)制則是一個(gè)非常微小的開關(guān)，用“開”來表示1，“關(guān)”來表示0。

20世紀(jì)被稱作第三次科技革命的重要標(biāo)志之一的計(jì)算機(jī)的發(fā)明與應(yīng)用，因?yàn)閿?shù)字計(jì)算機(jī)只能識(shí)別和處理由‘0’?！?’符號(hào)串組成的代碼。其運(yùn)算模式正是二進(jìn)制。19世紀(jì)愛爾蘭邏輯學(xué)家喬治布爾對(duì)邏輯命題的思考過程轉(zhuǎn)化為對(duì)符號(hào)“0‘’?！?‘’的某種代數(shù)演算，二進(jìn)制是逢2進(jìn)位的進(jìn)位制。0、1是基本算符。因?yàn)樗皇褂?、1兩個(gè)數(shù)字符號(hào)，非常簡(jiǎn)單方便，易于用電子方式實(shí)現(xiàn)。

二進(jìn)制壓縮 - 算法

二進(jìn)制壓縮

在編程時(shí)遇到每個(gè)數(shù)據(jù)只有兩種狀態(tài)，且 dfs 或者 bfs 時(shí)遍歷時(shí)間復(fù)雜度高時(shí)，可以采用二進(jìn)制壓縮數(shù)據(jù)，尤其是二維數(shù)組。

1.二進(jìn)制壓縮一個(gè)二位數(shù)組

例如：

-+--

----

----

-+--

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

0100

0000

0000

010012345678910

如果我們采用二進(jìn)制壓縮為一個(gè) int 類型的數(shù)據(jù)，正好用 16 位來表示。

這里有兩種表示方法，其實(shí)都一樣，一種先從上到下變?yōu)閺母呶坏降臀?，一種是從上到下變?yōu)閺牡臀坏礁呶弧?/p>

從低位到高位

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;

}

}

二進(jìn)制數(shù)據(jù)壓縮算法

LZFSE

1，zlib和gzip都對(duì)deflate進(jìn)行了封裝，比deflate多了數(shù)據(jù)頭和尾

1，蘋果開源了新的無損壓縮算法 LZFSE ，該算法是去年在iOS 9和OS X 10.10中 引入 的。按照蘋果公司的說法，LZFE的壓縮增益和ZLib level 5相同，但速度要快2~3倍，能源效率也更高。

LZFSE基于Lempel-Ziv，并使用了 有限狀態(tài)熵編碼，后者基于Jarek Duda在

非對(duì)稱數(shù)字系統(tǒng)（ANS）方面所做的熵編碼工作。簡(jiǎn)單地講，ANS旨在“終結(jié)速度和比率的平衡”，既可以用于精確編碼，又可以用于快速編碼，并且具有數(shù)據(jù)加密功能。使用ANS代替更為傳統(tǒng)的

Huffman和 算術(shù)編碼方法的壓縮庫(kù) 越來越多，LZFSE就位列其中。

顯然，LZFSE的目標(biāo)不是成為最好或最快的算法。事實(shí)上，蘋果公司指出，

LZ4的壓縮速度比LZFSE快，而 LZMA提供了更高的壓縮率，但代價(jià)是比Apple

SDK提供的其他選項(xiàng)要慢一個(gè)數(shù)量級(jí)。當(dāng)壓縮率和速度幾乎同等重要，而你又希望降低能源效率時(shí)，LZFSE是蘋果推薦的選項(xiàng)。

GitHub上提供了LZFSE的參考實(shí)現(xiàn)。在MacOS上構(gòu)建和運(yùn)行一樣簡(jiǎn)單：

$ xcodebuild install DSTROOT=/tmp/l***se.dst

如果希望針對(duì)當(dāng)前的iOS設(shè)備構(gòu)建LZFSE，可以執(zhí)行：

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

除了 API文檔之外，蘋果去年還提供了一個(gè) 示例項(xiàng)目，展示如何使用LZFSE 進(jìn)行塊和流壓縮，這是一個(gè)實(shí)用的LZFSE入門資源。

LZFSE是在谷歌 brotli之后發(fā)布的，后者在去年開源。與LZFSE相比，brotli 似乎是針對(duì)一個(gè)不同的應(yīng)用場(chǎng)景進(jìn)行了優(yōu)化，比如壓縮靜態(tài)Web資產(chǎn)和Android APK，在這些情況下，壓縮率是最重要的。