可变长编码（赫夫曼编码，UTF-8编码）
昨天电话面试的过程中被问到了可变长编码，被问的有点懵逼。。特地来记录一下。
由于度娘上面没有搜到相关的文章，所以只能自己总结一下，搜到的可变长编码好像有赫夫曼编码和UTF编码。UTF编码又有UTF-8和UTF-16，本文仅对更为常见的UTF-8编码进行简单的分析介绍。
一、赫夫曼编码
赫夫曼编码（Huffman Coding），又称哈夫曼编码、霍夫曼编码，是可变字长编码（VLC）的一种。在说赫夫曼编码前，需要先引入另一个概念：赫夫曼。赫夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。
赫夫曼树的定义：假设有 n 个权值{w1 ,w2 ,... ,wn}，试构造一颗有 n 个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树或霍夫曼树。
举个例子：假如现在有A ,B ,C ,D ,E这五个字符，它们分别出现的频率（即权值）为5,4,3,2,1，下图为赫夫曼树的构建过程（每次取两个权值最小的节点生成一个树）：
赫夫曼树构建过程
这样一个赫夫曼树就生成了，接下来就可以对这五个字符进行编码了，首先将这个五个字符把树中的权值替换掉，其次给树的左分支标记位0，右分支标记为1，然后从根结点一直到到该字符所在结点所走过的分支（标记的数）连接在一起所得的值就是该字符的赫夫曼编码：
如图，所得编码结果为：
| 字符 | 编码 |
|---|---|
| A | 11 |
| B | 10 |
| C | 00 |
| D | 011 |
| E | 010 |
赫夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。
二、UTF-8编码
UTF-8（8-bit Unicode Transformation Format）是一种针对Unicode的可变长度字符编码，又称万国码。
UTF-8编码规则：如果只有一个字节则其最高二进制位为0；如果是多字节，其第一个字节从最高位开始，连续的二进制位值为 1 的个数决定了其编码的字节数，其余各字节均以 10 开头。UTF-8转换表表示如下：
| Unicode/UCS-4 | bit数 | UTF-8 | byte数 | 备注 |
|---|---|---|---|---|
| 0000 ~ 007F | 0~7 | 0XXXXXXX | 1 | |
| 0080 ~ 07FF | 8~11 | 110XXXXX 10XXXXXX |
2 | |
| 0800 ~FFFF | 12~16 | 1110 XXXX 10XXXXXX 10XXXXXX |
3 | 基本定义范围：0~FFFF |
| 1 0000 ~1F FFFF | 17~21 | 11110XXX 10XXXXXX 10XXXXXX 10XXXXXX |
4 | Unicode6.1定义范围：0~10 FFFF |
| 20 0000 ~ 3FF FFFF |
22~26 | 111110XX 10XXXXXX 10XXXXXX 10XXXXXX 10XXXXXX |
5 | 说明：此非unicode编码范围，属于UCS-4 编码 早期的规范UTF-8可以到达6字节序列，可以覆盖到31位元（通用字符集原来的极限）。尽管如此，2003年11月UTF-8 被 RFC 3629 重新规范，只能使用原来Unicode定义的区域， U+0000到U+10FFFF。根据规范，这些字节值将无法出现在合法 UTF-8序列中 |
| 400 0000 ~ 7FFF FFFF |
27~31 | 1111 110X 10XXXXXX 10XXXXXX 10XXXXXX 10XXXXXX 10XXXXXX |
6 | 同上 |
实际表示ASCII字符的UNICODE字符，将会编码成1个字节，并且UTF-8表示与ASCII字符表示是一样的。所有其他的UNICODE字符转化成UTF-8将需要至少2个字节。每个字节由一个换码序列开始。第一个字节由唯一的换码序列，由n位连续的1加一位0组成, 首字节连续的1的个数表示字符编码所需的字节数。
Unicode转换为UTF-8时，可以将Unicode二进制从低位往高位取出二进制数字，每次取6位，如上述的二进制就可以分别取出为如下示例所示的格式，前面按格式填补，不足8位用0填补。
注：Unicode转换为UTF-8需要的字节数可以根据这个规则计算：如果Unicode小于0X80（Ascii字符），则转换后为1个字节。否则转换后的字节数为Unicode二进制位数+3再除以5。
