西安网站公司推广展示型企业网站营销目标主要有

当前位置： 首页 > news >正文

西安网站公司推广,展示型企业网站营销目标主要有,软件外包保密协议,wordpress如何上传超过2m注意#xff1a;这里是JAVA自学与了解的同步笔记与记录#xff0c;如有问题欢迎指正说明 目录 前言 一、前缀码定义 二、固定编码与一般变长编码的不足与Huffman编码的特性 1、固定编码与一般变长编码 2、Huffman编码 2.1 Huffman编码的提出 2.2 Huffman编码二叉树构建…注意这里是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当年通过简简单单的二叉树特性发现了前缀码而如今树形结构和二叉树有关的知识还在不断为更多的计算机研究者们开拓研究方向。所以二叉树与树形结构真是个神奇的东西。部分参考自灵光一现的创造——霍夫曼编码 - 知乎