iOS霍夫曼编码（译文）
Huffman Coding
此文章为本人翻译的译文，版权为原作者所有。
英文原文：Huffman Coding
思路：用更少的位数对经常出现的对象进行编码。
虽然任何类型的对象都可以用这种方案进行编码，但字节串压缩很常见，所以会通过字符串压缩进行讲解。 假设有以下文本，其中每个字符是一个字节：
so much words wow many compression
通过计算每个字节出现的频率，可以看到一些字节比其他字节出现次数更多：
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
我们用二进制位来表示每个字节。 一个字节越常见，我们分配给它的位就越少。 然后得到这样的编码表：
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
然后用这些位序列替换原始字节，压缩后的输出变为：
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位是用来在那里创建完整的字节数。 我们能够将原始的34个字节压缩成只有16个字节，节省了超过50％的空间！
（127+1)/8 = 16
为了能够解码这些二进制位，我们需要有原始的频率表。 该表格需要与压缩数据一起传输或保存。 否则，解码器不知道如何解释这些位。 由于这个频率表的开销（大约1千字节），不适合在小数据上使用霍夫曼编码。
How it works
在压缩字节流时，首先创建一个频率表，用于统计每个字节出现的频率。 基于此表，创建一个二叉树，用于描述每个输入字节的位序列。
我们的示例的二叉树像这样：
Tree.png
注意，该树有16个叶节点（灰色的），每个字节值来自输入。 每个叶节点还显示出现频率的次数。 其他节点是“中间”节点。 这些节点中显示的数字是其子节点的计数总和。 因此根节点的计数是输入中的总字节数。
节点之间的边是“1”或者“0”，对应于叶节点的位编码，每个左分支总是1，每个右分支总是0。
压缩就是遍历输入字节流以及遍历从根节点到该字节的所有叶节点。 每次经过左分支时，发出一个1-bit，经过右分支时，发出一个0-bit。
例如，要从根节点到c 右（0）-> 右（0）-> 左（1）-> 左（1）。 所以赫夫曼代码0011表示c。
解压的方式完全相反。 它逐个读取压缩的位序列并遍历树直到到达叶节点。 该叶节点的值就是是未压缩的字节。 例如，如果位是11010，我们从根开始，左 ->左 -> 右 -> 左 ->右到d。
The code
在开始真正的霍夫曼编码之前，需要一些代码将单个位写入NSData对像。 NSData能理解的最小单位是字节，但是我们处理的是位，所以我们需要在两者之间进行转换。
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，可以调用writeBit()。 这个辅助对象将每个新位加入变量outByte。 一旦写了8位，outByte便被添加到NSData对象。
flush()方法用于输出最后一个字节。 我们不能保证压缩位数是8的整数倍，flush()会添加一些0位来确保写入一个完整的字节。
这里是一个类似的辅助对象，用于从NSData中读取每个位：
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
}
}
通过这个对象，可以从NSData对象读取一个完整的字节并放入inByte。 然后，readBit()从该字节返回各个位。 一旦readBit()被调用8次，读取NSData中的下一个字节。
注意：如果你不熟悉这种类型的位操作，只需知道这两个辅助对象使我们可以简单地写入和读取位。
The frequency table
霍夫曼压缩的第一步是读取整个输入流并构建频率表。 该表包含所有256个可能的字节值，并显示输入数据中每个字节的出现频率。
我们可以将此频率信息存储在字典或数组中，由于我们需要构建树，因此将频率表存储为树的叶子。
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
}
树结构存储在对象为Node的tree数组中。 由于这是一棵二叉树，每个节点需要两个子节点，left和right，以及一个引用返回其parent节点。 与典型的二叉树不同，这些节点不使用指针来相互引用，而是在tree数组中使用简单的整数索引。我们也存储节点本身的数组index，原因稍后会变得清晰）
注意，该tree目前有256个条目的空间用于表示叶节点，因为有256个可能的字节值。 当然，并不是所有都最终被使用，这取决于输入。 稍后，我们将在构建实际树时添加更多节点。 目前，还没有一棵完整树，只是包括256个独立的叶节点，它们之间没有连接。所有节点计数都是0。
我们使用以下方法来计算输入数据中每个字节出现的频率：
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对象，并且每个字节递增相应叶节点的count。 countByteFrequency()完成后，tree数组中的前256个Node对象表示频率表。
为了解压哈夫曼编码的数据块，我们需要有原始的频率表。 如果我们将压缩数据写入文件，那么在文件的某个地方应该包含频率表。
我们可以转储tree数组中的前256个元素，但效率不高。 因为并不是所有这256个元素都会被使用，我们不需要序列化parent指针，right指针和left指针。 我们所需要的只是频率信息而不是整个树。
我们将添加一个方法来导出频率表，去掉不需要的部分：
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个节点，但只保留那些使用到的节点，没有parent节点，left节点和right节点指针。 它返回一个Freq对象数组。 必须将此数组与序列化的压缩数据一起使用，以便稍后进行解压。
The tree
例子压缩需要的树：
Tree.png
叶节点表示输入数据中的实际字节。中间节点以这样的方式连接叶节点，使得从根节点到常用字节值的路径短于不常用字节值的路径。 正如你所看到的，m，s，space和o是我们输入数据中最常见的字母，并且是树中最上层的字母。
为了构建树，执行以下操作：
- 查找具有最小计数的两个没有父节点的节点。
- 创建一个将这两个节点链接在一起的新父节点。
- 重复，直到只有一个没有父节点的节点，成为树的根节点。
这是使用优先队列的理想情况。 优先级队列是经过优化的数据结构，因此找到最小值总是很快。 在这里，我们反复找到计数最小的节点。
函数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
}
这是它如何工作的一步一步：
- 创建优先级队列并对所有具有至少1个计数的叶节点进行排队（如果计数为0，则该字节值不会出现在输入数据数据中）.
PriorityQueue对象按计数排序节点，具有最低计数的节点始终是第一个出列的节点。 - 当队列中至少有两个节点时，删除队列前面的两个节点。由于这是一个最小优先级队列，这给了我们两个具有最小计数但没有父节点的节点。
- 创建一个连接
node1和node2的新中间节点。 这个新节点的计数是node1和node2的计数之和。 由于节点使用数组索引而不是真实指针连接，因此我们使用node1.index和node2.index在tree数组中找到这些节点。（这就是为什么Node需要知道它自己的索引。） - 将两个节点链接到它们的新父节点。 现在这个新的中间节点已经成为树的一部分。
- 将新的中间节点放回队列中。 此时我们完成了
node1和node2，但是parentNode仍然需要连接到树中的其他节点。 - 重复步骤2-5，直到队列中只剩下一个节点。 这成为树的根节点。
该过程动画：
BuildTree.gif
注意：不使用优先级队列，也可以重复遍历树数组以找到接下来的两个最小节点，但这会使压缩器的运行速度变慢O（n ^ 2）。 使用优先级队列，运行时间仅为O（n log n），其中n是节点数量。
有趣的事实：由于二叉树的特点，如果有x个叶节点，最多可以为树添加x-1个附加节点。 鉴于最多会有256个叶节点，树节点总数 永远不会超过511个。
Compression
现在我们知道如何从频率表构建压缩树，可以使用它来压缩NSData对象。 代码如下：
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
}
首先调用countByteFrequency()创建频率表，然后调用buildTree()创建压缩树。 它还创建一个BitWriter对象来写入各个位。
然后遍历输入流并为每个字节调用traverseTree()。 此方法将遍历树节点，每个节点写入1或0。 最后，返回BitWriter的数据对象。
注意：压缩总是需要两次遍历整个输入数据：首先建立频率表，然后将字节转换成压缩的位序列。
有趣的事情发生在traverseTree()中。 这是一个递归方法：
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)
}
}
}
当在compressData()调用该方法时，nodeIndex参数是我们需要编码的字节的叶节点的数组索引。 该方法递归地将树从叶节点递归到根，然后再返回。
当我们从根节点回到叶节点时，为每个遇到的节点写1或0。
Compression.png
即使树的插图显示节点之间每个边为0或1，位值0和1实际上并不存储在树中！ 规则是，如果我们取左分支，我们写1位，如果我们取右分支，则写0位，所以只知道我们进入的方向足以确定要写入的位值。
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()方法返回一个Freq对象数组。 如果将压缩数据保存到文件中或通过网络发送，也会将[Freq]数组和它一起保存。
我们首先需要一些方法将[Freq]数组重新转换为压缩树：
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对象转换为叶节点，然后调用buildTree()来完成剩下的工作。
下面是decompressData()的代码，参数是霍夫曼编码的NSData对象和频率表，并返回原始数据：
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给定的叶节点。 在每个中间节点处，读取一个新位，然后向左（位为1）或向右（位为0）前进。 当到达叶节点时返回它的索引，也就是原始字节值。
Decompression.png
可以像这样使用解压方法：
let frequencyTable = huffman1.frequencyTable()
let huffman2 = Huffman()
let decompressedData = huffman2.decompressData(compressedData, frequencyTable: frequencyTable)
let s2 = String(data: decompressedData, encoding: NSUTF8StringEncoding)!
首先获得频率表，然后调用decompressData()，得到字符串应该与压缩前的字符串相同。
