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符号の長さ。符号化に失敗したときは -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;
/* 各文字を符号化 */
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;
}
これらの問題点を解決するために、入力テキストから１文字を読み込むごとに、 その時点までの各文字の出現頻度を再計算し、ハフマン木をつくり直し、文字を 符号化することが考案された。ハフマン木はその時点での出現頻度に対して最適 であり続けるように変化するので、適応型ハフマン符号という。またハフマン木 が文字ごとに変わるので、動的ハフマン符号ともいう。
しかし、実際にこのようにしてハフマン木を文字ごとに再構成することは、かな りの計算時間がかかる。実際の適応型ハフマン符号アルゴリズムでは、ハフマン 木の変形を最小限にするための工夫が必要である。
適応型ハフマン符号を少ない計算量で実現するアイデアは、最初 1970 年代に N. Faller と R. G. Gallager によって独立に考案された。1985年に Knuth が このアイデアに改良を加え、FGKアルゴリズムを開発した。
アルゴリズムの基礎は、Gallager によって定義された兄弟条件である。ある 木が兄弟条件を満たすとは、ルート以外の各ノードが１つの兄弟をも ち、しかも、ノードを兄弟同士が隣り合うように重みの非増加順に並べること ができる場合をいう。Gallager は、ある木がハフマン木であるのは、その木が 兄弟条件を満たす場合であり、かつその場合に限ることを示した。ここでいう 重みとはノードの文字出現頻度ののことで、内部ノードの文字出現頻度はその 子ノードのそれの和である。
FGK符号においても、初期ハフマン木はルートとその子ノード２つからなる。 ２つの子ノードは、それぞれ「未出現文字（以下 0-ノードと呼ぶ）」とEOF （符号の終了を表す特別記号）に対応する。0-ノードの出現頻度を 0、EOF ノードの出現頻度を 1 とする。また、ノード番号は 0-ノードが 0、EOFノード が 1、ルートが 2 の順とする。
0-ノードは、現在までに出現していない文字が初めて入力テキスト中に現れた ときに、その文字を符号化するために使う。その場合、0-ノードに対する符号 語を出力した後に、文字そのものも出力する（たとえば ASCIIコード等による）。
ハフマン木を以下のように更新する。