1、描述
Huffman编码，将字符串利用C++编码输出该字符串的Huffman编码。
Huffman树是一种特殊结构的二叉树，由Huffman树设计的二进制前缀编码，也称为Huffman编码在通信领域有着广泛的应用。在word2vec模型中，在构建层次Softmax的过程中，也使用到了Huffman树的知识。
在通信中，需要将传输的文字转换成二进制的字符串，假设传输的报文为：“AFTERDATAEARAREARTAREA”，现在需要对该报文进行编码。
2、实现过程
- 统计字符串中出现字符的频率
- 列出字符串的Huffman树
3、实现代码
#include<iostream>#include<string>using namespace std;struct huffTree{ int parent;//父亲 int lchild;//左孩子 int rchild;//右孩子 int weight;//权重 string flag;//标志};struct Lowest_Node//第0级节点的字符与频度{ char ch; int ch_num;};//确定每个字符的huffman编码,输出参数为a、bvoid coding(int length, huffTree tree[], int n, int &a, int &b){ int i; int r, s; r = s = length;//节点个数最大不会超过字符串的长度 for (i = 0; i < n; i++) { if ((tree[i].weight < r) && (tree[i].parent == -1)) { r = tree[i].weight; a = i; } } for (i = 0; i < n; i++) { if ((tree[i].weight < s) && (i != a) && (tree[i].parent == -1)) { s = tree[i].weight; b = i; } }}//计算每个字符出现的频度并排序void frequency(string str){ int length = str.length();//长度 // 开辟结构体数组 Lowest_Node *node = new Lowest_Node[length];//声明最0级节点 int i, j;//循环因子 for (i = 0; i < length; i++) node[i].ch_num = 0;//初始化频度 int char_type_num = 0;//初始为0种字符 for (i = 0; i < length; i++)//循环整个字符串 { for (j = 0; j < char_type_num; j++) if (str[i] == node[j].ch || // 判断字符频率结构中，这个字符是否相等 (node[j].ch >= 'a'&&node[j].ch <= 'z'&& //判断是否为字符 str[i] + 32 == node[j].ch //判断字符串的大写是否与字符频率结构中字符相等 )) break;//该字符没有出现过，跳出循环 if (j < char_type_num)//该字符重复出现，对应的记数器加1 node[j].ch_num++; else//新出现的字符，记录到ch[j]中，对应计数器加1 { if (str[i] >= 'A'&&str[i] <= 'Z') node[j].ch = str[i] + 32; //字符转换为大写存储起来 else node[j].ch = str[i]; node[j].ch_num++; char_type_num++;//字符的种类数加1 } } //按频度从大到小排序 for (i = 0; i < char_type_num; i++) //字符长度 { for (j = 0; j < char_type_num-1; j++) { //判断为字符就往下走，否则就不往下 if (node[j].ch >= 'a'&&node[j].ch <= 'z') { if (node[j].ch_num < node[j + 1].ch_num)//如果前一个小于后一个，交换 { int temp;//临时频度 char ch_temp;//临时字符 temp = node[j].ch_num; ch_temp = node[j].ch; node[j].ch_num = node[j + 1].ch_num; node[j].ch = node[j + 1].ch; node[j + 1].ch_num = temp; node[j + 1].ch = ch_temp; } } } } for (i = 0; i < char_type_num; i++)//打印字符频度 cout << "字符" << node[i].ch << "出现了" << node[i].ch_num << "次" << endl; huffTree *huff = new huffTree[2 * char_type_num - 1];//此变量的声明需位于确定char_type_num值后 huffTree temp; string *code = new string[2 * char_type_num - 1];//存放各个字符的编码 for (i = 0; i < 2 * char_type_num - 1; i++)//节点初始化 { huff[i].lchild = -1; huff[i].parent = -1; huff[i].rchild = -1; huff[i].flag = -1; } for (j = 0; j < char_type_num; j++)//将排序后的第0级节点权重赋给树节点 { huff[j].weight = node[j].ch_num; } int min1, min2; for (int k = char_type_num; k < 2 * char_type_num - 1; k++)//赋值0级之上的节点 { coding(length, huff, k, min1, min2); huff[min1].parent = k; huff[min2].parent = k; huff[min1].flag = "0"; huff[min2].flag = "1"; huff[k].lchild = min1; huff[k].rchild = min2; huff[k].weight = huff[min1].weight + huff[min2].weight; } for (i = 0; i < char_type_num; i++) { temp = huff[i]; while (1) { code[i] = temp.flag + code[i]; temp = huff[temp.parent]; if (temp.parent == -1) break; } } cout << "字符串的每个字符huffman编码为:" << endl; for (i = 0; i < char_type_num; i++) cout << node[i].ch << " " << code[i] << endl; cout << "整个字符串的huffman编码为：" << endl; for (i = 0; i < length; i++) { for (j = 0; j < char_type_num; j++) { if (str[i] == node[j].ch) cout << code[j]; } } //释放内存 delete[] node; node = NULL; delete[] huff; huff = NULL; delete[] code; code = NULL;}int main(){ int length = 0;//字符串长度 string str; //目标字符串 cout << "请输入一个字符串:"; cin >> str; frequency(str);//求各个元素的频度 printf("\n"); system("pause"); return 0;}4、参考
数据结构和算法——Huffman树和Huffman编码
http://blog.csdn.net/google19890102/article/details/54848262
微信扫一扫 
