enFGK FGK 부호 deFGK FGK 부호로부터의 복호
FGK 부호
long enFGK(unsigned char *code, long clen,
unsigned char *text, long tlen);
FGK 부호로부터의 복호
long deFGK(unsigned char *text, long tlen,
unsigned char *code, long clen);
FGK 부호 함수에 대해
code (입출력) FGK 부호를 격납하는 배열
clen (입력) 배열 code의 길이
text (입력) 텍스트를 격납하는 배열
tlen (입력) 배열 text의 길이
FGK 부호로부터의 복호 함수에 대해
text (입출력) 텍스트를 격납하는 배열
tlen (입력) 배열 text의 길이
code (입력) FGK 부호를 격납하는 배열
clen (입력) 배열 code의 길이
FGK 부호 함수에 대해
FGK 부호의 길이. encode에 실패했을 때는 -1L.
FGK 부호로부터의 복호 함수에 대해
텍스트의 길이. 복호에 실패했을 때는 -1L.
typedef struct {
int chr; /* 문자 */
long count; /* 자 노드의 출현 빈도의 화 */
int parent; /* 친노드에 */
int left; /* 좌측의 아이 노드에 */
int right; /* 우측의 아이 노드에 */
} NODE;
#define ROOT 0 /* 루트 */
#define EOF_NODE 1 /* EOF 노드 */
#define CHAR_SIZE 256
#define NODE_SIZE (2*CHAR_SIZE+2) /* 노드의 최대 개수 */
long enFGK(unsigned char *code, long clen,
unsigned char *text, long tlen)
{
int i, j, k;
long c, len;
int curChar;
int zeroNode, thisNode, maxid;
int node2id[NODE_SIZE]; /* 노드로부터 그 노드 번호 */
int char2node[CHAR_SIZE];
NODE node[NODE_SIZE]; int freeNode;
char bit[NODE_SIZE]; char *bitp;
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 (tlen <= 0) return -1L;
for (i = 0; i < CHAR_SIZE; i++) char2node[i] = 0;
/* 초기 하프맨나무 */
zeroNode = 2;
node[2]. count = 0;
node[2]. parent = ROOT;
node[EOF_NODE]. count = 1;
node[EOF_NODE]. parent = ROOT;
node[ROOT]. count = 0x7FFFFFFFL;
node[ROOT]. parent = 0;
node[ROOT]. left = zeroNode;
node[ROOT]. right = EOF_NODE;
node2id[zeroNode] = 0;
node2id[EOF_NODE] = 1;
node2id[ROOT] = 2;
freeNode = 3;
/* 각 문자를 encode */
for (i = 0, c = 0, len = 0, bitp = bit; ; c++) {
/* 입력 문자에 대응하는 노드 */
if (c >= tlen) thisNode = EOF_NODE;
else if ((thisNode = char2node[curChar = text[c]]) == 0) {
thisNode = zeroNode;
for (j = 7; j >= 0; j--) *bitp++ = curChar & bit1[j];
}
/* 부호어를 얻는다 */
k = thisNode;
do {
int parent = node[k]. parent;
*bitp++ = (node[parent]. left == k) ? 0 : 1;
k = parent;
} while (k ! = ROOT);
/* 역순서에 출력 */
do {
if (*--bitp) *code |= bit1[i];
else *code &= bit0[i];
if (++i == 8) {
code++;
if (++len > clen) return -1L;
i = 0;
}
} while (bitp ! = bit);
if (c == tlen) break; /* EOF */
/* 하프맨나무를 갱신 */
while (thisNode ! = ROOT) {
if (thisNode == zeroNode) {
for (j = 0; j < freeNode; j++) node2id[j] += 2;
node[zeroNode]. left = freeNode;
node[freeNode]. count = 0;
node[freeNode]. parent = zeroNode;
node2id[freeNode] = 0;
freeNode++;
node[zeroNode]. right = freeNode;
node[freeNode]. count = 1;
node[freeNode]. parent = zeroNode;
node2id[freeNode] = 1;
char2node[curChar] = freeNode; /* 신문자 */
freeNode++;
thisNode = zeroNode;
zeroNode = freeNode - 2;
} else {
if (node[thisNode]. count == 1 &&
node[k = node[thisNode]. parent]. count == 1) {
/* 0-노드의 형제 */
for (j = 0, maxid = thisNode; j < freeNode; j++)
if (node[j]. count == 1 && j ! = k &&
node2id[j] > node2id[maxid]) maxid = j;
} else {
for (j = 0, maxid = thisNode; j < freeNode; j++)
if (node[thisNode]. count == node[j]. count &&
node2id[j] > node2id[maxid]) maxid = j;
}
if (maxid ! = thisNode) {
int maxidP = node[maxid]. parent;
int thisP = node[thisNode]. parent;
int id = node2id[maxid];
if (node[maxidP]. left == maxid)
node[maxidP]. left = thisNode;
else node[maxidP]. right = thisNode;
if (node[thisP]. left == thisNode)
node[thisP]. left = maxid;
else node[thisP]. right = maxid;
node[maxid]. parent = thisP;
node[thisNode]. parent = maxidP;
node2id[maxid] = node2id[thisNode];
node2id[thisNode] = id;
}
node[thisNode]. count++;
thisNode = node[thisNode]. parent;
}
}
}
if (i > 0) len++;
return (len > clen) ? -1L : len;
}
long deFGK(unsigned char *text, long tlen,
unsigned char *code, long clen)
{
int i, j, k;
long c, len;
int curChar;
int zeroNode, thisNode, maxid;
int node2id[NODE_SIZE]; /* 노드로부터 그 노드 번호 */
NODE node[NODE_SIZE]; int freeNode;
static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1};
if (clen <= 0) return -1L;
/* 초기 하프맨나무 */
zeroNode = 2;
node[2]. chr = CHAR_SIZE+1;
node[2]. count = 0;
node[2]. parent = ROOT;
node[EOF_NODE]. chr = CHAR_SIZE;
node[EOF_NODE]. count = 1;
node[EOF_NODE]. parent = ROOT;
node[ROOT]. count = 0x7FFFFFFFL;
node[ROOT]. parent = 0;
node[ROOT]. left = zeroNode;
node[ROOT]. right = EOF_NODE;
node2id[zeroNode] = 0;
node2id[EOF_NODE] = 1;
node2id[ROOT] = 2;
freeNode = 3;
/* 복호화 */
for (i = 0, c = 0, len = 0; ; ) {
/* 부호어에 대응하는 문자 노드를 얻는다 */
thisNode = ROOT;
do {
thisNode = (*code & bit1[i]) ?
node[thisNode]. right : node[thisNode]. left;
if (thisNode >= freeNode) return -1L;
if (++i == 8) {
code++;
if (++c > clen) return -1L;
i = 0;
}
} while (node[thisNode]. chr < 0);
if (thisNode == EOF_NODE) break; /* EOF */
if (thisNode == zeroNode) { /* 신문자 */
curChar = 0;
for (j = 0; j < 8; j++) {
if (*code & bit1[i]) curChar |= bit1[j];
if (++i == 8) {
code++;
if (++c > clen) return -1L;
i = 0;
}
}
} else curChar = node[thisNode]. chr;
if (++len > tlen) return -1L;
*text++ = curChar; /* 문자의 출력 */
/* 하프맨나무를 갱신 */
while (thisNode ! = ROOT) {
if (thisNode == zeroNode) {
for (j = 0; j < freeNode; j++) node2id[j] += 2;
node[zeroNode]. left = freeNode;
node[freeNode]. count = 0;
node[freeNode]. parent = zeroNode;
node2id[freeNode] = 0;
node[freeNode]. chr = CHAR_SIZE + 1;
freeNode++;
node[zeroNode]. right = freeNode;
node[freeNode]. count = 1;
node[freeNode]. parent = zeroNode;
node2id[freeNode] = 1;
node[freeNode]. chr = curChar;
freeNode++;
thisNode = zeroNode;
node[thisNode]. chr = -1;
zeroNode = freeNode - 2;
} else {
if (node[thisNode]. count == 1 &&
node[k = node[thisNode]. parent]. count == 1) {
/* 0-노드의 형제 */
for (j = 0, maxid = thisNode; j < freeNode; j++)
if (node[j]. count == 1 && j ! = k &&
node2id[j] > node2id[maxid]) maxid = j;
} else {
for (j = 0, maxid = thisNode; j < freeNode; j++)
if (node[thisNode]. count == node[j]. count &&
node2id[j] > node2id[maxid]) maxid = j;
}
if (maxid ! = thisNode) {
int maxidP = node[maxid]. parent;
int thisP = node[thisNode]. parent;
int id = node2id[maxid];
if (node[maxidP]. left == maxid)
node[maxidP]. left = thisNode;
else node[maxidP]. right = thisNode;
if (node[thisP]. left == thisNode)
node[thisP]. left = maxid;
else node[thisP]. right = maxid;
node[maxid]. parent = thisP;
node[thisNode]. parent = maxidP;
node2id[maxid] = node2id[thisNode];
node2id[thisNode] = id;
}
node[thisNode]. count++;
thisNode = node[thisNode]. parent;
}
}
}
return len;
}
이러한 문제점을 해결하기 위해서, 입력 텍스트로부터 1 문자를 읽어들일 때 마다, 그 시점까지의 각 문자의 출현 빈도를 재계산해, 하프맨나무를 다시 만들어 , 문자를 encode 하는 것이 고안 되었다. 하프맨나무는 그 시점에서의 출현 빈도에 대해서 최적 (으)로 계속 되도록(듯이) 변화하므로, 적응형 허프만 코딩이라고 한다. 또 하프맨나무 하지만 문자 마다 바뀌므로, 동적 허프만 코딩이라고도 한다.
그러나, 실제로 이와 같이 해 하프맨나무를 문자 마다 복구성 하는 것은, 일까 의 계산 시간이 걸린다. 실제의 적응형 허프만 코딩 알고리즘에서는, 하프맨 나무의 변형을 최소한으로 하기 위한 궁리가 필요하다.
적응형 허프만 코딩을 적은 계산량으로 실현되는 아이디어는, 최초 1970 년대에 N. Faller 와 R. G. Gallager 에 의해 독립에 고안 되었다. 1985년에 Knuth 가 이 아이디어로 개량을 더해 FGK 알고리즘을 개발했다.
알고리즘의 기초는, Gallager 에 의해 정의된 형제 조건이다. 있다 나무가 형제 조건을 채운다는 것은, 루트 이외의 각 노드가 1개의 형제도 , 게다가, 노드를 형제끼리가 서로 이웃이 되도록(듯이) 중량감의 비증가순서에 늘어놓는 것 하지만 할 수 있는 경우를 말한다. Gallager 는, 어느 나무가 하프맨나무인 것은, 그 나무가 형제 조건을 채우는 경우이며, 한편 그 경우에 한정하는 것을 나타냈다. 여기서 말한다 중량감과는 노드의 문자 출현 빈도의 것으로, 내부 노드의 문자 출현 빈도는 그 아이 노드의 그것의 화이다.
FGK 부호에 대해도, 초기 하프맨나무는 루트와 그 아이 노드 2익고 된다. 2살의 아이 노드는, 각각 「미출현 문자(이하 0-노드라고 부른다)」라고 EOF (부호의 종료를 나타내는 특별 기호)에 대응한다. 0-노드의 출현 빈도를 0, EOF 노드의 출현 빈도를 1 으로 한다. 또, 노드 번호는 0-노드가 0, EOF 노드 하지만 1, 루트가 2 의 순서로 한다.
0-노드는, 현재까지 출현하고 있지 않는 문자가 처음으로 입력 텍스트중에 나타났다 때에, 그 문자를 encode 하기 위해서 사용한다. 그 경우,0-노드에 대한 부호 말을 출력한 후에, 문자 그 자체도 출력한다(예를 들어 ASCII 코드등에 의한다).
하프맨나무를 이하와 같이 갱신한다.