LZMA
Lempel-Ziv-Markov Chain Algorithm の略。LZ77 を改良し、高圧縮で高速・省メモリな復元を実現した圧縮アルゴリズム。7-zip に使われていることなどで有名。bzip2 や PPMD と同程度の高圧縮率を実現しているにも関わらず、復元が高速であることが特徴。圧縮にそれなりの時間・空間を要し、復元は高速かつ省メモリないわゆる distributed algorithm である。
XZ Utils
LZMA を用いた圧縮ライブラリである XZ Utils (http://tukaani.org/xz/) を用いることで tar アーカイブを圧縮し、配布することができる。XZ Utils で拡張子は tar.xz となる。tar コマンドのオプションで J を付加することで圧縮・復元が可能。
LZMA アルゴリズムのあらまし
LZMA が高圧縮率を達成できる理由は幾つかある。以下は参考文献 [1] からの要約である。
Repeated Offsets
LZ77法ではスライディングウィンドウ中から最長一致する部分文字列を探しだし、それをマッチ情報 (位置情報、長さ) に置き換える。
このとき、バイナリデータや表形式データでは、一定間隔で同じ情報が表れやすいという特徴がある。そこで LZMA では、マッチ情報を単なるマッチ情報として出力するのではなく、繰り返しマッチングが発生した場合は、その毎回のオフセット距離で保存する。この毎回のオフセット距離は LRU リストで管理され、出力には 4 要素の LRU のスロット番号が利用される。これを Repeated Offsets を呼ぶ。
Repeated Offsets を用いると、繰り返しマッチする情報は、偏った出現回数でのより短い整数で表現することができる。これにより圧縮率が向上する。(考え方としては Move to Front と同じ類と思われる)
Binary Range Coder
LZMA では、前述の Repeated Offsets の開始フラグや LRU のスロット番号など2値の値あるいは非常に小さな値を符号化することになる。この符号化に Binary Range Coder を用いる。
Binary Range Coder は二値に特化した Range Coder で、二値しか扱わないことを前提に、汎用の Range Coder で必要になる各種処理 (ベースラインの更新、累積確率表の更新、累積頻度表からの記号の発見) をスキップし、高速化、空間効率を上げた実装である。
コンテキストに基づいた確率分布
LZMA は、文字を符号化するにあたって直前の符号化の状態をコンテキストとして利用する。マッチングがあった、なかった、Repeated Offsets でマッチしたといった各種直前の状態をオートマトンで表現し、これから符号化しようとするのが、マッチングか、Repeated Offsets か、記号かのいずれかによって状態遷移を行う。
LZMA は 12 状態を用意し、その 12 状態それぞれに確率表を分けて、この確率表を Binary Range Coder で利用することにより圧縮率を高める。
最適マッチング
LZMA は符号化にあたって、最適マッチングを行う。具体的には、マッチングを今行う、あとで行う、Repeated Offsets を採用する、記号を符号化するという選択肢の中から最適なものを選ぶ。ただし、ある程度は最長一致を優先的に選択する妥協策も採っているとのこと。
参考文献
- [1] 岡野原大輔, "LZMA圧縮/bzip2圧縮/PPMD圧縮 7zipで使われている圧縮技術", C Magazine 2006年 1月号, ソフトバンククリエイティブ, 2006
参考URL
- 圧縮・解凍ソフト 7-Zip
- LZMA SDK (Software Development Kit)
- The Tukaani Project XZ Utils の配布先
- 静かな注目を集める圧縮アルゴリズム「LZMA」 - ITmedia エンタープライズ
- Lempel–Ziv–Markov chain algorithm - Wikipedia
- A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA ベンチマーク。復号処理は gzip よりは 2 ~ 3 倍遅いものの、bzip2 よりはかなり高速
このタグの解説について
この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。関連ブログ
ネットで話題
もっと見る
www.itmedia.co.jp
forest.watch.impress.co.jp
github.com
metacpan.org
kakurasan.hatenadiary.jp
github.com
7-zip.org
pokecraft.first-world.info
7-zip.opensource.jp
