人工智能语聊的相关原理学习(一):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

目录
相关文章
|
1月前
|
机器学习/深度学习 人工智能 分布式计算
人工智能平台PAI产品使用合集之机器学习PAI的学习方法不知道如何解决
阿里云人工智能平台PAI是一个功能强大、易于使用的AI开发平台,旨在降低AI开发门槛,加速创新,助力企业和开发者高效构建、部署和管理人工智能应用。其中包含了一系列相互协同的产品与服务,共同构成一个完整的人工智能开发与应用生态系统。以下是对PAI产品使用合集的概述,涵盖数据处理、模型开发、训练加速、模型部署及管理等多个环节。
|
1天前
|
机器学习/深度学习 人工智能 搜索推荐
智能增强:人工智能在个性化学习中的应用
【6月更文挑战第22天】随着技术的不断进步,人工智能(AI)已经渗透到教育领域,为个性化学习带来了革命性的变化。本文将探讨AI如何通过数据分析、模式识别和自适应学习路径等技术手段,实现对学生学习能力和偏好的精准把握,并据此提供定制化的学习内容和策略。文章还将分析AI在提升教育质量、促进教育公平以及预测学生表现等方面的潜力与挑战,旨在揭示AI技术如何在塑造未来教育格局中发挥关键作用。
|
4天前
|
人工智能 搜索推荐 安全
人工智能与未来教育:重塑学习方式的革命
【6月更文挑战第19天】随着人工智能技术的飞速发展,其在教育领域的应用正逐步深化。本文将探讨人工智能如何影响和改变传统教育模式,包括个性化学习、智能教学辅助、数据驱动的教育决策以及未来教育的发展趋势。通过分析AI技术在教育中的应用案例和潜在挑战,本文旨在为读者提供一个关于AI如何塑造未来教育环境的全面视角。
|
2天前
|
机器学习/深度学习 人工智能 自然语言处理
学习人工智能常用名词解释
人工智能是当今科技领域中备受关注的热门话题,涵盖了众多令人兴奋的技术和应用。包括机器学习、深度学习、自然语言处理、计算机视觉等众多领域的重要概念。从监督学习、无监督学习到增强学习,从卷积神经网络、循环神经网络到生成对抗网络,这些名词解释详尽地介绍了人工智能技术的基础理论和应用方法。无论你是初学者还是专业人士,这些名词解释都将为你提供一个全面的人工智能知识体系。在不断涌现的新技术和应用中,人工智能必将在未来的各个领域中扮演更为重要的角色。
7 1
|
19天前
|
机器学习/深度学习 人工智能 自然语言处理
人工智能该如何学习?
学习人工智能是一个迅速发展的领域,对于任何行业的从业者来说都是非常重要的。
26 2
|
24天前
|
存储 人工智能 机器人
人工智能内部原理(二)(4)
人工智能内部原理(二)
31 1
|
24天前
|
存储 人工智能 资源调度
人工智能内部原理(二)(3)
人工智能内部原理(二)
25 1
|
24天前
|
机器学习/深度学习 人工智能 搜索推荐
人工智能内部原理(二)(2)
人工智能内部原理(二)
36 0
|
24天前
|
机器学习/深度学习 人工智能 算法
人工智能内部原理(二)(1)
人工智能内部原理(二)
40 1
|
1月前
|
机器学习/深度学习 人工智能 算法
构建未来:人工智能在持续学习系统中的进化
【5月更文挑战第24天】 本文聚焦于人工智能(AI)技术中一个关键且迅速发展的分支——持续学习系统。不同于传统的静态机器学习模型,持续学习系统能够适应新数据的到来,不断更新知识库,实现长期的累积学习。文章首先概述了持续学习的理论基础及其在现代AI领域的重要性;随后,详细探讨了该领域的最新进展,包括算法创新、神经网络架构的优化以及数据处理策略;最后,分析了持续学习面临的挑战和未来的发展方向。本研究旨在为AI专业人士提供深入见解,并激发对AI持续学习能力提升的新思路。

热门文章

最新文章