enArith 산술 부호 deArith 산술 부호로부터의 복호
산술 부호
long enArith(unsigned char *code, long clen,
unsigned char *text, long tlen);
산술 부호로부터의 복호
long deArith(unsigned char *text, long tlen,
unsigned char *code, long clen);
산술 부호 함수에 대해
code (입출력) 산술 부호를 격납하는 배열
clen (입력) 배열 code의 길이
text (입력) 텍스트를 격납하는 배열
tlen (입력) 배열 text의 길이
산술 부호로부터의 복호 함수에 대해
text (입출력) 텍스트를 격납하는 배열
tlen (입력) 배열 text의 길이
code (입력) 산술 부호를 격납하는 배열
clen (입력) 배열 code의 길이
산술 부호 함수에 대해
산술 부호의 길이. encode에 실패했을 때는 -1L.
산술 부호로부터의 복호 함수에 대해
텍스트의 길이. 복호에 실패했을 때는 -1L.
#define CHAR_SIZE 256 /* 문자 종류 */
#define Q 0xffffffffL
#define Q1 0x40000000L
#define Q2 0x80000000L
#define Q3 0xC0000000L
long enArith(unsigned char *code, long clen, unsigned char *text, long tlen){
int i, k;
long c, len;
int comp;
long max;
long sum, t;
long count[CHAR_SIZE+2];
unsigned long L, R, q, r;
long outbit();
if (tlen <= 0 || clen <= 2*CHAR_SIZE)
return -1L;
/* 각 문자의 출현 빈도를 계산 */
for (i = 0; i < CHAR_SIZE; i++)
count[i] = 0;
for (c = 0; c < tlen; c++)
count[text[c]]++;
/* 최대 출현 빈도의 값이 2바이트를 넘지 않게 조정한다 */
for (i = 0, max = 0; i < CHAR_SIZE; i++)
if (count[i] > max) max = count[i];
if ((k = max/0x10000L) > 0)
for (i = 0, k++; i < CHAR_SIZE; i++)
if (count[i] > 0) {
count[i] /= k;
if (count[i] == 0)
count[i] = 1;
}
/* 각 문자의 출현 빈도를 출력 */
for (i = 0, len = 0; i < CHAR_SIZE; i++) {
code[len++] = (count[i] >> 8) & 0xff;
code[len++] = count[i] & 0xff;
}
/* EOF */
count[CHAR_SIZE] = 1;
/* 누적 빈도로 고친다 */
t = count[0];
count[0] = 0;
for (i = 1; i <= CHAR_SIZE+1; i++) {
long tmp = count[i];
count[i] = count[i-1] + t;
t = tmp;
}
sum = count[CHAR_SIZE+1];
/* 각 문자를 encode */
L = 0; R = Q;
for (c = 0, comp = 0, i = 0; ; c++) {
k = (c == tlen) ? CHAR_SIZE : text[c];
/* 구간을 갱신 */
q = (R - L) / sum;
r = (R - L) % sum;
R = L + q*count[k+1] + (r*count[k+1]) /sum - 1;
L = L + q*count[k] + (r*count[k]) /sum + 1;
/* 비트를 출력 */
while (R - L <= Q1) {
if (R < Q2) {
len = outbit(0, code, len, comp, &i);
if (len > clen) return -1L;
comp = 0;
} else if (L >= Q2) {
len = outbit(1, code, len, comp, &i);
if (len > clen) return -1L;
comp = 0;
L -= Q2; R -= Q2;
} else if (Q1 <= L && R < Q3) {
comp++;
L -= Q1; R -= Q1;
}
L <<= 1; R <<= 1;
}
if (k == CHAR_SIZE) break;
}
if (L <= Q1) {
len = outbit(0, code, len, comp, &i);
len = outbit(1, code, len, 0, &i);
} else if (L <= Q2) {
len = outbit(1, code, len, comp, &i);
len = outbit(0, code, len, 0, &i);
} else {
len = outbit(1, code, len, comp, &i);
len = outbit(1, code, len, 0, &i);
}
if (i > 0) {
while (i > 0) outbit(0, code, len, 0, &i);
len++;
}
return (len > clen) ? -1L : len;
}
static long outbit(int bit, unsigned char *code, long len,
int comp, int *i)
{
static unsigned char bit0[8] = {~128,~64,~32,~16,~8,~4,~2,~1};
static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1};
if (bit) code[len] |= bit1[*i];
else code[len] &= bit0[*i];
if (++(*i) == 8) {
len++;
*i = 0;
}
while (comp--) {
if (bit) code[len] &= bit0[*i];
else code[len] |= bit1[*i];
if (++(*i) == 8) {
len++;
*i = 0;
}
}
return len;
}
long deArith(unsigned char *text, long tlen,
unsigned char *code, long clen)
{
unsigned char c;
int i, k;
long j, len;
long sum, t;
long count[CHAR_SIZE+2];
unsigned long L, R, V, q, r;
static unsigned char bit1[8] = {128,64,32,16,8,4,2,1};
if (clen <= 2*CHAR_SIZE) return -1L;
/* 각 문자의 출현 빈도를 세트 */
for (i = 0; i < CHAR_SIZE; i++) count[i] = 0;
for (i = 0; i < CHAR_SIZE; i++) {
count[i] = *code++;
count[i] = (count[i] << 8) | *code++;
}
/* EOF */
count[CHAR_SIZE] = 1;
/* 누적 빈도로 고친다 */
t = count[0];
count[0] = 0;
for (i = 1; i <= CHAR_SIZE+1; i++) {
long tmp = count[i];
count[i] = count[i-1] + t;
t = tmp;
}
sum = count[CHAR_SIZE+1];
/* 복호화 */
L = 0; R = Q; V = 0;
for (i = 0, j = 2*CHAR_SIZE; i < 4; i++) {
V <<= 8;
if (j++ < clen) V |= *code++;
}
c = (j <= clen) ? *code : 0;
for (i = 0, len = 0; ; ) {
/* 구간을 갱신 */
q = (R - L) / sum;
r = (R - L) % sum;
for (k = 0; k <= CHAR_SIZE; k++) {
R = L + q*count[k+1] + (r*count[k+1]) /sum;
if (R > 0 && --R >= V) break;
}
L = L + q*count[k] + (r*count[k]) /sum + 1;
if (k == CHAR_SIZE) break;
*text++ = k;
if (++len > clen) return -1L;
/* 구간의 쉬프트 */
while (R - L <= Q1) {
if (R < Q2) ;
else if (L >= Q2) {
L -= Q2; R -= Q2; V -= Q2;
} else if (Q1 <= L && R < Q3) {
L -= Q1; R -= Q1; V -= Q1;
}
L <<= 1; R <<= 1; V <<= 1;
if (c & bit1[i]) V |= 1;
if (++i == 8) {
c = (j++ <= clen) ? *++code : 0;
i = 0;
}
}
}
return len;
}
산술 부호는 폭넓게 연구가 이루어지게 된 것은 1970년대의 후반이며, 일반적으로는 그다지 알려지지 않은 것이 현상이다.
산술 부호는 이론상, 평균 부호장이 엔트로피가 된다. 즉, 평균 부호장에 관계해서는, 산술 부호는 최적 부호이다. 이것에 대해서, 잘 알려져 있다 허프만 코딩은 그 평균 부호장은 반드시 엔트로피가 되지 않는다. 그러나 산술 부호에 대해서는, encode때, 무한자리수의 실수 연산이 이론상 필요하므로, 실용 상유한형의 정수로 근사 하는 궁리가 필요 일 것이다.
산술 부호는 입력 기호(문자)의 출현 확률에 근거해 단위 구간 [0, 1)(좌단이 0 (을)를 포함해, 우단이 1을 포함하지 않는 구간)을 순서대로 축소해, 최종적으로 얻을 수 있던 구간내의 값을 부호로 하는 부호이다. 허프만 코딩에서는 출현 확률의 큰 기호에 짧다 부호어를 할당하는데 대해, 산술 부호에서는, 출현 확률의 큰 문자에 폭의 큰 구간을 배분한다.