信息处理 - 数据压缩 - 哈夫曼编码
避免歧义的编码 在构建压缩编码的对应关系时，我们使用不同的数量的位来编码不同的字符. 比如摩斯密码. 如果单纯使用这种对应关系，会出现一些问题， 如•••−−−•••会产生歧义: SOS? V7? IAMIE? EEWNI? 所以在实际使用中, 密码使用一些间隔来分隔代码字。 那么对于不同的压缩编码, 有什么常用方法来避免歧义？ 方法是确保没有一个编码是另一个编码的前缀。比如 使用固定长度编码。 为每个编码添加特殊的stop char。 使用一种具备广泛使用性的prefix-free编码。 用什么数据结构来设计prefix-free编码? 用Trie构造编码 一个二叉(0, 1)Trie: 叶节点是字符, 根节点到叶节点的路径就是编码. 压缩: 方法1：从叶开始; 按照路径到达根; 反向打印bits。 方法2：创建键-值对的符号表。 解压: 从根节点开始, 根据位值是0还是1在Trie图上游走, 直到走到叶节点，则解压出一个字符 返回根节点, 继续第一步, 直到跑完所有编码. private static class Node implements Comparable<Node> { private final char ch; // used only for leaf nodes private final int freq; // used only for compress private final Node left, right; public Node(char ch, int freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } public boolean isLeaf() { return left == null && right == null; } // compare Nodes by frequency public int compareTo(Node that) { return this.freq - that.freq; } // Runtime - Linear in input size N public void expand() { Node root = readTrie(); // read in encoding trie int N = BinaryStdIn.readInt(); // read in number of chars for (int i = 0; i < N; i++) { Node x = root; while (!x.isLeaf()) { if (!BinaryStdIn.readBoolean()) x = x.left; else x = x.right; } BinaryStdOut.write(x.ch, 8); } BinaryStdOut.close(); } } 如何读取一个Trie：根据Trie的前序遍历序列重构. ...