20CN网络安全小组论坛 - 编程破解 - 数据压缩的c算法(斑竹，高手请进）

论坛: 编程破解标题: 数据压缩的c算法(斑竹，高手请进）

作者: jzit_wmm [jzit_wmm]

论坛用户

思索数据压缩的c算法（huffman），以下是我的思路：
1. 查出打开文件的各字节出现的次数，算出其概率。
2. 将概率按顺序排列，每次将最小的两个相加，直到和为1。
3. 将其存入链表（和，加数，加数）
4. 2叉树先序遍历
5. 写出压缩码。
大体是这样的，可能有些不全。（呵呵，从3开始有些迷糊！！尤其是链表的编程）知道的指点一下。

地主发表时间: 05-04-19 16:39

回复: 286 [unique]

版主

3. 将其存入链表（和，加数，加数）----》直接存成二叉树。利用二叉树的增加即可。

B1层发表时间: 05-04-20 09:15

回复: jzit_wmm [jzit_wmm]

论坛用户

怎么存啊？能不能写段程序举个例子。树，我学的不怎么好。

B2层发表时间: 05-04-20 19:11

回复: cac0527 [cac0527]

论坛用户

看看这段代码

int* index = new int[num]; int index_i = 0;

/* 当用于堆排序的二叉树中还有结点时循环 */
while (heap_num > 1)
{
int pos[2];
/* 循环2次,找出2个最小的子树,存入pos中 */
for (i = 0; i < 2; i++)
{
register int curr, child;
/* 根结点就是最小的结点 */
pos[i] = heap[0];
if (pos[i] >= num) // 如果是叶子结点，就记录
index[index_i++] = pos[i];
/* 将最后的结点移动到根结点处,总结点数目减1 */
heap[0] = heap[--heap_num];
/* 以下是重建堆的过程 */
curr = 1;
child = 2;
while (child <= heap_num)
{
if (child < heap_num &&
heap[heap[child]] < heap[heap[child - 1]])
child++;
if (heap[heap[curr - 1]] > heap[heap[child - 1]])
{
register int temp;
temp = heap[child - 1];
heap[child - 1] = heap[curr - 1];
heap[curr - 1] = temp;
curr = child;
child = 2 * curr;
}
else
break;
}
}

/* 合并子树,其结果作为新的结点放入堆中(但不在堆排序的二叉树内,实际
上,新加入的结点是和堆的后半段一起构成了Huffman树) */
heap[heap_num + 1] = heap[pos[0]] + heap[pos[1]];
/* 子树的左,右分支都指向子树的根结点 */
heap[pos[0]] = heap[pos[1]] = heap_num + 1;

/* 把子树根结点作为叶子结点，放到堆排序中的二叉树内 */
heap[heap_num] = heap_num + 1;
{
/* 在堆中,让新加入的叶子结点上升到合适的位置,不破坏堆的秩序 */
register int parent, curr;
heap_num++;
curr = heap_num;
parent = curr >> 1;
while (parent && heap[heap[parent - 1]] > heap[heap[curr - 1]])
{
register int temp;
temp = heap[parent - 1];
heap[parent - 1] = heap[curr - 1];
heap[curr - 1] = temp;
curr = parent;
parent = curr >> 1;
}
}
}

// 从根出发，求每个编码的码长
int overflow = 0; // 记录有多少个编码超长
const int tmp = sizeof(unsigned long)*8 + 1;
int len_count[tmp];
memset(len_count, 0, sizeof(int)*tmp);
heap[0] = (unsigned long)(-1l); // 双亲结点为0的叶子，可由此算得码长0
heap[1] = 0; // 根结点码长为0
for (i = 2; i < 2*num; i++)
{
heap[i] = heap[heap[i]] + 1; // 结点码长等于双亲结点码长加1
if (i >= num)
{
if (heap[i] <= (unsigned long)max_code_len)
len_count[heap[i]]++;
else // 统计超长叶子结点数量
{
heap[i] = max_code_len;
overflow++;
}
}
}

// 如果有编码被限制了码长，就意味着码长为max_code_len的编码
// 数量已经超过了二叉树的容量，必须做二叉树的重整
if (overflow > 0)
{
// 假设把超长叶子结点都去掉，计算码长max_code_len处还可腾出几个位置
// 计算方法是，从根开始，每层的分支结点数目等于上层分支结点数乘2减
// 本层叶子结点数；最后一层的分支结点数，就是可腾出的空位数量
int nonleaf = 1, bits;
for(i = 1; i <= max_code_len; i++)
nonleaf = nonleaf * 2 - len_count[i];

// 先把nonleaf个超长结点放到max_code_len这一层
overflow -= nonleaf;
len_count[max_code_len] += nonleaf;

// 调整剩下的超长结点，这个循环只调整码长的计数数组len_count
while(overflow > 0)
{
bits = max_code_len - 1;
while(len_count[bits] == 0) bits--; // 向上找到一个有叶子的层次
len_count[bits]--; // 把叶子移下一层
len_count[bits+1] += 2; // 把移下来的叶子和超长的一个结点合并为一个子树
overflow --;
};

// 下面这个循环真正对码长进行调整
// 从码长最长的结点开始，在堆中倒着数，如果发现实际数目
// 和len_count中记录的不一致，就调整码长，使之和len_count一致
int m, n; index_i = 0;
for(bits = max_code_len; bits != 0; bits--)
{
n = len_count[bits];
while(n != 0)
{
m = index[index_i++];
if (heap[m] != (unsigned long)bits)
heap[m] = bits;
n--;
}
}
}

B3层发表时间: 05-04-20 19:53

论坛: 编程破解