c - LZW 圧縮用のツリーを構築する方法は?

Question

cでLZW圧縮用のツリーを構築する方法を教えてもらえますか? struct tree{ short next[255]; のようなものですか？}

Answer 1

LZW のツリーは辞書のようなものです。各エントリは、コード (インデックス) と文字で構成されます。ツリーはすべての文字で論理的に初期化され、8 ビット文字を想定して、これらはコード 0x00 から 0xff を使用します。これらは、実際にはディクショナリに格納されていない可能性があり、格納されているかのようにエミュレートされているだけです。

各辞書エントリが (code | char) で構成され、入力文字列 "abcd" があるとすると、dictionary[100] = ('a' | 'b')、dictionary[101] = (100 | 'c') 、辞書[102] = (101 | 'd')。

デコーダーは文字列を逆の順序で取得するため、スタックのようなものを使用して文字列を保持する必要があることに注意してください。たとえば、コード 102 の場合、[102] から 'd'、[101] から 'c'、[100] から 'b' と 'a' をこの順序で取得します。code < 0x100 の場合、文字列の末尾 (実際には先頭) が示されます。

ディクショナリに入れる次のコードとなるコードをデコーダが受け取る特殊なケースもありますが、まだそこにはありません。これは、辞書[次のコード] = (前のコード | 前のコードの最後の文字) によって処理されます。このケースを処理するには、デコードされた各文字列の前のコードと最後の文字を保存する必要があります。

通常、制御コードは 8 つあり、圧縮プログラムは非制御コードのそれぞれに 8 を加算し、圧縮解除プログラムは非制御コードのそれぞれから 8 を減算します。

圧縮されたストリームは、ビッグ エンディアンまたはリトル エンディアン形式で格納されたコードで構成されている場合があります。ビッグ エンディアン形式の場合、圧縮されたストリームの各バイトは、新しいバイトを取得する前に左にシフトされる作業「レジスタ」の下位バイトに入ります。リトル エンディアン形式の場合、圧縮されたストリームからの各バイトは、作業中の「レジスタ」の上位部分に入り、「レジスタ」は新しいバイトを取得した直後にシフトされます。

エンコーダーとデコーダーの両方で、(code | char) に一致するものを辞書で検索する何らかの方法が必要です。ここでは、ある種のハッシュ関数が役立ちます。ハードウェアの実装では、コンテンツ アドレス指定可能な (連想) メモリが使用されます。

Web 検索を実行して、実際のコード例が見つかるかどうかを確認してください。

LZW は LZ78 の派生型です。LZ77 とその派生物は実装が簡単で、X86 プログラム ファイルの場合は、LZ77 の「移動ウィンドウ」圧縮アルゴリズムの方が優れていることに注意してください。ウィキリンクLZ77 LZ78 .