中科院分词系统分析ictclas

《中科院分词系统分析ictclas》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京即刻搜索博客www.jike.bj.cn两天我开始看ICTCLAS的实现代码了，和吕震宇的感觉完全一样，代码真的是糟糕透顶，呵呵，非常同情吕震宇和Sinboy能够那么认真地把那些代码读完。有了你们辛苦、认真的分析工作，让我更容易的读懂ICTCLAS的代码了，谢谢了。阅读过程中注意到了他们分析中有些地方有点小错误。ICTCLAS的命名好像没有正统的学过数据结构一样，对于数据结构的命名非常富有想象力，完全没有按照数据结构上大家公认的术语命名，所以给代码的读者带来很大的迷惑性。所以我们在看名字的时候一定要抛开名

2、字看实现，看本质，看他们到底是个啥。呵呵。首先就是CQueue的问题，CQueue虽然叫Queue，但是它不是FIFO的Queue。那它是什么呢？CQueue是优先级队列PriorityQueue和Stack的杂交。但是没有半点FIFO的Queue的概念在里面。CQueue元素有一个权重eWeight，这个权重如果不为0（或者说互相之间不等），那么CQueue此时的含义是按照权重由小到大排序的优先级队列。如果CQueue的所有元素的eWeight都相等，（在ICTCLAS代码里就是都为0），此时CQueue就

3、演变为FILO的Stack，栈。因此这个CQueue才会有Push和Pop两种插入和删除元素的命名。呵呵，挂着羊头卖的是狗肉，还是两只狗。对于C#、C++、Java来说，类库里面都有现成的优先级队列和栈的实现，而且可以用List重载小于号(C++)、重载CompareTo()（C#,Java）List.Sort()来代替优先级队列实现和并且具有和作者一样的Iterator的功能。那个CQueue完全可以省略掉。然后是DynamicArray。动态数组？非也。这个是用来表示稀疏图的邻接表，每一个元素表示的

4、是图上的一条边。对于非稀疏的图往往喜欢用NxN的数组来表示N个节点的连接关系。而对于稀疏图来说，无疑会浪费大量的空间，于是往往采用记录邻接两点的边的方式来记录图。作者为了能够让以后调用的时候方便，对于起点和终点进行排序（或者说维护了顺序）。对起点排序，就是代码中所谓的RowFirst，对于终点进行排序就是ColumnFirst。北京即刻搜索博客www.jike.bj.cn北京即刻搜索博客www.jike.bj.cn那为何作者叫DynamicArray呢？其实也不难想象，首先是因为邻接表实际上就是边的一个列表，

5、也可以看为数组。但是边的数量是在变化的，而不是最开始就可以知道的。因此这个数组是动态的。于是就叫动态数组了。。。。汗。对于DynamicArray，我们也完全可以用List<>.Sort()的方式来实现，对于C++来说，我们需要定义2个functor，分别是起点优先比较和终点优先比较。对于Java和C#也有类似的定义比较函数的办法。因此这个DynamicArray()，可以扔掉了。没必要用这么一个奇怪的东西。接下来我把NShortPath中的最主要的三个函数intOutput(int**nResult,boo

6、lbBest,int*npCount);intShortPath();voidGetPaths(unsignedintnNode,unsignedintnIndex,int**nResult=0,boolbBest=false);的代码和分析帖在下面，分析都写在注释里了。在具体开始之前，我先明确一个东西，在中科院的论文里称求解多个最优路径问题为N最短路径问题(N-ShortestPaths)，如果你google你会发现没有多少有用的结果，其实不然。不知道是不是作者不了解国际上对该问题的讨论，这个问题应该称为k

7、shortestpath（即K最短路径问题）。这个问题也已经有了不错的解法，DavidEppstein分别在1994年和1997年已经给出了大约复杂度为O(m+nlogn+kn)的解法。而中科院论文里面的解法的复杂度还是比较高的：O(n*N*k)。（两个复杂度的字母含义不同，定义请看原论文）。所以，如果可能，再次实现ICTCLAS的算法的朋友可以考虑抛开中科院的求kshortestpath的解法，而使用国际上比较流行的解法。BTW:问一下，吕震宇，你有什么比较可爱点的称呼么？呵呵，我这么直呼大名在中文的习惯里

8、似乎不太礼貌。：）intCNShortPath::ShortPath()...{unsignedintnCurNode=1,nPreNode,i,nIndex;ELEMENT_TYPEeWeight;PARRAY_CHAINpEdgeList;北京即刻搜索博客www.jike.bj.cn北京即刻搜索博客www.jike.bj.cn//循环从1开始，即从第二个节点开始。遍历所有节点。for(;nCur