对于哈夫曼编码的理解

哈夫曼编码,主要目的是根据使用频率来最大化节省字符(编码)的存储空间。

首先,计算机通过0-1进行运算,因此自然想到使用二叉树对字符进行编码,叶子对应字符,节点路径对应编码。

ABCDE可以有各种编码。

借用这个图片,https://blog.****.net/TW_345/article/details/50096819

对于哈夫曼编码的理解

这样随意的一个二叉树(忽略节点权值),它的总存储空间已经优于固定长度编码了。在不考虑出现概率的情况下,ABCDE字符的叶子位置是随意互换的。任何一串0-1编码(不考虑末位)都能被解析出唯一的字符串。

可是,如果考虑到进一步节省存储空间,就应该将出现概率大(占比多)的字符用尽量少的0-1进行编码,也就是更靠近根(节点少),这也就是最优二叉树-哈夫曼树。