Huffman Coding
此文章為本人翻譯的譯文起惕，版權(quán)為原作者所有奸晴。
英文原文：Huffman Coding
思路：用更少的位數(shù)對(duì)經(jīng)常出現(xiàn)的對(duì)象進(jìn)行編碼砸脊。
雖然任何類型的對(duì)象都可以用這種方案進(jìn)行編碼介返，但字節(jié)串壓縮很常見盯腌，所以會(huì)通過字符串壓縮進(jìn)行講解。 假設(shè)有以下文本鬼譬，其中每個(gè)字符是一個(gè)字節(jié)：
so much words wow many compression
通過計(jì)算每個(gè)字節(jié)出現(xiàn)的頻率娜膘，可以看到一些字節(jié)比其他字節(jié)出現(xiàn)次數(shù)更多：
space: 5 u: 1
o: 5 h: 1
s: 4 d: 1
m: 3 a: 1
w: 3 y: 1
c: 2 p: 1
r: 2 e: 1
n: 2 i: 1
我們用二進(jìn)制位來表示每個(gè)字節(jié)。 一個(gè)字節(jié)越常見优质，我們分配給它的位就越少竣贪。 然后得到這樣的編碼表：
space: 5 010 u: 1 11001
o: 5 000 h: 1 10001
s: 4 101 d: 1 11010
m: 3 111 a: 1 11011
w: 3 0010 y: 1 01111
c: 2 0011 p: 1 11000
r: 2 1001 e: 1 01110
n: 2 0110 i: 1 10000
然后用這些位序列替換原始字節(jié)，壓縮后的輸出變?yōu)椋?/p>
101 000 010 111 11001 0011 10001 010 0010 000 1001 11010 101
s o _ m u c h _ w o r d s
010 0010 000 0010 010 111 11011 0110 01111 010 0011 000 111
_ w o w _ m a n y _ c o m
11000 1001 01110 101 101 10000 000 0110 0
p r e s s i o n
最后的額外0位是用來在那里創(chuàng)建完整的字節(jié)數(shù)巩螃。 我們能夠?qū)⒃嫉?4個(gè)字節(jié)壓縮成只有16個(gè)字節(jié)演怎，節(jié)省了超過50％的空間！
（127+1)/8 = 16
為了能夠解碼這些二進(jìn)制位牺六，我們需要有原始的頻率表颤枪。 該表格需要與壓縮數(shù)據(jù)一起傳輸或保存。 否則淑际，解碼器不知道如何解釋這些位畏纲。 由于這個(gè)頻率表的開銷（大約1千字節(jié)），不適合在小數(shù)據(jù)上使用霍夫曼編碼春缕。
How it works
在壓縮字節(jié)流時(shí)盗胀，首先創(chuàng)建一個(gè)頻率表，用于統(tǒng)計(jì)每個(gè)字節(jié)出現(xiàn)的頻率锄贼。 基于此表票灰，創(chuàng)建一個(gè)二叉樹，用于描述每個(gè)輸入字節(jié)的位序列宅荤。
我們的示例的二叉樹像這樣：
注意屑迂，該樹有16個(gè)葉節(jié)點(diǎn)（灰色的），每個(gè)字節(jié)值來自輸入冯键。 每個(gè)葉節(jié)點(diǎn)還顯示出現(xiàn)頻率的次數(shù)惹盼。 其他節(jié)點(diǎn)是“中間”節(jié)點(diǎn)。 這些節(jié)點(diǎn)中顯示的數(shù)字是其子節(jié)點(diǎn)的計(jì)數(shù)總和惫确。 因此根節(jié)點(diǎn)的計(jì)數(shù)是輸入中的總字節(jié)數(shù)手报。
節(jié)點(diǎn)之間的邊是“1”或者“0”蚯舱，對(duì)應(yīng)于葉節(jié)點(diǎn)的位編碼，每個(gè)左分支總是1掩蛤，每個(gè)右分支總是0枉昏。
壓縮就是遍歷輸入字節(jié)流以及遍歷從根節(jié)點(diǎn)到該字節(jié)的所有葉節(jié)點(diǎn)。 每次經(jīng)過左分支時(shí)揍鸟，發(fā)出一個(gè)1-bit兄裂，經(jīng)過右分支時(shí)，發(fā)出一個(gè)0-bit蜈亩。
例如懦窘，要從根節(jié)點(diǎn)到c 右（0）-> 右（0）-> 左（1）-> 左（1）。 所以赫夫曼代碼0011表示c稚配。
解壓的方式完全相反。 它逐個(gè)讀取壓縮的位序列并遍歷樹直到到達(dá)葉節(jié)點(diǎn)港华。 該葉節(jié)點(diǎn)的值就是是未壓縮的字節(jié)道川。 例如，如果位是11010立宜，我們從根開始冒萄，左 ->左 -> 右 -> 左 ->右到d。
The code
在開始真正的霍夫曼編碼之前橙数，需要一些代碼將單個(gè)位寫入NSData對(duì)像尊流。 NSData能理解的最小單位是字節(jié)，但是我們處理的是位灯帮，所以我們需要在兩者之間進(jìn)行轉(zhuǎn)換崖技。
public class BitWriter {
public var data = NSMutableData()
var outByte: UInt8 = 0
var outCount = 0
public func writeBit(bit: Bool) {
if outCount == 8 {
data.append(&outByte, length: 1)
outCount = 0
}
outByte = (outByte << 1) | (bit ? 1 : 0)
outCount += 1
}
public func flush() {
if outCount > 0 {
if outCount < 8 {
let diff = UInt8(8 - outCount)
outByte <<= diff
}
data.append(&outByte, length: 1)
}
}
}
要添加一位到NSData，可以調(diào)用writeBit()钟哥。 這個(gè)輔助對(duì)象將每個(gè)新位加入變量outByte迎献。 一旦寫了8位，outByte便被添加到NSData對(duì)象腻贰。
flush()方法用于輸出最后一個(gè)字節(jié)吁恍。 我們不能保證壓縮位數(shù)是8的整數(shù)倍，flush()會(huì)添加一些0位來確保寫入一個(gè)完整的字節(jié)播演。
這里是一個(gè)類似的輔助對(duì)象冀瓦，用于從NSData中讀取每個(gè)位：
public class BitReader {
var ptr: UnsafePointer<UInt8>
var inByte: UInt8 = 0
var inCount = 8
public init(data: NSData) {
ptr = data.bytes.assumingMemoryBound(to: UInt8.self)
}
public func readBit() -> Bool {
if inCount == 8 {
inByte = ptr.pointee // load the next byte
inCount = 0
ptr = ptr.successor()
}
let bit = inByte & 0x80 // read the next bit
inByte <<= 1
inCount += 1
return bit == 0 ? false : true
}
}
通過這個(gè)對(duì)象，可以從NSData對(duì)象讀取一個(gè)完整的字節(jié)并放入inByte写烤。 然后翼闽，readBit()從該字節(jié)返回各個(gè)位。 一旦readBit()被調(diào)用8次顶霞，讀取NSData中的下一個(gè)字節(jié)肄程。
注意：如果你不熟悉這種類型的位操作锣吼，只需知道這兩個(gè)輔助對(duì)象使我們可以簡單地寫入和讀取位。
The frequency table
霍夫曼壓縮的第一步是讀取整個(gè)輸入流并構(gòu)建頻率表蓝厌。 該表包含所有256個(gè)可能的字節(jié)值玄叠，并顯示輸入數(shù)據(jù)中每個(gè)字節(jié)的出現(xiàn)頻率。
我們可以將此頻率信息存儲(chǔ)在字典或數(shù)組中拓提，由于我們需要構(gòu)建樹读恃，因此將頻率表存儲(chǔ)為樹的葉子。
Huffman定義如下：
class Huffman {
typealias NodeIndex = Int
struct Node {
var count = 0
var index: NodeIndex = -1
var parent: NodeIndex = -1
var left: NodeIndex = -1
var right: NodeIndex = -1
}
var tree = [Node](repeating: Node(), count: 256)
var root: NodeIndex = -1
}
樹結(jié)構(gòu)存儲(chǔ)在對(duì)象為Node的tree數(shù)組中代态。 由于這是一棵二叉樹寺惫，每個(gè)節(jié)點(diǎn)需要兩個(gè)子節(jié)點(diǎn)，left和right蹦疑，以及一個(gè)引用返回其parent節(jié)點(diǎn)西雀。 與典型的二叉樹不同，這些節(jié)點(diǎn)不使用指針來相互引用歉摧，而是在tree數(shù)組中使用簡單的整數(shù)索引艇肴。我們也存儲(chǔ)節(jié)點(diǎn)本身的數(shù)組index，原因稍后會(huì)變得清晰）
注意叁温，該tree目前有256個(gè)條目的空間用于表示葉節(jié)點(diǎn)再悼，因?yàn)橛?56個(gè)可能的字節(jié)值。 當(dāng)然膝但，并不是所有都最終被使用冲九，這取決于輸入。 稍后跟束，我們將在構(gòu)建實(shí)際樹時(shí)添加更多節(jié)點(diǎn)挟纱。 目前嗡靡，還沒有一棵完整樹抖誉，只是包括256個(gè)獨(dú)立的葉節(jié)點(diǎn)任洞，它們之間沒有連接。所有節(jié)點(diǎn)計(jì)數(shù)都是0花鹅。
我們使用以下方法來計(jì)算輸入數(shù)據(jù)中每個(gè)字節(jié)出現(xiàn)的頻率：
fileprivate func countByteFrequency(inData data: NSData) {
var ptr = data.bytes.assumingMemoryBound(to: UInt8.self)
for _ in 0..<data.length {
let i = Int(ptr.pointee)
tree[i].count += 1
tree[i].index = i
ptr = ptr.successor()
}
}
遍歷NSData對(duì)象氧腰，并且每個(gè)字節(jié)遞增相應(yīng)葉節(jié)點(diǎn)的count。 countByteFrequency()完成后刨肃，tree數(shù)組中的前256個(gè)Node對(duì)象表示頻率表古拴。
為了解壓哈夫曼編碼的數(shù)據(jù)塊，我們需要有原始的頻率表真友。 如果我們將壓縮數(shù)據(jù)寫入文件黄痪，那么在文件的某個(gè)地方應(yīng)該包含頻率表。
我們可以轉(zhuǎn)儲(chǔ)tree數(shù)組中的前256個(gè)元素盔然，但效率不高桅打。 因?yàn)椴⒉皇撬羞@256個(gè)元素都會(huì)被使用是嗜，我們不需要序列化parent指針，right指針和left指針挺尾。 我們所需要的只是頻率信息而不是整個(gè)樹鹅搪。
我們將添加一個(gè)方法來導(dǎo)出頻率表，去掉不需要的部分：
struct Freq {
var byte: UInt8 = 0
var count = 0
}
func frequencyTable() -> [Freq] {
var a = [Freq]()
for i in 0..<256 where tree[i].count > 0 {
a.append(Freq(byte: UInt8(i), count: tree[i].count))
}
return a
}
frequencyTable()方法查看樹中前256個(gè)節(jié)點(diǎn)遭铺，但只保留那些使用到的節(jié)點(diǎn)丽柿，沒有parent節(jié)點(diǎn)，left節(jié)點(diǎn)和right節(jié)點(diǎn)指針魂挂。 它返回一個(gè)Freq對(duì)象數(shù)組甫题。 必須將此數(shù)組與序列化的壓縮數(shù)據(jù)一起使用，以便稍后進(jìn)行解壓涂召。
The tree
例子壓縮需要的樹：
葉節(jié)點(diǎn)表示輸入數(shù)據(jù)中的實(shí)際字節(jié)坠非。中間節(jié)點(diǎn)以這樣的方式連接葉節(jié)點(diǎn)，使得從根節(jié)點(diǎn)到常用字節(jié)值的路徑短于不常用字節(jié)值的路徑芹扭。 正如你所看到的麻顶，m，s舱卡，space和o是我們輸入數(shù)據(jù)中最常見的字母，并且是樹中最上層的字母队萤。
為了構(gòu)建樹轮锥，執(zhí)行以下操作：
- 查找具有最小計(jì)數(shù)的兩個(gè)沒有父節(jié)點(diǎn)的節(jié)點(diǎn)。
- 創(chuàng)建一個(gè)將這兩個(gè)節(jié)點(diǎn)鏈接在一起的新父節(jié)點(diǎn)要尔。
- 重復(fù)舍杜，直到只有一個(gè)沒有父節(jié)點(diǎn)的節(jié)點(diǎn)，成為樹的根節(jié)點(diǎn)赵辕。
這是使用優(yōu)先隊(duì)列的理想情況既绩。 優(yōu)先級(jí)隊(duì)列是經(jīng)過優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，因此找到最小值總是很快还惠。 在這里饲握，我們反復(fù)找到計(jì)數(shù)最小的節(jié)點(diǎn)。
函數(shù)buildTree()變成這樣：
fileprivate func buildTree() {
var queue = PriorityQueue<Node>(sort: { $0.count < $1.count })
for node in tree where node.count > 0 {
queue.enqueue(node) // 1
}
while queue.count > 1 {
let node1 = queue.dequeue()! // 2
let node2 = queue.dequeue()!
var parentNode = Node() // 3
parentNode.count = node1.count + node2.count
parentNode.left = node1.index
parentNode.right = node2.index
parentNode.index = tree.count
tree.append(parentNode)
tree[node1.index].parent = parentNode.index // 4
tree[node2.index].parent = parentNode.index
queue.enqueue(parentNode) // 5
}
let rootNode = queue.dequeue()! // 6
root = rootNode.index
}
這是它如何工作的一步一步：
- 創(chuàng)建優(yōu)先級(jí)隊(duì)列并對(duì)所有具有至少1個(gè)計(jì)數(shù)的葉節(jié)點(diǎn)進(jìn)行排隊(duì)（如果計(jì)數(shù)為0蚕键，則該字節(jié)值不會(huì)出現(xiàn)在輸入數(shù)據(jù)數(shù)據(jù)中）.
PriorityQueue對(duì)象按計(jì)數(shù)排序節(jié)點(diǎn)救欧，具有最低計(jì)數(shù)的節(jié)點(diǎn)始終是第一個(gè)出列的節(jié)點(diǎn)。 - 當(dāng)隊(duì)列中至少有兩個(gè)節(jié)點(diǎn)時(shí)锣光，刪除隊(duì)列前面的兩個(gè)節(jié)點(diǎn)笆怠。由于這是一個(gè)最小優(yōu)先級(jí)隊(duì)列，這給了我們兩個(gè)具有最小計(jì)數(shù)但沒有父節(jié)點(diǎn)的節(jié)點(diǎn)誊爹。
- 創(chuàng)建一個(gè)連接
node1和node2的新中間節(jié)點(diǎn)蹬刷。 這個(gè)新節(jié)點(diǎn)的計(jì)數(shù)是node1和node2的計(jì)數(shù)之和瓢捉。 由于節(jié)點(diǎn)使用數(shù)組索引而不是真實(shí)指針連接，因此我們使用node1.index和node2.index在tree數(shù)組中找到這些節(jié)點(diǎn)办成。（這就是為什么Node需要知道它自己的索引泡态。） - 將兩個(gè)節(jié)點(diǎn)鏈接到它們的新父節(jié)點(diǎn)。 現(xiàn)在這個(gè)新的中間節(jié)點(diǎn)已經(jīng)成為樹的一部分诈火。
- 將新的中間節(jié)點(diǎn)放回隊(duì)列中兽赁。 此時(shí)我們完成了
node1和node2，但是parentNode仍然需要連接到樹中的其他節(jié)點(diǎn)冷守。 - 重復(fù)步驟2-5刀崖，直到隊(duì)列中只剩下一個(gè)節(jié)點(diǎn)。 這成為樹的根節(jié)點(diǎn)拍摇。
該過程動(dòng)畫：
注意：不使用優(yōu)先級(jí)隊(duì)列亮钦，也可以重復(fù)遍歷樹數(shù)組以找到接下來的兩個(gè)最小節(jié)點(diǎn)，但這會(huì)使壓縮器的運(yùn)行速度變慢O（n ^ 2）充活。 使用優(yōu)先級(jí)隊(duì)列蜂莉，運(yùn)行時(shí)間僅為O（n log n），其中n是節(jié)點(diǎn)數(shù)量混卵。
有趣的事實(shí)：由于二叉樹的特點(diǎn)映穗，如果有x個(gè)葉節(jié)點(diǎn)，最多可以為樹添加x-1個(gè)附加節(jié)點(diǎn)幕随。 鑒于最多會(huì)有256個(gè)葉節(jié)點(diǎn)蚁滋，樹節(jié)點(diǎn)總數(shù) 永遠(yuǎn)不會(huì)超過511個(gè)。
Compression
現(xiàn)在我們知道如何從頻率表構(gòu)建壓縮樹赘淮，可以使用它來壓縮NSData對(duì)象辕录。 代碼如下：
public func compressData(data: NSData) -> NSData {
countByteFrequency(inData: data)
buildTree()
let writer = BitWriter()
var ptr = data.bytes.assumingMemoryBound(to: UInt8.self)
for _ in 0..<data.length {
let c = ptr.pointee
let i = Int(c)
traverseTree(writer: writer, nodeIndex: i, childIndex: -1)
ptr = ptr.successor()
}
writer.flush()
return writer.data
}
首先調(diào)用countByteFrequency()創(chuàng)建頻率表，然后調(diào)用buildTree()創(chuàng)建壓縮樹梢卸。 它還創(chuàng)建一個(gè)BitWriter對(duì)象來寫入各個(gè)位走诞。
然后遍歷輸入流并為每個(gè)字節(jié)調(diào)用traverseTree()。 此方法將遍歷樹節(jié)點(diǎn)蛤高，每個(gè)節(jié)點(diǎn)寫入1或0蚣旱。 最后，返回BitWriter的數(shù)據(jù)對(duì)象襟齿。
注意：壓縮總是需要兩次遍歷整個(gè)輸入數(shù)據(jù)：首先建立頻率表姻锁，然后將字節(jié)轉(zhuǎn)換成壓縮的位序列。
有趣的事情發(fā)生在traverseTree()中猜欺。 這是一個(gè)遞歸方法：
private func traverseTree(writer: BitWriter, nodeIndex h: Int, childIndex child: Int) {
if tree[h].parent != -1 {
traverseTree(writer: writer, nodeIndex: tree[h].parent, childIndex: h)
}
if child != -1 {
if child == tree[h].left {
writer.writeBit(bit: true)
} else if child == tree[h].right {
writer.writeBit(bit: false)
}
}
}
當(dāng)在compressData()調(diào)用該方法時(shí)位隶，nodeIndex參數(shù)是我們需要編碼的字節(jié)的葉節(jié)點(diǎn)的數(shù)組索引。 該方法遞歸地將樹從葉節(jié)點(diǎn)遞歸到根开皿，然后再返回涧黄。
當(dāng)我們從根節(jié)點(diǎn)回到葉節(jié)點(diǎn)時(shí)篮昧，為每個(gè)遇到的節(jié)點(diǎn)寫1或0。
即使樹的插圖顯示節(jié)點(diǎn)之間每個(gè)邊為0或1笋妥，位值0和1實(shí)際上并不存儲(chǔ)在樹中懊昨！ 規(guī)則是，如果我們?nèi)∽蠓种Т盒覀儗?位酵颁，如果我們?nèi)∮曳种В瑒t寫0位月帝，所以只知道我們進(jìn)入的方向足以確定要寫入的位值躏惋。
compressData()方法如下：
let s1 = "so much words wow many compression"
if let originalData = s1.dataUsingEncoding(NSUTF8StringEncoding) {
let huffman1 = Huffman()
let compressedData = huffman1.compressData(originalData)
print(compressedData.length)
}
Decompression
解壓和壓縮是相反。但是嚷辅，沒有頻率表的壓縮位序列是沒有用的簿姨。 前面講到frequencyTable()方法返回一個(gè)Freq對(duì)象數(shù)組。 如果將壓縮數(shù)據(jù)保存到文件中或通過網(wǎng)絡(luò)發(fā)送簸搞，也會(huì)將[Freq]數(shù)組和它一起保存扁位。
我們首先需要一些方法將[Freq]數(shù)組重新轉(zhuǎn)換為壓縮樹：
fileprivate func restoreTree(fromTable frequencyTable: [Freq]) {
for freq in frequencyTable {
let i = Int(freq.byte)
tree[i].count = freq.count
tree[i].index = i
}
buildTree()
}
我們將Freq對(duì)象轉(zhuǎn)換為葉節(jié)點(diǎn)，然后調(diào)用buildTree()來完成剩下的工作趁俊。
下面是decompressData()的代碼域仇，參數(shù)是霍夫曼編碼的NSData對(duì)象和頻率表，并返回原始數(shù)據(jù)：
func decompressData(data: NSData, frequencyTable: [Freq]) -> NSData {
restoreTree(fromTable: frequencyTable)
let reader = BitReader(data: data)
let outData = NSMutableData()
let byteCount = tree[root].count
var i = 0
while i < byteCount {
var b = findLeafNode(reader: reader, nodeIndex: root)
outData.append(&b, length: 1)
i += 1
}
return outData
}
使用了findLeafNode方法遍歷樹：
private func findLeafNode(reader reader: BitReader, nodeIndex: Int) -> UInt8 {
var h = nodeIndex
while tree[h].right != -1 {
if reader.readBit() {
h = tree[h].left
} else {
h = tree[h].right
}
}
return UInt8(h)
}
findLeafNode()將樹從根走到由nodeIndex給定的葉節(jié)點(diǎn)寺擂。 在每個(gè)中間節(jié)點(diǎn)處殉簸，讀取一個(gè)新位，然后向左（位為1）或向右（位為0）前進(jìn)沽讹。 當(dāng)?shù)竭_(dá)葉節(jié)點(diǎn)時(shí)返回它的索引，也就是原始字節(jié)值武鲁。
可以像這樣使用解壓方法：
let frequencyTable = huffman1.frequencyTable()
let huffman2 = Huffman()
let decompressedData = huffman2.decompressData(compressedData, frequencyTable: frequencyTable)
let s2 = String(data: decompressedData, encoding: NSUTF8StringEncoding)!
首先獲得頻率表爽雄，然后調(diào)用decompressData()，得到字符串應(yīng)該與壓縮前的字符串相同沐鼠。
