このページの内容

LZ4 APIの例: 辞書によるランダムアクセス

dictionaryRandomAccess.cは、辞書による圧縮と、ランダムアクセスによる展開を実装するLZ4 APIのサンプルです。

出力ファイルはlz4frameと互換性がなく、プラットフォームに依存する点に注意してください。

このサンプルのポイント

同種のファイルに対する辞書ベースの圧縮。
圧縮ブロックへのランダムアクセス。

圧縮の仕組み

ファイルから辞書を読み込み、各ブロックの履歴として使います。これにより、圧縮率を保ちながら、各ブロックを独立させることができます。

    Dictionary
         +
         |
         v
    +---------+
    | Block#1 |
    +----+----+
         |
         v
      {Out#1}


    Dictionary
         +
         |
         v
    +---------+
    | Block#2 |
    +----+----+
         |
         v
      {Out#2}

マジックバイトTESTを書き、続いて圧縮ブロックを書いた後、ジャンプテーブルを書き出します。最後の4バイトは、ストリーム内のブロック数を格納する整数です。N個のブロックがある場合、最後の4バイトの直前に、各ブロックの先頭と末尾のオフセットを格納した、N + 1個の4バイト整数があります。簡単のため、Offset#Kを、Block#Kを書き出した後の総書き込みバイト数とし、マジックバイトも 含めます。

+------+---------+     +---------+---+----------+     +----------+-----+
| TEST | Block#1 | ... | Block#N | 4 | Offset#1 | ... | Offset#N | N+1 |
+------+---------+     +---------+---+----------+     +----------+-----+

展開の仕組み

展開では、逆の処理を行います。

ファイルの最後の4バイトにシークし、オフセット数を読み込みます。
各オフセットを配列に読み込みます。
読みたいデータを含む最初のブロックにシークします。最後のブロックを除き、各ブロックが固定量の非圧縮データを含むと分かっているため、場所を判定できます。最後のブロックは固定量でない場合があります。
そのブロックを展開し、必要なデータをファイルに書き込みます。
次のブロックを読み込みます。
展開し、そのページをファイルに書き込みます。

必要なデータをすべて読み込むまで、この手順を繰り返します。