欢迎您光临本小站。希望您在这里可以找到自己想要的信息。。。

N-最短路径分词算法

数据结构算法 water 331℃ 0评论

NSP分词算法是句子粗分的基本算法,在中科院计算所的文章中有详细描述。但是看了不甚明白,今天实现了这个算法,主要用的还是图论的基本算法Dijkstra算法。

将分词转化为图的最短路径问题
假设要切分一下句子 :主席出现在这里。可将其转化为以下的图:

N-最短路径分词算法

从而,找出这个句子的最短切分的问题就可以转化为找出上图的0–>7最短路径的问题。这里所有边的权值都是1。

Dijkstra最短路径算法
关于这个算法的描述,网上很多,诸多教科书中也有描述,这里就不详述了。我们现在任务是根据Dijkstra算法计算出的源点0到所有点的最短路径值distace[]来找出所有的最短路径。
比如上图就有2条最短路径,对应两种切分方法:

  1. 0->2->4->5->7 主席/出现/在/这里

  2. 0->2->3->5->7 主席/出/现在/这里

可以用广度优先搜索来找出所有的路径。算法如下:
Input : 源点S,汇点T,distance[]

  1. Queue VQ,用来作为广度优先搜索的队列, VQ.append(T)

  2. while(!VQ.empty())

  3. Vertex V = VQ.pop()

  4. if V == S :

  5. 回溯出一条路径

  6. for vn in vertexlist :

  7. if distace[vn] == distacnce[V]-1 and w(vn,V) == 1 :

  8. VQ.append(vn)

这以算法的复杂度主要取决于Dijkstra算法,而后面的回溯过程是和最短路径数成正比的。
Dijkstra算法的复杂度取决于图的数据结构,在最好的情况下可以达到VlogV的复杂度。

转载请注明:学时网 » N-最短路径分词算法

喜欢 (0)or分享 (0)

您必须 登录 才能发表评论!