扫码关注公众号免费阅读全文：冰山烈焰的黑板报
1 .学习数据压缩技术，可以大大压缩概念自然语言文件空间(以及许多其他类型的文件)。 其主要思想是放弃文档的一般保存方式。 不是用7位或8位二进制表示每个字符，而是用较少的位表示出现频率高的字符，用较多的位表示出现频率低的字符。
为了更形象地说明这个概念，我们先来看一个例子。 我们现在对字符串ABRACADABRA！ 编码。 7位ASCII字符编码得到位字符串。
1000011000101001001000110000011000001100000000001100000000000000000000000000001若要解码该位字符串，请每次读取7位，然后单击ASCII 在这个标准代码中，只出现1次的d和出现5次的a所需的位数是相同的。 ykdsn压缩的思想是，用较少的位表示出现频率高的字符，用较多的位表示出现频率低的字符，从而降低字符串中使用的总位数。
1.1可变长度前缀因为可以为最常用的字符指定最短的位字符串，所以：
字符编码频率的总位数A055B122R0024C0112D1012！ 112总数- -类似17的字符串ABRACADABRA！ 的代码为0 1 00 0 01 0 10 0 1 00 0 11此表示方法仅使用17位，而7为ASCII代码使用84位。 但是，这种表达方式并不完整，因为需要分隔符来区分字符。 但是，如果在17位中使用11个分隔符，则它比标准编码紧凑得多，并且未用于编码的位字符不会显示在此消息中。
如果所有字符编码都不会成为其他字符编码的前缀，那么就不需要分隔符了，包含这种性质的代码规则称为前缀码。 例如，编码为：
字符编码频率的总位数A055B111128C11013D10013R111028！ 10113总数--30中，解码以下长度30位字符串的方式只有字符串ABRACADABRA！ 一种：
011111001100100100011111100101所有前缀代码都以相同的方式进行解码和唯一(不需要分隔符)，因此前缀代码被广泛用于生产。 上述7位ASCII码那样的定长码也是前缀码。
1.2前缀码的单词检索树表示前缀码的一个简单方法是使用单词检索树。 在包含m个空链接的单词搜索树中定义了m个字符的前缀代码方法。 将空链接替换为指向包含两个空链接的叶节点的链接，并在每个叶节点中包含需要编码的字符。 这样，各字符的代码是表示从根节点到该节点的路径的位字符串，左链路表示0，右链路表示1。 图1显示了字符串ABRACADABRA！ 中字符的两种前缀代码。
可以压缩更多的单词搜索树吗？ 如何找到压缩率高的前缀？ 寻找最佳前缀代码的常用方法是David Albert Huffman在1952年发明的，当时他还是个学生！ 该方法的名称为ykdsn编码
2. ykdsn码2.1单词检索树的节点单词检索树和二叉树的定义相似，但增加了一个用于保存字符出现频率的实例变量frequency。 另一个实例变量aChar表示必须在叶节点上编码的字符。
privatestaticclassnodeimplementscomparablenode { privatefinalcharachar； //单词查找树中的节点，非叶节点不使用此变量private final int frequency； //编码字符的出现频率：私有金融节点左； 私有金融节点权限； 公共节点(charachar，int frequency，Node left，Node right ) { this.aChar=aChar； this.frequency=frequency； this.left=left； this.right=right； } @ overridepublicintcompareto (node that ) return this.frequency-that.frequency； }专用布尔is leaf () return ) left==null ) ) right==null )； }} 2.2单词检测树的构建过程将需要编码的字符串放在叶节点上，并在每个节点上保留一个名为frequency的实例变量，表示作为根节点的子树中所有字符出现的频率。 构建的第一步是将只有一个节点的多个节点(
即叶子节点）的树所组成的森林。每棵树都表示输入流中的一个字符，每个节点中的 frequency 变量的值都表示了它在输入流中的出现频率。接下来，自底向上根据频率构造这棵编码的单词查找树。在构造时，将它看作一棵节点中含有频率信息的二叉树；在构造后，我们才将它看作一棵用于编码的单词查找树。构造过程如下：首先找到两个频率最小的节点，然后创建一个以二者为子节点的新节点（新节点的频率值是它两个子节点的频率值之和）。这个操作会将森林中树的数量减一。然后不断重复这个过程，找到森林中的两棵频率最小的树并用相同的方式创建一个新的节点（每一步都会删除两棵树，添加一棵新树）。用优先级队列可以轻易的实现这个过程。简而言之，单词查找树的构造需要如下几个步骤： 统计被编码的字符出现的频率；将每个字符构建成的只有一个节点的树，然后组成一个森林。通过循环合并两棵频率最小的树，构造单词查找树，直到构造成一棵单词查找树。下面用于一个具体的例子进行说明，假设现在我们需要对字符串 ABRACADABRA! 进行编码。第一步，统计被编码的字符出现的频率，将每个字符构建成的只有一个节点的树，然后组成一个森林，并放入优先级队列中，如图2：
自底向上根据频率构造这棵编码的单词查找树，找到两个频率最小的节点 ! 和节点 C，并从优先级队列中删除，然后创建一个以二者为子节点的新节点，该节点频率是 1 + 1 = 2，重新放到优先级队列中，如图3：
重复这个过程，找到森林中的两棵频率最小树，并用相同的方式创建一个新的节点，该节点的频率是 1 + 2 = 3，重新放到优先级队列中，如图4：
继续重复这个过程，找到森林中的两棵频率最小树，并用相同的方式创建一个新的节点，该节点的频率是 2 + 2 = 4，重新放到优先级队列中，如图5：
继续重复这个过程，找到森林中的两棵频率最小树，并用相同的方式创建一个新的节点，该节点的频率是 3 + 4 = 7，重新放到优先级队列中，如图6：
继续重复这个过程，找到森林中的两棵频率最小树，并用相同的方式创建一个新的节点，该节点的频率是 5 + 7 = 12，重新放到优先级队列中，如图7：
到此为止，优先级队列中只有一棵树，即为单词查找树。
在压缩时，我们使用单词查找树定义的编码来构造编码表。对于任意单词查找树，它都能产生一张将树中的字符和比特字符串（用 0 和 1 组成的 String 字符串表示）相对应的编码表。编码表就是一张将每个字符和它的比特字符串相关联的符号表：为了提升效率，我们使用一个由字符索引的数组 table[] 而非普通的符号表或 Map 字典，因为字符的数量并不多。在构造该符号表的时候，递归遍历整棵树并为每个节点维护一条从根节点到它的路径所对应的二进制字符串（0 表示左链接，1 表示右链接）。每当到达一个叶子节点时，算法就将节点的编码设为该二进制字符串。编码表建立之后，压缩也就很简单了，只需在其中查找输入字符所对应的编码即可。代码如下所示：
private void buildCode(String[] table, Node node, String str){ if (node.isLeaf()){ table[node.aChar] = str; } else { buildCode(table, node.left, str + '0'); buildCode(table, node.right, str + '1'); }}通过上一节构造的单词查找树，我们可以计算出字符串 ABRACADABRA! 的编码表。
字符编码频率总位数!101014A055B11126C101114D10013R11026总数--28使用ykdsn编码最后需要的比特位是 28，而标准的 7 位 ASCII 编码压缩需要的比特位是 84，大大减少了空间浪费。
综上所述，ykdsn编码是一种高效的压缩算法，它是一种贪婪算法，因为它在每一步只是简单从集合中取出两个权值最小的树进行合并。
ykdsn编码参考代码
public class Huffman { // alphabet size of extended ASCII private static final int ASCII = 256; public void compress(String str){ char[] input = str.toCharArray(); int[] frequency = new int[ASCII]; // 1.统计被编码的字符出现的频率 for (int i = 0; i < input.length; i++){ frequency[input[i]]++; } // 2.将每个字符构建成的只有一个节点的树，组成一个森林。通过循环合并两颗频率最小的树，构造ykdsn树 Node root = buildTrie(frequency); // 3.构造编码表 String[] table = new String[ASCII]; buildCode(table, root, ""); // 打印编码表 for (int i = 0; i < table.length; i++){ if (table[i] != null){ System.out.printf("%ct%sn", i, table[i]); } } } /** * 将字符出现的频率制成编码表 */ private void buildCode(String[] table, Node node, String str){ if (node.isLeaf()){ table[node.aChar] = str; } else { buildCode(table, node.left, str + '0'); buildCode(table, node.right, str + '1'); } } /** * 构建单词查找树 */ private Node buildTrie(int[] frequency){ Queue<Node> queue = new PriorityQueue<>(); // 将每个被编码的字符构造的只有一个节点的树组成一片森林，放入优先级队列 for (char c = 0; c < ASCII; c++){ if (frequency[c] > 0){ queue.add(new Node(c, frequency[c], null, null)); } } // 将只有一个频率非0的字符构造成一颗树 if (queue.size() == 1){ if (frequency[' '] == 0){ queue.add(new Node(' ', 0, null, null)); } else { queue.add(new Node('1', 0, null, null)); } } while (queue.size() > 1){ // 合并两颗频率最小的树 Node x = queue.poll(); Node y = queue.poll(); Node parent = new Node(' ', x.frequency + y.frequency, x, y); queue.add(parent); } return queue.poll(); } private static class Node implements Comparable<Node>{ private final char aChar; private final int frequency; private final Node left; private final Node right; public Node(char aChar, int frequency, Node left, Node right) { this.aChar = aChar; this.frequency = frequency; this.left = left; this.right = right; } @Override public int compareTo(Node that) { return this.frequency - that.frequency; } private boolean isLeaf(){ return (left == null) && (right == null); } } public static void main(String[] args) { Huffman huffman = new Huffman(); huffman.compress("ABRACADABRA!"); }}