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是我们输入数据中最常见的字母，并且是树中最上层的字母。

为了构建树，执行以下操作：

1. 查找具有最小计数的两个没有父节点的节点。
2. 创建一个将这两个节点链接在一起的新父节点。
3. 重复，直到只有一个没有父节点的节点，成为树的根节点。

这是使用优先队列的理想情况。 优先级队列是经过优化的数据结构，因此找到最小值总是很快。 在这里，我们反复找到计数最小的节点。

函数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. 创建优先级队列并对所有具有至少1个计数的叶节点进行排队（如果计数为0，则该字节值不会出现在输入数据数据中）.PriorityQueue对象按计数排序节点，具有最低计数的节点始终是第一个出列的节点。
2. 当队列中至少有两个节点时，删除队列前面的两个节点。由于这是一个最小优先级队列，这给了我们两个具有最小计数但没有父节点的节点。
3. 创建一个连接node1和node2的新中间节点。 这个新节点的计数是node1和node2的计数之和。 由于节点使用数组索引而不是真实指针连接，因此我们使用node1.index和node2.index在tree数组中找到这些节点。（这就是为什么Node需要知道它自己的索引。）
4. 将两个节点链接到它们的新父节点。 现在这个新的中间节点已经成为树的一部分。
5. 将新的中间节点放回队列中。 此时我们完成了node1和node2，但是parentNode仍然需要连接到树中的其他节点。
6. 重复步骤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()，得到字符串应该与压缩前的字符串相同。