Loading article…
辞書コーダ(置換コーダとも呼ばれる) は、圧縮するテキストとエンコーダーによって管理されるデータ構造(「辞書」と呼ばれる) に含まれる文字列のセットとの一致を検索することによって動作する、ロスレスデータ圧縮アルゴリズムの一種です。エンコーダーは、このような一致を見つけると、データ構造内の文字列の位置への参照を置き換えます。
方法と応用
一部の辞書コーダは「静的辞書」を使用します。これは、コーディングを開始する前に文字列の完全なセットが決定され、コーディング プロセス中に変更されないものです。このアプローチは、エンコードされるメッセージまたはメッセージのセットが固定されていて大きい場合に最もよく使用されます。たとえば、PDAの限られたストレージ スペースに本のコンテンツを保存するアプリケーションは、通常、テキストのコンコーダンスから静的辞書を作成し、その辞書を使用して詩を圧縮します。ハフマン コーディングを使用してコンコーダンスのインデックスを表すこの方式は、 「ハフワード」と呼ばれています。 [1]
関連したより一般的な方法では、データ環境（さまざまな入力ストリーム）から抽出された冗長性から辞書が構築され、その辞書が静的に使用され、さらに別の入力ストリームが圧縮されます。たとえば、古い英語のテキストから辞書が構築され、それを使用して本が圧縮されます。[2]
より一般的なのは、辞書があらかじめ決められた状態で始まり、エンコード処理中に、すでにエンコードされたデータに基づいて内容が変化する方法です。LZ77 アルゴリズムとLZ78アルゴリズムはどちらも この原理で動作します。LZ77 では、 「スライディング ウィンドウ」と呼ばれる循環バッファが、処理されたデータの最後のNバイトを保持します。このウィンドウは辞書として機能し、過去Nバイトに出現したすべての部分文字列を辞書エントリとして効果的に格納します。辞書エントリを識別する単一のインデックスの代わりに、一致したテキストの長さを示す長さと、現在のテキストのoffsetバイト前から始まるスライディング ウィンドウ内で一致が見つかったことを示すオフセット(距離とも呼ばれる) の 2 つの値が必要です。
LZ78 はより明示的な辞書構造を使用します。エンコード プロセスの開始時には、辞書は空です。インデックス値 0 は文字列の末尾を表すために使用されるため、辞書の最初のインデックスは 1 です。エンコード プロセスの各ステップで一致がない場合は、最後に一致したインデックス (または 0) と文字の両方が辞書に追加され、圧縮ストリームに出力されます。一致がある場合は、作業インデックスが一致したインデックスに更新され、何も出力されません。
LZWは LZ78 に似ていますが、辞書はすべての可能なシンボルに初期化されます。一般的な実装は 8 ビット シンボルで動作するため、16 進数 00 から 16 進数 FF (10 進数 255) までの辞書「コード」が事前に定義されています。辞書エントリは、コード値 16 進数 100 から追加されます。LZ78 とは異なり、一致が見つからない場合 (またはデータの終わりの場合)、辞書コードのみが出力されます。デコーダ出力は辞書より 1 ステップ遅れているため、潜在的な問題が生じます。この処理方法については、 LZWを参照してください。LZW の拡張機能には、8 ビット以外のシンボル サイズの処理、辞書をリセットしてデータの終わりを示すための予約コードなどがあります。
参考文献
- ^ Ian H. Witten、Alistair Moffat、Timothy C. Bell。Managing Gigabytes。ニューヨーク：Van Nostrand Reinhold、1994年。ISBN 9780442018634。
- ^ Rodney J. Smith.動的接続グループを使用したストリーミング圧縮システム、米国特許 5,748,955、優先日 1993 年 12 月 20 日。