赫夫曼樹(shù)
在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中载弄，從樹(shù)中的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上分支的數(shù)目叫做路徑長(zhǎng)度撵颊，從根結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和叫做樹(shù)的路徑長(zhǎng)度宇攻。如果一個(gè)結(jié)點(diǎn)帶有權(quán)重，則路徑長(zhǎng)度和該結(jié)點(diǎn)權(quán)重的乘積叫做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度(WPL)倡勇，一棵樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和逞刷。
赫夫曼樹(shù)（霍夫曼樹(shù)），又稱最優(yōu)樹(shù)或者最優(yōu)二叉樹(shù)。假設(shè)有n個(gè)權(quán)值{,
,...,
}夸浅，通過(guò)這n個(gè)權(quán)值構(gòu)造n個(gè)結(jié)點(diǎn)仑最，每個(gè)結(jié)點(diǎn)的權(quán)值為
（1<=i<=n），然后以這n個(gè)結(jié)點(diǎn)為葉子結(jié)點(diǎn)構(gòu)造一棵二叉樹(shù)帆喇，在所有構(gòu)成的二叉樹(shù)中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)被稱作最優(yōu)二叉樹(shù)或者赫夫曼樹(shù)警医。如下:
給定4個(gè)權(quán)重分別為7, 5, 2, 4的四個(gè)葉子結(jié)點(diǎn)a, b, c, d, 下圖為用該4個(gè)結(jié)點(diǎn)構(gòu)造的3棵二叉樹(shù):
上面圖中三個(gè)二叉樹(shù)的帶權(quán)路徑長(zhǎng)度分別為:
(a) WPL = 72 + 52 + 22 + 42 = 36
(b) WPL = 73 + 53 + 21 + 42 = 46
(c) WPL = 71 + 52 + 23 + 43 = 35
其中(c)的帶權(quán)路徑最小，從圖中可以看出：權(quán)值從高到低的節(jié)點(diǎn)對(duì)應(yīng)路徑長(zhǎng)度依次遞增坯钦，可以得出該樹(shù)的帶權(quán)路徑為最小预皇，該樹(shù)即為赫夫曼樹(shù)。
赫夫曼樹(shù)的構(gòu)造
構(gòu)造赫夫曼樹(shù)的步驟如下:
根據(jù)給定的n個(gè)權(quán)值{
,
,...,
}構(gòu)成n棵二叉樹(shù)集合F={
,
,...,
}葫笼，其中每棵二叉樹(shù)
中只有一個(gè)帶權(quán)為
的根結(jié)點(diǎn)深啤，其左右子樹(shù)均為空（即初始集合中每棵樹(shù)只有一個(gè)根結(jié)點(diǎn)）。
在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)路星，并且新二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為兩棵子樹(shù)根結(jié)點(diǎn)的權(quán)值之和溯街。
在F中刪除步驟2中選中的兩棵樹(shù)，同時(shí)步驟2新構(gòu)造出的二叉樹(shù)加入到F中洋丐。
重復(fù)步驟2和3呈昔，直到F中只剩下一棵樹(shù)為止，此時(shí)剩下的這棵樹(shù)便是赫夫曼樹(shù)友绝。
具體過(guò)程如下圖所示堤尾，為前面給定的4個(gè)結(jié)點(diǎn)構(gòu)造赫夫曼樹(shù)的過(guò)程(注意：圖中的結(jié)點(diǎn)按照權(quán)值大小已經(jīng)排好序，在實(shí)際代碼中需要排序或者選出最小權(quán)值結(jié)點(diǎn)的過(guò)程):
赫夫曼樹(shù)的應(yīng)用-赫夫曼編碼
在現(xiàn)實(shí)生活中迁客，我們通常經(jīng)常會(huì)遇到對(duì)數(shù)據(jù)進(jìn)行編碼的場(chǎng)景郭宝，目的是為了對(duì)數(shù)據(jù)進(jìn)行一定程度的壓縮的同時(shí)也能對(duì)原始數(shù)據(jù)進(jìn)行加密工作，從而避免原始數(shù)據(jù)暴露在網(wǎng)絡(luò)中掷漱。最簡(jiǎn)單的方法是對(duì)每個(gè)原始數(shù)據(jù)的每個(gè)源符號(hào)生成一個(gè)固定長(zhǎng)度的編碼粘室，然后用編碼替換每個(gè)源符號(hào)，以達(dá)到對(duì)整個(gè)數(shù)據(jù)編碼的目的卜范。但是這種方法有兩個(gè)弊端:
每個(gè)編碼長(zhǎng)度固定衔统，容易被破譯。
每個(gè)編碼長(zhǎng)度固定海雪，導(dǎo)致編碼后的數(shù)據(jù)長(zhǎng)度不盡如人意锦爵。
而赫夫曼編碼則很好的規(guī)避了這兩個(gè)問(wèn)題，赫夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)進(jìn)行編碼奥裸，其中每個(gè)編碼的長(zhǎng)度是根據(jù)評(píng)估源符號(hào)出現(xiàn)幾率的方法得到的险掀，即出現(xiàn)頻率高的源符號(hào)使用較短的編碼，反之使用較長(zhǎng)的編碼湾宙，這樣編碼后的數(shù)據(jù)整體平均長(zhǎng)度降低迷郑，從而實(shí)現(xiàn)更高效的壓縮枝恋。例如在英文中，e的出現(xiàn)幾率最高嗡害，而z的出現(xiàn)幾率最低，當(dāng)利用赫夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)畦攘，假設(shè)e用一個(gè)bit來(lái)表示霸妹，而z則可能用25個(gè)bit表示。如果使用定長(zhǎng)的編碼表示知押，每個(gè)英文字母使用8個(gè)bit來(lái)表示叹螟。二者相比，普通方法中台盯，頻率最高的e就會(huì)浪費(fèi)7個(gè)bit罢绽，而赫夫曼中z則是3倍多，但是如果能夠?qū)τ⑽闹懈鱾€(gè)字母出現(xiàn)的概率有較準(zhǔn)確的估算静盅，則可以大幅度的提高無(wú)損壓縮比例良价。
赫夫曼編碼是對(duì)赫夫曼樹(shù)的一種應(yīng)用，常用于處理符號(hào)編寫工作蒿叠，根據(jù)原始數(shù)據(jù)中符號(hào)出現(xiàn)的頻率高低明垢，決定如何給符號(hào)編碼，頻率越高的符號(hào)編碼越短市咽，相反編碼越長(zhǎng)痊银。
赫夫曼編碼是由通過(guò)構(gòu)造赫夫曼樹(shù)生成的一種編碼。編碼生成過(guò)程如下:
假設(shè)給定的某些英文符號(hào)的出現(xiàn)頻率如下表所示:
| 符號(hào) | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 頻率 | 2 | 3 | 4 | 4 | 5 | 7 |
我們以頻率為權(quán)值構(gòu)造6棵只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)施绎，然后按照赫夫曼樹(shù)的構(gòu)造規(guī)則構(gòu)造赫夫曼樹(shù):
構(gòu)造好赫夫曼樹(shù)后溯革，下一步便是進(jìn)行編碼，赫夫曼編碼步驟為:
- 給赫夫曼樹(shù)中存在孩子結(jié)點(diǎn)的左路徑編碼"0"谷醉，右路徑編碼"1"
- 從赫夫曼樹(shù)的根結(jié)點(diǎn)開(kāi)始到每一個(gè)葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑的編碼組成的一個(gè)編碼串便是該葉子結(jié)點(diǎn)代表的符號(hào)的赫夫曼編碼致稀。
如下圖:
根據(jù)上圖得到每個(gè)字符的編碼為:
| 符號(hào) | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 頻率 | 2 | 3 | 4 | 4 | 5 | 7 |
| 編碼 | 010 | 011 | 110 | 111 | 00 | 10 |
注意: 赫夫曼編碼并不唯一，如上圖中的C和D的位置可以互換
對(duì)數(shù)據(jù)編碼的過(guò)程為構(gòu)造赫夫曼樹(shù)孤紧，然后根據(jù)生成的編碼來(lái)進(jìn)行壓縮豺裆，而數(shù)據(jù)解碼則與編碼相反，解碼根據(jù)給定的編碼數(shù)據(jù)号显，遍歷赫夫曼樹(shù)得到原始數(shù)據(jù)臭猜。下面為用Go語(yǔ)言實(shí)現(xiàn)的赫夫曼樹(shù)。
代碼實(shí)現(xiàn)
type HuffmanNodeList []*HuffmanNode
func (list HuffmanNodeList) Len() int {
return len(list)
}
func (list HuffmanNodeList) Swap(i, j int) {
list[i], list[j] = list[j], list[i]
}
func (list HuffmanNodeList) Less(i, j int) bool {
return list[i].Weight < list[j].Weight
}
//赫夫曼節(jié)點(diǎn)押蚤，用于構(gòu)成赫夫曼樹(shù)
type HuffmanNode struct {
Weight uint //權(quán)重
Data interface{} //數(shù)據(jù)
Parent *HuffmanNode //父節(jié)點(diǎn)
Left *HuffmanNode //左孩子
Right *HuffmanNode //右孩子
}
//赫夫曼樹(shù)結(jié)構(gòu)蔑歌，這里使用的interface作為源數(shù)據(jù)類型
type HuffmanTree struct {
root *HuffmanNode //根節(jié)點(diǎn)
leaf HuffmanNodeList //所有葉子節(jié)點(diǎn)（即數(shù)據(jù)對(duì)應(yīng)的節(jié)點(diǎn)）
src map[interface{}]uint //源數(shù)據(jù)，key為數(shù)據(jù)揽碘，value為權(quán)重
codeSet map[interface{}]string //編碼集次屠，key為數(shù)據(jù)园匹，value為通過(guò)構(gòu)造赫夫曼樹(shù)得到的數(shù)據(jù)的編碼
}
//給定一組字符及其權(quán)重的集合，初始化出一棵赫夫曼樹(shù)
func NewHuffmanTree(src map[interface{}]uint) *HuffmanTree {
var tree = &HuffmanTree{
src: src,
}
tree.init()
tree.build()
tree.parse()
return tree
}
//根據(jù)數(shù)據(jù)進(jìn)行赫夫曼編碼
func (h *HuffmanTree) Coding(target interface{}) (result string) {
if target == nil {
return
}
var s string
switch t := target.(type) {
case string:
s = t
case []byte:
s = string(t)
default:
return
}
for _, t := range s {
v := string(t)
if c, ok := h.codeSet[v]; !ok {
panic("invalid code: " + v)
} else {
result += c
}
}
return result
}
//根據(jù)赫夫曼編碼獲取數(shù)據(jù)
func (h *HuffmanTree) UnCoding(target string) (result string) {
node := h.root
for i := 0; i < len(target); i++ {
switch target[i] {
case '0':
node = node.Left
case '1':
node = node.Right
}
if node.Left == nil && node.Right == nil {
result = result + node.Data.(string)
node = h.root
}
}
return
}
//初始化所有葉子節(jié)點(diǎn)
func (h *HuffmanTree) init() {
if len(h.src) <= 1 {
panic("invalid src length.")
}
h.codeSet = make(map[interface{}]string)
h.leaf = make(HuffmanNodeList, len(h.src))
var i int
for data, weight := range h.src {
var node = &HuffmanNode{
Weight: weight,
Data: data,
}
h.leaf[i] = node
i++
}
//對(duì)leaf根據(jù)權(quán)值排序
sort.Sort(h.leaf)
}
//構(gòu)造赫夫曼樹(shù)
//src: key為data劫灶，value為權(quán)值
func (h *HuffmanTree) build() {
nodeList := h.leaf
//根據(jù)huffman樹(shù)的規(guī)則構(gòu)造赫夫曼樹(shù)
for nodeList.Len() > 1 {
//1. 選取權(quán)值最小的兩個(gè)node構(gòu)造出第一個(gè)節(jié)點(diǎn)
var temp = &HuffmanNode{
Weight: nodeList[0].Weight + nodeList[1].Weight,
Left: nodeList[0],
Right: nodeList[1],
}
nodeList[0].Parent = temp
nodeList[1].Parent = temp
//2.將生成的新節(jié)點(diǎn)插入節(jié)點(diǎn)序列中
nodeList = regroup(nodeList[2:], temp)
}
h.root = nodeList[0]
}
//獲取每個(gè)byte的編碼裸违，目的是為了下次需要編碼的時(shí)候不用再次遍歷樹(shù)以獲取每個(gè)byte的編碼了
//在赫夫曼樹(shù)中的所有節(jié)點(diǎn)要么沒(méi)有孩子節(jié)點(diǎn)，要么有兩個(gè)孩子節(jié)點(diǎn)本昏，不存在只有一個(gè)孩子節(jié)點(diǎn)的節(jié)點(diǎn)
//此處的編碼為由底至頂獲取供汛，也可以由頂至底的獲取
func (h *HuffmanTree) parse() {
if h.root == nil {
return
}
var temp *HuffmanNode
var code string
for _, n := range h.leaf {
temp = n
for temp.Parent != nil {
if temp == temp.Parent.Left {
code = "0" + code
} else {
code = "1" + code
}
temp = temp.Parent
}
h.codeSet[n.Data] = code
code = ""
}
}
//重組，將生成的節(jié)點(diǎn)放入既有的list涌穆，排序后返回怔昨，權(quán)值最小的始終在最前面
func regroup(src HuffmanNodeList, temp *HuffmanNode) HuffmanNodeList {
//將temp添加進(jìn)src，然后取出weight最小的一個(gè)
length := len(src)
result := make(HuffmanNodeList, len(src)+1)
if length == 0 {
result[0] = temp
return result
}
if src[length-1].Weight <= temp.Weight {
copy(result, src)
result[length] = temp
return result
}
for i := range src {
if src[i].Weight <= temp.Weight {
result[i] = src[i]
} else {
result[i] = temp
copy(result[i+1:], src[i:])
break
}
}
return result
}
參考文獻(xiàn)
《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》
《Wiki》
最后
謝謝閱讀宿稀，此處為源碼趁舀。
