哈夫曼树复习

哈夫曼树是一种用于数据压缩的树形数据结构，它的主要特点是将出现频率高的数据编码成长度较短的二进制码，从而实现对原始数据的高效压缩。在构建哈夫曼树时，首先需要统计原始数据中各个字符出现的频率，然后根据频率构建出一棵具有最小带权路径长度的二叉树，其中每个字符都映射到一条从根节点到叶子节点的路径，而该路径上的二进制码即为该字符的哈夫曼编码。

由于哈夫曼树上的每个节点都恰好有两个子节点，因此在构建哈夫曼树时，每次将出现频率最小的两个节点合并为一个节点，并将它们的权值之和作为新节点的权值。这个过程会一直持续到最后只剩下一个节点，这个节点就是哈夫曼树的根节点。由于每次合并两个节点都会产生一个新节点，因此哈夫曼树的叶子节点个数与原始数据中的字符个数相同。同时，由于每个字符都映射到一条从根节点到叶子节点的路径上，因此哈夫曼树上的所有字符一定在叶子节点出现。

在我写这个哈夫曼树时有一个疑问：我使用了哈希表，目的是想统计一个字符串中所有单个字符的频率，然后使用哈夫曼编码进行编码，会不会发生哈希碰撞使得统计的频率不对，进而导致编码不正确？

chatgpt的回答是：标准库中的哈希表（unordered_map）使用的是开链法（chaining）解决哈希碰撞的问题。当插入元素时，如果发生哈希碰撞，新元素会被插入到已有元素的链表中。当查找元素时，哈希表会先计算哈希值，然后遍历相应位置的链表来查找元素。因此，标准库中的哈希表使用时仍然会出现哈希碰撞的情况，但通过开链法可以尽可能地减小碰撞带来的影响。在大多数情况下，标准库中的哈希表已经足够处理大部分应用场景下的哈希碰撞问题，但在极端情况下，可能需要自行实现哈希表并选择更为高效的哈希算法来解决碰撞问题。在使用标准库中的 unordered_map 时，哈希碰撞是有可能发生的。但是对于我的代码，统计单个字符的频率的话，即使发生了哈希碰撞，也不会影响结果的准确性，因为每个字符只会对应一个值，所以在统计频率时也不会出现问题。因为标准库哈希表 std::unordered_map 中不允许键值相同的元素存在。当插入一个已经存在的键值时，该键值对会替换原来的键值对。这是由哈希表的实现方式决定的，每个键值通过哈希函数映射到一个唯一的桶中，因此不同的键值不可能被映射到同一个桶中。如果两个键值相同，则它们将被映射到同一个桶中，但这不符合哈希表的要求，因此只会保留一个键值对，后插入的会覆盖之前的。在使用哈夫曼编码进行编码时，如果需要使用哈希表，可以采用开放地址法等解决哈希碰撞的方法，或者使用红黑树等不依赖哈希函数的数据结构代替哈希表来实现。

我觉得这个哈夫曼树写得很好也很精妙。感谢chatgpt给我提供了很多意见！！！

#include<iostream>
#include<queue>
#include<cassert>
#include<string>
#include<map>
#include<unordered_map>
#include<algorithm>


using std::cout,std::cin,std::endl,std::unordered_map;
using std::construct_at,std::destroy_at,std::priority_queue,std::queue;
using std::string,std::map,std::pair,std::vector,std::count,std::make_pair;


//cout的格式化输出真是反人类，不知道为什么gcc没有format头文件，不能使用format输出函数。。。所以只能自己写一个了。。。
template<class...Args>
void print(const Args&... args) noexcept
{
	((cout << args),...);
}


//哈夫曼树节点
struct _tree_node_
{
	pair<string,size_t> _pair;
	_tree_node_* left;
	_tree_node_* right;
};


//优先级队列排序，根据字符串出现频率从小到大排序
struct compare
{
	bool operator()(_tree_node_* lhs,_tree_node_* rhs) noexcept
	{
		return lhs->_pair.second > rhs->_pair.second;
	}
};


//哈夫曼树结构体
class Hufferman_Tree
{
public:
	using _pnode = _tree_node_*;
	using _node = _tree_node_;

	Hufferman_Tree()noexcept:_root(nullptr),minimun_code(100){}

	~Hufferman_Tree() noexcept
	{
		clear();
	}

	Hufferman_Tree(const Hufferman_Tree& rhs) noexcept = delete;

	Hufferman_Tree& operator= (const Hufferman_Tree& rhs) noexcept = delete;


        //使用一个字符串来初始化哈夫曼树
	void init(const string& val) noexcept
	{
                //这个哈希表使用非常精妙！！！
                //可以统计任意字符的频率而且还是O(1)！！！
		unordered_map<string,size_t> m;
		for(const char& c : val)
		{
			++m[string(1,c)];
		}

                //根据字符和频率构建哈夫曼树节点，且加入到优先级队列中
		_pnode pt = nullptr;
		for(const auto& [key,value]: m)
		{
			pt = static_cast<_pnode>(calloc(1,sizeof(_node)));
			assert(pt);
			construct_at(&pt->_pair.first,key);
			construct_at(&pt->_pair.second,value);
			que.push(pt);
		}

               //从叶子开始构建哈夫曼树，时间复杂度是O(logn)
		_pnode lft = nullptr,rit = nullptr;
		while(que.size() > 1)
		{
			pt = static_cast<_pnode>(calloc(1,sizeof(_node)));
			assert(pt);
		        lft = que.top();
		        que.pop();
		        rit = que.top();
			que.pop();
		        pt->left = lft;
		        pt->right = rit;
		        pt->_pair.second = lft->_pair.second + rit->_pair.second;
		        que.push(pt);	
		}

		_root = que.top();
		que.pop();
	}


        //遍历所有的叶子节点
	void BFS()const noexcept
	{
		queue<_pnode> q;
		if(_root == nullptr)
		{
			return;
		}
		_pnode pt = nullptr;
		q.push(_root);
		while(!q.empty())
		{
			pt = q.front();
			q.pop();
			if(!pt->left && !pt->right)
			{
				cout << pt->_pair.first << "  " << pt->_pair.second<< endl;
			}
			if(pt->left)
			{
				q.push(pt->left);
			}
			if(pt->right)
			{
				q.push(pt->right);
			}
		}
	}


        //编码
	string encode(const string& val) noexcept
	{
		assert(_root);
		string code;
		_encode_(_root,code);
		code.clear();
		for(const char& c : val)
		{
			for(const auto& [key,value] : decoding_map)
			{
				if(value == string(1,c))
				{
					code += key;
				}
			}
		}
		return code;
	}


	void clear() noexcept
	{
		_destroy_(_root);
		_root = nullptr;
	}

        //计算哈夫曼树的节点数量
	size_t size()const noexcept
	{
		size_t siz = 0;
	        _size(_root,siz);
		return siz;
	}

        //计算树的高度
	size_t height() const noexcept
	{
		return _height_(_root);
	}

        //解码
	string decode(const string& val) noexcept
	{
		string code,curcode;
		map<string,string>::iterator iter;
		for(const char& c : val)
		{
			curcode += c;
			if(curcode.size() >= minimun_code)
			{
				iter = decoding_map.find(curcode);
			        if(iter != decoding_map.end())
			        {
				        code += iter->second;
				        curcode.clear();
			        }
			}
		}
		return code;
	}

protected:

	void _encode_(_pnode pt,string& code) noexcept
	{
		if(!pt->left && !pt->right)
		{
			print(pt->_pair.first," 出现频率为 ",pt->_pair.second," 被编码为 ",code,"\n");
			if(code.size() < minimun_code)
			{
				minimun_code = code.size();
			}
			decoding_map.insert(make_pair(code,pt->_pair.first));
		}
		if(pt->right)
		{
			code += '1';
			_encode_(pt->right,code);
			code.erase(code.end() - 1);
		}
		if(pt->left)
		{
			code += '0';
			_encode_(pt->left,code);
			code.erase(code.end() - 1);

		}
	}


	void _size(_pnode pt,size_t& size) const noexcept
	{
		if(!pt)
		{
			return;
		}
		_size(pt->left,size);
		_size(pt->right,size);
		++size;
	}


	void _destroy_(_pnode pt) noexcept
	{
		if(pt == nullptr)
		{
			return;
		}
		_destroy_(pt->left);
		_destroy_(pt->right);
		free(pt);
	}

	size_t _height_(_pnode pt)const noexcept
	{
		if(pt == nullptr)
		{
			return 0;
		}
		size_t lh = 0,rh = 0;
		lh = _height_(pt->left);
		rh = _height_(pt->right);
		return lh > rh ? ++lh : ++rh;
	}


private:
	priority_queue<_pnode,vector<_pnode>,compare> que;  //优先级队列，用来构建哈夫曼树
	_pnode _root;
	map<string,string> decoding_map; //保存编码和字符的表，用来解码
	size_t minimun_code;  //记录编码的最小字符数量，减少循环次数
};




int main()
{
	string test = "helloworldwoasdwk48942187das1145141919810owidawpzxicjwioadhsjdkhwu";

	Hufferman_Tree t;
	t.init(test);

	string s = t.encode(test);
	cout << endl;
	print(test," 被编码为 ",s,"\n");

	cout << endl;
	string st = t.decode(s);
	print(s," 被解码为 ",st,"\n");

	return 0;
}