开发者社区> 欲泰78786> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

人工智能语聊的相关原理学习(一):Huffman编码

简介:
+关注继续查看

引言

最近在学习人工智能相关的一些知识,第一阶段希望能将方向放在聊天机器人的实现原理上,在对聊天机器人设计的关键技术有了一个大概的了解后,决定先从google的著名开源项目 word2vec 开始入手。而Huffman编码则是word2vec原理的一个非常重要的背景知识。

何为Huffman树

我们都知道,树在计算机科学中是一种非常重要的非线性数据结构,它是数据元素按分支关系组织起来的结构,数据元素在树中被称之为结点。若干棵互不关联的树,我们称之为森林。

  • 路径:在一棵树中,从任意一个结点向下到达该结点的孩子或孙子结点之间的通路称为路径;
  • 路径长度:通路中分支的数据则为路径长度,如果一棵树有N层,那么从根结点到第N层结点的路径长度为 N-1;
  • 结点的权:如果树中的结点被赋予了具有意义的数值,且为正数,那么该数值则被称为该结点的权;
  • 带权路径长度:从根结点到某结点之间的路径长度与该结点的权的乘积,被称为带权路径长度;
  • 树的带权路径长度:树上所有叶子结点的带权路径长度之和则为树的带权路径长度。

二叉树是每个结点最多两个子树的有序树。两个子树称为“左子树”和“右子树”,有序的意思则是指两个子树有左右之分,不能搞错。
那么给定N个权值作为N个叶子结点,构造一棵二叉树,如果它的带权路径长度达到最小,那么这样的二叉树被称之为最优二叉树,也就是今天要学习的Huffman树。

Huffman树的构造

给定N个权值[X1, X2, X3 ... Xn]作为二叉树的N个叶子结点,我们来构造一棵Huffman树

    1. 将[X1, X2, X3 ... Xn]看成是有N棵树的森林,每棵树只有一个结点;
    1. 从森林中选出两个根结点的权值最小的树合并,作为一棵新的子树,且新树的根结点权值为其左右子树根结点权值之和;
    1. 将合并的新树,替换掉原森林中的两棵子树;
    1. 重复2和3,直到所有的子树都被合并而只剩下唯一的一棵树,这棵树则为Huffman树。

举个栗子:我在北京天安门广场观看升旗。 把这句话做分词切分为 “我”,“在”,“北京天安门”,“广场”,“观看“,”升旗“,假设它们出现的词频分别为15,8,6,5,3,1。我们将这6个词作为叶子结点,以相应的词频当做结点的权值,来构造一棵Huffman树。
screenshot.png
screenshot.png
screenshot.png
screenshot.png
screenshot.png
screenshot.png
通过5个步骤,我们构造出了这个Huffman树,可以从图中看出,词频越大的词,离词根则越近。

在构造过程中,通过合并后新增的结点被标记为了蓝色的结点,而每两个结点都要进行一次合并,由此可知,如果叶子结点的个数为N,则构造的Huffman树中新增结点的个数为N-1。上面的栗子中一共有6个词,则新增了5个结点。

Huffman编码

在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符。例如,需要传送的文字为“after data ear are art area”,这里用到的字符有"a,e,r,t,f,d",各个字母出现的次数为 8,4,5,3,1,1,现在尝试为这些字母设计编码。

要区别6个字母,最简单的二进制编码方式是等长编码,固定采用3位二进制,可分别用000,001,010,011,100,101对“a,e,r,t,f,d”进行编码发送,接收方再按照三位一分进行译码。那么由此看来,编码的长度则取决于报文中不同字符的个数,如果报文中可能出现26个不同字符,则固定编码程度为5,即2的5次方。然而,传送报文时总是希望总长度尽可能的短,那么在实际应用中,各个字符的出现频度或使用次数是不同的,如果a,b,c的使用频率远高于x,y,z,那在设计编码时,可以用使用频率高的用短码,而使用频率低的,则用长码,从而优化整个报文编码。

为使不等长编码为前缀编码,即要求一个字符的编码不能是另一个字符编码的前缀,可以用字符集中的每个字符作为叶子结点生成一棵编码二叉树,为了获得传送报文的最短长度,可将每个字符的出现频率作为字符结点的权值,而显然使用频率越小的权值越小,权值越小叶子就越靠下,于是频率小编码长,频率高编码短,这样就保证了这棵树的最小带权路径长度,效果上就是传送报文的最短长度。因此,求传递报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点,由字符出现频率作为其权值所产生的Huffman树的问题,利用Huffman树设计的二进制前缀编码,称为Huffman编码,它既能满足前缀编码的条件,又能保证报文编码总长度最短。

到目前为止,Huffman树和Huffman编码有两个约定,1. 将权值大的结点作为左孩子结点,权值小的作为右孩子结点;2. 左孩子结点编码为1,右孩子结点编码为0。在word2vec工具中也将用到Huffman编码,它把训练预料中的词当成叶子结点,其在预料中出现的次数当做权值,通过构造相应的Huffman树来对每一个词进行Huffman编码,将权值较大的孩子结点编码为1,较小的孩子结点编码为0。根据这个原则,我们再把前面构造好的Huffman树标上对应的编码就可以得到“我在北京天安门广场观看升旗”的Huffman编码: “我”-0,“在”-111,“北京天安门”-110,“广场”-101,“观看”1001,“升旗”-1000。可见,词频越高的词,编码则越短。
screenshot.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
人工智能基础知识
人工智能基础知识
0 0
人工智能入门四件套,你学人工智能避不开的知识点
为了照顾有基础的人,我这里将本文分为了6个阶段,如果你是这个阶段的 可以点击下面跳过已经看过的部分,毕竟不是所有人都有耐心重新看一遍已经会的东西的~~
0 0
人工智能与机器学习的区别与作用是什么?
你如何理解人工智能和机器学习的宣传?你应该如何思考认知计算能为你的业务做些什么?让我们仔细看看。
0 0
人工智能学习笔记之——人工智能基本概念和词汇
除了在这里记录一些生活琐事之外,我还决定在这里记录一下自己的学习和见闻。做一个简单的自我背景介绍吧,我本科来自国内某985高校的微电子专业,博士毕业于英国某罗素集团大学的物理学院,博士后加入了英国某高校电子信息与计算机学院的机器人课题组,并从此开始关注人工智能。
699 0
自学人工智能:3-0 算法
而真正开始认识到算法,方才接触到编程的灵魂。
16068 0
人工智能进阶心得:在战斗中学习,在学习中战斗
12月20日的北京云栖大会上,由云栖社区主办的开发者技术进阶峰会再度开启。在此之前,我们整理了2017杭州云栖大会开发者技术进阶专场上的精彩分享内容。
3695 0
4月10日云栖精选夜读:一篇文章搞懂人工智能、机器学习和深度学习之间的区别
现在人工智能是如此热门,引得许多传统的程序员纷纷投入这个领域,嘴巴每天都挂着人工智能、机器学习这些词语。不过,作为这个领域的研究者,如果真的有外行人问你什么是人工智能?人工智能与机器学习还有深度学习有什么不同呢?恐怕你也得稍稍思考一下了。
2555 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
人工智能应用实践
立即下载
人工智能在骨科领域的新实践和新探索
立即下载
人工智能人才技术进阶心得
立即下载