`

Hanlp中N最短路径分词详细介绍

阅读更多

 

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法算法基本思想很简单,就是给定一待处理字串,根据词典,找出词典中所有可能的词,构造出字串的一个有向无环图,算出从开始到结束所有路径中最短的前N条路径。因为允许相等长度的路径并列,故最终的结果集合会大于或等于N。

 

根据算法思想,当我们拿到一个字串后,首先构造图,接着针对图计算最短路径。下面以一个例子“他说的确实在理”进行说明,开始为了能够简单说明,首先假设图上的边权值均为1。 

先给出对这句话的3-最短路(即路径最短的前3名, 因为有并列成分, 所以可能候选路径大于3)径求解过程图: 

从节点4开始, 因为4是第一个出现多个前驱节点的

 



 

首先看图中上方,它是根据一个已有词典构造出的有向无环图。它将字串分为单个的字,每个字用图中相邻的两个结点表示,故对于长度为n的字串,需要n+1个结点。两节点间若有边,则表示两节点间所包含的所有结点构成的词,如图中结点2、3、4构成词“的确”。

图构造出来后,接下来就要计算最短路径,N-最短路径是基于Dijkstra算法的一种简单扩展,它在每个结点处记录了N个最短路径值与该结点的前驱,具体过程如上图中下方列表。Table(4)表示位于结点4时的最短路径情况,表示从结点0到4有两条路径,长度为3的路径前驱为2;长度为4的路径前驱为3。前驱括号里面第二个数表示对相同前驱结点的区分,如(4,1)、(4,2)。由列表可知,该字串的3-最短路径结果集合为{5,5,6,6,7}。

当然,在实际情况中,权值不可能都设为1的,否则随着字串长度n和最短路径N的增大,长度相同的路径数将会急剧增加。为了解决这样的问题,我们需要通过某种策略为有向图的边赋权重,很自然的想法就是边的权重就是该词出现的可能性。

 



 

NShortPath的基本思想是Dijkstra算法的变种,拿1-最短路来说吧,先Dijkstra求一次最短路,然后沿着最短路的路径走下去,只不过在走到某个节点的时候,检查到该节点在路径上的下一个节点是否还有别的路到它(从PreNode查),如果有,就走这些别的路中的没走过第一条(它们都是最短路上的途径节点)。然后推广到N-最短路,N-最短路中PreNode有N个,分别对应n-最短路时候的PreNode,就这么简单。

图解

再谈PreNode的准备

需要为每个顶点维护一个最小堆,最小堆里储存的是边的花费,每条边的终点是这个顶点。还需要维护到每个顶点的前N个最小路径的花费:

回忆一下Dijkstra求最短路的时候,我们只需记录一个最短路的累计花费就行了

这与此处的N-最短路径显著不同。

在遍历图的时候,与Dijkstra最短路径不同,N-最短路径从第二个节点开始,需要将当前节点可能到达的边根据累积第i短长度+该边的长度之和排序记录到PreNode队列数组中,排序由CQueue完成的。

然后从CQueue出队,这样路径长度就是升序了,按顺序更新 weightArray[当前节点][第几短路]就行了。

另外CQueue是一个不同于普通队列的队列,它维护了一个当前指针(下图的蓝色部分),这个蓝色指针在求解第i短路径的时候会用到。

 



 

假定看到这里,算法已经计算出了正确的PreNode队列,下面讨论如何从PreNode中找出N最短路径的确切途经节点集合。

1-最短路径的求解

整个计算过程维护了一个路径栈,对于上图来说,

1)首先将最后一个元素压入栈(本例中是6号结点),什么时候这个元素弹出栈,什么时候整个任务结束。

2)对于每个结点的PreNode队列,维护了一个当前指针,初始状态都指向PreNode队列中第一个元素。这个指针是由CQueue维护的,严格来讲不属于算法关心的问题。

3)从右向左依次取出PreNode队列中的当前元素(当前元素出队)并压入栈,并将队列指针重新指向队列中第一个元素。如上图:6号元素PreNode是3,3号元素PreNode是1,1号元素PreNode是0。

4)当第一个元素压入栈后,输出栈内容即为一条队列。本例中0, 1, 3, 6便是一条最短路径。

5)将栈中的内容依次弹出,每弹出一个元素,就将当时压栈时该元素对应的PreNode队列指针下移一格。如果到了末尾无法下移,则继续执行第5步(也就是继续出栈),如果仍然可以移动,则执行第3步。

对于本例,先将“0”弹出栈,在路径上0的下一个是1,得出该元素对应的是1号“A”结点的PreNode队列,该队列的当前指针已经无法下移,因此继续弹出栈中的“1” ;同理该元素对应3号“C”结点,因此将3号“C”结点对应的PreNode队列指针下移。由于可以移动,因此将队列中的2压入队列,2号“B”结点的PreNode是1,因此再压入1,依次类推,直到0被压入,此时又得到了一条最短路径,那就是0,1,2,3,6。如下图:

 



 

再往下,0、1、2都被弹出栈,3被弹出栈后,由于它对应的6号元素PreNode队列记录指针仍然可以下移,因此将5压入堆栈并依次将其PreNode入栈,直到0被入栈。此时输出第3条最短路径:0, 1, 2, 4, 5, 6。如下图:

 



 

输出完成后,紧接着又是出栈,此时已经没有任何栈元素对应的PreNode队列指针可以下移,于是堆栈中的最后一个元素6也被弹出栈,此时输出工作完全结束。我们得到了3条最短路径,分别是:

0, 1, 3, 6,

0, 1, 2, 3, 6,

0, 1, 2, 4, 5, 6,

推广到N-最短路

N-最短路中PreNode有N个,分别对应n-最短路时候的PreNode,也就是当前路径是第n短的时候,当前节点对应的PreNode队列。

 



 

在该图中,观察黄颜色的路径长度表格,到达1号、2号、3号结点的路径虽然有多条,但长度只有一种长度,但到达4号“D”结点的路径长度有两种,即长度可能是3也可能是4,此时在“最短路”处(index=0)记录长度为3时的PreNode,在“次短路”处(index=1)处记录长度为4时的PreNode,依此类推。

值得注意的是,此时用来记录PreNode的坐标已经由前文求“1-最短路径”时的一个数(ParentNode值)变为2个数(ParentNode值以及index值)。

如上图所示,到达6号“末”结点的次短路径有两个ParentNode,一个是index=0中的4号结点,一个是index=1的5号结点,它们都使得总路径长度为6。

N=2时,我们求得了2-最短路径,路径长度有两种,分别长度为5和6,而路径总共有6条,如下:

最短路径:

0, 1, 3, 6,

0, 1, 2, 3, 6,

0, 1, 2, 4, 5, 6,

========================

短路径

0, 1, 2, 4, 6,

0, 1, 3, 4, 5, 6,

0, 1, 2, 3, 4, 5, 6,

---------------------

作者:random-walk

原文:https://blog.csdn.net/asdfsadfasdfsa/article/details/80833781

 

  • 大小: 111.8 KB
  • 大小: 116.2 KB
  • 大小: 73.7 KB
  • 大小: 87.7 KB
  • 大小: 88.2 KB
  • 大小: 133.6 KB
分享到:
评论

相关推荐

    dev_最短路径中文分词_最短路径分词算法_

    在这个任务中,“最短路径分词算法”是一种常用的策略,用于解决如何高效准确地完成分词工作。本文将深入探讨最短路径分词算法的概念、原理及其在实际应用中的价值。 最短路径分词算法基于图论中的Dijkstra算法或...

    基于N最短路径方法与中国人名 识别的中文分词系统

    基于N最短路径方法与中国人名识别的中文分词系统 本文提出了一种基于N最短路径方法的中文词语粗分模型,用于中文文本的粗切分,并采用Viterbi算法对切分结果进行角色标注,在角色序列的基础上,进行模式最大匹配,...

    N-最短路径方法的中文词语粗分模型

    - **原理**:N-最短路径方法是一种在图中寻找多个最短路径的算法,可以应用于解决中文分词问题。 - **应用**:在中文分词中,可以将待分词的句子视为图的一个节点序列,通过构建图模型并运用N-最短路径算法找到最优...

    基于K最短路径的中文分词算法

    最短路径粗分模型是一种在中文分词中常用的算法,它通过构建一个特殊有向图来表示待分词文本的各种可能分词结果。在这个有向图中,每个节点代表文本中的某个位置,边则表示两个位置之间可能存在的一种分词方式。通过...

    N最短路径算法(包含算法说明文档).zip

    在压缩包中的"算法实现介绍.doc"可能是对N最短路径算法的详细描述,包括算法原理、步骤、时间复杂度分析以及可能的优化策略。而"N-shortestpath"可能是该算法的代码实现,可能使用Python、Java等编程语言,包含了...

    基于N_最短路径方法的中文词语粗分模型_张华平.pdf

    【N-最短路径方法】在中文词语粗分模型中,N-最短路径方法是一种常用的算法,它在处理中文词汇切分时考虑了多个可能的分词结果,并选取最合理的路径。这种方法的核心思想是通过构建有向图,将每个汉字视为图中的节点...

    基于HanLP对地址字符串分词流程图.eddx

    基于HanLP对地址字符串分词流程图.eddx

    读书笔记2之中文分词流程HanLP

    **细分阶段**,HanLP结合命名实体识别的结果,再次对词图进行分词,利用Dijkstra最短路径算法优化分词结果。 最后,**词性标注**阶段,HanLP使用Viterbi算法对分词结果进行词性标注,这是为了提供更丰富的语义信息...

    hanlp分词各类词性状态表,汉普分词规格表,hanlp各类词性表,hanlp分词词性表,nlp领域

    hanlp分词各类词性状态表: 比如: a 形容词 ad 副形词 b 区别词 n 名词 h 前缀 i 成语 j 简称略语 k 后缀 l 习用语 m 数词 mg 数语素 Mg 甲乙丙丁之类的数词 mq 数量词

    基于n_最短路径方法的中文词语粗分模型.doc

    这篇文档《基于n_最短路径方法的中文词语粗分模型》探讨了一种利用层叠隐马模型(Cascaded Hidden Markov Model, CHMM)来实现这一任务的方法。该模型将汉语的分词、词性标注、切分歧义解决和未登录词识别集成在一个...

    C++使用最短路径匹配算法实现中文文本分词源代码+实验报告+用户手册

    C++使用最短路径匹配算法实现中文文本分词源代码+实验报告+用户手册 1. 本程序的执行文件为 CWS.cpp,并且需要词典文件 dict.txt。需将词典文件放在程序 的运行目录下。 2. 进入演示程序后,程序会让用户输入一串...

    Java中通过HanLP实现文本分词、提取关键词、聚类(工具资源+实例)

    HanLP是由一系列模型与算法组成的工具包,目标是普及自然语言处理在生产环境中的应用。HanLP具备功能完善、性能高效、架构清晰、语料时新、可自定义的特点;提供词法分析(中文分词、词性标注、命名实体识别)、句法...

    Hanlp分词实现从网络片段中提取省份和城市

    在这个场景中,我们关注的是如何利用Java语言和HanLP分词库来实现从网络片段中抽取省份和城市这一特定需求。HanLP是由科大讯飞开发的一款高性能的自然语言处理工具包,它提供了丰富的中文分词、词性标注、命名实体...

    中文分词的一些文章

    这是一种广泛应用的分词策略,通过计算所有可能的分词路径并选取最短的N个作为结果。这种方法通常结合词频信息,利用动态规划算法来找到最优解,既能避免过分割也能减少漏分的问题。 其次,"一个求解次短和渐次短...

    HanLP中文分词所需内容_2.zip

    主要包含HanLP中文分词需要的jar包,properties文件,data文件夹,以及一些测试代码。HanLP是由一系列模型与算法组成的Java工具包,目标是普及自然语言处理在生产环境中的应用。HanLP具备功能完善、性能高效、架构...

    hanlp,jieba,nlpir分词工具安装报错完全解决方案.docx

    ### hanlp、jieba、nlpir...综上所述,针对hanlp、jieba、nlpir在安装过程中遇到的各种问题,我们分别提供了详细的分析和解决方案。遵循上述步骤,可以有效解决大多数安装报错问题,帮助用户顺利完成工具的部署和使用。

    hanlp jar ,最近搞分词技术把不同版本的jar 提供给大家

    首先,`hanlp-solr-plugin-1.1.2.jar` 是HanLP与Solr集成的插件,Solr是一个流行的开源搜索引擎,这个插件使得HanLP的分词能力可以无缝集成到Solr中,从而提升搜索的精准度。开发者可以通过这个插件,在Solr中实现对...

    基于hanlp的elasticsearch分词插件

    描述中的“基于hanlp的elasticsearch分词插件”意味着开发者已经实现了将HanLP的功能集成到Elasticsearch插件中,用户可以在Elasticsearch中直接使用HanLP的分词算法,无需在两个系统间做额外的数据转换。...

    基于python开发的微型中文分词器 附完整代码

    以下几种分词算法: 1.按照词语的频率来利用构建 DAG来分词,使用 Trie Tree 构建前缀字典树 2.使用隐马尔可夫模型来分词 3.融合 DAG 和 HMM 两种分词模型的结果,按照分词粒度最大化的原则进行融合得到的模型 4.正向...

Global site tag (gtag.js) - Google Analytics