分類と序数
まず、数値 $x$ を固定桁数（ビット幅 $w$）の２進数にして、「1」の個数 $b$ で分類します。
すると、分類ごとに、２進数の一覧ができます。
次に、２進数の一覧は、昇順で並べるようにします。
結果、「 $n$：一覧での番号（序数）」と「 $x$：２進数の値」の対 $\{n,x\}$ を作ることができます。
「1」の個数で分類
ビット幅 $w$ のデータ $x$ から、各ビットの "1" を数えて
1 が 0 個：$b=0$
1 が 1 個：$b=1$
...
1 が w 個：$b=w$
として、$(w+1)$ 種類に分類します。
$b$ は、プログラムでは
$b = bitcount \left( x \right)$
などですが、数式にすると
$bit \left( d, k \right) = \lfloor 2^{-k} d \rfloor \ mod\ 2$
$b = \sum_{k=0}^{w-1}{bit \left( x, k \right)}$
こんな感じ？
各ビットの "1" を数える関数 $bitcount \left( x \right)$ の例
int bitcount(unsigned int x) {
int b = 0;
while (x != 0) {
b += (x & 1);
x >>= 1;
}
return b;
}
x86/64 の POPCNT 命令が使えれば、１命令なのに...
序数 n
分類 $\left( w,b \right)$ での一覧にて、２進数の値 $x$ に序数 $n$ を 0 から割り当てます。
具体例がわかりやすいので、例示します。
$w=1$ の場合
| $n$ ＼ $b$ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 計 | 1 | 1 |
$w=2$ の場合
| $n$ ＼ $b$ | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 00 | 01 | 11 |
| 1 | 10 | ||
| 計 | 1 | 2 | 1 |
$w=3$ の場合
| $n$ ＼ $b$ | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 000 | 001 | 011 | 111 |
| 1 | 010 | 101 | ||
| 2 | 100 | 110 | ||
| 計 | 1 | 3 | 3 | 1 |
$w=4$ の場合
| $n$ ＼ $b$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0000 | 0001 | 0011 | 0111 | 1111 |
| 1 | 0010 | 0101 | 1011 | ||
| 2 | 0100 | 0110 | 1101 | ||
| 3 | 1000 | 1001 | 1110 | ||
| 4 | 1010 | ||||
| 5 | 1100 | ||||
| 計 | 1 | 4 | 6 | 4 | 1 |
分類 $\left( w,b \right)$ に含まれる「計：値の個数 $l$」は、二項係数
$l = C(w,b) = \frac{w!}{b!(w-b)!}$
になっています。
二項係数の参照表
二項係数は、パスカルの三角形
| 1 | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | |||||||||
| 1 | 2 | 1 | ||||||||
| 1 | 3 | 3 | 1 | |||||||
| 1 | 4 | 6 | 4 | 1 | ||||||
| 1 | 5 | 10 | 10 | 5 | 1 |
を左詰にして、参照表 $C(w,b)$
| w ＼ b | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 1 | |||||
| 1 | 1 | 1 | ||||
| 2 | 1 | 2 | 1 | |||
| 3 | 1 | 3 | 3 | 1 | ||
| 4 | 1 | 4 | 6 | 4 | 1 | |
| 5 | 1 | 5 | 10 | 10 | 5 | 1 |
| ... |
を作ります。これで階乗の計算が不要になります。
データ x と序数 n の変換
ビット幅 $w$ と分類 $b$ を共通項として
- データ $x$ から序数 $n$ を得る
- 序数 $n$ からデータ $x$ を得る
を考えます。
データ x から序数 n を得る
処理内容
データ $x$ の最上位ビットから、各ビットに対する 変則重み の和で求めます。
初期状態は
序列 ： $n' = 0$
ビット幅： $w' = w$
$1$ の個数： $b' = b$
とします。
$n',w',b'$ は変数です。
処理は、最大 $\left( w-1 \right)$ 回のループになります。
ループの中身は
$bit(x, w'-1) \ne 0$
の場合は
$n'$ に $C \left( w'-1,\ b' \right)$ を加える
$b'$ を $1$ 減らす
を実行します。
$w'$ のデクリメントがあります。
ループの終了条件は
$b' = 0$
または
$b' = w'$
です。
$0$ 回ループもあり得ます。
例： w=4, b=2 の場合
初期状態は
| $x$ | $b'$ | $n'$ | |
|---|---|---|---|
| 0011 | $2$ | $0$ | |
| 0101 | $2$ | $0$ | |
| 0110 | $2$ | $0$ | |
| 1001 | $2$ | $0$ | |
| 1010 | $2$ | $0$ | |
| 1100 | $2$ | $0$ |
$w' = 4$
です。最初のループで
| $x_3$ | $x_{210}$ | $b'$ | $n'$ | $n'$ | |
|---|---|---|---|---|---|
| 0 | 011 | $2$ | $0$ | $0$ | |
| 0 | 101 | $2$ | $0$ | $0$ | |
| 0 | 110 | $2$ | $0$ | $0$ | |
| 1 | 001 | $1$ | $3$ | $C \left( 3,2 \right)$ | |
| 1 | 010 | $1$ | $3$ | $C \left( 3,2 \right)$ | |
| 1 | 100 | $1$ | $3$ | $C \left( 3,2 \right)$ |
$w' = 3$
に更新されます。次のループでは
| $x_3$ | $x_2$ | $x_{10}$ | $b'$ | $n'$ | $n'$ | ||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 11 | $2$ | $0 = 0 + 0$ | $0 + 0$ | 終 | |
| 0 | 1 | 01 | $1$ | $1 = 0 + 1$ | $0 + C \left( 2,2 \right)$ | ||
| 0 | 1 | 10 | $1$ | $1 = 0 + 1$ | $0 + C \left( 2,2 \right)$ | ||
| 1 | 0 | 01 | $1$ | $3 = 3 + 0$ | $C \left( 3,2 \right) + 0$ | ||
| 1 | 0 | 10 | $1$ | $3 = 3 + 0$ | $C \left( 3,2 \right) + 0$ | ||
| 1 | 1 | 00 | $0$ | $5 = 3 + 2$ | $C \left( 3,2 \right) + C \left( 2,1 \right)$ | 終 |
$w' = 2$
に更新されます。$n'$ が $0$ か $5$ の場合では、ここで終了です。次が最後のループで
| $x_3$ | $x_2$ | $x_1$ | $x_0$ | $b'$ | $n'$ | $n'$ | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | $_1$ | $_1$ | $_2$ | $0 = 0 + 0$ | $0 + 0$ | |
| 0 | 1 | 0 | $_1$ | $1$ | $1 = 0 + 1 + 0$ | $0 + C \left( 2,2 \right) + 0$ | |
| 0 | 1 | 1 | $_0$ | $0$ | $2 = 0 + 1 + 1$ | $0 + C \left( 2,2 \right) + C \left( 1,1 \right)$ | |
| 1 | 0 | 0 | $_1$ | $1$ | $3 = 3 + 0 + 0$ | $C \left( 3,2 \right) + 0 + 0$ | |
| 1 | 0 | 1 | $_0$ | $0$ | $4 = 3 + 0 + 1$ | $C \left( 3,2 \right) + 0 + C \left( 1,1 \right)$ | |
| 1 | 1 | $_0$ | $_0$ | $_0$ | $5 = 3 + 2$ | $C \left( 3,2 \right) + C \left( 2,1 \right)$ |
$w' = 1$
に更新されて、$n=n'$ が得られます。
序数 n からデータ x を得る
データ $x$ に対応する最上位ビットから、各ビットに対する 変則重み を使って、$x$ の各ビットを求めます。
初期状態は
データ ： $x' = 0$
序列 ： $n' = n$
ビット幅： $w' = w$
$1$ の個数： $b' = b$
とします。
$x',n',w',b'$ は変数です。
処理は、最大 $\left( w-1 \right)$ 回のループになります。
ループの中身は
$n' \ge C(w'-1,b')$
の場合に
$n'$ から $C \left( w'-1,\ b' \right)$ を引く
$b'$ を $1$ 減らす
$x'$ に $2^{w'-1}$ を加える
を実行します。
$w'$ のデクリメントがあります。
ループの終了条件は
$b' = 0$
または
$b' = w'$
です。$0$ 回ループもあり得ます。
最後に $b'$ の残り追加
$x'$ に $2^{b'}-1$ を加える
で完了です。
「データ x から序数 n を得る」に対して、「各ビット」と「対応する二項係数」を入れ替えた処理になります。
例： w=4, b=2 の場合
初期状態は
| $n$ | $n'$ | $b'$ | $x'$ | |
|---|---|---|---|---|
| 0 | 0 | 2 | 0000 | |
| 1 | 1 | 2 | 0000 | |
| 2 | 2 | 2 | 0000 | |
| 3 | 3 | 2 | 0000 | |
| 4 | 4 | 2 | 0000 | |
| 5 | 5 | 2 | 0000 |
$w' = 4$
です。最初のループで
| $n$ | $n'$ | $b'$ | $x'_3$ | $x'_{210}$ | $n'$ の更新 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 2 | 0 | 000 | $0$ | |
| 1 | 1 | 2 | 0 | 000 | $0$ | |
| 2 | 2 | 2 | 0 | 000 | $0$ | |
| 3 | 0 | 1 | 1 | 000 | $C\left( 3,2 \right) = 3$ | |
| 4 | 1 | 1 | 1 | 000 | $C\left( 3,2 \right) = 3$ | |
| 5 | 2 | 1 | 1 | 000 | $C\left( 3,2 \right) = 3$ |
$w' = 3$
に更新されます。次のループでは
| $n$ | $n'$ | $b'$ | $x'_3$ | $x'_2$ | $x'_{10}$ | $n'$ の更新 | ||
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 2 | 0 | 0 | 00 | $0$ | 終 | |
| 1 | 0 | 1 | 0 | 1 | 00 | $C\left( 2,2 \right) = 1$ | ||
| 2 | 1 | 1 | 0 | 1 | 00 | $C\left( 2,2 \right) = 1$ | ||
| 3 | 0 | 1 | 1 | 0 | 00 | $0$ | ||
| 4 | 1 | 1 | 1 | 0 | 00 | $0$ | ||
| 5 | 0 | 0 | 1 | 1 | 00 | $C\left( 2,1 \right) = 2$ | 終 |
$w' = 2$
に更新されます。$n$ が $0,5$ の場合では、ここでループ終了条件に合致します。次が最後のループで
| $n$ | $n'$ | $b'$ | $x'_3$ | $x'_2$ | $x'_1$ | $x'_0$ | $n'$ の更新 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 2 | 0 | 0 | 0 | 0 | $0$ | |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | $C\left( 1,1 \right) = 1$ | |
| 2 | 1 | 1 | 0 | 1 | 0 | 0 | $0$ | |
| 3 | 0 | 1 | 1 | 0 | 0 | 0 | $0$ | |
| 4 | 0 | 0 | 1 | 0 | 1 | 0 | $C\left( 1,1 \right) = 1$ | |
| 5 | 0 | 0 | 1 | 1 | 0 | 0 | $0$ |
$w' = 1$
に更新されます。ループを抜けると、$b'$ のビット数で $x'$ を更新して
| $n$ | $n'$ | $b'$ | $x'_3$ | $x'_2$ | $x'_1$ | $x'_0$ | $x'$ の更新 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 2 | 0 | 0 | 1 | 1 | 11 | |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 00 | |
| 2 | 1 | 1 | 0 | 1 | 0 | 1 | 01 | |
| 3 | 0 | 1 | 1 | 0 | 0 | 1 | 01 | |
| 4 | 0 | 0 | 1 | 0 | 1 | 0 | 00 | |
| 5 | 0 | 0 | 1 | 1 | 0 | 0 | 00 |
となって、$x=x'$ が得られます。
サンプルプログラム
#include <stdio.h>
#include <stdlib.h>
static unsigned int **wbtab = NULL; /* 二項係数の参照用テーブル */
/* 二項係数のテーブルを用意する */
void make_wbtab(unsigned int w) {
unsigned int i, j;
if (wbtab != NULL)
return;
wbtab = (unsigned int **) malloc((w+1) * sizeof(unsigned int *));
for (i = 0; i <= w; i++)
wbtab[i] = (unsigned int *) malloc((i+1) * sizeof(unsigned int));
wbtab[0][0] = 1;
for (i = 1; i <= w; i++) {
wbtab[i][0] = 1;
for (j = 1; j < i; j++)
wbtab[i][j] = wbtab[i-1][j-1] + wbtab[i-1][j];
wbtab[i][i] = 1;
}
}
/* 二項係数 C(w,b) をテーブル参照で得る */
unsigned int comb(unsigned int w, unsigned int b) {
return wbtab[w][b];
}
/* 各ビットの "1" を数える */
int bitcount(unsigned int x) {
int b = 0;
while (x != 0) {
b += (x & 1);
x >>= 1;
}
return b;
}
/* データ x から序数 n を得る */
unsigned int wb_x2n(unsigned int w, unsigned int b, unsigned int x) {
unsigned int n = 0;
while (b && b < w) {
w -= 1;
if ((x & (1 << w)) != 0) {
n += comb(w, b); /* C(w,b) */
b -= 1;
}
}
return n;
}
/* 序数 n からデータ x を得る */
unsigned int wb_n2x(unsigned int w, unsigned int b, unsigned int n) {
unsigned int x = 0, c;
unsigned int m = 1 << (w - 1);
while (b && b < w) {
w -= 1;
c = comb(w, b); /* C(w,b) */
if (n >= c) {
x |= m;
n -= c;
b -= 1;
}
m >>= 1;
}
x |= (1 << b) - 1;
return x;
}
/*
* テスト用
*/
/* 分類を変更せず、次のデータへ */
static unsigned int wb_next(unsigned int x) {
unsigned int m, n, o;
m = x & (-x); /* 処理の開始位置を求める */
o = 1;
for (;;) {
n = m << 1;
if ((x & n) == 0)
return (x ^ m ^ n);
x ^= (m ^ o);
m <<= 1;
o <<= 1;
}
}
/* ２進数での出力 */
static void print_bin(unsigned int w, unsigned int x) {
unsigned int k = w;
while (k-- != 0)
putchar('0' + ((x >> k) & 1));
}
/* 分類(w,b) の一覧出力 */
static void print_wb(unsigned int w, unsigned int b) {
unsigned int m, n;
unsigned int p, x;
m = (1 << w) - 1;
x = (1 << b) - 1;
n = 0;
do {
printf("%3d: ", n++);
print_bin(w, x);
printf("\n");
p = x;
x = wb_next(p) & m;
} while (p < x);
}
/* ビット幅 w での全体出力 */
void print_w(unsigned int w) {
unsigned int b;
for (b = 0; b <= w; b++) {
printf("%d,%d ------\n", w, b);
print_wb(w, b);
}
}
/* make_wbtab(w) の確認用 */
void print_wbtab(unsigned int w) {
unsigned int i,j;
make_wbtab(w);
for (i = 0; i <= w; i++) {
printf("%2d:", i);
for (j = 0; j <= i; j++)
printf(" %2d", comb(i, j));
printf("\n");
}
}
/* wb_x2n の動作確認用 */
void print_wb_x2n(unsigned int w, unsigned int b) {
unsigned int n, x;
unsigned int i, wbn;
make_wbtab(w);
wbn = comb(w, b);
x = (1 << b) - 1;
for (i = 0; i < wbn; i++) {
n = wb_x2n(w, b, x);
printf("%2d: %2d <- ", i, n);
print_bin(w, x);
printf("\n");
x = wb_next(x);
}
}
/* wb_n2x の動作確認用 */
void print_wb_n2x(unsigned int w, unsigned int b) {
unsigned int n, x, xx;
unsigned int wbn;
make_wbtab(w);
wbn = comb(w, b);
x = (1 << b) - 1;
for (n = 0; n < wbn; n++) {
xx = wb_n2x(w, b, n);
print_bin(w, x);
printf(": ");
print_bin(w, xx);
printf(" <- %2d\n", n);
x = wb_next(x);
}
}
4,0 ------
0: 0000
4,1 ------
0: 0001
1: 0010
2: 0100
3: 1000
4,2 ------
0: 0011
1: 0101
2: 0110
3: 1001
4: 1010
5: 1100
4,3 ------
0: 0111
1: 1011
2: 1101
3: 1110
4,4 ------
0: 1111
0: 1
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
0: 0 <- 0011
1: 1 <- 0101
2: 2 <- 0110
3: 3 <- 1001
4: 4 <- 1010
5: 5 <- 1100
0011: 0011 <- 0
0101: 0101 <- 1
0110: 0110 <- 2
1001: 1001 <- 3
1010: 1010 <- 4
1100: 1100 <- 5
「圧縮されたデータは偏っているので再圧縮できそう」では、この変換を応用して、使用する数値の範囲を絞る方法を試していました。 $w$ は $4096$ より大きい値を試しています。
※ $x$ と $n$ を直接変換するテーブルを用いると、$x$ と $n$ の変換は高速化できます。しかし、ビット幅 $w$ が $30$ 程度より大きくなると、個人 PC では RAM 容量の問題が発生します。