学平面设计的网站老鬼seo

注意：这里是JAVA自学与了解的同步笔记与记录，如有问题欢迎指正说明

目录

前言

一、前缀码定义

二、固定编码与一般变长编码的不足与Huffman编码的特性

1、固定编码与一般变长编码

2、Huffman编码

2.1 Huffman编码的提出

2.2 Huffman编码二叉树构建

三、代码准备

1、Huffman树的结点

2、Huffman编码构造使用的相关参数

3、数据的读入

总结

---

前言

        Huffman编码是二叉树带来的二义性在编码领域应用的一种非常重要且常用的特性，同时也能让我们体会到二叉树强大的应用特性，接下来三天里面我们会逐步给大家说明Huffman编码的原理以及设计过程，以及Huffman树的建立和代码实现过程。

一、前缀码定义

        前缀码是编码领域的一种非常重要的设计。在引入前缀码之前，我们需要说明下什么是前缀：

        假设，是一个非0仅1构成的二进制字符串结构，有另一个同类型序列：  ，则我们称为的前缀。比如说有：

=101，那么1,10,101都是 的前缀。 

        有了这个定义准备后，接着做如下解释：在定义了前缀码特性后，作为一个前缀码，任何一个字符的编码都不能是其他字符编码的前缀，此即前缀码特性。具有前缀码特性的编码即为前缀码。设是一个字符串集合，现在有，这里不互为前缀，则我们就可以称为前缀码。这里要注意两个问题，第一，前缀码是一系列字符串所组成的集合，而并非单独的一个编码，而是一个集合的概念；第二，前缀码并不是说各个子串之间都有相同的前缀，而是他们的前缀都不同。举个例子，A={1,00,011,0101,01001}为前缀码，而B={1,00,011,0101,0100,01001,01000}并非前缀码，因为这里的子串中0100可以为01001前缀,0100可为01000前缀。（部分参考自《离散数学》第二版屈婉玲版）

        我这有个自己的理解，其实我们也可以用计算机中的字符串模式匹配来理解这个内容。Java的String库中自带了一个模式匹配的库函数indexOf()，假设有字符串str1与str2互为前缀不过就是str1.indexOf(str2)==0而已。所以所谓的前缀码其实就是一个多个字符串组成的集合，其中任意挑选两个不同的字符串str1与str2都有str1.indexOf(str2)!=0。

        最后，我们定义，以这种用0-1构成的2元前缀码为基础的编码就是Huffman编码。

二、固定编码与一般变长编码的不足与Huffman编码的特性

1、固定编码与一般变长编码

         计算机的存储空间是有限的，信息传输也是如此，信道所承载的信息量也不是多到可以任意挥霍。早期我们在设计信息的时候主要使用定长的二进制编码格式，这样设计固然方便快捷，容易实现信息同步，但是也非常容易陷入一个空间冗余的恶性循环。

        因为采用定长的二进制编码的话，无论数据的信息是什么，我都按照固定顺序以及固定长度为其编码，比如我们当前有64个数据，这个时候按照顺序，分别编码第2个和第3个元素：000001和000010，这样的话两个信息量总共占据了12个比特位，但是可以发现这两个编码1之前的信息位是冗余的，并不能承载信息，或者说1之前没有信息这件事情本身就是一种信息，说明了数据没有更高位了，所以可以没必要写前导零。（这里为严谨起见，我做个区分：如果说我们只是想让顺序的数据能有二进制映射，那么前导零信息就是没有意义的；但就某些情况下，前导零其实可以反映我们数据的极限长度信息，或者是格式对齐等，这里不深究，具体前导零是否设置看问题而分析，就编码传输来看是可以省略的）

        一旦省去了前导零，我们的编码就变得畅快很多：0,1,10,11,100...但是会出现一个新的问题：二义性

        我们用例子来说明这个问题，现在我们有一段二进制编码：100011010101001 我们可以按照下列的标准加以分割：10001 | 10 | 10 | 10100| 1 也可以按照下面这个标准分割：1000110 | 1010| 1001 甚至我可以不分割作为一个整体。可见这样的数据若从发送端发送出来是完全没有意义的，因为接收端完全没有一个可靠的准则去区分。这个案例只能在某些异步传输的设置中可以采用，实现信息流的逐个传送，但是这样效率不高。

2、Huffman编码

2.1 Huffman编码的提出

         好的编码到底以什么为基础？在人们使用编码的过程中为了避免冗余选择了变长编码，但是变长编码又有二义性。下面我们分析一个现象，可见下面这张图：

         这张图是知乎的一个大佬在对92518个单词中的字母出现的频度进行了一个统计后体现的排序图，大家有兴趣可以看下这篇回答（网址：英文各字母使用频率？ - 知乎），他还分析了30部英文著作中的单词中的字母出现频率。大体上来说，结果是一致的，单词的使用会伴随着习惯和发音等多重可能导致单词中字母的分布非常不均匀。现实中我们常用2-8准则去总结这种不均匀的使用，例如一般人玩手机，用了80%的时间却只使用了20%的APP。所以说，既然信息之间是不均匀不平等的，那么我们就没必要偏于一隅，不妨试着放弃按照固定顺序为其编码，尝试按照频度来进行编码，为频度高的信息分配更短的编码，而频度低的信息分配更长的编码，而这个频度就是信息的权值。这样，我们的编码思维便不再局限于二进制的映射。

        那么现在的问题是要怎么消除二义性，通过刚刚我们的距离可以发现，二义性诞生的一个根源就是我们常规的十进制转为二进制存在大量的前缀重叠，一个编码的前缀若是1001，那么二进制100110就可以解读为10011或者100110。恰好上文提到的一种互不为前缀的编码体系——前缀码，因此可以试着用这个工具可以解决前缀重叠的弊端。我们试用第一部分提出的前缀码：A={1,00,011,0101,01001}来分析这个上文说明一般变长码时用的这个信息：100011010101001，通过尝试，我们可以发现唯一的编码解析：1 | 00 | 011 | 0101 | 01001 | ，你无法找出第二种可以分割这样的编码方案。这就是前缀码无二义性的鲜明体现，同时上文提出的信息的权值分配策略结合就构成了Huffman编码。

2.2 Huffman编码二叉树构建

         信息权值的判定要看具体数据而定，只需要对传输的信息总量进行逐一统计即可。问题在于前缀码的设计，实际案例中，我们往往采用带权的仅有度为0和2的二叉树来实现前缀码。为了说明可行性，下面以二叉数的支点分叉模拟0-1的选择得到的二叉树：

         我们用叶子作为编码的终点，分支结点不作为编码终点。我们来观察这样的编码过程：首先，长度完全一致的编码之间只要不是一模一样，那么定然不互为前缀，所以同为第三层的3个叶子可以互为前缀码。那么第四层的这两2个叶子与之前的3个叶子互为前缀吗？结果是否定，因为在之前两次0-1选择中，第四层这两个叶子选择的是11路径，不同于前3个叶子的00、01、10路径。这就是为什么我们不选择分支，若我们选择了红色的分支点为编码终点，那么就构造了以这个红色结点为根的向下所有叶子节点的编码前缀。这就是为什么二叉树可以用于构造前缀码。

        明白二叉树的路径无二义性后，我们定义：每个结点都赋予一个权值（许多引用中，树中的结点常常被赋予一个表示某种含义的数值，成为该节点的权），然后从树的根到任意结点的路径长度（经过的边数目）与该结点上的权值的乘积我们称之为带权路径。对于Huffman编码，定义叶子节点才能代表有效信息，然后叶子节点的带权路径长度就是上文我们提出的信息的权值的代表，其与每个信息元的权值一一对应。进一步，定义所有叶子节点的权值总和就是树的带权路径长度（WPL:Weighted Path Length of Tree），而给定叶子数目，所构造的WPL最小的树，我们就定义和为Huffman树。

三、代码准备

1、Huffman树的结点

        今天我们的重点在于搞清楚我们的Huffman的实现原理为主，所以代码部分几天只做些基本的准备。本次代码我们计划完整再现编码与解码的全过程，而且数据的输入输出也打算使用外部文件完成，因此可能会简单介绍下Java面向操作系统的文件系统调用库。

    /*** An inner class for huffman nodes.*/class HuffmanNode {/*** The char. Only valid for leaf nodes.*/char character;/*** Weight. It can also be double*/int weight;/*** The left child.*/HuffmanNode leftChild;/*** The right child.*/HuffmanNode rightChild;/*** The parent. It helps constructing the Huffman node of each character.*/HuffmanNode parent;public HuffmanNode(char paraCharacter, int paraWeight, HuffmanNode paraLeftChild, HuffmanNode paraRightChild,HuffmanNode paraParent) {character = paraCharacter;weight = paraWeight;leftChild = paraLeftChild;rightChild = paraRightChild;parent = paraParent;}// Of HuffmanNode/********************* * To string.******************* */public String toString() {String resultString = "(" + character + ", " + weight + ")";return resultString;}// Of toString}// Of class HuffmanNode

        首先构造基本的树的结点，这里树结点有五个参数，其中左右孩子自不必多说；结点的值转变为权值（这里我们用的整型，当然权值带小数也完全没问题）和字符参数，权值是构建Huffman树的一个关键参数，其代表以当前结点为根的子树权值情况，而字符参数是Huffman树在信息编码部分的代表，也就是我们计划编码的信息元（这里是对文本流编码，因此单个信息元是字符），正如我们刚刚将Huffman树提到的，只有叶子才能代表信息元，所以这里只有叶子可以赋予给character变量值。

        然后值得注意的是我们引入了第三个指向双亲的指针，这里这样操作是为了后面自下而上构建Huffman的贪心算法而服务的，明日会具体介绍。（注：拥有三个指针的链表树，我们有时也会称三叉链表，所以此数据结构也可理解为一种带权三叉链表）

2、Huffman编码构造使用的相关参数

	/*** The number of characters. 256 for ASCII.*/public static final int NUM_CHARS = 256;/*** The input text. It is stored in a string for simplicity.*/String inputText;/*** The length of the alphabet, also the number of leaves.*/int alphabetLength;/*** The alphabet.*/char[] alphabet;/*** The count of chars. The length is 2 * alphabetLength - 1 to include non-laef* nodes.*/int[] charCounts;/*** The mapping of chars to the indices in the alphabet.*/int[] charMapping;/*** Codes for each char in the alphabet. It should have the same length as* alphabet.*/String[] huffmanCode;/*** All nodes. The last node is the root.*/HuffmanNode[] nodes;/************************ The first constructor.* * @param paraFilename The text filename.**********************/public Huffman(String paraFilename) {charMapping = new int[NUM_CHARS];readText(paraFilename);}// Of the first constructor

        这些参数是为后续的代码做必要准备的，有些数据内容单独解释显得有点...单薄，具体的操作我会放在后面几天结合操作一步步解释。 

        NUM_CHARS是我们定义的静态变量，用于说明ASCII码的合理范围；inputText是从文本读入的字符串数据，是我们获取的信息；alphabetLength与alphabet是用于统计信息中诸字符的数目与具体字符的列表。而charCounts是信息元的个数，也就是我们后续要为多少个字符进行编码，同时因为Huffman树是一个仅仅有度为0和2的树，所以根据二叉树的度性质，可以知道Huffman树的结点个数是charCounts * 2 + 1（叶子比度为2的分支多1个）；charMapping是一个以字符ASCII码为根据的，采用直接定址法实现的简易哈希表（直接定址法哈希表都可以用顺序表直接实现），其目的是实现字符到alphabet的对应字符所在下标的映射；huffmanCode其实就是Huffman编码表，用以记录不同的信息元对应的二进制编码结果；nodes用于统计我们创造的Huffman结点，因为是自下而上创建的，所以说这个表的最后一位是根结点。

3、数据的读入

	/************************ Read text.* * @param paraFilename The text filename.**********************/public void readText(String paraFilename) {try {inputText = Files.newBufferedReader(Paths.get(paraFilename), StandardCharsets.UTF_8).lines().collect(Collectors.joining("\n"));} catch (Exception ee) {System.out.println(ee);System.exit(0);} // Of trySystem.out.println("The text is:\r\b" + inputText);}// Of readText

         这次代码我们尝试用文件来实现读入，改变我们曾经的数据模拟方式。往往来说，对于文件中的数据读入，不同语言都有自己的操作方式，但是究其本质，无非是维护一个读指针，只不过不同程度的语言可能会对这个过程有不同程度的封装。这里Files.newBufferedReader( )是一种利用通用缓存读取文本流的工具，其位于java.nio.file.Files类之中，过于细的特征不用过多了解，只需要读取文件时，第一个参数需要是Path对象，而这个对象值可用Paths.get()方法将地址字符串转变获取，第二个参数是用于说明读取的编码类型，一般有中文我们都用UTF-8编码格式。

        到目前为止，Files.newBufferedReader(Paths.get(paraFilename), StandardCharsets.UTF_8)获取的应该是读指针之类的对象，而lines()方法用于返回从给定多行字符串中提取的行流，并用行终止符分隔。后续的collect是个收集器（收集器说来话长了...这不是今天重点，我们暂时略过吧），你只需要知道它能将流中的元素累积汇总起来，后续的joining操作是将我们个字符流仿照原文本中的换行汇总连接起来（有点像Python的join操作），因为我们lines()操作将文件中的数据逐行分流了，每个输入字符串在文本中原始模样就是按换行区分，现在分离汇总自然也按照换行汇总。

        其实分析了这么多，在以后的使用过程中，关于文件读入操作，我们只要记住这行代码就好了，需要用时直接复制就好，没必要深究太多。

        模拟结果：（下图显示没对齐是因为记事本中空格间隔和编译器显示界面的空格字符间距不同，总的来说，满足预期）

总结

        今天的文字认真给大家讲了我对于Huffman编码的自我看法，并且从定长编码和变长编码的角度分析了为什么会出现Huffman编码。当然这些都是我的一些自我理解，毕竟我不是学信息学的，关于信息的编码与构造，很多时候还是以一些计算机中浅显涉及的信息与编码知识为前提的。所以相关人士如果发现有纰漏的地方欢迎提出！让我也可以学习下。

        Huffman编码总的来说是树这一章集大成的一个代码，它结合了二叉树在编码领域的优点，属于二叉树在现实生活中的一个鲜活案例；同时，在构造Huffman树过程中，我们也会接触到三大算法之一的贪心思想；进一步，在Huffman编码的构造与解码的过程中，我们还会重温有关树的构造转换思想，这里会把我们前几天的内容进行一个结合。

        今天前半部分花了大部分时间聊了关于编码的东西，其实从定长编码到变长编码，人们对于信息存储的界限还留在非常有限的程度。而直到70年前的那个不知名的一天，百愁莫展的David A. Huffman正准备将论文笔记扔到垃圾桶中时，突然灵光一现，惊奇地发现了Huffman编码之后，信息存储的理论再次跨越一个全新台阶。放到生活中：传真机、调制解调器、电视信号转换开始出现，并且间接推动了信息与计算机的结合，再到后来的计算机网络。在那个人类群星闪耀的年代，计算机前辈们在一次次发现中奠定如今计算机领域大厦的根基，而如今我们也在不断续写这些故事，但是我们自始至终都可以发现一种东西在里面催化着：David A. Huffman当年通过简简单单的二叉树特性发现了前缀码，而如今，树形结构和二叉树有关的知识还在不断为更多的计算机研究者们开拓研究方向。所以，二叉树与树形结构真是个神奇的东西。（部分参考自灵光一现的创造——霍夫曼编码 - 知乎）