ASCII文字列を4バイト長の文字列でメモリに格納するCコードがあります。文字列の長さは10〜250バイトの範囲です。CのASCII文字列の圧縮
占有率を減らすために、各ストリングを個別に圧縮し、圧縮されたストリングの長さ(圧縮ストリングの長さ)を保存したいとします。
任意の文字列がいつでも読み書きできるため、個々の文字列よりも大きな範囲で圧縮したくありません。
これにはどのようなライブラリ/アルゴリズムが利用できますか?
ありがとうございました。 NickB
ASCII文字列を4バイト長の文字列でメモリに格納するCコードがあります。文字列の長さは10〜250バイトの範囲です。CのASCII文字列の圧縮
占有率を減らすために、各ストリングを個別に圧縮し、圧縮されたストリングの長さ(圧縮ストリングの長さ)を保存したいとします。
任意の文字列がいつでも読み書きできるため、個々の文字列よりも大きな範囲で圧縮したくありません。
これにはどのようなライブラリ/アルゴリズムが利用できますか?
ありがとうございました。 NickB
ZLib文字列に圧縮不能なデータが含まれている場合は、オーバーヘッドがほとんどなく、比較的高速で無料で簡単にCおよびC++プログラムに統合できます。
Zlibは確かにあなたの友人ですが、圧縮ヘッダーのオーバーヘッドが小さいため、圧縮が有効になる平均文字列長を検出するためにいくつかのテストを実行してください。
たとえば、20文字未満では、実際には圧縮された文字列が大きくなるため、長い文字列のみが圧縮されることがあります。
文字列が10-250バイトのときに4バイト長を使用する理由は、文字列ごとに3バイトを節約する1バイト長を使用します。
データはテキストのみ、つまり0-9 A-zまたは一部のサブセットですか?もしそうなら、それを再エンコードして、そのサブセットを使用し、1文字につき数ビットを保存します。
ハフマンエンコードセクションとlempel-zevセクションでhttp://gnosis.cx/publish/programming/compression_primer.htmlを見てください。
これは、あなたを始めてくれるはずです。
250バイト未満の短い文字列を個別に圧縮する場合、zlibまたはLZW圧縮手法がうまくいくかどうかはわかりません。重要な圧縮率が得られる前に、かなり大きな辞書を作成する必要があります。
おそらく、単純なハフマン符号化を固定の符号化ツリーで行うか、またはストリングのすべてのインスタンス間で共有することが考えられますか?また、80年代にメモリ制約のあるマイクロコンピュータで短い文字列を圧縮するために使用されたZSCIIエンコーディングを見たことがありますか?
ほとんどの圧縮アルゴリズムは、短い文字列では非常にうまく機能しません。 英語の短いテキスト文字列を圧縮するために設計された圧縮アルゴリズムがいくつかあります。 平文文字列内の任意のバイトを扱うことができますが、 などのバイトでは、「圧縮された」データが平文より長くなることがよくあります。 したがって、コンプレッサーは「圧縮不可能な」データを変更せずに保存し、このようなデータに「リテラル」フラグを設定することをお勧めします(Steve Jessopが示唆しているように)。
このような複数のストリングを使用する場合、\0
S(1バイト)と一緒にそれらを連結し、ルックアップ機能を使用して、各列(4または8バイトずつ)のためのポインタのオーバーヘッドを回避することができます。
#include <stdio.h>
static const char strings[]="hello\0world\0test";
char * nthstring(const char *s, unsigned n){
while(n--)
while(*s++)
;
return s;
}
int main(void) {
printf("%s\n",nthstring(strings,1));
return 0;
}
文字列の長さがUCHAR_MAX未満の場合しかし、あなたは(先頭にプラス1つの余分)の長さを格納するために、ゼロバイトのプレースホルダーを使用して検索を最適化することができます。これは、1つだけ追加のデータバイトがかかりますが、大幅に短縮できますルックアップ関数の条件付きジャンプとインクリメント
#include <stdio.h>
/* each "string" is prefixed with its octal length */
static const char lenstrings[]="\05hello\05world\04test";
char * ithstring(const char *s, unsigned n){
while(n--){
s+=*s+1;
}
return s;
}
int main(void) {
char *s=ithstring(lenstrings,1);
/* use the length because we don't have terminating \0 */
printf ("%.*s",(unsigned char)*s,s+1);
//write(1,s+1,(unsigned char)*s); //POSIX variation via <unistd.h>
return 0;
}
どちらのバリエーションでも、最も頻繁に必要な文字列を最初に保つ方が良いです。ただし、2番目の方法では、長さの区切り文字を圧縮された長さに調整する限り、圧縮データを使用することができます(データに最も適したものを選択 - David Cary's answerには実行可能なソリューションのリストがあります)。
注:あなたはおそらく(文字列の長さは256ではなく、65536バイトを超えた場合またはunsigned short
)それらのほとんどがしようとするとunsigned char
をする彼らのヘッダの長さフィールドを変更したいと思うでしょう、標準コンプレッサーのうち、最大の圧縮を取得するには大きなファイルの圧縮をサポートする(これは文字列ごとに3〜7バイトを節約できる)
そして、文字列が圧縮されているかどうかにフラグを立てるためにsizeフィールドの1ビットをスペアすることができます。各文字列を圧縮しようとします。それが小さくなったら、それを圧縮して保管してください。そうでない場合は、圧縮されていない状態で保管してください。これはおおまかにPKZIPが許すものです(そして、私は他の圧縮されたコンテナを想定しています。これはPKZIPは私が一度実装したものです)。残念ながら、サイズ範囲10-250では、8ビットアーキテクチャで「スペア」ビットを効率的に使用できません。 –