精华内容
下载资源
问答
  • 哈夫曼编码习题

    千次阅读 2019-11-07 19:57:45
    假设用于通信的电文仅由8个字母组成,字母在电文中出现的...请为这8个字母设计哈夫曼编码表格形式: NO. data parent Lchild Rchild 0 0.07(A) 10 NULL NULL 1 0.19(B) 12 ...

    假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为

    0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10

    请为这8个字母设计哈夫曼编码。

    表格形式:

    NO. data parent Lchild Rchild
    0 0.07(A) 10 NULL NULL
    1 0.19(B) 12 NULL NULL
    2 0.02(C) 8 NULL NULL
    3 0.06(D) 9 NULL NULL
    4 0.32(E) 13 NULL NULL
    5 0.03(F) 8 NULL NULL
    6 0.21(G) 12 NULL NULL
    7 0.10(H) 10 NULL NULL
    8 0.05 9 2 5
    9 0.11 11 8 3
    10 0.17 11 0 7
    11 0.28 13 9 10
    12 0.4 14 1 6
    13 0.6 14 11 4
    14 1.0 NULL 12 13

     

    该表格也就是静态三叉链表,小编自己由多加了一列编号,三叉链表从左到右依次为权值(data)、双亲序号(parent)、左孩子序号(Lchild)、右孩子序号(Rchild)。

    通俗的说,求哈夫曼编码就是根据三叉链表计算出最优二叉树,算法是(在链表权值内取最小的两位权值相加,然后删去最小的两位数,将它们的和存入链表,然后重复取最小的两个数,存入两个数的和,删去原来的两个相加的小数。这一个循环的过程,一直到最后算出的那个最终的数,就是最优二叉树的权值)

    本题来讲,第一步就是找到两个最小的数,编号分别为2(0.02),5(0.03).【一般以较小的数为左孩子,较大的数为右孩子】然后写入到编号为8的左孩子和右孩子的二叉链表处。直至填满编号为14的三叉链表。

    二叉树表示:

    根据三叉链表,便可以画出二叉树,A-H对应着相应的数据,可以在二叉树中找到对应的位置,按照左0右1的编码规则,得到每个字母对应的哈夫曼编码。(也就是每个字母对应的二叉树路径)

    Endeavor

    展开全文
  • 这里写自定义目录标题JavaFX实现哈夫曼树和哈夫曼编码的GUI界面的显示原理及作用GUI界面功能如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...

    JavaFX实现哈夫曼树和哈夫曼编码的GUI界面的显示

    原理及作用

    哈夫曼树又称最优二叉树,是带权路径长度(WPL)最短的树,可以生成哈夫曼编码,出现频率高的字符用较短的编码,这样可以用于数据传输,数据压缩,来提高效率。

    功能

    • 输入字符串后再点击Show Huffman Tree在界面生成哈夫曼树,及相关编码信息。
    • 在下方输入二进制编码产生相应的字符串信息。
    • 产生的信息通过弹窗展示
    • 对输入的内容进行合法判断

    思路

    开始对字符串中的字符进行计算权重,再创建对应的结点,加入ArrayList数组中。这是哈夫曼树中的一个小二叉树,哈夫曼树由多个它组成。
    在这里插入图片描述
    生成哈夫曼树时的过程:
    在这里插入图片描述

    GUI界面

    运行时初始界面运行时初始界面
    代码:
    在这里插入图片描述
    showHuffmanTree方法:

    • 第一个for循环用来统计输入字符串中的Ascii值。在第二个循环中会用到。
    • 第一个if语句用来判断字符串长长度,要求大于一
    • 第二个if语句用来判断输入的字符串是否全为一个字符,否则也无意义。
    • 最后的else方法来执行createTree方法,传入需要生成树的结点,以及输入的字符串信息。并通过getCode方法获取相应的哈夫曼编码信息显示到弹窗。

    decode方法

    • 第一个if判断是否生成了哈夫曼树,否则你无法来解码。
    • 第二个判断是否输入bits字符串
    • 第三个判断输入的字符串是否为01组成。
    • 最后调用getChar方法

    getCode方法

    • 由于执行了createTree方法,生成了哈夫曼树,相应的编码也存入了codeMap集合中,可以直接通过键来获取值,存储到字符串并在循环结束后返回。

    getChar方法

    • 原理和getCode方法一样,只不过现在是通过值来获取键。但是有一点要考虑到,你输入的bits码可能不能全转换为字符,所以要在里面进行判断。
    • 获取键的方法为遍历codeMap集合,将值与bits字符串的前n位比较,n为当前集合值的长度(此时又会发生另外一种情况,若bits字符串的长度已经小于了值的长度就会产生越界异常)所以这里我们定义一个length来获取n与bits长度的最小值。若匹配就分割bits字符串,去掉已匹配的字符串。直到匹配完成。
    • 如果bits剩下的字符串不能匹配到集合中的值,会在字符串的长度次循环中跳出循环,并弹出提示框。

    createTree方法

    • 创建一个树对象,调用该对象的printTree方法,传入相关参数,x是X轴的偏移量,y是Y轴的偏移量。deep是树的深度。由于根节点在结点中央,所以直接传入的500。当然也可以用其他的方法。
    • 用定义的sp的setContent方法添加结点到父结点。

    TreeNode类

    在这里插入图片描述
    c用来储存字符信息
    code用来储存哈夫曼编码
    weight来存放权值
    lTreeNode和rTreeNode分别存放左右孩子

    Tree类

    代码:
    在这里插入图片描述其中这个片段我想到之前写的有点不好修改了一下
    这里清空al的主要是释放内存。

    //当集合中只有两个结点时,连接到root结点并break
    if(al.size() == 2) {
    	root.lTreeNode = al.get(0);
    	root.rTreeNode = al.get(1);
    	al.clear();
    	break;
    }

    测试结果

    在这里插入图片描述
    上方的图片为生成的哈夫曼树
    下左为点击Show Huffman Tree后弹出的提示框
    下右为点击Decode Text后弹出的提示框
    如果输入的bits字符串不能全部按照哈夫曼编码解码会弹出一个提示框说明还剩哪些字符串没有解码
    **例如:**上图中产生的编码对应关系为
    r ——>000
    d ——>001
    o ——>01
    h ——>100
    e ——>1010
    w ——>1011
    l ——>11
    假如我输入0000010110
    解码为rdo,剩下的10无法通过哈夫曼编码转化为字符。
    在这里插入图片描述

    展开全文
  • 哈夫曼编码-Huffman

    2015-10-07 14:35:15
    详细内容参考:哈夫曼编码(百度百科)  Huffman编码流程 数据压缩流程 1、 读取输入 2、 将输入中的每个char值得出现频率制成表格 3、 根据频率构造Huffman编码树 4、 构造编译表,

           Huffman编码的思想是放弃文本文件的普通保存方式,不再使用7位或者8位二进制数表示一个字符,而是用较少的比特表示出频率高的字符,用较多的比特位表示出频率低的字符。详细内容参考:哈夫曼编码(百度百科) 


    Huffman编码流程

    数据压缩流程

    1、  读取输入

    2、  将输入中的每个char值得出现频率制成表格

    3、  根据频率构造Huffman编码树

    4、  构造编译表,将输入中的每个char值和一个比特字符串相关联

    5、  将单词查找树编码为比特字符串并写入输出流

    6、  将单词总数编码为比特字符串并写入输出流

    7、  使用编译表翻译每个输入字符


    /**
    	Huffman实际上会生成二进制流,这里把输入字符串翻译为二进制的字符串,比如"AAB"翻译为“001”,'A'为'0',‘B’为'1'
    	这样使用输出时更以观察生成的结果
    */
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <functional>
    
    using namespace std;
    
    struct HuffNode
    {
    	char data;
    	size_t freq;
    	HuffNode *left;
    	HuffNode *right;
    
    	HuffNode() : data('\0'), freq(0), left(NULL), right(NULL) {}
    	~HuffNode()
    	{
    		static int i = 0;
    		cout << "node" << ++i << endl;
    		if (left)
    			delete left;
    		if (right)
    			delete right;
    	}
    };
    
    class HuffTree
    {
    public:
    	HuffTree(const char *str) : rawStr(str), root(NULL), freqVec(N)   { init(); }
    	HuffTree(const string &str) : rawStr(str), root(NULL), freqVec(N) { init(); }
    	~HuffTree();
    
    	void printCodingVec();
    	void setBinStr();
    	void printBinStr();
    	void printRawStr() { cout << rawStr << endl; }
    	
    private:
    	static const size_t N = 256;
    	string rawStr;
    	string binStr;
    	HuffNode *root; // Huffman tree
    	vector<pair<char, size_t>> freqVec;
    	vector<pair<char, string>> codingVec;
    
    	void init();
    	void makeFreqVec();
    	void makeTree();
    	void makeCodingVec(HuffNode *root);
    };
    
    int main(void)
    {
    	HuffTree tree("ABCACAABF");
    
    	tree.printCodingVec();
    
    	tree.setBinStr();
    	tree.printRawStr();
    	tree.printBinStr();
    
    	system("pause");
    	return 0;
    }
    
    
    HuffTree::~HuffTree()
    {
    	if (root)
    		delete root;
    
    	system("pause");
    }
    
    void HuffTree::printCodingVec()
    {
    	for (size_t i = 0; i < codingVec.size(); i++)
    	{
    		cout << codingVec[i].first << ": " << codingVec[i].second << endl;
    	}
    }
    
    void HuffTree::setBinStr()
    {
    	for (size_t i = 0; i < rawStr.size(); i++)
    	{
    		for (size_t j = 0; j < codingVec.size(); j++)
    		{
    			if (rawStr[i] == codingVec[j].first)
    				binStr += codingVec[j].second;
    		}
    	}
    }
    
    void HuffTree::printBinStr()
    {
    	cout << binStr << endl;
    }
    
    template <typename T>
    struct greator
    {
    	bool operator()(const T &x, const T &y)
    	{
    		return (x->freq > y->freq); // 建立的是小堆
    	}
    };
    
    void HuffTree::init()
    {
    	makeFreqVec();
    	makeTree();
    	makeCodingVec(root);
    }
    
    void HuffTree::makeFreqVec()
    {
    	if (rawStr.empty())
    		return;
    	
    	for (size_t i = 0; i < rawStr.size(); i++)
    	{
    		freqVec[(size_t)rawStr[i]].second++;
    	}
    }
    
    void HuffTree::makeTree()
    {
    	if (rawStr.empty())
    		return;
    	
    	vector<HuffNode *> treeVec;
    	for (size_t i = 0; i < N; i++)
    	{
    		if (freqVec[i].second)
    		{
    			HuffNode *pnode = new HuffNode;
    
    			pnode->data = (char)i;
    			pnode->freq = freqVec[i].second;
    			treeVec.push_back(pnode);
    		}
    	}
    
    	make_heap(treeVec.begin(), treeVec.end(), greator<HuffNode *>());
    	size_t length = treeVec.size();
    
    	for (size_t i = 0; i < length - 1; i++)
    	{
    		pop_heap(treeVec.begin(), treeVec.end(), greator<HuffNode *>());
    		HuffNode *pnode1 = treeVec.back();
    		treeVec.pop_back();
    
    		pop_heap(treeVec.begin(), treeVec.end(), greator<HuffNode *>());
    		HuffNode *pnode2 = treeVec.back();
    		treeVec.pop_back();
    
    		HuffNode *pnode = new HuffNode;
    		pnode->data = -1; // 表示为内部节点
    		pnode->freq = pnode1->freq + pnode2->freq;
    		pnode->left = pnode1;
    		pnode->right = pnode2;
    
    		treeVec.push_back(pnode);
    		push_heap(treeVec.begin(), treeVec.end(), greator<HuffNode *>());
    	}
    
    	root = treeVec.front();
    }
    
    void HuffTree::makeCodingVec(HuffNode *pnode)
    {
    	if (!pnode)
    		return;
    
    	static vector<char> cvec;
    
    	if ((int)pnode->data > 0) // 内部节点的data域为-1,初始化为0
    	{
    		string s(cvec.begin(), cvec.end());
    		pair<char, string> tmp(pnode->data, s);
    
    		codingVec.push_back(tmp);
    	}
    
    	cvec.push_back('0');
    	makeCodingVec(pnode->left);
    	cvec.pop_back();
    
    	cvec.push_back('1');
    	makeCodingVec(pnode->right);
    	cvec.pop_back();
    }

    参考:

    1、《算法 第4版》5.5 数据压缩

    2、algorithm_data_structure


    展开全文
  • 贪心算法详解:哈夫曼编码

    千次阅读 2019-01-17 16:34:35
    现在有一个能装100g物品的背包,和一些可拆分的物品(见表格),怎么装才能使背包中物品价值最大? 物品 重量 价值 A 100g 100 B 60g 120 C 50g 150 D 20g 50 容易...

    理解贪心算法

    贪心算法是一种算法思想,并不是一个具体的算法,因此我们用两个例子来理解什么样的问题适合用贪心算法解决。

    例一
    现在有一个能装 100g 物品的背包,和一些可拆分的物品(见表格),怎么装才能使背包中物品价值最大?

    物品 重量 价值
    A 100g 100
    B 60g 120
    C 50g 150
    D 20g 50

    容易想到的方法是通过计算物品单价,从高到低往背包中放。

    例二
    在一个加权有向图中,求 A 到 G 的最短距离。
    在这里插入图片描述

    若依旧使用例一中的方法,则找到的路径是 A->B>D>E>G,明显不是最短的路径。

    综述
    例一和例二的相同点:

    1. 要得到最终的结果,都需要多次决策,
      比如例一中每次决策选择一个物品,例二中每次决策选择一条路。

    例一和例二的区别:

    1. 例一中每次决策都不会影响后续的决策范围,即选择了一个物品后,下次选择范围仍然是所有物品,而例二中,第一次决策选择一条路后,第二次决策的可选项会受到第一次决策的影响。

    假设我们给例一增加条件:物品 B 和 D 不能在背包中共存,如此,贪心算法便不可用了,因为当我们在某次决策中选择了物品 B 后,会影响到下一次决策。

    贪心算法,就是在每一次决策时,都选择当前最优的选项。

    贪心算法练习

    钱币找零问题。
    人民币有 1 元,5 元,10 元,20 元,50 元,100 元面值的钱,当我们要找零 98 元时,如何凑呢?

    通常做法是从面值大的开始凑,即 1 张 50,2 张 20,1 张 5,4 张 1,可以得到 98。

    区间覆盖问题
    现在有几个区间[6,8],[2,4],[3,5],[1,5],[5,9],[8,0],要求的是两两不相交的区间最多有几个?

    解决思路,首先对这些区间排序,以右边值从小到大排序,右边值相同的情况下,按左边值从小到大排序,决策时,候选区间左端点不能与已选择的区间相交。

    哈夫曼编码

    假设现在有 10000 个字符,均是由a,b,c,d,e,f,g这7个字符构成,每个字符占 8 bit,一共需要占 80000 bit,思考如何压缩呢?

    方法一:7 个字符可以使用 3 bit 来表示,因为 3 bit 可以表示 8 个字符
    000,001,010,011,100,101,110,111,每个字符用 3 位表示,总大小为 30000 bit。

    方法二:哈弗曼编码,统计 10000 个字符中,a,b,c,d,e,f,g的出现频率,频率高的编码少,频率低的编码多。

    每个字符的编码都不等长的话,在解码的时候,为了避免出现歧义,字符的编码不能存在前缀关系。

    计算哈夫曼编码一般是使用一个优先队列,将每个字符看做一个节点,节点的值是字符的出现频次,每次从队列中取两个节点,组合成一个节点,再入队。

    字符 出现的频率 编码
    a 45 0
    b 13 101
    c 12 100
    d 16 110
    e 9 1111
    f 5 1110

    以上述方法画出哈夫曼树:
    哈弗曼树

    展开全文
  • 哈夫曼序列检测器

    2019-09-30 17:57:09
    被检测序列所涉及的哈弗曼编码,在上面的表格中都已经给出,该实验的目的就是判断序列中的码字,确定被编码的字节。例如序列中的EE 0F…二进制表示为111011 100 00 01 111…,解码出的字节为0x41、0x03、0x01、0x02;...
  • 无失真信源编码主要适用于离散信源或数字信号,如文本、表格及工程图纸等信源,它们要求进行无失真地数据压缩,要求完全能够无失真地可逆恢复。凡是能载荷一定的信息量,且码字的平均长度最短,可分离的变长码的码字...
  • Huffman Encode(哈夫曼编码) c++实现欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定...
  • hadoop深入研究:(七)——压缩

    万次阅读 2013-06-24 16:27:32
    转载请标明出处:hadoop深入研究:(七)——压缩文件压缩主要有两...hadoop里支持很多种压缩格式,我们看一个表格:DEFLATE是同时使用了LZ77算法与哈夫曼编码(Huffman Coding)的一个无损数据压缩算法,源代码可以在zlib
  • 文件压缩主要有两个好处,一是减少了存储文件所占空间,另一个就是为数据传输提速。...DEFLATE是同时使用了LZ77算法与哈夫曼编码(Huffman Coding)的一个无损数据压缩算法,源代码可以在zlib库中找到。gzip是以DEF
  • hadoop 压缩

    2014-04-09 11:17:47
    转载请标明出处:hadoop深入研究:(七)——压缩 文件压缩主要有两个好处,一是减少了存储文件所占空间,另一个就是为数据传输提速。...DEFLATE是同时使用了LZ77算法与哈夫曼编码(Huffman Coding)的一个无
  • 常见数据压缩算法压缩文件压缩主要有两个好处,一是减少了存储文件所占空间,另一个就是为数据传输提速。在hadoop大数据的背景下...1、DEFLATE是同时使用了LZ77与哈夫曼编码的一个无损数据压缩算法, 源代码可以在zlib
  • 范例1-75 哈夫曼编码(1) 223 ∷相关函数:HuffmanCoding函数 1.4.22 哈夫曼编码(2) 226 范例1-76 哈夫曼编码(2) 226 ∷相关函数:HuffmanCoding函数 1.5 排序 229 1.5.1 直接插入排序 229 范例1-77 ...
  • C语言通用范例开发金典.part2.rar

    热门讨论 2012-08-31 14:18:18
    范例1-75 哈夫曼编码(1) 223 ∷相关函数:HuffmanCoding函数 1.4.22 哈夫曼编码(2) 226 范例1-76 哈夫曼编码(2) 226 ∷相关函数:HuffmanCoding函数 1.5 排序 229 1.5.1 直接插入排序 229 范例1-77 ...
  • C 开发金典

    2013-06-20 16:20:03
    范例1-75 哈夫曼编码(1) 223 ∷相关函数:HuffmanCoding函数 1.4.22 哈夫曼编码(2) 226 范例1-76 哈夫曼编码(2) 226 ∷相关函数:HuffmanCoding函数 1.5 排序 229 1.5.1 直接插入排序 229 范例1-77 ...
  • C语言通用范例开发金典.part1.rar

    热门讨论 2012-08-31 14:09:26
    范例1-75 哈夫曼编码(1) 223 ∷相关函数:HuffmanCoding函数 1.4.22 哈夫曼编码(2) 226 范例1-76 哈夫曼编码(2) 226 ∷相关函数:HuffmanCoding函数 1.5 排序 229 1.5.1 直接插入排序 229 范例1-77 ...
  • 实例114 哈夫曼编码 167 3.6 图及图的应用 169 实例115 图的邻接表存储 170 实例116 图的深度优先搜索 172 实例117 图的广度优先搜索 175 实例118 Prim算法求最小生成树 177 实例119 迪杰斯特拉算法 ...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

哈夫曼编码表格