一步一步写算法(之哈夫曼树 上)

  1. 云栖社区>
  2. 博客>
  3. 正文

一步一步写算法(之哈夫曼树 上)

杰克.陈 2014-12-11 10:21:00 浏览438
展开阅读全文
原文: 一步一步写算法(之哈夫曼树 上)

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】 


     在数据传输的过程当中,我们总是希望用尽可能少的带宽传输更多的数据,哈夫曼就是其中的一种较少带宽传输的方法。哈夫曼的基本思想不复杂,那就是对于出现频率高的数据用短字节表示,对于频率比较低得数据用长字节表示。

    比如说,现在有4个数据需要传输,分别为A、B、C、D,所以一般来说,如果此时没有考虑四个数据出现的概率,那么我们完全可以这么分配,平均长度为2,

/*
*  A - 00         B - 01
*  C - 10         D - 11
*/
    但是,现在条件发生了改变,四个数据出现的频率并不一样,分别为0.1/0.2/0.3/0.4。那么这时候应该怎么分配长度呢,其实也简单。我们只要把所有数据按照频率从低到高排列,每次取前两位合并成新的节点,再把这个新节点放到队列中重新排序即可。新节点的左结点默认设为1,右结点默认设为0。然后重复上面的过程,直到所有的节点都合并成一个节点为止。如果应用到实际的示例中,合并的过程应该是这样的,

    第一步,首先合并A和B,因为A和B是概率最小的

/*
*  
*           total_1(0.3)           C (0.3)   D(0.4)
*          /         \
*        A(0.1)      B(0.2)
*/
    第二步,接着合并total_1和C,

/*
*                 total_2 (0.6)
*               /          \     
*           total_1(0.3)    C (0.3)    D(0.4)
*          /         \
*        A(0.1)      B(0.2)
*/
    最后一步,合并total_2和D,

/*
*            final (1.0)
*          /       \          
*       D (0.4)    total_2 (0.6)    
*                /          \     
*           total_1(0.3)    C (0.3)   
*          /         \
*        A(0.1)      B(0.2)
*/
    所以按照上面的生成树,数据的编号应该这么安排,

/*
*   A - 011       B - 010
*   C - 00        D - 1
*/
    看上去A和B的长度还增加了,但是D的长度减少了。那么整个数据的平均长度有没有减少呢?我们可以计算一下。3 * 0.1 + 3 * 0.2 + 2 * 0.3 + 0.4 = 1.9 < 2。我们发现调整后的数据平均长度比原来减少了近(2 - 1.9)/2 * 100% = 10 %,这可是巨大的发现啊。

    为了完成整个哈夫曼树的创建,我们还需要定义一个数据结构:

typedef struct _HUFFMAN_NODE
{
	char str;
	double frequence;
	int symbol;
	struct _HUFFMAN_NODE* left;
	struct _HUFFMAN_NODE* right;
	struct _HUFFMAN_NODE* parent;

}HUFFMAN_NODE;
    其中str记录字符,frequency记录字符出现的频率, symbol记录分配的数据,左子树为1、右子树为0,left为左子树,right为右子树,parent为父节点。接下来,我们从创建huffman结点开始。

HUFFMAN_NODE* create_new_node(char str, double frq)
{
	HUFFMAN_NODE* pNode = (HUFFMAN_NODE*)malloc(sizeof(HUFFMAN_NODE));
	assert(NULL != pNode);

	pNode->str = str;
	pNode->frequence = frq;
	pNode->symbol = -1;
	pNode->left = NULL;
	pNode->right = NULL;
	pNode->parent = NULL;
	return pNode;
}


【未完,待续】



网友评论

登录后评论
0/500
评论
杰克.陈
+ 关注