Monday, April 24, 2006

 

Some notes on Chinese Words Segmentation - 4

这移植工作到也不错,不过不知是正则表达式效率高还是手工优化效率高

1.
http://www.cnblogs.com/zhenyulu/articles/667359.html

实现ICTCLAS到C#平台的移植
在研究了一段时间中科院计算所张华平、刘群所开发的ICTCLAS分词系统(Free版)代码后,阅读了大量的相关资料,我开始着手将C++的ICTCLAS分词系统移植到.net平台下,并取得了较好的实验结果。这种移植并不容易,在研究了ICTCLAS分词理论的同时还要阅读C++代码实现,其中遇到了很多困惑、迷茫,也不得不重写了一小部分代码,我将在随后的文章中介绍具体实现。

目前除了最后的词性标注部分还没有完全完工外,其它部分已经接近尾声(包括初始切分、N最短路径、人名、地名的识别以及最终优化等),我们先来看看程序对以下句子的分词结果:

Copy CodeSharpICTCLAS程序分词结果
==== 原始句子:

王晓平在滦南大会上说的确实在理

==== 粗切分后的结果(N个结果):

始##始, 王, 晓, 平, 在, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,

始##始, 王, 晓, 平, 在, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末,

始##始, 王, 晓, 平, 在, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末,

始##始, 王, 晓, 平, 在, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末,

始##始, 王, 晓, 平, 在, 滦, 南, 大, 会, 上, 说, 的, 确实, 在, 理, 末##末,

==== 加入对姓名、翻译人名以及地名的识别:

row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 2, eWeight: 218.00, nPOS: 0, sWord:王
row: 1, col: 4, eWeight: 10.86, nPOS: -28274, sWord:未##人
row: 2, col: 3, eWeight: 9.00, nPOS: 0, sWord:晓
row: 2, col: 4, eWeight: 13.27, nPOS: -28274, sWord:未##人
row: 3, col: 4, eWeight: 271.00, nPOS: 0, sWord:平
row: 4, col: 5, eWeight: 78484.00, nPOS: 0, sWord:在
row: 5, col: 6, eWeight: 1.00, nPOS: 27136, sWord:滦
row: 5, col: 7, eWeight: 20.37, nPOS: -28275, sWord:未##地
row: 6, col: 7, eWeight: 813.00, nPOS: 0, sWord:南
row: 7, col: 8, eWeight: 14536.00, nPOS: 0, sWord:大
row: 7, col: 9, eWeight: 1333.00, nPOS: 28160, sWord:大会
row: 8, col: 9, eWeight: 6136.00, nPOS: 0, sWord:会
row: 8, col: 10, eWeight: 469.00, nPOS: 0, sWord:会上
row: 9, col: 10, eWeight: 23706.00, nPOS: -27904, sWord:上
row: 10, col: 11, eWeight: 17649.00, nPOS: 0, sWord:说
row: 11, col: 12, eWeight: 358156.00, nPOS: 0, sWord:的
row: 12, col: 14, eWeight: 361.00, nPOS: 0, sWord:确实
row: 14, col: 15, eWeight: 78484.00, nPOS: 0, sWord:在
row: 14, col: 16, eWeight: 3.00, nPOS: 24832, sWord:在理
row: 15, col: 16, eWeight: 129.00, nPOS: 0, sWord:理
row: 16, col: 17, eWeight:2079997.00, nPOS: 4, sWord:末##末

==== 最终识别结果:

始##始, 王晓平, 在, 滦南, 大会, 上, 说, 的, 确实, 在, 理, 末##末,

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

==== 原始句子:

馆内陈列周恩来和邓颖超生前使用过的物品

==== 粗切分后的结果(N个结果):

始##始, 馆内, 陈列, 周恩来, 和, 邓, 颖, 超, 生前, 使用, 过, 的, 物品, 末##末,

始##始, 馆内, 陈列, 周恩来, 和, 邓, 颖, 超生, 前, 使用, 过, 的, 物品, 末##末,

始##始, 馆内, 陈列, 周恩来, 和, 邓, 颖, 超, 生前, 使用, 过, 的, 物, 品, 末##末,

始##始, 馆内, 陈列, 周恩来, 和, 邓, 颖, 超生, 前, 使, 用, 过, 的, 物品, 末##末,

始##始, 馆内, 陈列, 周恩来, 和, 邓, 颖, 超, 生, 前, 使用, 过, 的, 物品, 末##末,

==== 加入对姓名、翻译人名以及地名的识别:

row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 3, eWeight: 24.00, nPOS: 0, sWord:馆内
row: 3, col: 5, eWeight: 70.00, nPOS: 0, sWord:陈列
row: 5, col: 8, eWeight: 1990.00, nPOS: 28274, sWord:周恩来
row: 8, col: 9, eWeight: 72562.00, nPOS: 0, sWord:和
row: 9, col: 10, eWeight: 90.00, nPOS: 28274, sWord:邓
row: 9, col: 12, eWeight: 15.93, nPOS: -28274, sWord:未##人
row: 10, col: 11, eWeight: 2.00, nPOS: 28274, sWord:颖
row: 11, col: 12, eWeight: 200.00, nPOS: 0, sWord:超
row: 11, col: 13, eWeight: 4.00, nPOS: 0, sWord:超生
row: 12, col: 13, eWeight: 532.00, nPOS: 0, sWord:生
row: 12, col: 14, eWeight: 175.00, nPOS: 29696, sWord:生前
row: 13, col: 14, eWeight: 5107.00, nPOS: 0, sWord:前
row: 14, col: 15, eWeight: 8224.00, nPOS: 0, sWord:使
row: 14, col: 16, eWeight: 1876.00, nPOS: 0, sWord:使用
row: 15, col: 16, eWeight: 5300.00, nPOS: 0, sWord:用
row: 16, col: 17, eWeight: 5090.00, nPOS: 0, sWord:过
row: 17, col: 18, eWeight: 358156.00, nPOS: 0, sWord:的
row: 18, col: 19, eWeight: 200.00, nPOS: 0, sWord:物
row: 18, col: 20, eWeight: 189.00, nPOS: 28160, sWord:物品
row: 19, col: 20, eWeight: 75.00, nPOS: 0, sWord:品
row: 20, col: 21, eWeight:2079997.00, nPOS: 4, sWord:末##末

==== 最终识别结果:

始##始, 馆内, 陈列, 周恩来, 和, 邓颖超, 生前, 使用, 过, 的, 物品, 末##末,
从上面结果可以看出,切分效果还是令人满意的(当然这完全是由原有ICTCLAS的良好设计理论所决定)。

在移植的过程中,比较突出的问题包括:

1、C#支持Unicode,而原有设计是基于单字节表示
在原有设计中使用了大量的字符数组,而且一个汉字在字符数组中占两个字符位置。为了取出一个字符,必须考虑是半角字符还是全角汉字。所以随处可见类似代码:

Copy CodeC++代码实现取一个字符
char tchar[3];
tchar[2] = 0;

tchar[0] = sWord[k];
tchar[1] = 0;
if (sWord[k] < 0)
{
tchar[1] = sWord[k + 1];
k += 1;
}
k += 1;
为了判断是否是汉字,使用了“if (sWord[k] < 0) ”等手段异常繁琐。

而C#本身对Unicode有很好的支持,所以只需要string.ToCharArray()方法就可以将一个一个字符拆分开来。但需要注意的是,在C#中一个汉字的长度是1,而C++实现中一个汉字的长度是2,这要求在移植过程中要仔细对待。

2、使用正则表达式简化了部分设计
原有设计中为了判断一个字符串是否是数字需要很长的代码(例如Utility类中的IsAllNum方法),代码行数将近7~80行,而改用正则表达式后,一行代码就解决问题了。 移植后的代码使用了很多正则表达式简化类似代码。

3、字符串比较问题
由于原有设计中,对汉字大小的比较是基于CCID的(尤其是对词典库进行检索时),一个汉字的CCID计算方式如下:

Copy CodeCCID计算方法(C#)
//====================================================================
// 根据汉字返回对应的CC_ID
//====================================================================
public static int CC_ID(char c)
{
byte[] b = Encoding.GetEncoding("gb2312").GetBytes(c.ToString());
if (b.Length != 2)
return -1;
else
return (Convert.ToInt32(b[0]) - 176) * 94 + (Convert.ToInt32(b[1]) - 161);
}

而C#的字符串比较没有一个适合CCID方式的字符串比较,例如在原有设计中,“声”、“生”、“现”的大小关系是:“声” < “生” < “现”,而C#中string.Compare方法不管设置为StringComparison.Ordinal、StringComparison.CurrentCulture还是StringComparison.InvariantCulture都无法达到这个结果,因此不得已设计了自己的字符串比较函数。

4、重写了部分代码
由于原有ICTCLAS系统代码的繁琐和不易理解(可以参考《天书般的ICTCLAS分词系统代码(一)》、《天书般的ICTCLAS分词系统代码(二)》) ,我重写了部分代码,主要包括:

1)重写了DynamicArray代码。新代码使用了三个类实现了原有代码,将不同功能分离开,使得代码简单易读。

2)重写了NShortPath代码。到现在我也没有完全弄明白原作者在实现NShortPath时的思路,干脆自己写吧。重写后的新代码比原有代码简化了不少,而且比较容易理解(至少我是这么认为的)。

3)Segment类中重写了GenerateWord方法,使用了链表而不是数组记录结果,并采用了管道式的处理流程,这简化了后续的合并逻辑。

4)对原有代码中部分属性、变量、字段的命名进行了调整,让其更具有实际意义。例如原有代码中nHandle和nPOS据我理解应当是一会事,所以新程序中全部使用nPOS这个命名。

5、保留了相当一部分原有代码
对于某些逻辑结构异常复杂的情况,在新代码中保留了原有的设计内容。

例如Segment类中对日期、年份、时间等的合并策略,其if条件嵌套有5层之多,为了保留原有逻辑,在移植过程中仅做了微小的调整。

另外CSpan、Unknown等类中的代码几乎没有做任何调整(其中包含了大量的计算逻辑),保留了原汁原味的内容。

2.
http://www.cnblogs.com/zhenyulu/articles/668024.html

SharpICTCLAS分词系统简介(1)读取词典库
ICTCLAS分词的总体流程包括:1)初步分词;2)词性标注;3)人名、地名识别;4)重新分词;5)重新词性标注这五步。就第一步分词而言,又细分成:1)原子切分;2)找出原子之间所有可能的组词方案;3)N-最短路径中文词语粗分三步。

在所有内容中,词典库的读取是最基本的功能。ICTCLAS中词典存放在Data目录中,常用的词典包括coreDict.dct(词典库)、BigramDict.dct(词与词间的关联库)、nr.dct(人名库)、ns.dct(地名库)、tr.dct(翻译人名库),它们的文件格式是完全相同的,都使用CDictionary类进行解析。如果想深入了解ICTCLAS词典结构,可以参考sinboy的《ICTCLAS分词系统研究(二)--词典结构》一文,详细介绍了词典结构。我这里只给出SharpICTCLAS中的实现。

首先是对基本元素的定义。在SharpICTCLAS中,对原有命名进行了部分调整,使得更具有实际意义并适合C#的习惯。代码如下:

Copy CodeWordDictionaryElement.cs 程序
using System;
using System.Collections.Generic;
using System.Text;

namespace SharpICTCLAS
{
//==================================================
// Original predefined in DynamicArray.h file
//==================================================
public class ArrayChainItem
{
public int col, row;//row and column
public double value;//The value of the array
public int nPOS;
public int nWordLen;
public string sWord;
//The possible POS of the word related to the segmentation graph
public ArrayChainItem next;
}

public class WordResult
{
//The word
public string sWord;

//the POS of the word
public int nPOS;

//The -log(frequency/MAX)
public double dValue;
}

//--------------------------------------------------
// data structure for word item
//--------------------------------------------------
public class WordItem
{
public int nWordLen;

//The word
public string sWord;

//the process or information handle of the word
public int nPOS;

//The count which it appear
public int nFrequency;
}

//--------------------------------------------------
//data structure for dictionary index table item
//--------------------------------------------------
public class IndexTableItem
{
//The count number of words which initial letter is sInit
public int nCount;

//The head of word items
public WordItem[] WordItems;
}

//--------------------------------------------------
//data structure for word item chain
//--------------------------------------------------
public class WordChain
{
public WordItem data;
public WordChain next;
}

//--------------------------------------------------
//data structure for dictionary index table item
//--------------------------------------------------
public class ModifyTableItem
{
//The count number of words which initial letter is sInit
public int nCount;

//The number of deleted items in the index table
public int nDelete;

//The head of word items
public WordChain pWordItemHead;
}
}

其中ModifyTableItem用于组成ModifyTable,但在实际分词时,词库往往处于“只读”状态,因此用于修改词库的ModifyTable实际上起的作用并不大。因此在后面我将ModifyTable的代码暂时省略。

有了基本元素的定义后,就该定义“词典”类了。原有C++代码中所有类名均以大写的“C”打头,词典类名为CDictionary,在SharpICTCLAS中,我去掉了开头的“C”,并且为了防止和系统的Dictionary类重名,特起名为“WordDictionary”类。该类主要负责完成词典库的读、写以及检索操作。让我们看看如何读取词典库:

Copy Code词典库的读取:
public class WordDictionary
{
public bool bReleased = true;

public IndexTableItem[] indexTable;
public ModifyTableItem[] modifyTable;

public bool Load(string sFilename)
{
return Load(sFilename, false);
}

public bool Load(string sFilename, bool bReset)
{
int frequency, wordLength, pos; //频率、词长、读取词性
bool isSuccess = true;
FileStream fileStream = null;
BinaryReader binReader = null;

try
{
fileStream = new FileStream(sFilename, FileMode.Open, FileAccess.Read);
if (fileStream == null)
return false;

binReader = new BinaryReader(fileStream, Encoding.GetEncoding("gb2312"));

indexTable = new IndexTableItem[Predefine.CC_NUM];

bReleased = false;
for (int i = 0; i < Predefine.CC_NUM; i++)
{
//读取以该汉字打头的词有多少个
indexTable[i] = new IndexTableItem();
indexTable[i].nCount = binReader.ReadInt32();

if (indexTable[i].nCount <= 0)
continue;

indexTable[i].WordItems = new WordItem[indexTable[i].nCount];

for (int j = 0; j < indexTable[i].nCount; j++)
{
indexTable[i].WordItems[j] = new WordItem();

frequency = binReader.ReadInt32(); //读取频率
wordLength = binReader.ReadInt32(); //读取词长
pos = binReader.ReadInt32(); //读取词性

if (wordLength > 0)
indexTable[i].WordItems[j].sWord = Utility.ByteArray2String(binReader.ReadBytes(wordLength));
else
indexTable[i].WordItems[j].sWord = "";

//Reset the frequency
if (bReset)
indexTable[i].WordItems[j].nFrequency = 0;
else
indexTable[i].WordItems[j].nFrequency = frequency;

indexTable[i].WordItems[j].nWordLen = wordLength;
indexTable[i].WordItems[j].nPOS = pos;
}
}
}
catch (Exception e)
{
Console.WriteLine(e.Message);
isSuccess = false;
}
finally
{
if (binReader != null)
binReader.Close();

if (fileStream != null)
fileStream.Close();
}
return isSuccess;
}
//......
}


下面内容节选自词库中CCID为2、3、4、5的单元, CCID的取值范围自1~6768,对应6768个汉字,所有与该汉字可以组成的词均记录在相应的单元内。词库中记录的词是没有首汉字的(我用带括号的字补上了),其首汉字就是该单元对应的汉字。词库中记录了词的词长、频率、词性以及词。

另外特别需要注意的是在一个单元内,词是按照CCID大小排序的!这对我们后面的分析至关重要。

Copy CodeICTCLAS词库部分内容
汉字:埃, ID :2

词长 频率 词性 词
0 128 h (埃)
0 0 j (埃)
2 4 n (埃)镑
2 28 ns (埃)镑
4 4 n (埃)菲尔
2 511 ns (埃)及
4 4 ns (埃)克森
6 2 ns (埃)拉特湾
4 4 nr (埃)里温
6 2 nz (埃)默鲁市
2 27 n (埃)塞
8 64 ns (埃)塞俄比亚
22 2 ns (埃)塞俄比亚联邦民主共和国
4 3 ns (埃)塞萨
4 4 ns (埃)舍德
6 2 nr (埃)斯特角
4 2 ns (埃)松省
4 3 nr (埃)特纳
6 2 nz (埃)因霍温
====================================
汉字:挨, ID :3

词长 频率 词性 词
0 56 h (挨)
2 1 j (挨)次
2 19 n (挨)打
2 3 ns (挨)冻
2 1 n (挨)斗
2 9 ns (挨)饿
2 4 ns (挨)个
4 2 ns (挨)个儿
6 17 nr (挨)家挨户
2 1 nz (挨)近
2 0 n (挨)骂
6 1 ns (挨)门挨户
2 1 ns (挨)批
2 0 ns (挨)整
2 12 ns (挨)着
2 0 nr (挨)揍
====================================
汉字:哎, ID :4

词长 频率 词性 词
0 10 h (哎)
2 3 j (哎)呀
2 2 n (哎)哟
====================================
汉字:唉, ID :5

词长 频率 词性 词
0 9 h (唉)
6 4 j (唉)声叹气
在这里还应当注意的是,一个词可能有多个词性,因此一个词可能在词典中出现多次,但词性不同。若想从词典中唯一定位一个词的话,必须同时指明词与词性。

另外在WordDictionary类中用到得比较多的就是词的检索,这由FindInOriginalTable方法实现。原ICTCLAS代码中该方法的实现结构比较复杂,同时考虑了多种检索需求,因此代码也相对复杂一些。在SharpICTCLAS中,我对该方法进行了重载,针对不同检索目的设计了不同的FindInOriginalTable方法,简化了程序接口和代码复杂度。其中一个FindInOriginalTable方法代码如下,实现了判断某一词性的一词是否存在功能。

Copy CodeFindInOriginalTable方法的一个重载版本
private bool FindInOriginalTable(int nInnerCode, string sWord, int nPOS)
{
WordItem[] pItems = indexTable[nInnerCode].WordItems;

int nStart = 0, nEnd = indexTable[nInnerCode].nCount - 1;
int nMid = (nStart + nEnd) / 2, nCmpValue;

//Binary search
while (nStart <= nEnd)
{
nCmpValue = Utility.CCStringCompare(pItems[nMid].sWord, sWord);

if (nCmpValue == 0 && (pItems[nMid].nPOS == nPOS || nPOS == -1))
return true;//find it
else if (nCmpValue < 0 || (nCmpValue == 0 && pItems[nMid].nPOS < nPOS && nPOS != -1))
nStart = nMid + 1;
else if (nCmpValue > 0 || (nCmpValue == 0 && pItems[nMid].nPOS > nPOS && nPOS != -1))
nEnd = nMid - 1;

nMid = (nStart + nEnd) / 2;
}
return false;
}

其它功能在这里就不再介绍了。

小结
1、WordDictionary类实现了对字典的读取、写入、更改、检索等功能。

2、词典中记录了以6768个汉字打头的词、词性、出现频率的信息,具体结构需要了解。

3.
http://www.cnblogs.com/zhenyulu/articles/668035.html

SharpICTCLAS分词系统简介(2)初步分词
ICTCLAS初步分词包括:1)原子切分;2)找出原子之间所有可能的组词方案;3)N-最短路径中文词语粗分三步。

例如:“他说的确实在理”这句话。

1)原子切分的目的是完成单个汉字的切分。经过原子切分后变成“始##始/他/说/的/确/实/在/理/末##末”。

2)然后根据“词库字典”找出所有原子之间所有可能的组词方案。经过词库检索后,该句话变为“始##始/他/说/的/的确/确/确实/实/实在/在/在理/末##末”。

3)N-最短路径中文词语粗分。下面的过程就比较复杂了,首先我们要找出这些词之间所有可能的两两组合的距离(这需要检索BigramDict.dct词典库)。对于上面的案例而言,得到的BiGraph结果如下:

Copy Code所有可能成句的词间两两组合距离
row: 0, col: 1, eWeight: 3.37, nPOS: 1, sWord:始##始@他
row: 1, col: 2, eWeight: 2.25, nPOS: 0, sWord:他@说
row: 2, col: 3, eWeight: 4.05, nPOS: 0, sWord:说@的
row: 2, col: 4, eWeight: 7.11, nPOS: 0, sWord:说@的确
row: 3, col: 5, eWeight: 4.10, nPOS: 0, sWord:的@确
row: 3, col: 6, eWeight: 4.10, nPOS: 0, sWord:的@确实
row: 4, col: 7, eWeight: 11.49, nPOS: 25600, sWord:的确@实
row: 5, col: 7, eWeight: 11.63, nPOS: 0, sWord:确@实
row: 4, col: 8, eWeight: 11.49, nPOS: 25600, sWord:的确@实在
row: 5, col: 8, eWeight: 11.63, nPOS: 0, sWord:确@实在
row: 6, col: 9, eWeight: 3.92, nPOS: 0, sWord:确实@在
row: 7, col: 9, eWeight: 10.98, nPOS: 0, sWord:实@在
row: 6, col: 10, eWeight: 10.97, nPOS: 0, sWord:确实@在理
row: 7, col: 10, eWeight: 10.98, nPOS: 0, sWord:实@在理
row: 8, col: 11, eWeight: 11.17, nPOS: 0, sWord:实在@理
row: 9, col: 11, eWeight: 5.62, nPOS: 0, sWord:在@理
row: 10, col: 12, eWeight: 14.30, nPOS: 24832, sWord:在理@末##末
row: 11, col: 12, eWeight: 11.95, nPOS: 0, sWord:理@末##末
可以从上表中可以看出“的@确实”的距离为4.10,而“的确@实”间的距离为11.49,这说明“的@确实”的组合可能性要大一些。不过这只是一面之词,究竟如何组词需要放到整句话的环境下通盘考虑,达到整体最优。这就是N最短路径需要完成的工作。

在求最短路径前我们需要将上表换一个角度观察,其实上表可以等价的表述成如下图所示的“有向图”:



上表中词与词的组合(例如“的@确实”)在该图中对应一条边(由节点“的”到节点“确实”),其路径长度就是上表中的eWeight值。这样一来,求最优分词方案就成了求整体最短路径。

由于是初次切分,为了提高后续优化质量,这里求的是N最短路径,即路径长度由小到大排序后的前N种长度的所有路径。对于上面案例,我们假设N=2,那么求解得到的路径有2条(注意也可能比两条多,关于这点我 将在后续专门介绍NShortPath时再说):

路径(1):

0, 1, 2, 3, 6, 9, 11, 12, 13

始##始 / 他 / 说 / 的 / 确实 / 在 / 理 / 末##末

路径(2):

0, 1, 2, 3, 6, 10, 12, 13

始##始 / 他 / 说 / 的 / 确实 / 在理 / 末##末


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

如果要想真正搞清楚上述过程,必须对下面的数据结构以及它的几种不同的表述方式有个透彻的了解。

DynamicArray
DynamicArray是什么?其实它的本质是一个经过排序的链表。为了表达的更明白些,我们不妨看下面这张图:



(图一)

上面这张图是一个按照index值进行了排序的链表,当插入新结点时必须确保index值的有序性。DynamicArray类完成的功能基本上与上面这个链表差不多,只是排序规则不是index,而是row和col两个数据,如下图:



(图二)

大家可以看到,这个有序链表的排序规则是先按row排序,row相同的按照col排序。当然排序规则是可以改变的,如果先按col排,再按row排,则上面的链表必须表述成:



(图三)

原有ICTCLAS实现时,在一个类里面综合考虑了row先排序和col先排序的两种情况,这在SharpICTCLAS中做了很大调整,将DynamicArray类作为父类提供一些基础操作,同时设计了RowFirstDynamicArray和ColumnFirstDynamicArray类作为子类提供专门的方法,这使得代码变得清晰多了(有关DynamicArray的实现我在下一篇文章中再做介绍)。

在本文最前面给出的案例中,根据“词库字典”找出所有原子字间的组词方案,其结果为“始##始/他/说/的/的确/确/确实/实/实在/在/在理/末##末”,而内容就是靠一个RowFirstDynamicArray存储的,如下:

Copy Code程序
row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 2, eWeight: 19823.00, nPOS: 0, sWord:他
row: 2, col: 3, eWeight: 17649.00, nPOS: 0, sWord:说
row: 3, col: 4, eWeight: 358156.00, nPOS: 0, sWord:的
row: 3, col: 5, eWeight: 210.00, nPOS: 25600, sWord:的确
row: 4, col: 5, eWeight: 181.00, nPOS: 0, sWord:确
row: 4, col: 6, eWeight: 361.00, nPOS: 0, sWord:确实
row: 5, col: 6, eWeight: 357.00, nPOS: 0, sWord:实
row: 5, col: 7, eWeight: 295.00, nPOS: 0, sWord:实在
row: 6, col: 7, eWeight: 78484.00, nPOS: 0, sWord:在
row: 6, col: 8, eWeight: 3.00, nPOS: 24832, sWord:在理
row: 7, col: 8, eWeight: 129.00, nPOS: 0, sWord:理
row: 8, col: 9, eWeight:2079997.00, nPOS: 4, sWord:末##末
DynamicArray的二维图表表示
如果根据RowFirstDynamicArray中row和col的坐标信息将DynamicArray放到一个二维表格中的话,我们就得到了DynamicArray的二维图表表示。如下图所示:



(图四)

在这张图中,行和列有一个非常有意思的关系:col为 n 的列中所有词可以与row为 n 的所有行中的词进行组合。例如“的确”这个词,它的col = 5,需要和它计算平滑值的有两个,分别是row = 5的两个词:“实”和“实在”。

如果将所有行与列之间词与词之间的关系找到,我们就可以得到另外一个ColumnFirstDynamicArray,如本文第一张表中内容所示。将该ColumnFirstDynamicArray的内容放到另外一个二维表中就得到如下图所示内容:



(图五)

ColumnFirstDynamicArray的有向图表示
上面这张表可以和一张有向图所对应,就如前文所说,词与词的组合(例如“的@确实”)在该图中对应一条边(由节点“的”到节点“确实”),其路径长度就是上表中的eWeight值,如下图所示:

剩下的事情就是针对该图求解N最短路径了,这将在后续文章中介绍。

小结
ICTCLAS的初步分词是一个比较复杂的过程,涉及的数据结构、数据表示以及相关算法都颇有难度。在SharpICTCLAS中,对原有C++代码做了比较多的更改,重新设计了DynamicArray类与NShortPath方法,在牺牲有限性能的同时力争大幅度简化代码的复杂度,提高可读性。

有关SharpICTCLAS中DynamicArray类的实现以及在代码可读性与性能之间的权衡将在下一篇文章中加以介绍。

4.
http://www.cnblogs.com/zhenyulu/articles/668695.html

SharpICTCLAS分词系统简介(3)DynamicArray
从前文可以看出,ICTCLAS中DynamicArray类在初步分词过程中起到了至关重要的所用,而ICTCLAS中DynamicArray类的实现比较复杂,可以说是包罗万象,在一个GetElement方法就综合考虑了1)row优先排序的链表;2)col优先排序的链表;3)当nRow为-1时的行为;4)当nCol为-1时的行为;5)当nRow与nCol都不为-1时的行为 (可以参考本人的《天书般的ICTCLAS分词系统代码(一)》一文)。

为了简化编程接口,并将纠缠不清的代码逻辑剥离开来,我重新设计了DynamicArray类,利用三个类实现原有一个类的功能。具体改造包括:1) 将DynamicArray类做成一个抽象父类,实现一些公共功能;2)设计了RowFirstDynamicArray类与ColumnFirstDynaimcArray类作为DynamicArray的子类,分别实现row优先排序和col优先排序的DynamicArray。2) 在牺牲有限性能的同时力争大幅度简化代码的复杂度,提高可读性。

具体实现如下:

1、DynamicArray链表结点的定义
为了使得DynamicArray更具有通用性,使用了范型方式定义了链表的结点,代码如下:

Copy CodeDynamicArray链表结点的定义
public class ChainItem
{
public int row;
public int col;
public T Content;
public ChainItem next;
}
2、DynamicArray类
DynamicArray类是一个抽象类,主要为RowFirstDynamicArray类与ColumnFirstDynaimcArray类提供公共的基础功能,例如查找行、列值为nRow, nCol的结点等。同时,该类将插入一新结点的方法设计成抽象方法,需要具体类根据row优先排序还是col优先排序自行决定具体实现。DynamicArray类的代码实现如下(应当说非常简单):

Copy CodeDynamicArray.cs 程序
public abstract class DynamicArray
{
protected ChainItem pHead; //The head pointer of array chain
public int ColumnCount, RowCount; //The row and col of the array

public DynamicArray()
{
pHead = null;
RowCount = 0;
ColumnCount = 0;
}

public int ItemCount
{
get
{
ChainItem pCur = pHead;
int nCount = 0;
while (pCur != null)
{
nCount++;
pCur = pCur.next;
}
return nCount;
}
}

//====================================================================
// 查找行、列值为nRow, nCol的结点
//====================================================================
public ChainItem GetElement(int nRow, int nCol)
{
ChainItem pCur = pHead;

while (pCur != null && !(pCur.col == nCol && pCur.row == nRow))
pCur = pCur.next;

return pCur;
}

//====================================================================
// 设置或插入一个新的结点
//====================================================================
public abstract void SetElement(int nRow, int nCol, T content);

//====================================================================
// Return the head element of ArrayChain
//====================================================================
public ChainItem GetHead()
{
return pHead;
}

//====================================================================
//Get the tail Element buffer and return the count of elements
//====================================================================
public int GetTail(out ChainItem pTailRet)
{
ChainItem pCur = pHead, pPrev = null;
int nCount = 0;
while (pCur != null)
{
nCount++;
pPrev = pCur;
pCur = pCur.next;
}
pTailRet = pPrev;
return nCount;
}

//====================================================================
// Set Empty
//====================================================================
public void SetEmpty()
{
pHead = null;
ColumnCount = 0;
RowCount = 0;
}

public override string ToString()
{
StringBuilder sb = new StringBuilder();

ChainItem pCur = pHead;

while (pCur != null)
{
sb.Append(string.Format("row:{0,3}, col:{1,3}, ", pCur.row, pCur.col));
sb.Append(pCur.Content.ToString());
sb.Append("\r\n");
pCur = pCur.next;
}

return sb.ToString();
}
}
3、RowFirstDynamicArray类的实现
RowFirstDynamicArray类主要实现了row优先排序的DynamicArray,里面包含了两个方法:GetFirstElementOfRow(获取row为nRow的第一个元素)和SetElement方法。其中GetFirstElementOfRow有两个重载版本。

这等价于将原有ICTCLAS中GetElement方法拆分成了三个方法,如果算上重载版本的话共五个方法,它们分别是:1)获取行、列值为nRow, nCol的结点,此方法由DynamicArray类实现;2)对于Row优先排序的链表而言,单独提供了GetFirstElementOfRow方法。3)对于Column优先排序的链表而言,单独提供了GetFirstElementOfColumn方法。

RowFirstDynamicArray类的实现如下:

Copy CodeRowFirstDynamicArray.cs 程序
public class RowFirstDynamicArray : DynamicArray
{
//====================================================================
// 查找行为 nRow 的第一个结点
//====================================================================
public ChainItem GetFirstElementOfRow(int nRow)
{
ChainItem pCur = pHead;

while (pCur != null && pCur.row != nRow)
pCur = pCur.next;

return pCur;
}

//====================================================================
// 从 startFrom 处向后查找行为 nRow 的第一个结点
//====================================================================
public ChainItem GetFirstElementOfRow(int nRow, ChainItem startFrom)
{
ChainItem pCur = startFrom;

while (pCur != null && pCur.row != nRow)
pCur = pCur.next;

return pCur;
}

//====================================================================
// 设置或插入一个新的结点
//====================================================================
public override void SetElement(int nRow, int nCol, T content)
{
ChainItem pCur = pHead, pPre = null, pNew; //The pointer of array chain

if (nRow > RowCount)//Set the array row
RowCount = nRow;

if (nCol > ColumnCount)//Set the array col
ColumnCount = nCol;

while (pCur != null && (pCur.row < nRow || (pCur.row == nRow && pCur.col < nCol)))
{
pPre = pCur;
pCur = pCur.next;
}

if (pCur != null && pCur.row == nRow && pCur.col == nCol)//Find the same position
pCur.Content = content;//Set the value
else
{
pNew = new ChainItem();//malloc a new node
pNew.col = nCol;
pNew.row = nRow;
pNew.Content = content;

pNew.next = pCur;

if (pPre == null)//link pNew after the pPre
pHead = pNew;
else
pPre.next = pNew;
}
}
}
有关ColumnFirstDynamicArray类的实现大同小异,这里就不再提供代码了。我们此时可以对比一下原有ICTCLAS中GetElement的实现:

Copy CodeDynamicArray.cpp
ELEMENT_TYPE CDynamicArray::GetElement(int nRow, int nCol, PARRAY_CHAIN pStart,
PARRAY_CHAIN *pRet)
{
PARRAY_CHAIN pCur = pStart;
if (pStart == 0)
pCur = m_pHead;
if (pRet != 0)
*pRet = NULL;
if (nRow > (int)m_nRow || nCol > (int)m_nCol)
//Judge if the row and col is overflow
return INFINITE_VALUE;
if (m_bRowFirst)
{
while (pCur != NULL && (nRow != - 1 && (int)pCur->row < nRow || (nCol !=
- 1 && (int)pCur->row == nRow && (int)pCur->col < nCol)))
{
if (pRet != 0)
*pRet = pCur;
pCur = pCur->next;
}
}
else
{
while (pCur != NULL && (nCol != - 1 && (int)pCur->col < nCol || ((int)pCur
->col == nCol && nRow != - 1 && (int)pCur->row < nRow)))
{
if (pRet != 0)
*pRet = pCur;
pCur = pCur->next;
}
}
if (pCur != NULL && ((int)pCur->row == nRow || nRow == - 1) && ((int)pCur
->col == nCol || nCol == - 1))
//Find the same position
{
//Find it and return the value
if (pRet != 0)
*pRet = pCur;
return pCur->value;
}
return INFINITE_VALUE;
}
可以看出,将原有GetElement方法拆分成3个方法后,代码得到大大简化,而且逻辑更为清晰了。

3、性能与代码可读性的权衡
DynamicArray类为了确保代码的清晰可读,在某些地方做了些调整,让我们对比一下SharpICTCLAS与ICTCLAS中在这方面的不同考虑。下面的代码演示了GetFirstElementOfRow方法在两者之间的不同之处(我特意对ICTCLAS代码做了逻辑上的简化):

Copy Code程序
//====================================================================
// SharpICTCLAS 中的查找行为 nRow 的第一个结点
//====================================================================
public ChainItem GetFirstElementOfRow(int nRow)
{
ChainItem pCur = pHead;

while (pCur != null && pCur.row != nRow)
pCur = pCur.next;

return pCur;
}

//====================================================================
// ICTCLAS 中的查找行为 nRow 的第一个结点
//====================================================================
... GetElement(int nRow, int nCol, PARRAY_CHAIN pStart, PARRAY_CHAIN *pRet)
{
PARRAY_CHAIN pCur = pStart;

while (pCur != NULL && (pCur->row < nRow || (pCur->row == nRow && pCur->col < nCol)))
{
if (pRet != 0)
*pRet = pCur;
pCur = pCur->next;
}

if (pCur != NULL && pCur->row == nRow && pCur->col == nCol)
{
if (pRet != 0)
*pRet = pCur;
return pCur->value;
}
//......
}
从上面代码中可以看出,原有ICTCLAS代码充分考虑到DynamicArray是一个排序链表,因此仅仅在pCur->row < nRow与pCur->col < nCol范围内检索,如果找到了“pCur->row == nRow && pCur->col == nCol”,那么再去做该做的事情。

而SharpICTCLAS中,判断条件仅为“pCur != null && pCur.row != nRow”,这意味着如果你要找的nRow不再该链表中,则会来个“完全遍历”,搜索范围似乎太大了。

不过出于以下几点考虑我还是采用了这种表示方式:

1)汉语中的一句话不会太长,这意味着链表长度不会很长,即使来个“完全遍历”也不会牺牲多少时间。

2)毕竟要找的nRow不在该链表中的可能性不大,出现“完全遍历”的机会也不多。

3)原有ICTCLAS虽然在搜索范围内下了翻功夫,但为了确保pRet变量得到赋值,循环体内部多次执行了“if (pRet != 0)”的判断,这从性能角度上说得不偿失。

4)原有ICTCLAS为了缩小搜索范围确增加了条件判断次数“pCur != NULL && (pCur->row < nRow || (pCur->row == nRow && pCur->col < nCol))”,而由此带来的性能损失不得不考虑一下。

正因为以上几点考虑,所以在SharpICTCLAS中采用了这种简单而且并不见得低效的方式取代原有的GetElement方法。

小结
SharpICTCLAS重新设计了DynamicArray类,力争简化原有设计中复杂的代码逻辑,应当说效果比较明显。即便有性能损失,那也是微不足道的,权衡利弊,我选择了走简单的代码这条路。

5.
http://www.cnblogs.com/zhenyulu/articles/669795.html

SharpICTCLAS分词系统简介(4)NShortPath-1
N-最短路径中文词语粗分是分词过程中非常重要的一步,而原有ICTCLAS中该部分代码也是我认为最难读懂的部分,到现在还有一些方法没有弄明白,因此我几乎重写了NShortPath类。要想说明N-最短路径代码是如何工作的并不容易,所以分成两步分,本部分先说说SharpICTCLAS中1-最短路径是如何实现的,在下一篇文章中再引申到N-最短路径。

1、数据表示
这里我们求最短路的例子使用如下的有向图,每条边的权重已经在图中标注出来了。



(图一)

根据上篇文章内容,该图该可以等价于如下的二维表格表示:



(图二)

而对应于该表格的是一个ColumnFirstDynamicArray,共有10个结点,每个结点的取值如下表所示:

Copy Code该示例对应的ColumnFirstDynamicArray
row:0, col:1, eWeight:1, nPOS:0, sWord: 始@A
row:1, col:2, eWeight:1, nPOS:0, sWord: A@B
row:1, col:3, eWeight:2, nPOS:0, sWord: A@C
row:2, col:3, eWeight:1, nPOS:0, sWord: B@C
row:2, col:4, eWeight:1, nPOS:0, sWord: B@D
row:3, col:4, eWeight:1, nPOS:0, sWord: C@D
row:4, col:5, eWeight:1, nPOS:0, sWord: D@E
row:3, col:6, eWeight:2, nPOS:0, sWord: C@末
row:4, col:6, eWeight:3, nPOS:0, sWord: D@末
row:5, col:6, eWeight:1, nPOS:0, sWord: E@末
2、计算出每个结点上可达最短路的PreNode
在求解N-最短路径之前,先看看如何求最短PreNode。如下图所示:



(图三)

首先计算出到达每个结点的最短路径,并将该结点的父结点压入该结点所对应的队列。例如3号“C”结点,到达该结点的最短路径长度为3,它的Parent结点可以是1号“A”结点,也可以是2号“B”结点,因此在队列中存储了两个PreNode结点。

而在实际计算时,如何知道到达3号“C”结点的路径有几条呢?其实我们首先计算所有到达3号“C”结点的路径长度,并按照路径长度从小到大的顺序排列(所有这些都是靠CQueue这个类完成的),然后从队列中依次向后取值,取出所有最短路径对应的PreNode。

计算到当前结点(nCurNode)可能的边,并根据总路径长度由小到大压入队列的代码如下(经过简化):

Copy CodeEnQueueCurNodeEdges方法
//====================================================================
// 将所有到当前结点(nCurNode)可能的边根据eWeight排序并压入队列
//====================================================================
private void EnQueueCurNodeEdges(ref CQueue queWork, int nCurNode)
{
int nPreNode;
double eWeight;
ChainItem pEdgeList;

queWork.Clear();
pEdgeList = m_apCost.GetFirstElementOfCol(nCurNode);

// 获取所有到当前结点的边
while (pEdgeList != null && pEdgeList.col == nCurNode)
{
nPreNode = pEdgeList.row; // 很特别的命令,利用了row与col的关系
eWeight = pEdgeList.Content.eWeight;

// 第一个结点,没有PreNode,直接加入队列
if (nPreNode == 0)
{
queWork.EnQueue(new QueueElement(nPreNode, eWeight));
break;
}

queWork.EnQueue(new QueueElement(nPreNode, eWeight + m_pWeight[nPreNode - 1]));
pEdgeList = pEdgeList.next;
}
}

这段代码中有一行很特别的命令,就是用红颜色注释的那句“nPreNode = pEdgeList.row;”,让我琢磨了半天终于弄明白原有ICTCLAS用意的一句话。这需要参考本文图二,为了方便起见,我将它挪到了这里:



注意 3 号“C”结点在该表中处于第 3 列,所有可以到达该结点的边就是该列中的元素(目前有两个元素“A@C”与“B@C”)。而与 3 号“C”结点构成这两条边的PreNode结点恰恰是这两个元素的“行号”,分别是 1 号“A”结点与 2 号“B”结点。正是因为这种特殊的对应关系,为我们检索所有可达边提供了便捷的方法。阅读上面那段代码务必把握好这种关系。

3、求解最短路径
求出每个结点上最短路径的PreNode后就需要据此推导出完整的最短路径。原ICTCLAS代码中是靠GetPaths方法实现的,只是到现在我也没有读懂这个方法的代码究竟想干什么 ,只知道它用了若干个while,若干个if,若干个嵌套...(将ICTCLAS中的GetPaths放上来,如果谁读懂了,回头给我讲讲 ,感觉应该和我的算法差不多)。

Copy CodeNShortPath.cpp程序中的GetPaths方法
void CNShortPath::GetPaths(unsigned int nNode, unsigned int nIndex, int
**nResult, bool bBest)
{
CQueue queResult;
unsigned int nCurNode, nCurIndex, nParentNode, nParentIndex, nResultIndex = 0;

if (m_nResultCount >= MAX_SEGMENT_NUM)
//Only need 10 result
return ;
nResult[m_nResultCount][nResultIndex] = - 1; //Init the result
queResult.Push(nNode, nIndex);
nCurNode = nNode;
nCurIndex = nIndex;
bool bFirstGet;
while (!queResult.IsEmpty())
{
while (nCurNode > 0)
//
{
//Get its parent and store them in nParentNode,nParentIndex
if (m_pParent[nCurNode - 1][nCurIndex].Pop(&nParentNode, &nParentIndex, 0,
false, true) != - 1)
{
nCurNode = nParentNode;
nCurIndex = nParentIndex;
}
if (nCurNode > 0)
queResult.Push(nCurNode, nCurIndex);
}
if (nCurNode == 0)
{
//Get a path and output
nResult[m_nResultCount][nResultIndex++] = nCurNode; //Get the first node
bFirstGet = true;
nParentNode = nCurNode;
while (queResult.Pop(&nCurNode, &nCurIndex, 0, false, bFirstGet) != - 1)
{
nResult[m_nResultCount][nResultIndex++] = nCurNode;
bFirstGet = false;
nParentNode = nCurNode;
}
nResult[m_nResultCount][nResultIndex] = - 1; //Set the end
m_nResultCount += 1; //The number of result add by 1
if (m_nResultCount >= MAX_SEGMENT_NUM)
//Only need 10 result
return ;
nResultIndex = 0;
nResult[m_nResultCount][nResultIndex] = - 1; //Init the result

if (bBest)
//Return the best result, ignore others
return ;
}
queResult.Pop(&nCurNode, &nCurIndex, 0, false, true); //Read the top node
while (queResult.IsEmpty() == false && (m_pParent[nCurNode -
1][nCurIndex].IsSingle() || m_pParent[nCurNode - 1][nCurIndex].IsEmpty
(true)))
{
queResult.Pop(&nCurNode, &nCurIndex, 0); //Get rid of it
queResult.Pop(&nCurNode, &nCurIndex, 0, false, true); //Read the top node
}
if (queResult.IsEmpty() == false && m_pParent[nCurNode -
1][nCurIndex].IsEmpty(true) == false)
{
m_pParent[nCurNode - 1][nCurIndex].Pop(&nParentNode, &nParentIndex, 0,
false, false);
nCurNode = nParentNode;
nCurIndex = nParentIndex;
if (nCurNode > 0)
queResult.Push(nCurNode, nCurIndex);
}
}
}
我重写了求解最短路径的方法,其算法表述如下:



(图四)

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

2)对于每个结点的PreNode队列,维护了一个当前指针,初始状态都指向PreNode队列中第一个元素。

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

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

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

对于本例,先将“0”弹出堆栈,该元素对应的是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,
让我们看看在SharpICTCLAS中,该算法是如何实现的:

Copy CodeSharpICTCLAS中的GetPaths方法
//====================================================================
// 注:index = 0 : 最短的路径; index = 1 : 次短的路径
// 依此类推。index <= this.m_nValueKind
//====================================================================
public List GetPaths(int index)
{
Stack stack = new Stack();
int curNode = m_nNode - 1, curIndex = index;
QueueElement element;
PathNode node;
int[] aPath;
List result = new List();

element = m_pParent[curNode - 1][curIndex].GetFirst();
while (element != null)
{
// ---------- 通过压栈得到路径 -----------
stack.Push(new PathNode(curNode, curIndex));
stack.Push(new PathNode(element.nParent, element.nIndex));
curNode = element.nParent;

while (curNode != 0)
{
element = m_pParent[element.nParent - 1][element.nIndex].GetFirst();
stack.Push(new PathNode(element.nParent, element.nIndex));
curNode = element.nParent;
}

// -------------- 输出路径 --------------
PathNode[] nArray = stack.ToArray();
aPath = new int[nArray.Length];

for(int i=0; i aPath[i] = nArray[i].nParent;

result.Add(aPath);

// -------------- 出栈以检查是否还有其它路径 --------------
do
{
node = stack.Pop();
curNode = node.nParent;
curIndex = node.nIndex;

} while (curNode < 1 || (stack.Count != 0 && !m_pParent[curNode - 1][curIndex].CanGetNext));

element = m_pParent[curNode - 1][curIndex].GetNext();
}

return result;
}
注意,上面的代码是N-最短路径的,比起1-最短路径来说增加了点复杂度,但总体架构不变。这段代码将原有ICTCLAS的70多行求解路径代码缩短到了40多行。

小结
1)N-最短路径的求解比较复杂,本文先从求解1-最短路径着手,说明SharpICTCLAS是如何计算的,在下篇文章中将推广到N-最短路径。

2)1-最短路径并不意味着只有一条最短路径,而是路径最短的若干条路径。就如本文案例所示,1-最短路径算法最终求得了3条路径,它们的长度都是5,因此都是最短路径。

6.
http://www.cnblogs.com/zhenyulu/articles/672442.html

SharpICTCLAS分词系统简介(5)NShortPath-2
在了解了1-最短路径的计算方式后,我们看看N-最短路径的计算。

N-最短路径的计算方式与1-最短路径基本相同,只是在记录所有可达路径时,要保留最短的前N个结果。让我们仍然以上篇文章的案例来看看如何实现N-最短路径的运算。

1、数据表示
这里我们仍然沿用前文例子,对下图求N-最短路径,每条边的权重已经在图中标注出来了。



(图一)

2、运算过程
仍然象1-最短路径一样,计算出每个结点上可达N-最短路的PreNode。我们这里以2-最短路径为例:

1)首先计算出每个结点上所有可达路径的可能路径长度并按从小到大排序。

2)根据排序结果取前2种路径长度并分别记录进各结点的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。

3、具体实现
在具体实现上述算法时,首先要求得所有可能路径的长度,这在SharpICTCLAS中是通过一个EnQueueCurNodeEdges方法实现的,上篇文章给出了它的简化版本的代码,这里将完整的求N-最短路径的EnQueueCurNodeEdges方法代码放上来:

Copy Code程序
//====================================================================
// 将所有到当前结点(nCurNode)可能的边根据eWeight排序并压入队列
//====================================================================
private static void EnQueueCurNodeEdges(ref CQueue queWork, int nCurNode)
{
int nPreNode;
double eWeight;
ChainItem pEdgeList;

queWork.Clear();
pEdgeList = m_apCost.GetFirstElementOfCol(nCurNode);

// Get all the edges
while (pEdgeList != null && pEdgeList.col == nCurNode)
{
nPreNode = pEdgeList.row; // 很特别的命令,利用了row与col的关系
eWeight = pEdgeList.Content.eWeight; //Get the eWeight of edges

for (int i = 0; i < m_nValueKind; i++)
{
// 第一个结点,没有PreNode,直接加入队列
if (nPreNode == 0)
{
queWork.EnQueue(new QueueElement(nPreNode, i, eWeight));
break;
}

// 如果PreNode的Weight == Predefine.INFINITE_VALUE,则没有必要继续下去了
if (m_pWeight[nPreNode - 1][i] == Predefine.INFINITE_VALUE)
break;

queWork.EnQueue(new QueueElement(nPreNode, i, eWeight + m_pWeight[nPreNode - 1][i]));
}
pEdgeList = pEdgeList.next;
}
}
这里的m_nValueKind就是你希望N-最短路径保留几种路径的结果。

当m_nValueKind=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,
4、求解N-最短路径
N-最短路径的最终输出与上篇文章完全一致,仍然是借助堆栈完成的。只不过根据index的取值的不同,分多次完成压栈与出栈的操作而已。此处就不再重复,感兴趣的可以再看看上一篇文章。

 

小结
1)N-最短路径中用来记录PreNode的坐标由前文求“1-最短路径”时的一个数(ParentNode值)变为2个数(ParentNode值以及index值)。

2)N-最短路径并不意味着求得得路径只有N条。

3)文中只演示了2-最短路径,但可以推广到N-最短路径。程序求得的3-最短路径中,最长的路径为:(0, 1, 3, 4, 6)与(0, 1, 2, 3, 4, 6),它们的长度都是7。

7.
http://www.cnblogs.com/zhenyulu/articles/673650.html

SharpICTCLAS分词系统简介(6)Segment
DynamicArray与NShortPath是ICTCLAS中的基础类,本人在完成了基础改造工作后,就着手开始对Segment分词进行移植与改造。SharpICTCLAS中的改造主要体现在以下几方面:

1)合并不同类中的部分代码

原有ICTCLAS中使用了SegGraph与Segment两个类完成分词过程,SegGraph类负责完成原子分词与segGraph的生成,而Segment类负责BiSegGraph的生成和NShortPath优化,而最终的人名、地名识别以及Optimum优化又分散在了Segment类与WordSegment类中。

SharpICTCLAS将原有SegGraph类与Segment合二为一,因为它们所作的工作仅仅是分词中的几个步骤而已。而WordSegment类中基本保留了原有内容,因为这个类更多的做一些外围工作。

2)改造了程序中用到的部分数据结构

原有ICTCLAS大量使用了数组与二维数组,由于数组的固有缺陷使得我们随处可以看到如此这般的数组定义:

m_pWordSeg = new PWORD_RESULT[MAX_SEGMENT_NUM];

由于不知道最终会分成几个词,所以定义数组时只能用最大的容量 MAX_SEGMENT_NUM 进行预设,所以一旦存在某些异常数据就会造成“溢出”错误。

而SharpICTCLAS中大量使用了 List 的方式记录结果 ,范型的List首先可以确保结果集的数量可以动态调整而不用事先定义,另外每个结果的数组长度也可各不相同。

再有的改造就是在Segment类中使用了链表结构处理结果,这大大简化了原有ICTCLAS中的数组结构带来的种种问题。

3)大量使用了静态方法

由于某些过程的调用根本不需要建立对象,这些过程仅仅完成例行计算而已,因此将这些方法声明为静态方法更合适,何况静态方法的调用效率比实例方法高。因此本人在将ICTCLAS移植到C#平台上时,将尽可能的方法定义成静态方法。

下面我就说说SharpICTCLAS中Segment类的一些主要内容:

1、主体部分
比较典型的一个运算过程可以参考BiSegment方法,代码(经过简化)如下:

Copy CodeSegment类的BiSegment方法
public int BiSegment(string sSentence, double smoothPara, int nKind)
{
WordResult[] tmpResult;
WordLinkedArray linkedArray;
m_pWordSeg = new List();
m_graphOptimum = new RowFirstDynamicArray();

//---原子分词
atomSegment = AtomSegment(sSentence);

//---检索词库,加入所有可能分词方案并存入链表结构
segGraph = GenerateWordNet(atomSegment, coreDict);

//---检索所有可能的两两组合
biGraphResult = BiGraphGenerate(segGraph, smoothPara, biDict, coreDict);

//---N 最短路径计算出多个分词方案
NShortPath.Calculate(biGraphResult, nKind);
List spResult = NShortPath.GetNPaths(Predefine.MAX_SEGMENT_NUM);

//---对结果进行优化,例如合并日期等工作
for (int i = 0; i < spResult.Count; i++)
{
linkedArray = BiPath2LinkedArray(spResult[i], segGraph, atomSegment);
tmpResult = GenerateWord(spResult[i], linkedArray, m_graphOptimum);

if (tmpResult != null)
m_pWordSeg.Add(tmpResult);
}

return m_pWordSeg.Count;
}
从上面代码可以看出,已经将原有ICTCLAS的原子分词功能合并入Segment类了。

就拿“他在1月份大会上说的确实在理”这句话来说,上面几个步骤得到的中间结果如下:

Copy Code程序
//==== 原始句子:

他在1月份大会上说的确实在理


//==== 原子切分:

始##始, 他, 在, 1, 月, 份, 大, 会, 上, 说, 的, 确, 实, 在, 理, 末##末,


//==== 生成 segGraph:

row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 2, eWeight: 19823.00, nPOS: 0, sWord:他
row: 2, col: 3, eWeight: 78484.00, nPOS: 0, sWord:在
row: 3, col: 4, eWeight: 0.00, nPOS: -27904, sWord:未##数
row: 4, col: 5, eWeight: 1900.00, nPOS: 0, sWord:月
row: 4, col: 6, eWeight: 11.00, nPOS: 28160, sWord:月份
row: 5, col: 6, eWeight: 1234.00, nPOS: 0, sWord:份
row: 6, col: 7, eWeight: 14536.00, nPOS: 0, sWord:大
row: 6, col: 8, eWeight: 1333.00, nPOS: 28160, sWord:大会
row: 7, col: 8, eWeight: 6136.00, nPOS: 0, sWord:会
row: 7, col: 9, eWeight: 469.00, nPOS: 0, sWord:会上
row: 8, col: 9, eWeight: 23706.00, nPOS: 0, sWord:上
row: 9, col: 10, eWeight: 17649.00, nPOS: 0, sWord:说
row: 10, col: 11, eWeight: 358156.00, nPOS: 0, sWord:的
row: 10, col: 12, eWeight: 210.00, nPOS: 25600, sWord:的确
row: 11, col: 12, eWeight: 181.00, nPOS: 0, sWord:确
row: 11, col: 13, eWeight: 361.00, nPOS: 0, sWord:确实
row: 12, col: 13, eWeight: 357.00, nPOS: 0, sWord:实
row: 12, col: 14, eWeight: 295.00, nPOS: 0, sWord:实在
row: 13, col: 14, eWeight: 78484.00, nPOS: 0, sWord:在
row: 13, col: 15, eWeight: 3.00, nPOS: 24832, sWord:在理
row: 14, col: 15, eWeight: 129.00, nPOS: 0, sWord:理
row: 15, col: 16, eWeight:2079997.00, nPOS: 4, sWord:末##末


//==== 生成 biSegGraph:

row: 0, col: 1, eWeight: 3.37, nPOS: 1, sWord:始##始@他
row: 1, col: 2, eWeight: 3.37, nPOS: 0, sWord:他@在
row: 2, col: 3, eWeight: 3.74, nPOS: 0, sWord:在@未##数
row: 3, col: 4, eWeight: -27898.79, nPOS: -27904, sWord:未##数@月
row: 3, col: 5, eWeight: -27898.75, nPOS: -27904, sWord:未##数@月份
row: 4, col: 6, eWeight: 9.33, nPOS: 0, sWord:月@份
row: 5, col: 7, eWeight: 13.83, nPOS: 28160, sWord:月份@大
row: 6, col: 7, eWeight: 9.76, nPOS: 0, sWord:份@大
row: 5, col: 8, eWeight: 13.83, nPOS: 28160, sWord:月份@大会
row: 6, col: 8, eWeight: 9.76, nPOS: 0, sWord:份@大会
row: 7, col: 9, eWeight: 7.30, nPOS: 0, sWord:大@会
row: 7, col: 10, eWeight: 7.30, nPOS: 0, sWord:大@会上
row: 8, col: 11, eWeight: 2.11, nPOS: 28160, sWord:大会@上
row: 9, col: 11, eWeight: 8.16, nPOS: 0, sWord:会@上
row: 10, col: 12, eWeight: 3.42, nPOS: 0, sWord:会上@说
row: 11, col: 12, eWeight: 4.07, nPOS: 0, sWord:上@说
row: 12, col: 13, eWeight: 4.05, nPOS: 0, sWord:说@的
row: 12, col: 14, eWeight: 7.11, nPOS: 0, sWord:说@的确
row: 13, col: 15, eWeight: 4.10, nPOS: 0, sWord:的@确
row: 13, col: 16, eWeight: 4.10, nPOS: 0, sWord:的@确实
row: 14, col: 17, eWeight: 11.49, nPOS: 25600, sWord:的确@实
row: 15, col: 17, eWeight: 11.63, nPOS: 0, sWord:确@实
row: 14, col: 18, eWeight: 11.49, nPOS: 25600, sWord:的确@实在
row: 15, col: 18, eWeight: 11.63, nPOS: 0, sWord:确@实在
row: 16, col: 19, eWeight: 3.92, nPOS: 0, sWord:确实@在
row: 17, col: 19, eWeight: 10.98, nPOS: 0, sWord:实@在
row: 16, col: 20, eWeight: 10.97, nPOS: 0, sWord:确实@在理
row: 17, col: 20, eWeight: 10.98, nPOS: 0, sWord:实@在理
row: 18, col: 21, eWeight: 11.17, nPOS: 0, sWord:实在@理
row: 19, col: 21, eWeight: 5.62, nPOS: 0, sWord:在@理
row: 20, col: 22, eWeight: 14.30, nPOS: 24832, sWord:在理@末##末
row: 21, col: 22, eWeight: 11.95, nPOS: 0, sWord:理@末##末


//==== NShortPath 初步切分的到的 N 个结果:

始##始, 他, 在, 1, 月份, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1, 月份, 大会, 上, 说, 的, 确实, 在理, 末##末,
始##始, 他, 在, 1, 月份, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1, 月, 份, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1, 月份, 大, 会上, 说, 的, 确实, 在理, 末##末,


//==== 经过数字、日期合并等策略处理后的 N 个结果:

始##始, 他, 在, 1月份, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1月份, 大会, 上, 说, 的, 确实, 在理, 末##末,
始##始, 他, 在, 1月份, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1月, 份, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1月份, 大, 会上, 说, 的, 确实, 在理, 末##末,

这些内容在前面的文章中已经涉及过,我这里主要说说SharpICTCLAS中两处地方的内容,分别是原子分词以及数字日期合并策略。

2、原子分词
原子分词看起来应当是程序中最简单的部分,无非是将汉字逐一分开。但是也是最值得改进的地方。SharpICTCLAS目前仍然沿用了原有ICTCLAS的算法并做了微小调整。但我对于 这种原子分词方法不太满意,如果有机会,可以考虑使用一系列正则表达式将某些“原子”词单独摘出来。比如“甲子”、“乙亥”等年份信息属于原子信息,还有URL、Email等都可以预先进行原子识别,这可以大大简化后续工作。因此日后可以考虑这方面的处理。

3、对结果的处理
ICTCLAS与SharpICTCLAS都通过NShortPath计算最短路径并将结果以数组的方式进行输出,数组仅仅记录了分词的位置,我们还需要通过一些后续处理手段将这些数组转换成“分词”结果。

原有ICTCLAS的实现如下:

Copy CodeICTCLAS对NShortPath结果的处理
while (i < m_nSegmentCount)
{
BiPath2UniPath(nSegRoute[i]); //Path convert to unipath
GenerateWord(nSegRoute, i); //Gernerate word according the Segmentation route
i++;
}
其中这个BiPath2UniPath方法做的工作可以用如下案例说明:

将BiPath转换为UniPath
例如“他说的确实在理”

BiPath:(0, 1, 2, 3, 6, 9, 11, 12)
0 1 2 3 4 5 6 7 8 9 10 11 12
始##始 他 说 的 的确 确 确实 实 实在 在 在理 理 末##末

经过转换后
UniPath:(0, 1, 2, 3, 4, 6, 7, 8)
0 1 2 3 4 5 6 7 8
始##始 他 说 的 确 实 在 理 末##末

由此可见UniPath记录了针对原子分词的分割位置。而后面的GenerateWord方法又针对这个数组去做合并及优化工作。

本人在SharpICTCLAS的改造过程中发现在这里数组的表述方式给后续工作带来了很大的困难(可以考虑一下,让你合并链表中两个相邻结点简单呢还是数组中两个相邻结点简单?),所以我决定在SharpICTCLAS中将BiPath转换为链表结构供后续使用,实践证明简化了不少工作。

这点在BiSegment方法中有所体现,如下:

linkedArray = BiPath2LinkedArray(spResult[i], segGraph, atomSegment);

这样改造后,还使得原有ICTCLAS中 int *m_npWordPosMapTable; 不再需要,与其相关的代码也可以一并删除了。

4、日期、数字合并策略
数字、日期等合并以及拆分策略的实施是在GenerateWord方法中实现的,原有ICTCLAS中,该方法是一个超级庞大的方法,里面有不下6、7层的if嵌套、while嵌套等,分析其内部功能的工作异常复杂。经过一番研究后,我将其中的主要功能部分提取出来,改用了“管道”方式进行处理,简化了代码复杂度。但对于部分逻辑结构异常复杂的日期时间识别功能,SharpICTCLAS中仍然保留了绝大多数原始内容。

让我们先来看看原始ICTCLAS的GenerateWord方法(超级长的一个方法):

Copy CodeICTCLAS中GenerateWord方法
//Generate Word according the segmentation route
bool CSegment::GenerateWord(int **nSegRoute, int nIndex)
{
unsigned int i = 0, k = 0;
int j, nStartVertex, nEndVertex, nPOS;
char sAtom[WORD_MAXLENGTH], sNumCandidate[100], sCurWord[100];
ELEMENT_TYPE fValue;
while (nSegRoute[nIndex][i] != - 1 && nSegRoute[nIndex][i + 1] != - 1 &&
nSegRoute[nIndex][i] < nSegRoute[nIndex][i + 1])
{
nStartVertex = nSegRoute[nIndex][i];
j = nStartVertex; //Set the start vertex
nEndVertex = nSegRoute[nIndex][i + 1]; //Set the end vertex
nPOS = 0;
m_graphSeg.m_segGraph.GetElement(nStartVertex, nEndVertex, &fValue, &nPOS);
sAtom[0] = 0;
while (j < nEndVertex)
{
//Generate the word according the segmentation route
strcat(sAtom, m_graphSeg.m_sAtom[j]);
j++;
}
m_pWordSeg[nIndex][k].sWord[0] = 0; //Init the result ending
strcpy(sNumCandidate, sAtom);
while (sAtom[0] != 0 && (IsAllNum((unsigned char*)sNumCandidate) ||
IsAllChineseNum(sNumCandidate)))
{
//Merge all seperate continue num into one number
//sAtom[0]!=0: add in 2002-5-9
strcpy(m_pWordSeg[nIndex][k].sWord, sNumCandidate);
//Save them in the result segmentation
i++; //Skip to next atom now
sAtom[0] = 0;

while (j < nSegRoute[nIndex][i + 1])
{
//Generate the word according the segmentation route
strcat(sAtom, m_graphSeg.m_sAtom[j]);
j++;
}
strcat(sNumCandidate, sAtom);
}
unsigned int nLen = strlen(m_pWordSeg[nIndex][k].sWord);
if (nLen == 4 && CC_Find("第上成±—+∶·./",
m_pWordSeg[nIndex][k].sWord) || nLen == 1 && strchr("+-./",
m_pWordSeg[nIndex][k].sWord[0]))
{
//Only one word
strcpy(sCurWord, m_pWordSeg[nIndex][k].sWord); //Record current word
i--;
}
else if (m_pWordSeg[nIndex][k].sWord[0] == 0)
//Have never entering the while loop
{
strcpy(m_pWordSeg[nIndex][k].sWord, sAtom);
//Save them in the result segmentation
strcpy(sCurWord, sAtom); //Record current word
}
else
{
//It is a num
if (strcmp("--", m_pWordSeg[nIndex][k].sWord) == 0 || strcmp("—",
m_pWordSeg[nIndex][k].sWord) == 0 || m_pWordSeg[nIndex][k].sWord[0] ==
'-' && m_pWordSeg[nIndex][k].sWord[1] == 0)
//The delimiter "--"
{
nPOS = 30464; //'w'*256;Set the POS with 'w'
i--; //Not num, back to previous word
}
else
{
//Adding time suffix

char sInitChar[3];
unsigned int nCharIndex = 0; //Get first char
sInitChar[nCharIndex] = m_pWordSeg[nIndex][k].sWord[nCharIndex];
if (sInitChar[nCharIndex] < 0)
{
nCharIndex += 1;
sInitChar[nCharIndex] = m_pWordSeg[nIndex][k].sWord[nCharIndex];
}
nCharIndex += 1;
sInitChar[nCharIndex] = '\0';
if (k > 0 && (abs(m_pWordSeg[nIndex][k - 1].nHandle) == 27904 || abs
(m_pWordSeg[nIndex][k - 1].nHandle) == 29696) && (strcmp(sInitChar,
"—") == 0 || sInitChar[0] == '-') && (strlen
(m_pWordSeg[nIndex][k].sWord) > nCharIndex))
{
//3-4月 //27904='m'*256
//Split the sInitChar from the original word
strcpy(m_pWordSeg[nIndex][k + 1].sWord, m_pWordSeg[nIndex][k].sWord +
nCharIndex);
m_pWordSeg[nIndex][k + 1].dValue = m_pWordSeg[nIndex][k].dValue;
m_pWordSeg[nIndex][k + 1].nHandle = 27904;
m_pWordSeg[nIndex][k].sWord[nCharIndex] = 0;
m_pWordSeg[nIndex][k].dValue = 0;
m_pWordSeg[nIndex][k].nHandle = 30464; //'w'*256;
m_graphOptimum.SetElement(nStartVertex, nStartVertex + 1,
m_pWordSeg[nIndex][k].dValue, m_pWordSeg[nIndex][k].nHandle,
m_pWordSeg[nIndex][k].sWord);
nStartVertex += 1;
k += 1;
}
nLen = strlen(m_pWordSeg[nIndex][k].sWord);
if ((strlen(sAtom) == 2 && CC_Find("月日时分秒", sAtom)) || strcmp
(sAtom, "月份") == 0)
{
//2001年
strcat(m_pWordSeg[nIndex][k].sWord, sAtom);
strcpy(sCurWord, "未##时");
nPOS = - 29696; //'t'*256;//Set the POS with 'm'
}
else if (strcmp(sAtom, "年") == 0)
{
if (IsYearTime(m_pWordSeg[nIndex][k].sWord))
//strncmp(sAtom,"年",2)==0&&
{
//1998年,
strcat(m_pWordSeg[nIndex][k].sWord, sAtom);
strcpy(sCurWord, "未##时");
nPOS = - 29696; //Set the POS with 't'
}
else
{
strcpy(sCurWord, "未##数");
nPOS = - 27904; //Set the POS with 'm'
i--; //Can not be a time word
}
}
else
{
//早晨/t 五点/t
if (strcmp(m_pWordSeg[nIndex][k].sWord + strlen
(m_pWordSeg[nIndex][k].sWord) - 2, "点") == 0)
{
strcpy(sCurWord, "未##时");
nPOS = - 29696; //Set the POS with 't'
}
else
{
if (!CC_Find("∶·./", m_pWordSeg[nIndex][k].sWord + nLen - 2) &&
m_pWordSeg[nIndex][k].sWord[nLen - 1] != '.' &&
m_pWordSeg[nIndex][k].sWord[nLen - 1] != '/')
{
strcpy(sCurWord, "未##数");
nPOS = - 27904; //'m'*256;Set the POS with 'm'
}
else if (nLen > strlen(sInitChar))
{
//Get rid of . example 1.
if (m_pWordSeg[nIndex][k].sWord[nLen - 1] == '.' ||
m_pWordSeg[nIndex][k].sWord[nLen - 1] == '/')
m_pWordSeg[nIndex][k].sWord[nLen - 1] = 0;
else
m_pWordSeg[nIndex][k].sWord[nLen - 2] = 0;
strcpy(sCurWord, "未##数");
nPOS = - 27904; //'m'*256;Set the POS with 'm'
i--;
}
}
i--; //Not num, back to previous word
}
}
fValue = 0;
nEndVertex = nSegRoute[nIndex][i + 1]; //Ending POS changed to latter
}
m_pWordSeg[nIndex][k].nHandle = nPOS; //Get the POS of current word
m_pWordSeg[nIndex][k].dValue = fValue;
//(int)(MAX_FREQUENCE*exp(-fValue));//Return the frequency of current word
m_graphOptimum.SetElement(nStartVertex, nEndVertex, fValue, nPOS, sCurWord);
//Generate optimum segmentation graph according the segmentation result
i++; //Skip to next atom
k++; //Accept next word
}
m_pWordSeg[nIndex][k].sWord[0] = 0;
m_pWordSeg[nIndex][k].nHandle = - 1; //Set ending
return true;
}
SharpICTCLAS中,对这段超长代码进行了功能剥离,采用一种“流水线”式的处理流程,不同工作部分负责处理不同功能,而将处理结果节节传递(很象设计模式中的职责链模式),这样使得整体结构变的清晰起来。SharpICTCLAS中GenerateWord方法定义如下:

Copy CodeSharpICTCLAS中的GenerateWord方法
private static WordResult[] GenerateWord(int[] uniPath, WordLinkedArray linkedArray,
RowFirstDynamicArray m_graphOptimum)
{
if (linkedArray.Count == 0)
return null;

//--------------------------------------------------------------------
//Merge all seperate continue num into one number
MergeContinueNumIntoOne(ref linkedArray);

//--------------------------------------------------------------------
//The delimiter "--"
ChangeDelimiterPOS(ref linkedArray);

//--------------------------------------------------------------------
//如果前一个词是数字,当前词以“-”或“-”开始,并且不止这一个字符,
//那么将此“-”符号从当前词中分离出来。
//例如 “3 / -4 / 月”需要拆分成“3 / - / 4 / 月”
SplitMiddleSlashFromDigitalWords(ref linkedArray);

//--------------------------------------------------------------------
//1、如果当前词是数字,下一个词是“月、日、时、分、秒、月份”中的一个,则合并,且当前词词性是时间
//2、如果当前词是可以作为年份的数字,下一个词是“年”,则合并,词性为时间,否则为数字。
//3、如果最后一个汉字是"点" ,则认为当前数字是时间
//4、如果当前串最后一个汉字不是"∶·./"和半角的'.''/',那么是数
//5、当前串最后一个汉字是"∶·./"和半角的'.''/',且长度大于1,那么去掉最后一个字符。例如"1."
CheckDateElements(ref linkedArray);

//--------------------------------------------------------------------
//遍历链表输出结果
WordResult[] result = new WordResult[linkedArray.Count];

WordNode pCur = linkedArray.first;
int i = 0;
while (pCur != null)
{
WordResult item = new WordResult();
item.sWord = pCur.theWord.sWord;
item.nPOS = pCur.theWord.nPOS;
item.dValue = pCur.theWord.dValue;
result[i] = item;

m_graphOptimum.SetElement(pCur.row, pCur.col, new ChainContent(item.dValue, item.nPOS, pCur.sWordInSegGraph));

pCur = pCur.next;
i++;
}

return result;
}
从中可以看到linkedArray作为“绣球”在多个处理流程中被传递和加工,最终输出相应的结果。只是CheckDateElement方法内容涉及到的东西太多,因此目前看来其实现仍有些臃肿,日后可以进一步进行功能的剥离。

 

小结
1)Segment类是SharpICTCLAS中最大的一个类,实现了分词过程中一些关键的步骤。

2)Segment类对原有ICTCLAS中的代码做了大量修改,力争通过新的数据结构简化原有操作。

3)Segment中定义了部分静态方法以提高调用效率。


# re: SharpICTCLAS分词系统简介(6)Segment 2007-03-31 20:37 jory
目前版本好象只能对一段话进行测试,如果字符串中包含“\r\n”的话就会出现
数组越界的异常
比如
result = sample.Segment(@"他说的确实在理
");

就会出错,这样就不能对整篇文章进行分词了

# re: SharpICTCLAS分词系统简介(6)Segment 2007-04-01 21:24 吕震宇
@jory

目前这应当算是小问题,因为完全可以在一篇文章预处理时去掉这些回车符号。

我还发现了一些更麻烦的问题,主要因为词性标注部分的代码存在问题(应当是从ICTCLAS)就存在的问题,我没经修改就直接拿过来了,主要表现在如果某个汉字没有词性,则在词性标注时会出现异常。例如:“这些是永远也没有现成的答桉的”其中“答案”写错了,当对这个有错别字的句子分词时将出现错误。

另外,ICTCLAS在对地名识别时也存在问题,在Span类的PlaceRecognize方法中,nStart与nEnd在某些时候会计算错误,测试版的SharpICTCLAS也存在这个问题。例如“明定陵是明十三陵中第十座陵墓”在分词时会因为这个问题导致触发异常。

我现在对测试版的代码做了些调整,暂时解决了这些问题,但日后仍然有必要对Span类的代码进行大幅度重构。

8.
http://www.cnblogs.com/zhenyulu/articles/675217.html

SharpICTCLAS分词系统简介(7)OptimumSegment
上一篇文章说到经过NShortPath计算后,我们得到了数个候选分词方案,那么这么多个候选分词方案是如何最终成为一个分词结果的呢?其实这个过程是靠OptimumSegment完成的。SharpICTCLAS与ICTCLAS的OptimumSegment过程基本一样没有太大的变化。

1、OptimumSegment的运算过程
经过NShortPath处理后的多个结果首先会经过日期合并策略的处理,这就是前文说的GenerateWord方法完成的功能。在GenerateWord方法中可以看到如下命令:

m_graphOptimum.SetElement(pCur.row, pCur.col, ......);

它的功能就是将所有得到的多个分词方案合并归入一个 m_graphOptimum 属性,如下面的NShortPath运算结果,经过归并后,在 m_graphOptimum 属性中将包含所有红色词。

Copy Code经过NShortPath处理后的初步分词结果
//==== 原始句子:

王晓平在1月份滦南大会上说的确实在理

//==== NShortPath 初步切分的到的 N 个结果:

始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末,
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末,
始##始, 王, 晓, 平, 在, 1, 月, 份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,


//==== 经过数字、日期合并等策略处理后的 N 个结果:

始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末,
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末,
始##始, 王, 晓, 平, 在, 1月, 份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,

紧接着对归并后的 m_graphOptimum 进行人名与地名的识别,找出所有可能的人名、地名方案,经过人名、地名识别后的 m_graphOptimum 如下:

Copy Code加入人名、地名识别
//==== 加入对姓名、翻译人名以及地名的识别:

row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 2, eWeight: 218.00, nPOS: 0, sWord:王
row: 1, col: 4, eWeight: 10.86, nPOS: -28274, sWord:未##人
row: 2, col: 3, eWeight: 9.00, nPOS: 0, sWord:晓
row: 2, col: 4, eWeight: 13.27, nPOS: -28274, sWord:未##人
row: 3, col: 4, eWeight: 271.00, nPOS: 0, sWord:平
row: 4, col: 5, eWeight: 78484.00, nPOS: 0, sWord:在
row: 5, col: 7, eWeight: 0.00, nPOS: -29696, sWord:未##时
row: 5, col: 8, eWeight: 0.00, nPOS: -29696, sWord:未##时
row: 7, col: 8, eWeight: 1234.00, nPOS: 0, sWord:份
row: 8, col: 9, eWeight: 1.00, nPOS: 27136, sWord:滦
row: 8, col: 10, eWeight: 20.37, nPOS: -28275, sWord:未##地
row: 9, col: 10, eWeight: 813.00, nPOS: 0, sWord:南
row: 10, col: 11, eWeight: 14536.00, nPOS: 0, sWord:大
row: 10, col: 12, eWeight: 1333.00, nPOS: 28160, sWord:大会
row: 11, col: 13, eWeight: 469.00, nPOS: 0, sWord:会上
row: 12, col: 13, eWeight: 23706.00, nPOS: -27904, sWord:未##数
row: 13, col: 14, eWeight: 17649.00, nPOS: 0, sWord:说
row: 14, col: 15, eWeight: 358156.00, nPOS: 0, sWord:的
row: 15, col: 17, eWeight: 361.00, nPOS: 0, sWord:确实
row: 17, col: 18, eWeight: 78484.00, nPOS: 0, sWord:在
row: 17, col: 19, eWeight: 3.00, nPOS: 24832, sWord:在理
row: 18, col: 19, eWeight: 129.00, nPOS: 0, sWord:理
row: 19, col: 20, eWeight:2079997.00, nPOS: 4, sWord:末##末

到此为止, m_graphOptimum 包含了所有最终分词结果中可能包含的元素(人名、地名以及NShortPath筛选后所有可能组词方案),Segment类对这个 m_graphOptimum 再次使用NShortPath,并计算出最优结果作为最终的分词方案。

整个过程可从WordSegment类的Segment方法看出,SharpICTCLAS中该方法定义如下(经过简化):

Copy Code分词主程序
public List Segment(string sentence, int nKind)
{
m_pNewSentence = Predefine.SENTENCE_BEGIN + sentence + Predefine.SENTENCE_END;
//---初步分词
int nResultCount = m_Seg.BiSegment(m_pNewSentence, m_dSmoothingPara, nKind);

//---人名、地名识别
for (int i = 0; i < nResultCount; i++)
{
m_uPerson.Recognition(m_Seg.m_pWordSeg[i], m_Seg.m_graphOptimum, ......);
m_uTransPerson.Recognition(m_Seg.m_pWordSeg[i], m_Seg.m_graphOptimum, ......);
m_uPlace.Recognition(m_Seg.m_pWordSeg[i], m_Seg.m_graphOptimum, ......);
}

//---最终优化
m_Seg.BiOptimumSegment(1, m_dSmoothingPara);

//---词性标注
for (int i = 0; i < m_Seg.m_pWordSeg.Count; i++)
m_POSTagger.POSTagging(m_Seg.m_pWordSeg[i], m_dictCore, m_dictCore);

return m_Seg.m_pWordSeg;
}
2、人名与地名的识别
ICTCLAS中人名的识别采用的是模板匹配的方法,首先对初步分词得到的多的结果计算词性,然后根据词性串对人名信息进行匹配。整个运算过程如下:

首先定义了人名匹配模板:

Copy Code人名识别模板
string[] sPatterns = { "BBCD", "BBC", "BBE", "BBZ", "BCD",
"BEE", "BE", "BG", "BXD", "BZ", "CDCD", "CD", "EE", "FB",
"Y", "XD", "" };
/*------------------------------------
The person recognition patterns set
BBCD:姓+姓+名1+名2;
BBE: 姓+姓+单名;
BBZ: 姓+姓+双名成词;
BCD: 姓+名1+名2;
BE: 姓+单名;
BEE: 姓+单名+单名;韩磊磊
BG: 姓+后缀
BXD: 姓+姓双名首字成词+双名末字
BZ: 姓+双名成词;
B: 姓
CD: 名1+名2;
EE: 单名+单名;
FB: 前缀+姓
XD: 姓双名首字成词+双名末字
Y: 姓单名成词
------------------------------------*/
然后将初步分词得到的结果进行词性标注,清理掉其它不必要的信息后进行模板匹配得到人名:

Copy Code人名识别过程
//==== 经过初步分词后的一个结果集

始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,

//==== 经过计算得到的m_nBestTag

始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
B C D M A A A A A A A A A A

//==== 经过模板匹配后识别出来的人名

王晓平
地名的识别与此类似,就不再多说。有关人名、地名识别的进一步内容可以参考:http://qxred.yculblog.com/post.1204714.html;《ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注》作者:风暴红QxRed 。

 

小结
经过NShortPath得到的多个初步分词结果被归并入 m_graphOptimum ,然后经过人名与地名识别过程将所有可能的人名、地名也放入其中,最后通过OptimumSegment方法最终得到分词结果。

9.
http://www.cnblogs.com/zhenyulu/articles/675218.html

SharpICTCLAS分词系统简介(8)其它
前文对SharpICTCLAS中的一些主要内容做了介绍,本文介绍一下SharpICTCLAS中一些其它考虑,包括事件机制以及如何使用SharpICTCLAS。

1、SharpICTCLAS中的事件
分词过程比较复杂,所以很可能有人希望能够追踪分词的过程,设置代码断点比较麻烦,因此SharpICTCLAS中提供了事件机制,可以在分词的不同阶段触发相关事件,使用者可以订阅这些事件并输出中间结果供查错使用。

事件的阶段被定义在SegmentStage枚举当中,代码如下:

Copy CodeSegmentStage程序
public enum SegmentStage
{
BeginSegment, //开始分词
AtomSegment, //原子切分
GenSegGraph, //生成SegGraph
GenBiSegGraph, //生成BiSegGraph
NShortPath, //N最短路径计算
BeforeOptimize, //对N最短路径进一步整理得到的结果
OptimumSegment, //初始OptimumSegmentGraph
PersonAndPlaceRecognition, //人名与地名识别后的OptimumSegmentGraph
BiOptimumSegment, //生成BiOptimumSegmentGraph
FinishSegment //完成分词,输出结果
}
分别对应分词过程中的10个阶段。

SharpICTCLAS中还定义了一个EventArgs,里面包含了两个元素,分别用来记录该事件元素所处的分词阶段以及该阶段的相关中间结果信息。中间结果信息使用的是string类型数据,日后可以考虑采用更复杂的表示形式输出中间结果。该事件元素定义如下:

Copy CodeSegmentEventArgs的定义
public class SegmentEventArgs : EventArgs
{
public SegmentStage Stage;
public string Info = "";

......
}
剩下的工作就是定义委派并发布事件了。由于分词过程主要集中在两个类中:WordSegment类与Segment类,而用户通常只需要与WordSegment类打交道,因此WordSegment类中转发了Segment类产生的事件。

委派的定义以及事件的定义如下(部分):

Copy Code程序
//---定义委派
public delegate void SegmentEventHandler(object sender, SegmentEventArgs e);

//---定义事件
public event SegmentEventHandler OnSegmentEvent;

//---发布事件的方法
private void SendEvents(SegmentEventArgs e)
{
if (OnSegmentEvent != null)
OnSegmentEvent(this, e);
}

//---开始分词
private void OnBeginSegment(string sentence)
{
SendEvents(new SegmentEventArgs(SegmentStage.BeginSegment, sentence));
}

......

//---结束分词
private void OnFinishSegment(List m_pWordSeg)
{
StringBuilder sb = new StringBuilder();
for (int k = 0; k < m_pWordSeg.Count; k++)
{
for (int j = 0; j < m_pWordSeg[k].Length; j++)
sb.Append(string.Format("{0} /{1} ", m_pWordSeg[k][j].sWord,
Utility.GetPOSString(m_pWordSeg[k][j].nPOS)));
sb.Append("\r\n");
}

SendEvents(new SegmentEventArgs(SegmentStage.FinishSegment, sb.ToString()));
}
有了这些事件,用户可以根据需要订阅不同的事件来获取分词的中间结果,极大方便了程序调试工作。

2、SharpICTCLAS的使用
下面是一个使用SharpICTCLAS的示例代码:

Copy CodeWordSegmentSample.cs
using System;
using System.Collections.Generic;
using System.Text;
using SharpICTCLAS;

public class WordSegmentSample
{
private int nKind = 1; //在NShortPath方法中用来决定初步切分时分成几种结果
private WordSegment wordSegment;

//=======================================================
// 构造函数,在没有指明nKind的情况下,nKind 取 1
//=======================================================
public WordSegmentSample(string dictPath) : this(dictPath, 1) { }

//=======================================================
// 构造函数
//=======================================================
public WordSegmentSample(string dictPath, int nKind)
{
this.nKind = nKind;
this.wordSegment = new WordSegment();

//---------- 订阅分词过程中的事件 ----------
wordSegment.OnSegmentEvent += new SegmentEventHandler(this.OnSegmentEventHandler);
wordSegment.InitWordSegment(dictPath);
}

//=======================================================
// 开始分词
//=======================================================
public List Segment(string sentence)
{
return wordSegment.Segment(sentence, nKind);
}

//=======================================================
// 输出分词过程中每一步的中间结果
//=======================================================
private void OnSegmentEventHandler(object sender, SegmentEventArgs e)
{
switch (e.Stage)
{
case SegmentStage.BeginSegment:
Console.WriteLine("\r\n==== 原始句子:\r\n");
Console.WriteLine(e.Info + "\r\n");
break;
case SegmentStage.AtomSegment:
Console.WriteLine("\r\n==== 原子切分:\r\n");
Console.WriteLine(e.Info);
break;
case SegmentStage.GenSegGraph:
Console.WriteLine("\r\n==== 生成 segGraph:\r\n");
Console.WriteLine(e.Info);
break;
case SegmentStage.GenBiSegGraph:
Console.WriteLine("\r\n==== 生成 biSegGraph:\r\n");
Console.WriteLine(e.Info);
break;
case SegmentStage.NShortPath:
Console.WriteLine("\r\n==== NShortPath 初步切分的到的 N 个结果:\r\n");
Console.WriteLine(e.Info);
break;
case SegmentStage.BeforeOptimize:
Console.WriteLine("\r\n==== 经过数字、日期合并等策略处理后的 N 个结果:\r\n");
Console.WriteLine(e.Info);
break;
case SegmentStage.OptimumSegment:
Console.WriteLine("\r\n==== 将 N 个结果归并入OptimumSegment:\r\n");
Console.WriteLine(e.Info);
break;
case SegmentStage.PersonAndPlaceRecognition:
Console.WriteLine("\r\n==== 加入对姓名、翻译人名以及地名的识别:\r\n");
Console.WriteLine(e.Info);
break;
case SegmentStage.BiOptimumSegment:
Console.WriteLine("\r\n==== 对加入对姓名、地名的OptimumSegment生成BiOptimumSegment:\r\n");
Console.WriteLine(e.Info);
break;
case SegmentStage.FinishSegment:
Console.WriteLine("\r\n==== 最终识别结果:\r\n");
Console.WriteLine(e.Info);
break;
}
}
}

从中我们可以看出,首先添加对SharpICTCLAS命名空间的引用,然后创建WordSegment类的一个实例。如果需要拦截分词过程中的事件的话,那么可以订阅WordSegment类的OnSegmentEvent事件,上面的代码用OnSegmentEventHandler方法订阅了事件,并且输出了所有分词Stage的中间结果。

WordSegmentSample类中的 nKind 属性是在NShortPath方法中用来决定初步切分时分成几种结果。如果不特殊指明,nKind取1,用户也可以自己定义一个1~10之间的整数(超过10,系统自动取10),数越大分词准确率越高(可以参考张华平的论文),但系统执行效率会下降。

WordSegment类的InitWordSegment方法主要用来初始化各个词典,用户在这里需要提供词典所在的目录信息,系统自动到该目录下搜索所有词典。

有了WordSegmentSample类,主程序如下:

Copy Code程序
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using SharpICTCLAS;

class Program
{
static void Main(string[] args)
{
List result;

string DictPath = Path.Combine(Environment.CurrentDirectory, "Data") +
Path.DirectorySeparatorChar;

Console.WriteLine("正在初始化字典库,请稍候...");
WordSegmentSample sample = new WordSegmentSample(DictPath, 5);

result = sample.Segment(@"王晓平在1月份滦南大会上说的确实在理");

//---------- 输出结果 ----------
//Console.WriteLine("\r\n==== 最终识别结果:\r\n");
//for (int i = 0; i < result.Count; i++)
//{
// for (int j = 0; j < result[i].Length; j++)
// Console.Write("{0} /{1} ", result[i][j].sWord, Utility.GetPOSString(result[i][j].nPOS));
// Console.WriteLine();
//}

Console.Write("按下回车键退出......");
Console.ReadLine();
}
}

内容比较简单,此处就不再多说。由于我们在WordSegmentSample中订阅了所有阶段的事件,因此程序会输出整个过程各个阶段的中间结果,也包括最终分词结果,因此上面代码中我将输出结果部分的代码注释起来了。如果没有订阅任何事件的话,可以使用注释起来的这段代码输出分词最终结果。

该程序的执行结果如下:

Copy CodeWordSegmentSample程序执行结果
正在初始化字典库,请稍候...

//==== 原始句子:

王晓平在1月份滦南大会上说的确实在理


//==== 原子切分:

始##始, 王, 晓, 平, 在, 1, 月, 份, 滦, 南, 大, 会, 上, 说, 的, 确, 实, 在, 理, 末##末,


//==== 生成 segGraph:

row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 2, eWeight: 218.00, nPOS: 0, sWord:王
row: 2, col: 3, eWeight: 9.00, nPOS: 0, sWord:晓
row: 3, col: 4, eWeight: 271.00, nPOS: 0, sWord:平
row: 4, col: 5, eWeight: 78484.00, nPOS: 0, sWord:在
row: 5, col: 6, eWeight: 0.00, nPOS: -27904, sWord:未##数
row: 6, col: 7, eWeight: 1900.00, nPOS: 0, sWord:月
row: 6, col: 8, eWeight: 11.00, nPOS: 28160, sWord:月份
row: 7, col: 8, eWeight: 1234.00, nPOS: 0, sWord:份
row: 8, col: 9, eWeight: 1.00, nPOS: 27136, sWord:滦
row: 9, col: 10, eWeight: 813.00, nPOS: 0, sWord:南
row: 10, col: 11, eWeight: 14536.00, nPOS: 0, sWord:大
row: 10, col: 12, eWeight: 1333.00, nPOS: 28160, sWord:大会
row: 11, col: 12, eWeight: 6136.00, nPOS: 0, sWord:会
row: 11, col: 13, eWeight: 469.00, nPOS: 0, sWord:会上
row: 12, col: 13, eWeight: 23706.00, nPOS: 0, sWord:上
row: 13, col: 14, eWeight: 17649.00, nPOS: 0, sWord:说
row: 14, col: 15, eWeight: 358156.00, nPOS: 0, sWord:的
row: 14, col: 16, eWeight: 210.00, nPOS: 25600, sWord:的确
row: 15, col: 16, eWeight: 181.00, nPOS: 0, sWord:确
row: 15, col: 17, eWeight: 361.00, nPOS: 0, sWord:确实
row: 16, col: 17, eWeight: 357.00, nPOS: 0, sWord:实
row: 16, col: 18, eWeight: 295.00, nPOS: 0, sWord:实在
row: 17, col: 18, eWeight: 78484.00, nPOS: 0, sWord:在
row: 17, col: 19, eWeight: 3.00, nPOS: 24832, sWord:在理
row: 18, col: 19, eWeight: 129.00, nPOS: 0, sWord:理
row: 19, col: 20, eWeight:2079997.00, nPOS: 4, sWord:末##末


//==== 生成 biSegGraph:

row: 0, col: 1, eWeight: 4.18, nPOS: 1, sWord:始##始@王
row: 1, col: 2, eWeight: 11.46, nPOS: 0, sWord:王@晓
row: 2, col: 3, eWeight: 13.93, nPOS: 0, sWord:晓@平
row: 3, col: 4, eWeight: 11.25, nPOS: 0, sWord:平@在
row: 4, col: 5, eWeight: 3.74, nPOS: 0, sWord:在@未##数
row: 5, col: 6, eWeight: -27898.79, nPOS: -27904, sWord:未##数@月
row: 5, col: 7, eWeight: -27898.75, nPOS: -27904, sWord:未##数@月份
row: 6, col: 8, eWeight: 9.33, nPOS: 0, sWord:月@份
row: 7, col: 9, eWeight: 13.83, nPOS: 28160, sWord:月份@滦
row: 8, col: 9, eWeight: 9.76, nPOS: 0, sWord:份@滦
row: 9, col: 10, eWeight: 14.46, nPOS: 27136, sWord:滦@南
row: 10, col: 11, eWeight: 5.19, nPOS: 0, sWord:南@大
row: 10, col: 12, eWeight: 10.17, nPOS: 0, sWord:南@大会
row: 11, col: 13, eWeight: 7.30, nPOS: 0, sWord:大@会
row: 11, col: 14, eWeight: 7.30, nPOS: 0, sWord:大@会上
row: 12, col: 15, eWeight: 2.11, nPOS: 28160, sWord:大会@上
row: 13, col: 15, eWeight: 8.16, nPOS: 0, sWord:会@上
row: 14, col: 16, eWeight: 3.42, nPOS: 0, sWord:会上@说
row: 15, col: 16, eWeight: 4.07, nPOS: 0, sWord:上@说
row: 16, col: 17, eWeight: 4.05, nPOS: 0, sWord:说@的
row: 16, col: 18, eWeight: 7.11, nPOS: 0, sWord:说@的确
row: 17, col: 19, eWeight: 4.10, nPOS: 0, sWord:的@确
row: 17, col: 20, eWeight: 4.10, nPOS: 0, sWord:的@确实
row: 18, col: 21, eWeight: 11.49, nPOS: 25600, sWord:的确@实
row: 19, col: 21, eWeight: 11.63, nPOS: 0, sWord:确@实
row: 18, col: 22, eWeight: 11.49, nPOS: 25600, sWord:的确@实在
row: 19, col: 22, eWeight: 11.63, nPOS: 0, sWord:确@实在
row: 20, col: 23, eWeight: 3.92, nPOS: 0, sWord:确实@在
row: 21, col: 23, eWeight: 10.98, nPOS: 0, sWord:实@在
row: 20, col: 24, eWeight: 10.97, nPOS: 0, sWord:确实@在理
row: 21, col: 24, eWeight: 10.98, nPOS: 0, sWord:实@在理
row: 22, col: 25, eWeight: 11.17, nPOS: 0, sWord:实在@理
row: 23, col: 25, eWeight: 5.62, nPOS: 0, sWord:在@理
row: 24, col: 26, eWeight: 14.30, nPOS: 24832, sWord:在理@末##末
row: 25, col: 26, eWeight: 11.95, nPOS: 0, sWord:理@末##末


//==== NShortPath 初步切分的到的 N 个结果:

始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末,
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末,
始##始, 王, 晓, 平, 在, 1, 月, 份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,


//==== 经过数字、日期合并等策略处理后的 N 个结果:

始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末,
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末,
始##始, 王, 晓, 平, 在, 1月, 份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末,


//==== 加入对姓名、翻译人名以及地名的识别:

row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 2, eWeight: 218.00, nPOS: 0, sWord:王
row: 1, col: 4, eWeight: 10.86, nPOS: -28274, sWord:未##人
row: 2, col: 3, eWeight: 9.00, nPOS: 0, sWord:晓
row: 2, col: 4, eWeight: 13.27, nPOS: -28274, sWord:未##人
row: 3, col: 4, eWeight: 271.00, nPOS: 0, sWord:平
row: 4, col: 5, eWeight: 78484.00, nPOS: 0, sWord:在
row: 5, col: 7, eWeight: 0.00, nPOS: -29696, sWord:未##时
row: 5, col: 8, eWeight: 0.00, nPOS: -29696, sWord:未##时
row: 7, col: 8, eWeight: 1234.00, nPOS: 0, sWord:份
row: 8, col: 9, eWeight: 1.00, nPOS: 27136, sWord:滦
row: 8, col: 10, eWeight: 20.37, nPOS: -28275, sWord:未##地
row: 9, col: 10, eWeight: 813.00, nPOS: 0, sWord:南
row: 10, col: 11, eWeight: 14536.00, nPOS: 0, sWord:大
row: 10, col: 12, eWeight: 1333.00, nPOS: 28160, sWord:大会
row: 11, col: 13, eWeight: 469.00, nPOS: 0, sWord:会上
row: 12, col: 13, eWeight: 23706.00, nPOS: -27904, sWord:未##数
row: 13, col: 14, eWeight: 17649.00, nPOS: 0, sWord:说
row: 14, col: 15, eWeight: 358156.00, nPOS: 0, sWord:的
row: 15, col: 17, eWeight: 361.00, nPOS: 0, sWord:确实
row: 17, col: 18, eWeight: 78484.00, nPOS: 0, sWord:在
row: 17, col: 19, eWeight: 3.00, nPOS: 24832, sWord:在理
row: 18, col: 19, eWeight: 129.00, nPOS: 0, sWord:理
row: 19, col: 20, eWeight:2079997.00, nPOS: 4, sWord:末##末


//==== 生成 biSegGraph:

row: 0, col: 1, eWeight: 4.18, nPOS: 1, sWord:始##始@王
row: 0, col: 2, eWeight: 2.88, nPOS: 1, sWord:始##始@未##人
row: 1, col: 3, eWeight: 11.46, nPOS: 0, sWord:王@晓
row: 1, col: 4, eWeight: 3.88, nPOS: 0, sWord:王@未##人
row: 3, col: 5, eWeight: 13.93, nPOS: 0, sWord:晓@平
row: 2, col: 6, eWeight: -28270.43, nPOS: -28274, sWord:未##人@在
row: 4, col: 6, eWeight: -28270.43, nPOS: -28274, sWord:未##人@在
row: 5, col: 6, eWeight: 11.25, nPOS: 0, sWord:平@在
row: 6, col: 7, eWeight: 4.01, nPOS: 0, sWord:在@未##时
row: 6, col: 8, eWeight: 4.01, nPOS: 0, sWord:在@未##时
row: 7, col: 9, eWeight: -29690.16, nPOS: -29696, sWord:未##时@份
row: 8, col: 10, eWeight: -29690.16, nPOS: -29696, sWord:未##时@滦
row: 9, col: 10, eWeight: 9.76, nPOS: 0, sWord:份@滦
row: 8, col: 11, eWeight: -29690.17, nPOS: -29696, sWord:未##时@未##地
row: 9, col: 11, eWeight: 9.76, nPOS: 0, sWord:份@未##地
row: 10, col: 12, eWeight: 14.46, nPOS: 27136, sWord:滦@南
row: 11, col: 13, eWeight: -28267.95, nPOS: -28275, sWord:未##地@大
row: 12, col: 13, eWeight: 5.19, nPOS: 0, sWord:南@大
row: 11, col: 14, eWeight: -28266.85, nPOS: -28275, sWord:未##地@大会
row: 12, col: 14, eWeight: 10.17, nPOS: 0, sWord:南@大会
row: 13, col: 15, eWeight: 7.30, nPOS: 0, sWord:大@会上
row: 14, col: 16, eWeight: 4.81, nPOS: 28160, sWord:大会@未##数
row: 15, col: 17, eWeight: 3.42, nPOS: 0, sWord:会上@说
row: 16, col: 17, eWeight: -27898.75, nPOS: -27904, sWord:未##数@说
row: 17, col: 18, eWeight: 4.05, nPOS: 0, sWord:说@的
row: 18, col: 19, eWeight: 4.10, nPOS: 0, sWord:的@确实
row: 19, col: 20, eWeight: 3.92, nPOS: 0, sWord:确实@在
row: 19, col: 21, eWeight: 10.97, nPOS: 0, sWord:确实@在理
row: 20, col: 22, eWeight: 5.62, nPOS: 0, sWord:在@理
row: 21, col: 23, eWeight: 14.30, nPOS: 24832, sWord:在理@末##末
row: 22, col: 23, eWeight: 11.95, nPOS: 0, sWord:理@末##末


//==== 最终识别结果:

王晓平 /nr 在 /p 1月份 /t 滦南 /ns 大会 /n 上 /v 说 /v 的 /uj 确实 /ad 在 /p 理 /n

 

小结
有关SharpICTCLAS的系列文章到此为止就全部结束。

非常高兴在这一篇文章写完之时得到了张华平老师的授权。我会尽可能快的将SharpICTCLAS源文件放上来供大家测试使用的。

10.
http://www.cnblogs.com/zhenyulu/articles/718375.html

SharpICTCLAS分词系统简介(9)词库扩充
1、SharpICTCLAS中词库的扩充
如果对SharpICTCLAS目前词库不满意的化,可以考虑扩充现有词库。扩充方法非常简单,代码如下:

Copy Code词库扩充
static void Main(string[] args)
{
string DictPath = Path.Combine(Environment.CurrentDirectory, "Data") +
Path.DirectorySeparatorChar;
Console.WriteLine("正在读入字典,请稍候...");

WordDictionary dict = new WordDictionary();
dict.Load(DictPath + "coreDict.dct");

Console.WriteLine("\r\n向字典库插入“设计模式”一词...");
dict.AddItem("设计模式", Utility.GetPOSValue("n"), 10);

Console.WriteLine("\r\n修改完成,将字典写入磁盘文件coreDictNew.dct,请稍候...");
dict.Save(DictPath + "coreDictNew.dct");

Console.Write("按下回车键退出......");
Console.ReadLine();
}
通过AddItem方法可以轻松实现添加新词汇,添加时除了要指明词外,还需指明词性、词频。

2、其它工具
SharpICTCLAS示例代码中还提供了一些用于对文件进行预处理的工具类PreProcessUtility,里面提供了将GB2312中繁体汉字转换为简体字的代码,以及将全角字母转换为半角字母的方法,除此之外,还提供了对HTML文件进行预处理,去除HTML标记的方法,用户可酌情使用。

11.
http://www.cnblogs.com/zhenyulu/archive/2007/04/18/718383.html

SharpICTCLAS 1.0 发布!
SharpICTCLAS 1.0 发布 (感谢工控网发现了一个问题,问题出在字符串比较上,目前已经修正,请重新下载。2007年4月20日)

一、SharpICTCLAS 1.0 版相对于测试版的改进
1、修改了原子分词代码,使得对于全角字母有较好的识别

2、修改了部分词性标注部分的代码

因为词性标注部分的代码存在问题(应当是从ICTCLAS就存在的问题),主要表现在如果某个汉字没有词性,则在词性标注时会出现异常。例如:“这些是永远也没有现成的答桉的”其中“答案”写错了,当对这个有错别字的句子分词时,“桉”字是没有词性的,程序在此时将出现错误。

目前的解决办法是对于这些没有词性的词在最终标注时标注为“字符串”。

2、修改了地名识别的一些问题

这个问题出现在Span类的PlaceRecognize方法中,nStart与nEnd在某些时候会计算错误。在测试版SharpICTCLAS中,句子“明定陵是明十三陵中第十座陵墓”在分词时会因为这个问题导致异常。

3、修改了基于CCID的字符串比较代码

原有代码没有很好考虑对全角、半角混合字符串的比较问题,现在修正过来了。

4、修改了向词库添加词汇的代码

原有代码存在错误,现在改正了过来。

二、仍然有待改进的地方
现在的程序仍然有很多地方有待改进,例如原子分词部分的代码对电子邮件、URL等识别还不是很好,日后可利用正则表达式加以改进;除此之外,对于词性标注以及人名地名识别部分代码 ,我除了修改了部分问题代码外,没有做任何改进和调整,这使得整个代码显得凌乱,有待做一次全面重构。

三、SharpICTCLAS使用时的一些示例代码
为了能够更好的使用SharpICTCLAS,现提供一些示例代码,主要完成的工作包括:1)向词库中添加新词汇;2)对文件的预处理,实现繁体向简体的转换、全角字符向半角字符的转换、利用正则表达式过滤多余HTML标记以及断句等。具体可以访问我的文章《SharpICTCLAS分词系统简介(9)词库扩充》。

目前经过调整后的SharpICTCLAS运行效果还算不错。在对博客园一万五千篇文章进行分词测试过程中,向词库中添加了一千三百多个词汇然后进行分词,效果还不错, 分词异常一共发生了15次,其中有9处是因为存在大量日文字符,另外6处是一句话中单词过多,超出了软件限制(200词)。分词效率也比较令人满意(尽管总体还是比较慢),15000篇文章总用时2.5小时,但这不只是分词的时间,还包括了繁体转简体、利用正则表达式去掉HTML符号,统计词频(这需要进行重复词的判别,我使用了AVL树 ,共统计得到16万词汇)、将分词结果写入SQL Server 2005数据库。如果不考虑这些因素的话,感觉应当和C++程序效率差不多,当然这是没有经过严格测试的结论。

如果大家在使用时发现什么新问题,还请及时告知,我会继续修正这些问题。

ICTCLAS简介:
计算所汉语词法分析系统ICTCLAS(Institute of Computing Technology, Chinese Lexical Analysis System),功能有:中文分词;词性标注;未登录词识别。分词正确率高达97.58%(973专家评测结果),未登录词识别召回率均高于90%,其中中国人名的识别召回率接近98%;处理速度为31.5Kbytes/s。

著作权: Copyright(c)2002-2005中科院计算所 职务著作权人:张华平

遵循协议:自然语言处理开放资源许可证1.0

Email: zhanghp@software.ict.ac.cn

Homepage: http://www.i3s.ac.cn

SharpICTCLAS:
.net平台下的ICTCLAS,是由河北理工大学经管学院吕震宇根据Free版ICTCLAS改编而成,并对原有代码做了部分重写与调整。

Email: zhenyulu@163.com

Blog: http://www.cnblogs.com/zhenyulu



<< Home

This page is powered by Blogger. Isn't yours?