LZFSE
From Wikipedia, the free encyclopedia
概要
LZFSEアルゴリズムの名称は、Lempel-ZivとFinite State Entropy（ANS: Asymmetric Numeral Systems、非対称数系を応用したエントロピー符号）の頭字語である[5]。2015年のWWDCで発表され、同年リリースのOS X El CapitanとiOS 9から導入された。
Appleによれば、LZFSEの圧縮率はzlib (DEFLATE) と同程度で、それでいて伸張速度は2～3倍速く、しかも使用リソースが少ないため、zlibよりもエネルギー効率が良い[5]。LZFSEは、伸長速度と圧縮率の優先度が同等の場合に適した方式として開発された。最新のマイクロアーキテクチャの中でも、特にarm64に焦点を当ててアルゴリズムを最適化したことが、高いエネルギー効率を達成できた要因のひとつである[6]。サードパーティーによるベンチマークでは、LZFSEの伸長速度がzlibよりも速いことが確認されたが、他の最新可逆圧縮アルゴリズムの多くが圧縮率と圧縮速度、伸長速度などで、大幅に優秀な性能特性を有していることも示された[7]。
Squashベンチマークによれば、LZFSEはZSTD（レベル6）と同等の圧縮速度だが、圧縮率でやや劣る。LZVNの速度はLZ4（レベル4）と同等で、やはり圧縮率の面でやや劣っている[8]。LZFSEとLZVNのいずれも実行時にチューニングはできない。ただし、コンパイル時には、いくつかの定数を調整することによって一般的な速度と圧縮率のトレードオフは行える[9]。
実装
Eric Bainvilleによって記述されたリファレンス用のCライブラリが、2016年のWWDC後に3条項BSDライセンスで開示されることが発表された[2]。公開されたライブラリには、LZFSEストリームの圧縮・伸張に使用可能な実行形式も含まれている。LZVNについてはAPIの提供予定はない[10]。
AppleのLZFSEは、入力がLZFSE_ENCODE_LZVN_THRESHOLD（4096バイト）より小さいときは、よりシンプルなアルゴリズムのLZVNを使用する実装となっている。LZVNは、エントロピー符号を使用しないが、3種の幅（L、M、D）のREPパケットを使用する。オープンソースのリファレンス実装は、Appleによれば、サイズが小さいとLZFSEの性能はさほど良くないため、代わりにLZVNを使用している[9]。libfastCompression.aで使われているアルゴリズムは先行して開発されていたため、2014年のMac OS X Yosemiteデベロッパー・プレビュー1に使われる既定の kernelcache 圧縮方式として、奥村晴彦によるレガシー圧縮方式の lzss を置き換える形で採用された[11]。
応用
OS X 10.9以降の HFS PlusおよびApple File Systemの疑似透過圧縮メカニズムである AppleFSCompression.framework（AFSC）は、LZFSEとLZVNをサポートしている。
Appleディスクイメージフレームワークは、Mac OS X 10.11以降、 LZFSEベースのエンコーディング方式である ULFO をサポートしている[12]。ULFO は、hdiutil(1)から[13]、または一部のサードパーティ製イメージユーティリティから使用である。
