网站建设规定,东莞发布最新通告,招商码头无忧查询系统,网站制作公司违法N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法#xff0c;张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法算法基本思想很简单#xff0c;就是给定一待处理字串#xff0c;根据词典#xff0c;找出词典中所有…N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法算法基本思想很简单就是给定一待处理字串根据词典找出词典中所有可能的词构造出字串的一个有向无环图算出从开始到结束所有路径中最短的前N条路径。因为允许相等长度的路径并列故最终的结果集合会大于或等于N。 根据算法思想当我们拿到一个字串后首先构造图接着针对图计算最短路径。下面以一个例子“他说的确实在理”进行说明开始为了能够简单说明首先假设图上的边权值均为1。 先给出对这句话的3-最短路(即路径最短的前3名, 因为有并列成分, 所以可能候选路径大于3)径求解过程图 从节点4开始, 因为4是第一个出现多个前驱节点的 首先看图中上方它是根据一个已有词典构造出的有向无环图。它将字串分为单个的字每个字用图中相邻的两个结点表示故对于长度为n的字串需要n1个结点。两节点间若有边则表示两节点间所包含的所有结点构成的词如图中结点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是33号元素PreNode是11号元素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被压入此时又得到了一条最短路径那就是01236。如下图 再往下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此时在“最短路”处index0记录长度为3时的PreNode在“次短路”处index1处记录长度为4时的PreNode依此类推。 值得注意的是此时用来记录PreNode的坐标已经由前文求“1-最短路径”时的一个数ParentNode值)变为2个数ParentNode值以及index值。 如上图所示到达6号“末”结点的次短路径有两个ParentNode一个是index0中的4号结点一个是index1的5号结点它们都使得总路径长度为6。 当N2时我们求得了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://www.cnblogs.com/tiantiankong/p/10150152.html
