enShannon 섀넌·파노 부호 deShannon 섀넌·파노 부호로부터의 복호
섀넌·파노 부호
long enShannon(unsigned char *code, long clen, unsigned char *text, long tlen);
섀넌·파노 부호로부터의 복호
long deShannon(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.
typedef struct {
long count; /* 출현 빈도 */
int chr; /* 문자 */
int len; /* 부호어의 비트수 */
unsigned char code[8]; /* 부호어 */
int info; /* 0:처리대, 1:Group 선두,2:처리필 */
} CELL;
#define CHAR_SIZE 256 /* 기호 종류 */
long enShannon(unsigned char *code, long clen, unsigned char *text, long tlen){
int i, j, k;
long c, len;
long max;
CELL *cell;
int cellsize;
long count[CHAR_SIZE+1];
int char2cell[CHAR_SIZE+1];
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};
CELL *getCode();
if (tlen <= 0 || clen <= 512) 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; i < CHAR_SIZE; i++) {
*code++ = (count[i] >> 8) & 0xff;
*code++ = count[i] & 0xff;
}
count[CHAR_SIZE] = 1; /* EOF */
/* 부호어를 얻는다 */
if ((cell = getCode(&cellsize, count)) == NULL) return -1L;
/* 문자를 부호어와 대응시킨다 */
for (i = 0; i < cellsize; i++) char2cell[cell[i]. chr] = i;
/* 각 문자를 encode */
for (c = 0, i = 0, len = 512; ; c++) {
k = (c == tlen) ? 256 : text[c];
k = char2cell[k];
/* 부호어를 출력 */
for (j = 0; j < cell[k]. len; j++) {
if (cell[k]. code[j>>3] & bit1[j&7]) *code |= bit1[i];
else *code &= bit0[i];
if (++i == 8) {
code++;
if (++len > clen) {
free(cell);
return -1L;
}
i = 0;
}
}
if (c == tlen)
break;
}
free(cell);
if (i > 0)
len++;
return (len > clen) ? -1L : len;
}
long deShannon(unsigned char *text, long tlen, unsigned char *code, long clen){
int i, j, k;
long c, len;
CELL *cell;
int cellsize;
long count[CHAR_SIZE+1];
# define NODE_SIZE (2*CHAR_SIZE+2)
struct { int chr, left, right; } node[NODE_SIZE];
int root, freeNode;
static unsigned char bit1[8] = {128,64,32,16,8,4,2,1};
CELL *getCode();
if (clen <= 512)
return -1L;
/* 각 문자의 출현 빈도를 세트 */
for (i = 0; i < CHAR_SIZE; i++)
count[i] = 0;
for (i = 0; i < 256; i++) {
count[i] = *code++;
count[i] = (count[i] << 8) | *code++;
}
/* EOF */
count[256] = 1;
/* 부호어를 얻는다 */
if ((cell = getCode(&cellsize, count)) == NULL) return -1L;
/* 부호어에 대응하는 부호나무를 만든다 */
for (i = 0; i < NODE_SIZE; i++) {
node[i]. chr = NODE_SIZE;
node[i]. left = node[i]. right = 0;
}
root = 0; freeNode = 1;
for (i = 0; i < cellsize; i++) {
for (j = 0, k = root; j < cell[i]. len; j++) {
if (cell[i]. code[j>>3] & bit1[j&7]) {
if (node[k]. right == 0) node[k]. right = freeNode++;
k = node[k]. right;
} else {
if (node[k]. left == 0) node[k]. left = freeNode++;
k = node[k]. left;
}
}
node[k]. chr = cell[i]. chr;
}
/* 복호화 */
for (i = 0, len = 0, c = 512; ; ) {
/* 부호어에 대응하는 문자 노드를 얻는다 */
k = root;
do {
k = (*code & bit1[i]) ? node[k]. right : node[k]. left;
if (++i == 8) {
code++;
if (++c > clen) return -1L;
i = 0;
}
} while (node[k]. chr > CHAR_SIZE);
if (node[k]. chr == CHAR_SIZE) break;
if (++len > tlen) {
free(cell);
return -1L;
}
*text++ = node[k]. chr;
}
free(cell);
return len;
}
/* 부호어를 얻는다 */
static CELL *getCode(int *cellsize, long *count)
{
int i, j, k;
CELL *cell;
int size;
long sum, half;
int left, mid, right;
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};
/* 그룹 크기의 결정 */
for (i = 0, size = 0; i <= CHAR_SIZE; i++) if (count[i] > 0) size++;
if ((cell = (CELL *) malloc(sizeof(CELL) *size)) == NULL) return NULL;
/* 문자의 출현 빈도를 내림차순에 소트 */
for (i = 0, j = 0; i <= CHAR_SIZE; i++)
if (count[i] > 0) {
cell[j]. count = count[i];
cell[j]. chr = i;
cell[j]. len = 0;
cell[j]. info = 0;
j++;
}
for (i = 0; i < size - 1; i++) {
k = i;
for (j = i+1; j < size; j++)
if (cell[j]. count > cell[k]. count) k = j;
if (k ! = i) {
long tcount = cell[k]. count;
int tchr = cell[k]. chr;
cell[k]. count = cell[i]. count;
cell[i]. count = tcount;
cell[k]. chr = cell[i]. chr;
cell[i]. chr = tchr;
}
}
cell[0]. info = 1;
/* 그룹을 세분비율 해, 부호어를 얻는다 */
for ( ; ; ) {
/* 그룹의 선두를 찾아낸다 */
for (i = 0, left = -1; i < size; i++)
if (cell[i]. info == 1) {
left = i;
break;
}
if (left < 0) break;
/* 그룹의 말미를 찾아낸다 */
for (i = left + 1, right = size - 1; i < size; i++)
if (cell[i]. info > 0) {
right = i - 1;
break;
}
/* 그룹내의 출현 빈도의 화 */
for (i = left, sum = 0; i <= right; i++) sum += cell[i]. count;
/* 그룹의 분할 위치 */
for (mid = left, half = 0; mid < right && half < sum/2; mid++)
half += cell[mid]. count;
/* 부호어의 추가 */
for (i = left; i <= right; i++) {
if (i>3]&=bit0[cell[i]. len&7];
else cell[i]. code[cell[i]. len>>3]|=bit1[cell[i]. len&7];
cell[i]. len++;
}
if (mid == left + 1) cell[left]. info = 2;
cell[mid]. info = (mid == right) ? 2 : 1;
}
*cellsize = size;
return cell;
}
섀넌·파노 부호는, 최초로 고안 된 부호이지만, 항상 최소의 평균 부호장을 얻을 수 있는허프만 코딩에는 압축 성능이 뒤떨어지기 (위해)때문에, 그 역사적 의의로부터 정보이론의 교과서에 취해 인상라고 있지만, 실제의 데이터 압축 알고리즘으로서는, 거의 사용되고 있고 없다.
부호어를 이하와 같이 구성할 수 있다.
encode 프로그램에서는, 텍스트를 2회 주사 한다. 1회째로는 각 기호(문자)의 출현 빈도를 조사한 다음, 부호어를 만든다. 또 복호 할 수 있도록(듯이), 각 기호의 출현 빈도를 부호의 일부로서 출력한다. 2번째의 주사에서는, 실제로 각 문자를 encode 한다.
출력 부호의 포맷은, 선두에 1 문자 2바이트씩의 출현 빈도, 합계 512바이트의 헤더부와 그 후에 계속되는 부호어열로부터 된다.
덧붙여 부호어열의 종료를 나타내기 위해서(때문에), 출현 빈도가 1의 EOF 기호(코드 256) 에 대응하는 부호어를 기입한다.