algorithm - 如何在具有 2N-1 + N*ceil(lg(n)) 位的一组符号 {0,1,2,..,N-1} 上传输霍夫曼码？

Question

这是 Sedgewick 的书网站上的一个问题。他给出了“使用2N-1位来指定对应的trie的结构”的提示。

我可能不明白这个问题，尤其是他所说的 {0,1,2,..,N-1} 是什么意思。但我会使用 N 位来指定需要多少位来编码第 0、1 等代码，如下所示: 如果我们在第 i 个位置有 1，那么第 i 个代码使用 i 位，如果它有 0，则查看下一个有 1 的位置，第 (i+x) 个位置将指定位数(或查看如果下一个位置没有人，则在前一个位置(例如平衡二叉树给出))。

但这只有在编码特里接近完美时才有效，因为如果我们有频率的斐波那契分布，我们的编码特里将如下所示:

  o
 / \
o   o
   / \
  o   o
     / \
    o   o
 .....

这意味着我们总共将有 (n^2+n)/2-1 位，在长度描述位串之后(1+2+...+N 和 -1 的算术级数，因为 2 个节点具有相同的深度)。如何达到指定的空间复杂度？

这是一个链接:http://algs4.cs.princeton.edu/55compression/引用练习 20。

Answer 1

假设您有这些频率:

A 11
B 7
C 5
D 4
E 3
F 1

他们生成这个编码:

R: 0: 0:       B
      1:       C
   1: 0:       A
      1: 0:    D
         1: 0: E
            1: F

您可以使用数组 BCADEF 和将节点标识为终端 (0) 和非终端 (1) 的位序列描述此 trie 的结构，深度优先顺序:

11001010100

(第一个 110 表示 R: 0: 0: 路径 - root 是非终结符，0 也是非终结符，并且接下来的 0 是带有标签 B 的终端；接下来的 0 代表 1: 分支，它是另一个终端，标记为 C；接下来的 10 是 1:0: 分支，终止于 A；等等.) 这不是模棱两可的，因为霍夫曼编码是严格的二叉树 - 一个节点要么有两个 child ，要么没有。

您会注意到 11001010100 有 11 位，即 2 * 6 - 1，正如公式预测的那样。 (严格二叉树有N-1个内部节点和N个叶子)。

重构:

function restoreTree(alphabet, structure) {
  if (structure.shift() == "0") {
    return alphabet.shift();
  } else {
    var left = restoreTree(alphabet, structure);
    var right = restoreTree(alphabet, structure);
    return [left, right];
  }
}

var alphabet = "BCADEF".split('');
var structure = "11001010100".split('');
var tree = restoreTree(alphabet, structure);
document.body.textContent = JSON.stringify(tree);

编辑:N * ceil(lg(N)) 部分描述了字母表顺序的空间要求(假设字母表本身已知)。例如，假设您知道字母表是 "ABCDEF" - 位置从 0 到 5(A = 0，F = 5)。因此，每个位置都可以用三个位表示 (ceil(lg(6)) == 3，三个位足以表示 0..7)。因此，为了表示 “BCADEF” 顺序，您需要将 1、2、0、3、4、5 分别转换为三位:001010000011100101。这有 18 位，或 6 * ceil(lg(6))。从 "ABCDEF" 和 001010000011100101 重建 "BCADEF" 应该很简单。