文档介绍：基于一种粗切分的最短途径中文分词研究
　　摘要本论文在分析现有的分词算法并比拟各种算法优缺点的根底上，提出了将正向匹配算法与逆向匹配算法所得到的结果集进展叠加，生成粗分结果集的新观点，再对生成的粗分结果集构造非负权有向图，然后应用最短途径中同时存在AB与AB，这样构成的有向图会严重影响整个切分效率和准确性。
　　本文采用的叠加方法防止了上述情况的发生，如下描绘：正向切分按照切分结果顺序排列Lz，逆向切分按照切分结果倒序排列Lr。对于Lz与Lr，从某一个切分词i〔i=0，1，2，…，n,其中n=in{length〔Lz〕，length〔Lr〕}〕开场比拟，保存词应该是两者中长度最大的。根据保存词从Lz和Lr中获得下一个比拟词的开场字符，重复上述过程直到Lz与Lr中长度最小的结果集比拟完毕。这样就能保证有向图中的顶点唯一，顶点个数最少。
　　
　　用给定的字符串构造非负权图的方法如下所述：
　　①对于给定语句S〔从构成来看由许多单字组成，而表达的意义是由多个语义单位构成〕；
　　②根据提供的统一分词词典，按照正向最大匹配算法找出字符串中所有可能的语意对象或者词，求得构词集Vd={vd1,vd2,…,vdn}；
　　③如同②，按照反向最大匹配算法找出字符串中所有可能的语意对象或者词；求得构词集Vr={vr1,vr2,…,vrn}；
　　④对②与③的构词集Vd与Vr按照本论文算法进展叠加运算，连同语句中所有的单字集Vs获得无负权图所有构词集V={v1,v2,…,vn}，边权值定义为ij=1(i,j=1,2,…,n)；
　　⑤在相邻节点Nk-1，Nk之间建立有向边Nk-1,Nk，边的长度值为Lk，边对应的词默认为vk(k=1,2,…,n)；
　　⑥假设=vivi+1…vj是一个在V中的词，那么在节点Ni-1，Nj之间建立有向边Ni-1,Nj，边的长度为L，边对应的词为(0ij≤n)。
　　在本论文中，边的长度Lk(k=1,2,…,n)统一赋值为1。由上述方法构造的非负
　　权图如图1所示。
　　[1]
　　假设P(i,j)是顶点集N中ni到nj的途径集合(i,j=0,2,…,n)，L(p)是某两点间途径长度，其值等于p中所有边的长度之和。LS是G中所有n0到nn途径的长度集合，LS={len|len=L(p),p∈P(1,n)}。NLS为n0到nn的N-最短途径长度集合，，|NLS|=in(|LS|)；，b∈NLS←ab。NSP为n0到nn的N-最短途径集合，NSP={p|p∈P(1,n),L(p)∈NLS}。而RS是最终的N-最短途径结果集，RS={12…|i是p的第i个顶点对应的词，i=1,2,…,，其中p∈NSP}。RS是NSP对应的分词结果，即为所求的结果集。这样，N-最短途径方法转化为：如何求解无负权有向图G的集合NSP。在每一个节点处记录下最短途径值，并记录相应途径受骗前节点的前驱。假如同一长度对应多条途径，必须同时记录这些途径受骗前节点的前驱，最后通过回溯即可求出NSP。
　　以上求解算法借鉴了文献[1]最短途径匹配算法的求解形式。而本文所提出的算法与文献[1]有明显不同，在最短途径匹配算法中根据分词词典找出所有可能的词，直接构造有向无环图G，每一个词对应图中的一条有向边