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

目录
相关文章
|
10天前
|
机器学习/深度学习 人工智能 算法
普通人怎么学人工智能?这些隐藏学习秘籍大揭秘,生成式人工智能认证(GAI认证)来助力
在人工智能(AI)快速发展的今天,普通人学习AI已成为必然趋势。本文从明确学习目标与路径、利用多元化资源、注重实践应用、关注GAI认证及持续自我提升五个方面,为普通人提供系统化的AI学习指南。通过设定目标、学习编程语言、参与项目实践和获取专业认证,普通人可逐步掌握AI技能,在未来职场中占据优势并开启智能时代新篇章。
|
5月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
5月前
|
人工智能 自然语言处理 搜索推荐
人工智能与教育:个性化学习的未来
【10月更文挑战第31天】在科技飞速发展的今天,人工智能(AI)正深刻改变教育领域,尤其是个性化学习的兴起。本文探讨了AI如何通过智能分析、个性化推荐、智能辅导和虚拟现实技术推动个性化学习,分析了其带来的机遇与挑战,并展望了未来的发展前景。
|
5月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法及应用
探索人工智能中的强化学习:原理、算法及应用
|
6月前
|
人工智能 搜索推荐 语音技术
人工智能与未来教育:重塑学习方式的双刃剑
在21世纪,人工智能(AI)技术正以前所未有的速度发展,深刻影响着社会的各个方面,其中包括教育领域。本文探讨了AI如何改变传统教育模式,提出其既带来积极影响也伴随着挑战的观点。通过分析具体案例和数据,文章旨在启发读者思考如何在保留人类教师不可替代价值的同时,有效利用AI技术优化教育体验。
|
6月前
|
机器学习/深度学习 人工智能 自然语言处理
人工智能与未来教育:重塑学习体验
【10月更文挑战第20天】 在21世纪的今天,人工智能(AI)技术正以前所未有的速度改变着我们的生活、工作和学习方式。本文探讨了AI如何深刻影响未来教育的各个方面,从个性化学习路径的设计到智能辅导系统的开发,再到虚拟现实(VR)和增强现实(AR)技术在学习中的应用。通过分析这些变革,我们不仅能够预见一个更加高效、互动和包容的教育未来,而且还能理解这一过程中所面临的挑战和机遇。文章强调了持续创新的重要性,并呼吁教育工作者、技术开发者和政策制定者共同努力,以确保技术进步惠及每一个学习者。
123 2
|
7月前
|
机器学习/深度学习 人工智能 自然语言处理
人工智能在教育中的创新应用:个性化学习的未来
【9月更文挑战第18天】人工智能在教育中的创新应用正在深刻改变着我们的教学方式和学习体验。从个性化学习方案的制定到智能化辅导与反馈,从多元化学习资源的推荐到自动化评分与智能考试系统,AI技术正在为教育领域带来前所未有的变革。面对这一变革,我们需要以开放和批判的态度拥抱它,共同探索AI时代教育的无限可能,为每一个学习者创造更美好的未来。
481 12
|
6月前
|
机器学习/深度学习 算法 数据建模
计算机前沿技术-人工智能算法-生成对抗网络-算法原理及应用实践
计算机前沿技术-人工智能算法-生成对抗网络-算法原理及应用实践
92 0
|
6月前
|
机器学习/深度学习 人工智能 算法
人工智能-大语言模型-微调技术-LoRA及背后原理简介
人工智能-大语言模型-微调技术-LoRA及背后原理简介
134 0
|
6月前
|
机器学习/深度学习 人工智能 自然语言处理
探索人工智能:从原理到实践
【10月更文挑战第6天】在这篇文章中,我们将深入探讨人工智能的基本原理,并展示如何将这些理论应用到实际编程中。无论你是AI新手还是有经验的开发者,这篇文章都将为你提供有价值的信息和启示。我们将从基础概念开始,逐步深入到复杂的编程示例,最后总结出一些关于人工智能未来发展的思考。让我们一起踏上这段探索之旅吧!

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等