インクリメンタルエンコーディング

インクリメンタルエンコーディング（フロント圧縮、バック圧縮、フロントコーディングとも呼ばれる）は、デルタエンコーディング圧縮アルゴリズムの一種で、共通の接頭辞や接尾辞とその長さを記録することで、重複を避けることができる。このアルゴリズムは、辞書の単語リストなど、ソートされたデータの圧縮に特に適している。

例えば：

共通接頭辞の長さを格納するために使用されるエンコーディングは、アプリケーションによって異なります。一般的な手法としては、値を1バイトとして格納する方法、共通接頭辞の長さの変化のみを格納するデルタエンコーディング、および各種ユニバーサルコードなどがあります。残りの接尾辞を圧縮するために、エントロピーエンコーディングや辞書符号化などの他の一般的な可逆データ圧縮技術と組み合わせることもできます。

インクリメンタルエンコーディングは、情報検索において検索インデックスで使用される語彙集を圧縮するために広く使用されています。語彙集には、すべての文書で見つかったすべての単語と、それぞれの単語に対応する場所のリストへのポインタが含まれています。通常、この方法ではこれらのインデックスを約40%圧縮できます。^{[ 1 ]}

例えば、 GNU locateユーティリティは、ファイル名とディレクトリのインデックスを作成する際に、インクリメンタルエンコーディングを起点として使用します。さらに、 GNU locateユーティリティは、よく使われるファイルパスの接頭辞をさらに短縮するために、バイグラムエンコーディングを使用します。