LZFSE

LZFSE: Appleが開発した高速で効率的な圧縮アルゴリズム

LZFSE (Lempel–Ziv Finite State Entropy) は、Appleによって開発された、無料でオープンソースの可逆圧縮アルゴリズムです。その名前が示唆するように、Lempel-ZivアルゴリズムとFinite State Entropy（ANS: Asymmetric Numeral Systems、非対称数系を応用したエントロピー符号化）を組み合わせた技術です。よりシンプルなアルゴリズムであるLZVNと同時に2015年にリリースされ、同年リリースのOS X El CapitanとiOS 9に導入されました。

LZFSEの特徴：高速性と効率性を両立

Appleによれば、LZFSEはzlib (DEFLATE)と同等の圧縮率を達成しながら、伸張速度は2～3倍高速です。さらに、使用リソースが少ないため、zlibよりもエネルギー効率に優れています。この高いエネルギー効率は、特にarm64アーキテクチャへの最適化によって実現されました。

ただし、サードパーティによるベンチマークテストでは、圧縮率と速度において、他の最新の可逆圧縮アルゴリズムがLZFSEを上回る結果も示されています。例えば、Squashベンチマークでは、圧縮速度はZSTD（レベル6）と同等ですが、圧縮率はやや劣ると評価されています。LZVNについても、LZ4（レベル4）と同等の速度ながら、圧縮率はやや劣るという結果が出ています。

LZFSEとLZVNは、実行時のチューニングはできませんが、コンパイル時にいくつかの定数を調整することで、速度と圧縮率のバランスを調整することができます。

LZFSEの実装とライブラリ

LZFSEの参照実装は、Eric Bainvilleによって記述されたCライブラリとして、2016年のWWDC後に3条項BSD[[ライセンス]]で公開されました。このライブラリには、LZFSEストリームの圧縮と伸張を行うための実行ファイルも含まれています。一方、LZVNについては、APIは提供されていません。

Appleの実装では、入力データサイズがLZFSE_ENCODE_LZVN_THRESHOLD（4096バイト）より小さい場合、よりシンプルなLZVNアルゴリズムが使用されます。LZVNはエントロピー符号化を使用せず、3種類の幅（L、M、D）のREPパケットを使用する点が特徴です。オープンソースのリファレンス実装において、小規模なデータではLZFSEの性能が低下するため、LZVNが代わりに使用されていると説明されています。

なお、libfastCompression.aで使用されているアルゴリズムは、先行して開発されており、2014年のMac OS X Yosemiteデベロッパー・プレビュー1では、従来のlzssを置き換える形で、既定のkernelcache圧縮方式として採用されました。

LZFSEの応用事例

LZFSEとLZVNは、OS X 10.9以降のHFS PlusおよびApple File Systemの疑似透過圧縮メカニズムであるAppleFSCompression.framework（AFSC）でサポートされています。また、Appleディスクイメージフレームワークは、Mac OS X 10.11以降、LZFSEベースのエンコーディング方式であるULFOをサポートしています。ULFOは、hdiutil(1)や一部のサードパーティ製イメージユーティリティから使用可能です。

まとめ

LZFSEは、その高速な伸張速度とエネルギー効率から、特にAppleのエコシステムにおいて重要な役割を果たす圧縮アルゴリズムです。圧縮率と速度のバランスの良さが特徴で、様々な用途に柔軟に対応できる点が強みです。ただし、他の最新の圧縮アルゴリズムと比較すると、圧縮率においては必ずしも優れているとは限らないため、用途に応じて適切なアルゴリズムを選択することが重要です。

もう一度検索