LZ4ストリーミングAPIの例: 行単位のテキスト圧縮
著者: Takayuki Matsuoka
blockStreaming_lineByLine.cは、行単位の逐次圧縮・展開を実装する、LZ4ストリーミングAPIのサンプルです。
次の制約に注意してください。
- まず「LZ4ストリーミングAPIの基礎」を読んでください。
- 比較的高度なアプリケーションの例です。
- 出力ファイルはlz4frameと互換性がなく、プラットフォームに依存します。
このサンプルのポイント
- 行単位の逐次圧縮・展開。
- 少量のメモリで巨大なファイルを扱う。
- 一般にBlock APIより高い圧縮率。
- 不均一なブロックサイズ。
圧縮の仕組み
まず、入力用の「リングバッファー」と、出力用のLZ4圧縮データバッファーを確保します。
(1)
Ring Buffer
+--------+
| Line#1 |
+---+----+
|
v
{Out#1}
(2)
Prefix Mode Dependency
+----+
| |
v |
+--------+-+------+
| Line#1 | Line#2 |
+--------+---+----+
|
v
{Out#2}
(3)
Prefix Prefix
+----+ +----+
| | | |
v | v |
+--------+-+------+-+------+
| Line#1 | Line#2 | Line#3 |
+--------+--------+---+----+
|
v
{Out#3}
(4)
External Dictionary Mode
+----+ +----+
| | | |
v | v |
------+--------+-+------+-+--------+
| .... | Line#X | Line#X+1 |
------+--------+--------+-----+----+
^ |
| v
| {Out#X+1}
|
Reset
(5)
Prefix
+-----+
| |
v |
------+--------+--------+----------+--+-------+
| .... | Line#X | Line#X+1 | Line#X+2 |
------+--------+--------+----------+-----+----+
^ |
| v
| {Out#X+2}
|
Reset次に、図(1)のように最初の行をリングバッファーに読み込み、LZ4_compress_continue()で圧縮します。初回は、LZ4は先行する依存先を知りません。そのため、その行を依存関係なしで圧縮し、LZ4圧縮データバッファーに圧縮した行{Out#1}を生成します。その後、{Out#1}をファイルに書き込み、リングバッファーのオフセットを進めます。
二番目の行にも同じ処理を行います（図(2)）。ただし、今度は、LZ4がLine#1への依存関係を使い、圧縮率を改善できます。この依存関係を「プレフィックスモード」と呼びます。
やがてLine#Xでリングバッファーの末尾に到達します（図(4)）。この時点でリングバッファーのオフセットをリセットすべきです。リセット後、Line#X+1のポインターは隣接していませんが、LZ4はまだそのメモリを保持しています。これを「外部辞書モード」と呼びます。
Line#X+2（図(5)）では、LZ4はついにほぼすべてのメモリを忘れますが、Line#X+1はまだ残っています。これはLine#2と同じ状況です。
テキストファイルの末尾まで、この手順を繰り返します。
展開の仕組み
展開では、逆の処理を行います。
- ファイルから圧縮した行をバッファーに読み込みます。
- リングバッファーに展開します。
- 展開したプレーンテキストの行をファイルに出力します。
- リングバッファーのオフセットを進めます。オフセットがリングバッファーの末尾を超えた場合は、リセットします。
圧縮ファイルの末尾まで、この手順を繰り返します。