哈夫曼树 - wangshengliang

哈夫曼树对应的是一种哈夫曼编码，这种编码主要应用于文件压缩领域。

编码会遇到问题
哈夫曼树以及哈夫曼编码
落地到代码

编码会遇到的问题

编码：将一段字符编码为二进制。

ABAACDC

A: 0
B: 1
C: 10
D: 11

0100101110

编码完成了，但是解码会遇到很大的问题。以前三位010为例：

究其原因是因为一个字符的编码成为了另一个字符编码的前缀。

B：1 但是 C 和 D 它们的编码都是 1 开头的。

BC --> 110 --> DA

因此，在进行编码的时候，不能让一个字符的编码成为另外一个字符的前缀。

另外一种方案：等长编码：

A：0000
B：0001
C：0010
D：0011

ABAACDC
0000000100000000001000110010

这种方式虽然能够解决解码歧义的问题，但是编码出来的结果太长了。

哈夫曼树

使用哈夫曼树形成的哈夫曼编码：

不会有歧义（不会有任何一个字符的编码是另外一个字符的前缀）
编出来的码是最短的

哈夫曼编码核心思想：出现频率越高的字符，编码应该越短，出现频率低的字符，编码长一点也没关系。

ABAACDC

A: 3
B: 1
C: 2
D: 1

接下来就需要根据频率来构建二叉树结构。

从出现频率低的字符开始：

接下来再取一个节点：C，将 C 放置在和 2 同一级。

最后取 A，和 4 同一层：

至此，整颗二叉树就构建完成，这颗二叉树就是哈夫曼树。

构建哈夫曼树是为了得到哈夫曼编码：

将整颗树左边的边记为 0，右边的边记为 1:

A： 1
B：010
C：00
D：011

课堂练习

将下面的字符串生成哈夫曼树以及哈夫曼编码：

CEABEACDA

统计各个字符出现的次数：

A：3
B：1
C：2
D：1
E：2

A(3)、B(1)、C(2)、D(1)、E(2)

首先取 B(1) 和 D(1)：

A(3)、C(2)、E(2)、BD(2)

接下来继续取，C 和 E 都是相同，随便取一个：

A(3)、E(2)、BDC(4)

接下来是一个关键：A 和 E 分别对应 3 和 2，比当前的顶层节点 BDC 的 4 要小，因此取这两个节点进行合并

BDC(4)、AE(5)

最终合并出来的哈夫曼树为：

A：10
B：010
C：00
D：011
E：11

哈夫曼编码不是唯一。在构建哈夫曼树的时候，节点放的位置不同，最终得到的哈夫曼树就会有所不同，自然哈夫曼编码也就不一样。但是最终的哈夫曼编码一定满足前面所说的特点：

不会有歧义
频率高的编码越短

代码实现

/**
 * 哈夫曼节点类
 */
class HuffmanNode {
  constructor(char, freq, left = null, right = null) {
    this.char = char // 字符
    this.freq = freq // 频率
    this.left = left // 左子节点
    this.right = right // 右子节点
  }
}

/**
 * str - 待编码的字符串
 * return - 返回一个对象，对象的键是对应的字符，对象的值是该字符所出现的次数
 * { 'a': 5, 'b': 2, ...}
 */
function getFrequencyMap(str) {
  const freq = {}

  // 遍历字符串的每一个字符
  for (const ch of str) {
    freq[ch] = (freq[ch] || 0) + 1
  }

  return freq
}

/**
 * str - 待编码的字符串
 * return - 构建的哈夫曼树所对应的根节点
 */
function buildHuffmanTree(str) {
  // 1. 先得到字符串里面每一个字符出现的频率
  const freqMap = getFrequencyMap(str)

  // 这里得到的就是键所构成的数组，例如 ['A', 'B', 'C', ...]
  const uniqueChars = Object.keys(freqMap)
  // 做一下边界处理
  if (uniqueChars.length === 0) return null
  if (uniqueChars.length === 1) {
    // 说明整个字符串里面只有一种字符，类似于 'AAAAAAAAAA...'
    // 那么这里我们就可以直接指定编码为 0
    return new HuffmanNode(uniqueChars[0], freqMap[uniqueChars[0]])
  }

  // 代码来到这里，说明有多个字符
  // 首先将所有出现了的字符生成哈夫曼节点对象
  // 注意这里是一种字符就会生成一个哈夫曼节点对象
  let nodes = uniqueChars.map((ch) => new HuffmanNode(ch, freqMap[ch]))

  // 接下来就是哈夫曼节点两两进行合并
  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq) // 首先按照频率进行排序
    const left = nodes.shift() // 取出一个频率最小的作为左子节点
    const right = nodes.shift() // 再取出一个频率最小的作为右子节点

    // 合并出新的子节点
    const newNode = new HuffmanNode(null, left.freq + right.freq, left, right)

    // 放回到数组里面
    nodes.push(newNode)
  }

  // 跳出上面的while循环，说明node数组的长度没有大于1，整个数组只剩1个节点
  // 这个节点就是整颗哈夫曼树的根节点
  return nodes[0]
}

/**
 * root - 哈夫曼树的根节点
 * return - 返回对应的哈夫曼编码表 { a: '00', b : '11'}
 */
function buildHuffmanCodes(root) {
  const codes = {} // 存储生成的哈夫曼编码表

  // 用于深度遍历哈夫曼树的辅助方法
  function traverse(node, prefix) {
    if (!node) return

    if (node.char !== null) {
      // 说明是叶子节点，需要保存对应的编码
      codes[node.char] = prefix
      return
    }

    // 代码来到这儿，说明不是叶子节点
    // 继续深度遍历
    traverse(node.left, prefix + '0') // 深度遍历左分支，并且因为是左分支，前缀加0
    traverse(node.right, prefix + '1') // 深度遍历右分支，并且因为是右分支，前缀加1
  }
  traverse(root, '')
  return codes
}

/**
 * str - 待编码的字符串
 * codes - 对应的哈夫曼编码表，例如 { A: '0', C: '10', B: '110', D: '111' }
 */
function huffmanEncode(str, codes) {
  let encodedResult = '' // 存储编码后的结果

  for (const ch of str) {
    encodedResult += codes[ch]
  }

  return encodedResult
}

/**
 * encodedStr - 编码后的字符串，例如 0110001011110
 * root - 哈夫曼树的根节点
 */
function huffmanDecode(encodedStr, root) {
  let decodedResult = '' // 存储解码后的结果

  let currentNode = root // 暂存树的根节点

  // 遍历编码后的字符串的每一位
  for (const bit of encodedStr) {
    if (bit === '0') {
      // 根据哈夫曼的核心思想，0 处于左分支
      currentNode = currentNode.left
    } else {
      // 1 处于右分支
      currentNode = currentNode.right
    }

    if (currentNode.char !== null) {
      // 进入此分支，说明进入到了叶子节点，叶子节点代表具体的字符
      decodedResult += currentNode.char
      currentNode = root // 重新回到根节点，每一次解析出来一个字符，都需要重新回到根节点
    }
  }

  return decodedResult
}

-EOF-