増分エンコード

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

例えば：

入力

共通接頭辞

圧縮された出力

ミクサ 粘液植物 粘液脚類 捕まえる 逮捕された 捕物 ナビット ナブク ナボブ ナカラット ナセル

先行する単語なし 「ミックス」 「ミクソップ」 共通の接頭辞なし 「捕まえる」 「ナブ」 「捕まえる」 「捕まえる」 「捕まえる」 「な」 「ナック」

0 ミクサ 3 眼球 5 od 0 ナブ 3ベッド 4 ing 3 それ 3k 3 オブ 2カラット 3 エル

64バイト

46バイト

共通プレフィックス長自体を格納するために使用されるエンコーディングは、アプリケーションによって異なります。一般的な手法としては、値を1バイトとして格納する、共通プレフィックス長の変化のみを格納するデルタエンコーディング、そして様々なユニバーサルコードが挙げられます。残りのサフィックスを圧縮するために、エントロピーエンコーディングや辞書コーダなどの他の一般的なロスレスデータ圧縮手法と組み合わせることもできます。

アプリケーション

増分符号化は、情報検索において検索インデックスに使用される語彙集を圧縮するために広く用いられています。語彙集には、すべての文書で見つかったすべての単語と、それぞれの単語に対応する位置リストへのポインタが含まれています。通常、この手法ではこれらのインデックスを約40%圧縮できます。^{[ 1 ]}

一例として、 GNU locateユーティリティは、ファイル名とディレクトリのインデックスにおいて、増分エンコーディングを起点として利用します。GNU locateユーティリティは、一般的なファイルパスのプレフィックスをさらに短縮するために、バイグラムエンコーディングを使用します。

^イアン・H・ウィッテン、アリスター・モファット、ティモシー・C・ベル著『Managing Gigabytes（ギガバイト管理）』第2版、アカデミック・プレス、 ISBN 1-55860-570-3セクション4.1: 語彙集へのアクセス、サブセクションフロントコーディング、pp.159–161。