LZ0 - 超軽量デコーダを備えた非対称LZコンプレッサー

Show HN: LZ0 -An asymmetric LZ compressor with ultra minimal, 0-alloc decoder

LZ0は、解凍側の負担を極限まで減らすことに特化した実験的な可逆圧縮フォーマットです。エンコード時に複雑な処理を集中させることで、デコーダは動的メモリ割り当て(malloc)を一切行わず、わずか約150行のCコードで実装できます。数百MB/秒の高速解凍を実現し、ブートローダーやマイコン、カーネル空間などリソース制約の厳しい環境に最適。ZX0に匹敵する圧縮率を保ちつつ、エンコード時間を数分から数秒に短縮しました。C言語に加え、x86-64、ARM64、RISC-V向けのコンパクトなアセンブリデコーダも提供しています。

複雑さをデコーダからエンコーダへ移す——この単一の原則が、超軽量で高速な解凍を可能にします。
  1. nellacross

    LZ4とのより深い比較を見てみたいです。LZ4スタイルのデコーダは最小限に作れますし、LZ4HCを使えば解凍速度を犠牲にせずに圧縮率を上げられますからね。

  2. aidenn0

    lz4hc -9とのベンチマークも見てみたいですね。圧縮速度と解凍速度の両方で最も近い競合ですから。

  3. seb3773

    私はLZ0を作りました。これは非対称LZコンプレッサーで、解凍リソースが厳しく制限される環境(ブートローダー、マイクロコントローラー、組み込みアセットの読み込み)や、デコーダのシンプルさが最も重要な場面を対象としています。

    Einar SaukasのZX0のようなマイクロデコーダにはいつも憧れていました。動的アロケーションゼロ、スクラッチRAM不要、そしてほんの数命令に収まるほど小さいのです。従来の最適パーサーの問題点は、しばしばO(N^2)でスケールし、ファイルが数百キロバイトを超えると数十秒から数分かかってしまうことです。私は、マルチメガバイトのファイルをミリ秒で圧縮しながら、同じデコーダフットプリントを維持するためにLZ0を書きました。

    位置づけ(圧縮率対速度): - 圧縮密度:LZ4/Snappyを上回り、zlib/Deflateや徹底的なZX0と比べて1〜3%以内に収まります。 - 解凍速度:ポータブルCで200〜350 MB/s、コンパクトASMで250〜700 MB/s、ベクターASMで520〜1,330 MB/s。これはDeflateの最大10倍高速でありながら、ヒープメモリや状態テーブルを一切必要としません。 - 圧縮スループット:典型的な1 MB入力で約1.3〜1.6秒。

    エンコーダがO(N^2)の壁を回避する方法(H2C8パイプライン): - 多層マッチファインディング:ローカルマッチ用の二段階ハッシュチェーンと、深い長距離マッチ用のO(N) SA-ISサフィックスアレイを組み合わせています。 - スパースDPパース:グラフのすべてのエッジを評価する代わりに、Eliasガンマビットコストを数学的なプラトーにグループ化して冗長な探索をスキップします。

    リポジトリには3つのゼロアロケーションデコーダ実装が同梱されています: 1. ポータブルC(`lz0dec_min.c`):フリースタンディングCで約75行、z […]

この日のほかの記事

2026-11-21