HanLP-最短路径分词
今天介绍的内容是最短路径分词。最近换回了thinkpad x1,原因是mac的13.3寸的屏幕看代码实在是不方便,也可能是人老了吧,^_^。等把HanLP词法分析介绍结束后,还是会换回macbook pro的。个人有强迫症,只要看或写Java或C/C++代码或者用开发机的化,还是喜欢在windows下工作。看论文特别是理论的研究还是习惯用mac了。感觉开发还是windows比较顺手,理论研究还是mac比较顺手。
基本思想:首先根据词典,找出字串中所有可能的词(也称全切分),然后构造词语切分有向无环图(也称作粗分词图或粗分词网)。每个词对应图中的一条有向边。若赋给相应的边长一个权值(该权值可以是常数,也可以是所构成的词的属性值),然后根据该切分图,在起点到终点的所有路径中,求出长度值(包括权值)为最短的一条路径,这条路径上包含的词就是该句子的切分结果。若每个结点处记录N个最短路径值,则该方法也称N-最短路径算法。
为进一步提高切分精度,在词典中增加词的属性值,即给每个词也给权重。这样每个词在汉字串中的权重不同(即构成的有向图的边不为等长)。最简单的词的权重可以用词频表示,高频词的权重大,低频词的权重小。具体的权重值可以通过大规模语料库获得。
虽然HanLP中提供了dijkstra算法的实现,但是当前HanLP中最短路径分词使用的是viterbi算法。
例子:他说的确实在理
遍历
计算过程和回溯分词过程
(1) node列与to列
node列的词语为粗分词网中所有的词,to列为在node列为词word_node的情况下,后边接的所有可能的词word_to。第1个词语前边有一个“始”词,最后一个词语后边有一个“末”词。
(2) begin2node_w的计算
表示从“始”到node词的最短路径权值。可以从待计算值所在行的node列读取出word词,在to列中以待计算值所在行开始向上查找word,找到word所在行后(以首次遇到的词为准),begin2to_w列所对应的值就是待计算值。见图中下划线。第一个词对“始-他”的begin2node_w的值为0。
(3) node2to_w的计算
由node+w构成的2gram串的概率,也就是转移概率,计算公式为
计算的HanLP代码为https://github.com/hankcs/HanLP/blob/master/src/main/java/com/hankcs/hanlp/utility/MathUtility.java calculateWeight(Vertex from, Vertex to)。“始”的频次取为MAX_FREQUENCY,“始-他”的共现频次值为“他”作为句首的频次,“理-末”的共现频次值为“理”作为句末的频次。
(4) begin2to_w_n的计算
表示从“始”到to词的最短路径权值。begin2to_w_n = begin2node_w + node2to_w。
(5) begin2to_w_o
表示记录在to词下的,到to词的最短路径权值,它的初始值为0,之后由begin2to_w来更新。
(6) from
表示词语to的前驱词。
可以看表中(7,9),(8,10),(11,13),(12,14),(15,16),(17,18)成对行来验证该公式,其中只有(17.18)行满足了第3个式子。
(6)和(7)的HanLP实现代码https://github.com/hankcs/HanLP/blob/master/src/main/java/com/hankcs/hanlp/seg/common/Vertex.java updateFrom(Vertex from)
(8) 回溯确定分词路径
从“末”开始向前回溯,末->理->在->确实->的->说->他,可以看表中黄色单元格进行验证。
经过(6)、(7)两步,可以确保粗分词网中任意词的前驱都是最短路径的。
遍历计算过程和回溯过程的HanLP代码https://github.com/hankcs/HanLP/blob/master/src/main/java/com/hankcs/hanlp/seg/Viterbi/ViterbiSegment.java viterbi(WordNet wordNet)
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
大神是怎样用函数式JavaScript计算数组平均值的
译者按: 有时候一个算法的直观、简洁、高效是需要作出取舍的。 原文: FUNCTIONAL JAVASCRIPT: FIVE WAYS TO CALCULATE AN AVERAGE WITH ARRAY REDUCE 译者: Fundebug 本文采用意译,版权归原作者所有 函数式编程中用于操作数组的方法就像“毒品”一样,它让很多人爱上函数式编程。因为它们真的十分常用而且又超级简单。 .map() 和 .filter()都仅需一个参数,该参数定义操作数组每一个元素的函数即可。reduce()会复杂一些,我之前写过一篇文章介绍为什么人们难以掌握reduce()方法,其中一个原因在于很多入门资料都仅仅用算术作为例子。我写了很多用reduce()来做算术以外的例子。 用reduce()来计算数组的平均值是一个常用的模式。代码看起来非常简单,不过在计算最终结果之前你需要做两个准备工作: 数组的长度 数组所有元素之和 这两个事情看起来都很简单,那么计算数组的平均值并不是很难了吧。解法如下: function average(nums) { return nums.reduce((a, b) =...
- 下一篇
Leetcode 498:对角线遍历Diagonal Traverse(python3、java)
对角线遍历 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.示例: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,4,7,5,3,6,8,9] 解释: 说明: 给定矩阵中的元素总数不会超过 100000 。 思路: 实例输入的二维数组范围均是0~2 先观察一下遍历规律:(0,0)->(0,1)->(1,0)->(2,0)->(1,1)->(0,2)->(1,2)->(2,1)->(2,2) 数组索引(m,n),两种改变方式1、(m-1,n+1) 2、(m+1,n-1) 数组从(0,0)开始,先是(m-1,n+1) ,(0...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8编译安装MySQL8.0.19
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7,8上快速安装Gitea,搭建Git服务器
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Docker安装Oracle12C,快速搭建Oracle学习环境
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS7安装Docker,走上虚拟化容器引擎之路