给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,则称之为最优二叉树,也就是哈夫曼树。
主要用于文件的不等长编码的无损压缩,如视频、文件等
假如,有一个文件中有一串文本:hello,huffman
,接着需要对该文件进行压缩。
在压缩前,文本使用ASCII进行编码,每一个字符都占用1个字节,8bit,那么写入文件后会占用13个字节,共占用104bit。
如果使用Huffuman编码进行压缩的话,会需要这几个步骤:
字符 | h | f | l | e | o | , | u | m | a | n |
---|---|---|---|---|---|---|---|---|---|---|
次数 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
a
与n
构建A与N
u
与m
构建U与M
O
与,
的叶子节点
构建O与,
O
与,
组成的子树以及E
,来构建一个新的子树,然后再根据权重重新排序
构建O与,与E的子树
构建新子树
F
与L
的子树
构建F与L的子树
最优二叉树
0
与1
的编码,而对应的编码也就是Huffman编码。
部分编码如下:字符 | A | H | L | M |
---|---|---|---|---|
编码 | 0000 | 11 | 011 | 0011 |
由于所有的字符都在Huffman树的叶子节点上,所以编码与解码不会有冲突。
通过这棵编码树,就可以对文件进行编解码,来压缩与解压文件了。