小さな辞書を使った圧縮アルゴリズム

Question

私はバイトより小さいシンボルで動作する圧縮アルゴリズムを探しています。圧縮アルゴリズムについて簡単に研究しましたが、使用されているシンボルのサイズを調べるのは難しいです。とにかく、8ビットより小さいシンボルを持つストリームがあります。シンボルのサイズを定義するDEFLATEのパラメータはありますか？バイトより小さい

Answer 1

平文シンボルLZ77及びLZ78の

元の記述は、それらは、桁（約バイトの半分の大きさであるシンボル）のシーケンスの観点から説明しています。

Googleの「DNA圧縮アルゴリズム」の場合は、ほぼ4つの文字AGCT、4つの記号の辞書で構成された圧縮ファイル専用のアルゴリズムに関する情報を得ることができます1バイトほど小さい。 これらのアルゴリズムのうちの1つが、比較的小さな調整で機能するかもしれません。 LZMAに使用

LZ77スタイルの圧縮は、圧縮する最初のいくつかのシンボルについて、シンボルごとに2つのバイトを使用するように見えることがあります。 しかし、数百平文シンボル （自然言語テキストの文字、または小数点以下の桁数の配列またはDNA塩基などを表す4つの文字の配列）圧縮した後、2バイトを圧縮「チャンク」というLZMA多くの場合、12個以上の平文記号を表す。 （これはDEFLATEで使用されているLZ77アルゴリズムなど、すべての同様のアルゴリズムに当てはまると思われます）。

ファイルがすべての256の可能なバイト値よりもはるかに小さい制限されたアルファベットのみを使用する場合、 は原則としてプログラマがそのアルファベットに関する情報を利用してDEFLATE（または他のアルゴリズム）標準のDEFLATEで圧縮された同じファイルよりもサイズが数ビット小さく圧縮されたファイルです。 しかし、多くのバイト指向のテキスト圧縮アルゴリズム - LZ77、LZW、LZMA、DEFLATEなどの一般的な長い文字列の辞書を構築し、圧縮性能を与える可能性があり（十分に大きなソースファイル付き）が特注の数パーセント内標準圧縮ファイル形式を使用する利点は、スペース節約の可能性を数％犠牲にする価値があります。バイトよりも小さい

圧縮シンボルベンチマークファイルで最もよく知られている圧縮を与えるものも含め

多くの圧縮アルゴリズム、出力圧縮情報ビットごと（例えばコンプレッサーのPAQシリーズの最も、およびいくつかの種類の算術コーダ）、バイト境界（ハフマン圧縮など）に関係なく、可変長圧縮情報を出力するものもあります。

「情報の1ビット未満」に圧縮されるように、個々のビットまたは画素としての情報、話を算術符号化を説明するいくつかの方法。

EDIT： 「カウント引数」は、8ビット未満のすべてのコードワードに可能なすべてのバイト、すべての可能なバイトおよびいくつかの共通のバイトシーケンスを圧縮できない理由を説明します。 はそれにもかかわらず、いくつかの圧縮アルゴリズムができ、多くの場合、「犠牲」またはエンドあまり共通バイトを「エスケープ」することによって、（まれ）、いくつかのバイト又はバイトのいくつかの配列を表す未満8ビット長でコードワードとのそれぞれを表す行います他のコードワード（「エスケープ」を含む）によって表される最大ビット長は8ビット以上です。

ようなアルゴリズムは、次のとおり各記号はの配列を表し、「記号」にファイルのLZ77状解析を行う

• パイクText compression using 4 bit coding
• バイト指向ハフマン
• いくつcombination algorithmsをDEFLATE、LZX、LZH、LZHAMなどのシンボルをハフマン圧縮する。

Pikeアルゴリズムでは、4ビットの "01 （またはいくつかの文脈「E」）を表すために「01」を、単語「the」を表すために8ビット「0000 0001」（それ以前のスペースを含む4バイト） "THE"など） それは、最も頻繁な英語の単語のうちの約200の小さな辞書であり、 は、非常に一般的な16の英単語のサブ辞書を含む。

バイト指向のハフマン符号化で英語のテキストを圧縮する場合、シーケンス「e」（e空間）は、合計6ビットの2つの符号語に圧縮されます。

ハフマンコーディングが含まれていると、それらの「小さな」コードワードの正確なサイズを教えたり、小さなコードワードが表すバイトまたはバイトシーケンスを正確に伝えることはできません。 多くの場合、同じコードワードは、同じファイル内の異なる場所にある異なるバイト（または異なるバイトシーケンス）を表します。 デコーダは、ヘッダー内のコンプレッサーによって残された手がかりおよびこれまでに解凍されたデータに基づいて、コードワードが表すバイトまたはバイトシーケンスを決定します。 範囲符号化または算術符号化では、「符号語」は整数ビットでなくてもよい。

Answer 2

Golomb-Codeを調べることができます。ゴロムのコードは、分割と征服のアルゴリズムを使用してinoutを圧縮します。これは辞書の圧縮ではありませんが、言及する価値があります。