非死book開源新的壓縮算法，性能超zlib

近日，非死book 開源 了新的壓縮算法 Zstandard 1.0 。據非死book工程師 Yann Collet 和Chip Turner介紹，該算法是少數能夠在性能和效率方面超過zlib的壓縮算法之一，而后者當前是“占統治地位的標準”。非死book Zstandard利用了 Collet之前所做的工作 。Collet是 LZ4 的作者，他在 2015 年發布了其新算法的第一個版本。

非死book的基準測試顯示，在任意壓縮率和壓縮帶寬組合下，Zstandard的性能都要高于zlib。

特別地，當使用標準無損壓縮語料庫 Silesia 時，相比zlib，Zstandard展示了出色的性能：

• _{在壓縮率相同的情況下，它的速度快大約3到5倍；}

• _{在壓縮速度相同的情況下，它生成的文件小10%到15%；}

• _{不管壓縮率多大，它解壓縮的速度都要快2倍；}

• _{它的最大壓縮率要高許多（大約為4比3.15）。}

Zstandard使用了 有限狀態熵 ，并以Jarek Duda在熵編碼 非對稱數字系統 （ANS）方面的工作為基礎。ANS的目標是“避免在壓縮速度和壓縮率之間進行取舍”，它既可以用于精確編碼，也可以用于快速編碼，并且支持數據加密。但是，從根本上講，Zstandard之所以提供了更好的性能是因為它的多項設計和實現選擇。

• zlib受一個32KB的窗口限制，而Zstandard并沒有任何固有的限制，它可以更充分地利用現代環境中的內存，包括移動和嵌入式環境。
• 一個新的Huffman解碼器 Huff0 。它可以借助多個 ALU 并行解碼符號，減少算術操作之間的依賴。

• Zstandard設法盡量減少分支，從而將因為分支預測錯誤而導致的、開銷很高的管道清理最小化。下面的例子展示了如何在不使用分支的情況下重寫while循環：

  /* 經典版本 */
  while (nbBitsUsed >= 8) { /* 每個while測試都是一個分支 */
    accumulator <<= 8;
    accumulator += *byte++;
    nbBitsUsed  -= 8;
  }
  
  /* 無分支版本 */
  nbBytesUsed = nbBitsUsed >> 3;
  nbBitsUsed &= 7;
  ptr += nbBytesUsed;
  accumulator = read64(ptr);

• 對于差別只有幾個字節的序列，重復碼建模極大地改善了壓縮。

Zstandard是使用C語言編寫的。它既是一個命令行工具，也是一個庫。它提供了20多個壓縮級別，讓用戶可以根據具體可用的硬件、待壓縮的數據和待優化的瓶頸進行仔細地調整。非死book建議開始時使用默認級別3。該級別適合大多數情況。然后，可以嘗試9以下的級別，合理地平衡速度和空間，或者使用更高的級別獲得更高的壓縮率，而20以上的級別則適合那些你不關心壓縮速度的情況。

對于Zstandard的未來版本會帶來什么特性，Collet和Turner也提供了一些信息，其中包括支持多線程，以及可以提供更快壓縮速度和更高壓縮率的新的壓縮級別。

Zstandard是繼蘋果的ZLFSE和谷歌的 Brotli 之后的又一個開源壓縮算法。ZLFSE和Brotli都是開源的，每一種算法都針對特定的應用場景進行了優化：Brotli似乎為實現Web資產和Android APK的高壓縮率進行了 優化 ，而LZFSE的目標是，在壓縮率相同的情況下，提供比zlib更快的壓縮速度和更低的電量消耗。

來自： http://www.infoq.com/cn/news/2016/09/非死book-zstandard-compression