LZFSE
LZFSE (Lempel–Ziv Finite State Entropy) は、Appleによって開発されたフリーかつオープンソースの可逆圧縮アルゴリズムである[3]。LZFSEよりもシンプルなアルゴリズムのLZVNと同時にリリースされた[4]。
| 開発元 | Apple |
|---|---|
| 初版 | 2015年 |
| 最新版 |
1.0
/ 2017年5月8日[1] |
| リポジトリ | |
| プログラミング 言語 | C |
| 対応OS | |
| 種別 | データ圧縮 |
| ライセンス | 修正BSDライセンス |
概要
編集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]、または一部のサードパーティ製イメージユーティリティから使用である。
脚注
編集- ^ “Releases”. GitHub. 2019年12月1日閲覧。
- ^ a b “lzfse/lzfse”. GitHub. 2019年12月1日閲覧。
- ^ “Data Compression”. Apple Inc.. 2018年9月24日時点のオリジナルよりアーカイブ。2019年12月1日閲覧。
- ^ LZFSE - New Apple Data Compression, (2015) 6 November 2022閲覧。
- ^ a b Sergio De Simone (2016年7月2日). “Apple Open-Sources its New Compression Algorithm LZFSE”. InfoQ. 2019年12月1日閲覧。
- ^ “Low Energy, High Performance: Compression and Accelerate”. Apple Inc. (2015年6月12日). 2022年11月6日閲覧。
- ^ “Compression Benchmark”. lzturbo. 2022年11月6日閲覧。
- ^ “Squash Compression Benchmark”. GitHub. Squash. 25 December 2019閲覧。
- ^ a b “lzfse_tunables.h”. GitHub (18 December 2019). 22 December 2019閲覧。
- ^ Bainville, Eric (2016年6月7日). “LZFSE compression library and command line tool”. GitHub. 2022年11月6日閲覧。
- ^ “OS X 10.10 Yosemite DP1 kernel(cache)” (英語). Pike's Universum (4 June 2014). 22 December 2019閲覧。
- ^ Tsai, Michael (2015年10月7日). “LZFSE Disk Images in El Capitan”. 2017年4月9日時点のオリジナルよりアーカイブ。2022年4月15日閲覧。
- ^ “hdiutil(1) mojave man page”. 2022年4月15日閲覧。
