あなたは数えることによってあなたができる最善のことのアイデアを得ることができます。（私はstackoverflowがmath.stackexchangeのようなTeX方程式を許可することを望みます。とにかく...）
ceiling(log(Combination(2^32,1000)) / (8 * log(2))) = 2934
したがって、あなたが言うように、選択肢が均一に分散されている場合、その特定のケースで平均して期待できる最高の圧縮は2934バイトです。最適な比率は、4000バイトのエンコードされていない表現の73.35％です。
Combination(2^32,1000)は、圧縮アルゴリズムへの可能な入力の総数です。それらが均一に分散されている場合、最適なコーディングは、インデックスによって可能な各入力を識別する1つの巨大な整数です。各巨大整数値は、入力の1つを一意に識別します。巨大なテーブルのインデックスで入力を検索することを想像してみてください。 ceiling(log(Combination(2^32,1000)) / log(2))そのインデックス整数に必要なビット数です。
アップデート：
既製の圧縮ツールを使用して、理論上の最良のものに近づく方法を見つけました。並べ替え、デルタコーディングを適用し、そこから1を減算します（連続する個別の要素間のデルタは少なくとも1つであるため）。次に、すべての上位バイト、次に最上位バイトなどを書き出すのがコツです。デルタの上位バイトから1を引いたものはゼロになる傾向があるため、標準の圧縮ユーティリティが好む多くのゼロをグループ化します。 。また、次のバイトセットは低い値にバイアスされる傾向があります。
例（0..2 ^ 32-1からの1000の均一で別個のサンプル）では、それを実行すると平均3110バイト、通過するgzip -9と3098バイトになりますxz -9（xzは7zipと同じ圧縮LZMAを使用します）。これらは、理論上の最良の平均である2934にかなり近いものです。また、ヘッダーとトレーラーの両方で、gzipのオーバーヘッドは18バイト、xzのオーバーヘッドは24バイトです。したがって、理論上の最良値とのより公平な比較は、の場合は3092、の場合はgzip -93074になりxz -9ます。理論上の最良値よりも約5％大きい。
アップデート2：
順列の直接エンコードを実装し、平均2974バイトを達成しました。これは、理論上の最良値より1％強多いだけです。私はGNU多精度算術ライブラリを使用して、各順列のインデックスを巨大な整数にエンコードしました。エンコードとデコードの実際のコードを以下に示します。mpz_*関数がどの算術演算を実行しているかが名前からわからない場合がある関数にコメントを追加しました。
/* Recursively code the members in set[] between low and high (low and high
themselves have already been coded). First code the middle member 'mid'.
Then recursively code the members between low and mid, and then between mid
and high. */
local void combination_encode_between(mpz_t pack, mpz_t base,
const unsigned long *set,
int low, int high)
{
int mid;
/* compute the middle position -- if there is nothing between low and high,
then return immediately (also in that case, verify that set[] is sorted
in ascending order) */
mid = (low + high) >> 1;
if (mid == low) {
assert(set[low] < set[high]);
return;
}
/* code set[mid] into pack, and update base with the number of possible
set[mid] values between set[low] and set[high] for the next coded
member */
/* pack += base * (set[mid] - set[low] - 1) */
mpz_addmul_ui(pack, base, set[mid] - set[low] - 1);
/* base *= set[high] - set[low] - 1 */
mpz_mul_ui(base, base, set[high] - set[low] - 1);
/* code the rest between low and high */
combination_encode_between(pack, base, set, low, mid);
combination_encode_between(pack, base, set, mid, high);
}
/* Encode the set of integers set[0..num-1], where each element is a unique
integer in the range 0..max. No value appears more than once in set[]
(hence the name "set"). The elements of set[] must be sorted in ascending
order. */
local void combination_encode(mpz_t pack, const unsigned long *set, int num,
unsigned long max)
{
mpz_t base;
/* handle degenerate cases and verify last member <= max -- code set[0]
into pack as simply itself and set base to the number of possible set[0]
values for coding the next member */
if (num < 1) {
/* pack = 0 */
mpz_set_ui(pack, 0);
return;
}
/* pack = set[0] */
mpz_set_ui(pack, set[0]);
if (num < 2) {
assert(set[0] <= max);
return;
}
assert(set[num - 1] <= max);
/* base = max - num + 2 */
mpz_init_set_ui(base, max - num + 2);
/* code the last member of the set and update base with the number of
possible last member values */
/* pack += base * (set[num - 1] - set[0] - 1) */
mpz_addmul_ui(pack, base, set[num - 1] - set[0] - 1);
/* base *= max - set[0] */
mpz_mul_ui(base, base, max - set[0]);
/* encode the members between 0 and num - 1 */
combination_encode_between(pack, base, set, 0, num - 1);
mpz_clear(base);
}
/* Recursively decode the members in set[] between low and high (low and high
themselves have already been decoded). First decode the middle member
'mid'. Then recursively decode the members between low and mid, and then
between mid and high. */
local void combination_decode_between(mpz_t unpack, unsigned long *set,
int low, int high)
{
int mid;
unsigned long rem;
/* compute the middle position -- if there is nothing between low and high,
then return immediately */
mid = (low + high) >> 1;
if (mid == low)
return;
/* extract set[mid] as the remainder of dividing unpack by the number of
possible set[mid] values, update unpack with the quotient */
/* div = set[high] - set[low] - 1, rem = unpack % div, unpack /= div */
rem = mpz_fdiv_q_ui(unpack, unpack, set[high] - set[low] - 1);
set[mid] = set[low] + 1 + rem;
/* decode the rest between low and high */
combination_decode_between(unpack, set, low, mid);
combination_decode_between(unpack, set, mid, high);
}
/* Decode from pack the set of integers encoded by combination_encode(),
putting the result in set[0..num-1]. max must be the same value used when
encoding. */
local void combination_decode(const mpz_t pack, unsigned long *set, int num,
unsigned long max)
{
mpz_t unpack;
unsigned long rem;
/* handle degnerate cases, returning the value of pack as the only element
for num == 1 */
if (num < 1)
return;
if (num < 2) {
/* set[0] = (unsigned long)pack */
set[0] = mpz_get_ui(pack);
return;
}
/* extract set[0] as the remainder after dividing pack by the number of
possible set[0] values, set unpack to the quotient */
mpz_init(unpack);
/* div = max - num + 2, set[0] = pack % div, unpack = pack / div */
set[0] = mpz_fdiv_q_ui(unpack, pack, max - num + 2);
/* extract the last member as the remainder after dividing by the number
of possible values, taking into account the first member -- update
unpack with the quotient */
/* rem = unpack % max - set[0], unpack /= max - set[0] */
rem = mpz_fdiv_q_ui(unpack, unpack, max - set[0]);
set[num - 1] = set[0] + 1 + rem;
/* decode the members between 0 and num - 1 */
combination_decode_between(unpack, set, 0, num - 1);
mpz_clear(unpack);
}
mpz_*数値をファイルに書き込んで読み戻したり、メモリ内の指定した形式に数値をエクスポートしてインポートし直したりする機能があります。