MyException - 我的异常网
当前位置:我的异常网» 人工智能 » 人工智能语聊的相干原理学习(一):Huffman编码

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

www.MyException.Cn  网友分享于:2013-11-16  浏览:0次
人工智能语聊的相关原理学习(一):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棵树的森林,每棵树只有一个结点;
  • 2. 从森林中选出两个根结点的权值最小的树合并,作为一棵新的子树,且新树的根结点权值为其左右子树根结点权值之和;
  • 3. 将合并的新树,替换掉原森林中的两棵子树;
  • 4. 重复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

 

点击有惊喜

文章评论

中美印日四国程序员比较
中美印日四国程序员比较
一个程序员的时间管理
一个程序员的时间管理
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
漫画:程序员的工作
漫画:程序员的工作
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
鲜为人知的编程真相
鲜为人知的编程真相
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员的鄙视链
程序员的鄙视链
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序员都该阅读的书
程序员都该阅读的书
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
我是如何打败拖延症的
我是如何打败拖延症的
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
10个调试和排错的小建议
10个调试和排错的小建议
如何成为一名黑客
如何成为一名黑客
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
那些争议最大的编程观点
那些争议最大的编程观点
 程序员的样子
程序员的样子
代码女神横空出世
代码女神横空出世
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员应该关注的一些事儿
程序员应该关注的一些事儿
老程序员的下场
老程序员的下场
Java程序员必看电影
Java程序员必看电影
程序员必看的十大电影
程序员必看的十大电影
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
旅行,写作,编程
旅行,写作,编程
总结2014中国互联网十大段子
总结2014中国互联网十大段子
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有