昨天電話面試的過程中被問到了可變長編碼，被問的有點懵逼。。特地來記錄一下。
由于度娘上面沒有搜到相關(guān)的文章，所以只能自己總結(jié)一下，搜到的可變長編碼好像有赫夫曼編碼和UTF編碼。UTF編碼又有UTF-8和UTF-16，本文僅對更為常見的UTF-8編碼進行簡單的分析介紹。
一、赫夫曼編碼
赫夫曼編碼（Huffman Coding），又稱哈夫曼編碼、霍夫曼編碼，是可變字長編碼（VLC）的一種。在說赫夫曼編碼前，需要先引入另一個概念：赫夫曼。赫夫曼樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。
赫夫曼樹的定義：假設(shè)有 n 個權(quán)值{w1 ,w2 ,... ,wn}，試構(gòu)造一顆有 n 個葉子結(jié)點的二叉樹，每個葉子結(jié)點帶權(quán)為wi，則其中帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或霍夫曼樹。
舉個例子：假如現(xiàn)在有A ,B ,C ,D ,E這五個字符，它們分別出現(xiàn)的頻率（即權(quán)值）為5,4,3,2,1，下圖為赫夫曼樹的構(gòu)建過程（每次取兩個權(quán)值最小的節(jié)點生成一個樹）：
這樣一個赫夫曼樹就生成了，接下來就可以對這五個字符進行編碼了，首先將這個五個字符把樹中的權(quán)值替換掉，其次給樹的左分支標記位0，右分支標記為1，然后從根結(jié)點一直到到該字符所在結(jié)點所走過的分支（標記的數(shù)）連接在一起所得的值就是該字符的赫夫曼編碼：
如圖，所得編碼結(jié)果為：
| 字符 | 編碼 |
|---|---|
| A | 11 |
| B | 10 |
| C | 00 |
| D | 011 |
| E | 010 |
赫夫曼編碼是一種無前綴編碼。解碼時不會混淆。其主要應(yīng)用在數(shù)據(jù)壓縮，加密解密等場合。
二、UTF-8編碼
UTF-8（8-bit Unicode Transformation Format）是一種針對Unicode的可變長度字符編碼，又稱萬國碼。
UTF-8編碼規(guī)則：如果只有一個字節(jié)則其最高二進制位為0；如果是多字節(jié)，其第一個字節(jié)從最高位開始，連續(xù)的二進制位值為 1 的個數(shù)決定了其編碼的字節(jié)數(shù)，其余各字節(jié)均以 10 開頭。UTF-8轉(zhuǎn)換表表示如下：
| Unicode/UCS-4 | bit數(shù) | UTF-8 | byte數(shù) | 備注 |
|---|---|---|---|---|
| 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 編碼 早期的規(guī)范UTF-8可以到達6字節(jié)序列，可以覆蓋到31位元（通用字符集原來的極限）。盡管如此，2003年11月UTF-8 被 RFC 3629 重新規(guī)范，只能使用原來Unicode定義的區(qū)域， U+0000到U+10FFFF。根據(jù)規(guī)范，這些字節(jié)值將無法出現(xiàn)在合法 UTF-8序列中 |
| 400 0000 ~ 7FFF FFFF |
27~31 | 1111 110X 10XXXXXX 10XXXXXX 10XXXXXX 10XXXXXX 10XXXXXX |
6 | 同上 |
實際表示ASCII字符的UNICODE字符，將會編碼成1個字節(jié)，并且UTF-8表示與ASCII字符表示是一樣的。所有其他的UNICODE字符轉(zhuǎn)化成UTF-8將需要至少2個字節(jié)。每個字節(jié)由一個換碼序列開始。第一個字節(jié)由唯一的換碼序列，由n位連續(xù)的1加一位0組成, 首字節(jié)連續(xù)的1的個數(shù)表示字符編碼所需的字節(jié)數(shù)。
Unicode轉(zhuǎn)換為UTF-8時，可以將Unicode二進制從低位往高位取出二進制數(shù)字，每次取6位，如上述的二進制就可以分別取出為如下示例所示的格式，前面按格式填補，不足8位用0填補。
注：Unicode轉(zhuǎn)換為UTF-8需要的字節(jié)數(shù)可以根據(jù)這個規(guī)則計算：如果Unicode小于0X80（Ascii字符），則轉(zhuǎn)換后為1個字節(jié)。否則轉(zhuǎn)換后的字節(jié)數(shù)為Unicode二進制位數(shù)+3再除以5。
