Sunday, April 30, 2006

 

Some DM SE related Websites

1.
数据挖掘与电子商务实验室
http://www.cit.fudan.edu.cn/research/www-dmgp/

2.
http://www.ysearchblog.com/

3.
http://www.vgoogle.net/

4.
The Search Engine and Web Mining (SEWM) Group, part of the network lab of Department of Computer Science and Technology, Peking University
http://net.cs.pku.edu.cn/~webg/

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

Sunday, April 23, 2006

 

Some notes on Chinese Words Segmentation - 3

1.
From http://blog.csdn.net/group/ictclas4j/

(一)分词思想

ICTClAS分词系统是由中科院计算所的张华平、刘群所开发的一套获得广泛好评的分词系统,难能可贵的是该版的Free版开放了源代码,为我们很多初学者提供了宝贵的学习材料。

但有一点不完美的是,该源代码没有配套的文档,阅读起来可能有一定的障碍,尤其是对C/C++不熟的人来说.本人就一直用Java/VB作为主要的开发语言,C/C++上大学时倒是学过,不过工作之后一直没有再使用过,语法什么的忘的几乎一干二净了.但语言这东西,基本的东西都相通的,况且Java也是在C/C++的基础上形成的,有一定的相似处.阅读一遍源代码,主要的语法都应该不成问题了.

虽然在ICTCLAS的系统中没有完整的文档说明,但是我们可以通过查阅张华平和刘群发表的一些相关论文资料,还是可以窥探出主要的思路.

该分词系统的主要是思想是先通过CHMM(层叠形马尔可夫模型)进行分词,通过分层,既增加了分词的准确性,又保证了分词的效率.共分五层

基本思路:先进行原子切分,然后在此基础上进行N-最短路径粗切分,找出前N个最符合的切分结果,生成二元分词表,然后生成分词结果,接着进行词性标注并完成主要分词步骤.

下面是对源代码的主要内容的研究:

1.首先,ICTCLAS分词程序首先调用CICTCLAS_WinDlg::OnBtnRun()开始程序的执行.并且可以从看出它的处理方法是把源字符串分段处理。并且在分词前,完成词典的加载过程,即生成m_ICTCLAS对象时调用构造函数完成词典库的加载。关于词典结构的分析,请参加分词系统研究(二)。

void CICTCLAS_WinDlg::OnBtnRun()
{

......

//在此处进行分词和词性标记

if(!m_ICTCLAS.ParagraphProcessing((char *)(LPCTSTR)m_sSource,sResult))
m_sResult.Format("错误:程序初始化异常!");
else
m_sResult.Format("%s",sResult);//输出最终分词结果

......

}

2.在OnBtnRun()方法里面调用分段分词处理方法bool CResult::ParagraphProcessing(char *sParagraph,char *sResult)完成分词的整个处理过程,包括分词的词性标注.其中第一个参数为源字符串,第二个参数为分词后的字符串.在这两个方法中即完成了整个分词处理过程,下面需要了解的是在此方法中,如何调用其它方法一步步按照上图所示的分析框架完成分词过程.为了简单起见,我们先不做未登录词的分析。

//Paragraph Segment and POS Tagging
bool CResult::ParagraphProcessing(char *sParagraph,char *sResult)
{

........

Processing(sSentence,1); //Processing and output the result of current sentence.
Output(m_pResult[0],sSentenceResult,bFirstIgnore); //Output to the imediate result

.......

}

3.主要的分词处理是在Processing()方法里面发生的,下面我们对它进行进一步的分析.

bool CResult::Processing(char *sSentence,unsigned int nCount)
{

......

//进行二叉分词

m_Seg.BiSegment(sSentence, m_dSmoothingPara,m_dictCore,m_dictBigram,nCount);

......

//在此处进行词性标注

m_POSTagger.POSTagging(m_Seg.m_pWordSeg[nIndex],m_dictCore,m_dictCore);

......

}

4.现在我们先不管词性标注,把注意力集中在二叉分词上,因为这个是分词的两大关键步骤的第一步.

参考文章:

1.<<基于层叠隐马模型的汉语词法分析>>,刘群 张华平等

2.<<基于N-最短路径的中文词语粗分模型>>,张华平 刘群

(二)词典结构

ICTCLAS的词典结构是理解分词的重要依据,通过这么一个数据结构设计合理访问速度高效的词典才能达到快速准备的分词的目的。

通过阅读和分析源代码,我们可以知道,是程序运行初,先把词典加载到内存中,以提高访问的速度。源代码在Result.cpp的构造函数CResult()内实现了词典和分词规则库的加载。如下代码所示:

CResult::CResult()
{
……

m_dictCore.Load("data\\coreDict.dct");
m_POSTagger.LoadContext("data\\lexical.ctx");

……

}

我们再跳进Load方法具体分析它是怎样读取数据词典的,看Load的源代码:

bool CDictionary::Load(char *sFilename,bool bReset)
{
FILE *fp;
int i,j,nBuffer[3];

//首先判断词典文件能否以二进制读取的方式打开
if((fp=fopen(sFilename,"rb"))==NULL)
return false;//fail while opening the file

//为新文件释放内存空间
for( i=0;iri delete m_IndexTable[i].pWordItemHead[j].sWord;
delete [] m_IndexTable[i].pWordItemHead;
}
DelModified();//删除掉修改过的,可以先不管它

//CC_NUM:6768,应该是GB2312编码中常用汉字的数目6763个加上5个空位码
for(i=0;i {

//读取一个整形数字(词块的数目)
fread(&(m_IndexTable[i].nCount),sizeof(int),1,fp);
if(m_IndexTable[i].nCount>0)
m_IndexTable[i].pWordItemHead=new WORD_ITEM[m_IndexTable[i].nCount];
else
{
m_IndexTable[i].pWordItemHead=0;
continue;
}
j=0;

//根据前面读到的词块数目,循环读取一个个词块
while(j {

//读取三字整数,分别为频度(Frequency)/词内容长度(WordLen)/句柄(Handle)
fread(nBuffer,sizeof(int),3,fp);
m_IndexTable[i].pWordItemHead[j].sWord=new char[nBuffer[1]+1];

//读取词内容
if(nBuffer[1])//String length is more than 0
{
fread(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
}
m_IndexTable[i].pWordItemHead[j].sWord[nBuffer[1]]=0;
if(bReset)//Reset the frequency
m_IndexTable[i].pWordItemHead[j].nFrequency=0;
else
m_IndexTable[i].pWordItemHead[j].nFrequency=nBuffer[0];
m_IndexTable[i].pWordItemHead[j].nWordLen=nBuffer[1];
m_IndexTable[i].pWordItemHead[j].nHandle=nBuffer[2];
j+=1;//Get next item in the original table.
}
}
fclose(fp);
return true;
}

看完上面的源代码,词典的结构也应该基本清楚了.修改表的数据结构和上图差不多,但是在词块数目后面多了一个nDelete数目,即删除的数目

GB2312(1980年)一共收录了7445个字符,包括6763个汉字和682个其它符号。汉字区的内码范围高字节从B0-F7,低字节从A1-FE,占用的码位是72*94=6768。其中有5个空位是D7FA-D7FE。词典库图一所示的6768个块即对应GB2312编码中的这个6768个区位.图一中每一个大块代表以该字开头的所有词组,括号内的字为区位码对应的汉字,词典表中并不存在,为了说明方便才添加上去的.如下所示:

块6759
count:5
wordLen:2 frequency:0 handle:24832 word:(黯)淡
wordLen:2 frequency:1 handle:24942 word:(黯)淡
wordLen:2 frequency:3 handle:31232 word:(黯)然
wordLen:6 frequency:0 handle:27648 word:(黯)然神伤
wordLen:6 frequency:0 handle:26880 word:(黯)然失色
块6760
count:1
wordLen:2 frequency:0 handle:28160 word:(鼢)鼠

块6761
count:2
wordLen:4 frequency:0 handle:28160 word:(鼬)鼠皮
wordLen:2 frequency:0 handle:28160 word:(鼬)獾



对修改后如何保存的源代码进行分析:

bool CDictionary::Save(char *sFilename)
{
FILE *fp;
int i,j,nCount,nBuffer[3];
PWORD_CHAIN pCur;
if((fp=fopen(sFilename,"wb"))==NULL)
return false;//fail while opening the file

//对图一中所示的6768个数据块进行遍历
for(i=0;i {
pCur=NULL;
if(m_pModifyTable)
{

//计算修改后有效词块的数目

nCount=m_IndexTable[i].nCount+m_pModifyTable[i].nCount-m_pModifyTable[i].nDelete;
fwrite(&nCount,sizeof(int),1,fp);
pCur=m_pModifyTable[i].pWordItemHead;
j=0;

//对原表中的词块和修改表中的词块进行遍历,并把修改后的添加到原表中
while(pCur!=NULL&&j {

//如果修改表中的词长度小于原表中对应位置的词的长度或者长度相等但nHandle值比原表中的小,则把修改表中的写入到词典文件当中.

if(strcmp(pCur->data.sWord,m_IndexTable[i].pWordItemHead[j].sWord)<0||(strcmp(pCur->data.sWord,m_IndexTable[i].pWordItemHead[j].sWord)==0&&pCur->data.nHandle {//Output the modified data to the file
nBuffer[0]=pCur->data.nFrequency;
nBuffer[1]=pCur->data.nWordLen;
nBuffer[2]=pCur->data.nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(pCur->data.sWord,sizeof(char),nBuffer[1],fp);
pCur=pCur->next;//Get next item in the modify table.
}

//频度nFrequecy等于-1说明该词已被删除,跳过它
else if(m_IndexTable[i].pWordItemHead[j].nFrequency==-1)
{
j+=1;
}

//如果修改表中的词长度比原表中的长度大或 长度相等但句柄值要多,就把原表的词写入的词典文件中
else if(strcmp(pCur->data.sWord,m_IndexTable[i].pWordItemHead[j].sWord)>0||(strcmp(pCur->data.sWord,m_IndexTable[i].pWordItemHead[j].sWord)==0&&pCur->data.nHandle>m_IndexTable[i].pWordItemHead[j].nHandle))
{//Output the index table data to the file
nBuffer[0]=m_IndexTable[i].pWordItemHead[j].nFrequency;
nBuffer[1]=m_IndexTable[i].pWordItemHead[j].nWordLen;
nBuffer[2]=m_IndexTable[i].pWordItemHead[j].nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
j+=1;//Get next item in the original table.
}
}

//把原表中剩余的词写入的词典文件当中
if(j {
while(j {
if(m_IndexTable[i].pWordItemHead[j].nFrequency!=-1)
{//Has been deleted
nBuffer[0]=m_IndexTable[i].pWordItemHead[j].nFrequency;
nBuffer[1]=m_IndexTable[i].pWordItemHead[j].nWordLen;
nBuffer[2]=m_IndexTable[i].pWordItemHead[j].nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
}
j+=1;//Get next item in the original table.
}
}
else////原表已到尾部但修改表还没有遍历完,把修改表中剩余的词写入到词典文件当中
while(pCur!=NULL)//Add the rest data to the file.
{
nBuffer[0]=pCur->data.nFrequency;
nBuffer[1]=pCur->data.nWordLen;
nBuffer[2]=pCur->data.nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(pCur->data.sWord,sizeof(char),nBuffer[1],fp);
pCur=pCur->next;//Get next item in the modify table.
}
}



//不是修改标记,则把原表的数据全部写入到词典文件当中
else
{
fwrite(&m_IndexTable[i].nCount,sizeof(int),1,fp);
//write to the file
j=0;
while(j {
nBuffer[0]=m_IndexTable[i].pWordItemHead[j].nFrequency;
nBuffer[1]=m_IndexTable[i].pWordItemHead[j].nWordLen;
nBuffer[2]=m_IndexTable[i].pWordItemHead[j].nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
j+=1;//Get next item in the original table.
}
}
}
fclose(fp);
return true;
}

增加一个词条目:

bool CDictionary::AddItem(char *sWord, int nHandle,int nFrequency)
{

char sWordAdd[WORD_MAXLENGTH-2];
int nPos,nFoundPos;
PWORD_CHAIN pRet,pTemp,pNext;
int i=0;

//预处理,去掉词的前后的空格
if(!PreProcessing(sWord, &nPos,sWordAdd,true))
return false;

//查找词典原表中该词是否存在
if(FindInOriginalTable(nPos,sWordAdd,nHandle,&nFoundPos))
{//The word exists in the original table, so add the frequency
//Operation in the index table and its items
if(m_IndexTable[nPos].pWordItemHead[nFoundPos].nFrequency==-1)
{//The word item has been removed
m_IndexTable[nPos].pWordItemHead[nFoundPos].nFrequency=nFrequency;
if(!m_pModifyTable)//Not prepare the buffer
{
m_pModifyTable=new MODIFY_TABLE[CC_NUM];
memset(m_pModifyTable,0,CC_NUM*sizeof(MODIFY_TABLE));
}
m_pModifyTable[nPos].nDelete-=1;
}
else
m_IndexTable[nPos].pWordItemHead[nFoundPos].nFrequency+=nFrequency;
return true;
}

//如果修改表为空,为它初始化空间

if(!m_pModifyTable)//Not prepare the buffer
{
m_pModifyTable=new MODIFY_TABLE[CC_NUM];
memset(m_pModifyTable,0,CC_NUM*sizeof(MODIFY_TABLE));
}

//在修改表中查询该词是否存在,如果存在增加该词的频度
if(FindInModifyTable(nPos,sWordAdd,nHandle,&pRet))
{
if(pRet!=NULL)
pRet=pRet->next;
else
pRet=m_pModifyTable[nPos].pWordItemHead;
pRet->data.nFrequency+=nFrequency;
return true;
}


//如果没有在修改表中找到,则添加进去

pTemp=new WORD_CHAIN;//Allocate the word chain node
if(pTemp==NULL)//Allocate memory failure
return false;
memset(pTemp,0,sizeof(WORD_CHAIN));//init it with 0
pTemp->data.nHandle=nHandle;//store the handle
pTemp->data.nWordLen=strlen(sWordAdd);
pTemp->data.sWord=new char[1+pTemp->data.nWordLen];
strcpy(pTemp->data.sWord,sWordAdd);
pTemp->data.nFrequency=nFrequency;
pTemp->next=NULL;

//插入到修改表中
if(pRet!=NULL)
{
pNext=pRet->next;//Get the next item before the current item
pRet->next=pTemp;//link the node to the chain
}
else
{
pNext=m_pModifyTable[nPos].pWordItemHead;
m_pModifyTable[nPos].pWordItemHead=pTemp;//Set the pAdd as the head node
}
pTemp->next=pNext;//Very important!!!! or else it will lose some node
//把词块数目加一
m_pModifyTable[nPos].nCount++;//the number increase by one
return true;
}



删除修改过的词条

bool CDictionary::DelModified()
{
PWORD_CHAIN pTemp,pCur;
if(!m_pModifyTable)
return true;


for(int i=0;i {
pCur=m_pModifyTable[i].pWordItemHead;

//删除链表上的节点
while(pCur!=NULL)
{
pTemp=pCur;
pCur=pCur->next;
delete pTemp->data.sWord;
delete pTemp;
}
}
delete [] m_pModifyTable;
m_pModifyTable=NULL;
return true;
}

//采用二分法进行查找

bool CDictionary::FindInOriginalTable(int nInnerCode,char *sWord,int nHandle,int *nPosRet)
{
PWORD_ITEM pItems=m_IndexTable[nInnerCode].pWordItemHead;
int nStart=0,nEnd=m_IndexTable[nInnerCode].nCount-1,nMid=(nStart+nEnd)/2,nCount=0,nCmpValue;
while(nStart<=nEnd)//Binary search
{
nCmpValue=strcmp(pItems[nMid].sWord,sWord);

//如果中间那个正好是要查找的
if(nCmpValue==0&&(pItems[nMid].nHandle==nHandle||nHandle==-1))
{
if(nPosRet)
{
if(nHandle==-1)//Not very strict match
{//Add in 2002-1-28
nMid-=1;

//Get the first item which match the current word
while(nMid>=0&&strcmp(pItems[nMid].sWord,sWord)==0)
nMid--;
if(nMid<0||strcmp(pItems[nMid].sWord,sWord)!=0)
nMid++;
}
*nPosRet=nMid;
return true;
}
if(nPosRet)
*nPosRet=nMid;
return true;//find it
}
else if(nCmpValue<0||(nCmpValue==0&&pItems[nMid].nHandle {
nStart=nMid+1;
}
else if(nCmpValue>0||(nCmpValue==0&&pItems[nMid].nHandle>nHandle&&nHandle!=-1))
{
nEnd=nMid-1;
}
nMid=(nStart+nEnd)/2;
}
if(nPosRet)
{
//Get the previous position
*nPosRet=nMid-1;
}
return false;
}



//在修改表中查询

bool CDictionary::FindInModifyTable(int nInnerCode,char *sWord,int nHandle,PWORD_CHAIN *pFindRet)
{
PWORD_CHAIN pCur,pPre;
if(m_pModifyTable==NULL)//empty
return false;
pCur=m_pModifyTable[nInnerCode].pWordItemHead;
pPre=NULL;

//sWord相等且句柄(nHandle)相等
while(pCur!=NULL&&(_stricmp(pCur->data.sWord,sWord)<0||(_stricmp(pCur->data.sWord,sWord)==0&&pCur->data.nHandle //sort the link chain as alphabet
{
pPre=pCur;
pCur=pCur->next;
}
if(pFindRet)
*pFindRet=pPre;
if(pCur!=NULL && _stricmp(pCur->data.sWord,sWord)==0&&(pCur->data.nHandle==nHandle||nHandle<0))
{//The node exists, delete the node and return
return true;
}
return false;
}



得到词的类型,共三种汉字、分隔符和其他

int CDictionary::GetWordType(char *sWord)
{
int nType=charType((unsigned char *)sWord),nLen=strlen(sWord);
if(nLen>0&&nType==CT_CHINESE&&IsAllChinese((unsigned char *)sWord))
return WT_CHINESE;//Chinese word
else if(nLen>0&&nType==CT_DELIMITER)
return WT_DELIMITER;//Delimiter
else
return WT_OTHER;//other invalid
}

(三)原子切分

ICTCLAS分词的第一步就是原子分词。但在进行原子切分之前,首先要进行断句处理。所谓断句,就是根据分隔符、回车换行符等语句的分隔标志,把源字符串分隔成多个稍微简单一点的短句,再进行分词处理,最后再把各个分词结果合起来,形成最终的分词结果。

分成短句之后,即可进行原子分词,所谓原子,是指该短句中不可分割的最小语素单位。一个汉字、短句前后的开始结束标识字段、全角标点符号、连在一起的数字字母单字节字符等。最后一种情况可以举例说明,比如:三星SHX-132型号的手机1元钱,则SHX-132、1都是一个原子,其它的每个汉字是一个原子。

按照这种方式,通过简单的汉字分割就形成了原子分词的结果,并对每个原子单位进行词性标注。nPOS=1表示是开始标记,nPOS=4表示结束标记,nPOS=0表示未识别词。

经过原子分词之后,下面即可进行初次分词。

(四)初次切分

经过原子分词后,源字符串成了一个个独立的最小语素单位。下面的初次切分,就是把原子之间所有可能的组合都先找出来。算法是用两个循环来实现,第一层遍历整个原子单位,第二层是当找到一个原子时,不断把后面相邻的原子和该原子组合到一起,访问词典库看它能否构成一个有意义有词组。

用数学方法可以做如下描述:

有一个原子序列:A(n)(0<=n
用伪码表示:

for(int I=0;I
String s=A[I];

for(int j=I+1;j
s+=A[j];

if(s是一个词组){

把s加入到初次切分的列表中;

记录该词组的词性;

记录该词组所在表中的坐标位置及其它信息;

}

else

break;

}

}

从上图三可以看出,在二维表中,初次切分后的词组,第一次字相同的在同一行,最后一个字相同的在同一列,原来的原子在对称轴上.

对上述过程进行处理的参考源代码如下:

bool CSegment::BiSegment(char *sSentence, double dSmoothingPara, CDictionary &dictCore, CDictionary &dictBinary, unsigned int nResultCount)
{

......

//在此处完成上图一的处理结果,生成一个链表结构

m_graphSeg.GenerateWordNet(sSentence,dictCore,true);//Generate words array


......

在生成图二所示的表结构之后,进一步生成二叉图表.

....

//Generate the biword link net

BiGraphGenerate(m_graphSeg.m_segGraph,aBiwordsNet,dSmoothingPara,dictBinary,dictCore);

....

对该函数进行深入分析:

bool CSegment::BiGraphGenerate(CDynamicArray &aWord, CDynamicArray &aBinaryWordNet,double dSmoothingPara,CDictionary &DictBinary,CDictionary &DictCore)
{
......

//获取链表的长度
m_nWordCount=aWord.GetTail(&pTail);//Get tail element and return the words count
if(m_npWordPosMapTable)
{//free buffer
delete [] m_npWordPosMapTable;
m_npWordPosMapTable=0;
}

//分配一个数组,存贮图二中每个结点的词的位置,如下图四所示
if(m_nWordCount>0)//Word count is greater than 0
m_npWordPosMapTable=new int[m_nWordCount];//Record the position of possible words


//把指针指向当前链表的开头,并计算每个词的位置,然后把它放到数组中

pCur=aWord.GetHead();
while(pCur!=NULL)//Set the position map of words
{
m_npWordPosMapTable[nWordIndex++]=pCur->row*MAX_SENTENCE_LEN+pCur->col;
pCur=pCur->next;
}

//遍历所有的结点,并计算相临两个词之间的平滑值

pCur=aWord.GetHead();
while(pCur!=NULL)//
{
if(pCur->nPOS>=0)//It's not an unknown words
dCurFreqency=pCur->value;
else//Unknown words
dCurFreqency=DictCore.GetFrequency(pCur->sWord,2);

//取得和当前结点列值(col)相同的下个结点
aWord.GetElement(pCur->col,-1,pCur,&pNextWords);
while(pNextWords&&pNextWords->row==pCur->col)//Next words
{
//前后两个词用@分隔符连接起来

strcpy(sTwoWords,pCur->sWord);
strcat(sTwoWords,WORD_SEGMENTER);
strcat(sTwoWords,pNextWords->sWord);

//计算两个连接词的边长
nTwoWordsFreq=DictBinary.GetFrequency(sTwoWords,3);
//Two linked Words frequency
dTemp=(double)1/MAX_FREQUENCE;
//计算平滑值
dValue=-log(dSmoothingPara*(1+dCurFreqency)/(MAX_FREQUENCE+80000)+(1-dSmoothingPara)*((1-dTemp)*nTwoWordsFreq/(1+dCurFreqency)+dTemp));
//-log{a*P(Ci-1)+(1-a)P(Ci|Ci-1)} Note 0 if(pCur->nPOS<0)//Unknown words: P(Wi|Ci);while known words:1
dValue+=pCur->value;

//Get the position index of current word in the position map table
nCurWordIndex=BinarySearch(pCur->row*MAX_SENTENCE_LEN+pCur->col,m_npWordPosMapTable,m_nWordCount);
nNextWordIndex=BinarySearch(pNextWords->row*MAX_SENTENCE_LEN+pNextWords->col,m_npWordPosMapTable,m_nWordCount);

//把当前结点在位置表中的位置和下个结点在位置表中的位置及平滑值/词性插入到二叉链表中
aBinaryWordNet.SetElement(nCurWordIndex,nNextWordIndex,dValue,pCur->nPOS);
pNextWords=pNextWords->next;//Get next word
}
pCur=pCur->next;
}
return true;
}

其中小数值代表了相临两个词之间的耦合成度,即构成更大长度词的可能性的机率,值越小说明两个词独立成词的可能性越大。

# 飞天小猪 发表于2006-05-26 00:17:00 IP: 58.49.193.*
一直关注中 偶也在做中文词性标注的毕业论文 请问 如图五所示的nPOS值是24832是什么意思?
急盼指点 谢谢

# sinboy 发表于2006-05-26 17:53:00 IP: 124.90.23.*
nPOS指的应该是词性

# sinboy 发表于2006-05-26 18:05:00 IP: 124.90.23.*
我现在还没有开始研究词性标记的处理部分,只是先分析分词的过程。读源代码累,搞清楚里面的原理更是困难。如果你也在研究这方面的东西,我们有时间多多交流一下。

# 飞天小猪 发表于2006-05-27 02:29:00 IP: 58.49.197.*
请教一下: 如果按照刘群和张化平的关于N最短路径求法的论文中介绍: 他说的确实在理 切分为他/说/的/确实/在理

然而用中科院的程序运行得到的结果为: 他/说/的/确实/在/理

与论文不符 请问这是怎么回事?盼指点

# 飞天小猪 发表于2006-05-27 02:40:00 IP: 58.49.197.*
对于图六中的数据是怎么计算得到的呢?

# sinboy 发表于2006-05-27 15:08:00 IP: 124.90.19.*
从源程序运行的结果来(对照图六),他认为分成:在/理两个词比成一个词的更好,从(9,11),(10,12)这两个的值得知。按照N-最短路径的思想,应该是生成N条最短路径,然后再选一个最佳的。但在源程序里面,我分析N可能被设置成了1。图六的生成结果是在函数BiGraphGenerate()里面实现的,就是计算(我想应该是统计它们在语料库中出现的概率)相邻两个词的耦合度。

(五)N最短路径

ICTCLAS和别的分司系统不一样的地方就是于--N最短路径分词算法。所谓N最短路径其实就是最短路径和最大路径的折中,保留前N个最优路径。这样做的目的就是对这两种方法取长补短,既能达到一个比较理解的分词不达意效果,又能保证分词不达意速度。在此处,我们中国人的中庸思想被完美体现:)。

在源程序中,N最短路径是在CNShortPath类里里面实现的。

bool CSegment::BiSegment(char *sSentence, double dSmoothingPara, CDictionary &dictCore, CDictionary &dictBinary, unsigned int nResultCount)
{

......

//调用构造函数,生成一个二维链表,如下图一所示。每个链表节点是一个队列,数据结构如下图二所示
CNShortPath sp(&aBiwordsNet,nResultCount);

//最短路径算法实现
sp.ShortPath();

//输出最短路径
sp.Output(nSegRoute,false,&m_nSegmentCount);

.....

}

对NShortPath的构造函数分进一步分析:

CNShortPath::CNShortPath(CDynamicArray *apCost,unsigned int nValueKind)
{
//研究(四)中图五所示的链表

m_apCost=apCost;//Set the cost
m_nValueKind=nValueKind;//Set the value kind

//顶点数
m_nVertex=apCost->m_nCol+1;
if(m_nVertexm_nRow+1)
m_nVertex=apCost->m_nRow+1;//Get the vertex numbers

m_pParent=new CQueue*[m_nVertex-1];//not including the first node
m_pWeight=new ELEMENT_TYPE *[m_nVertex-1];


for(unsigned int i=0;i {
m_pParent[i]=new CQueue[nValueKind];
m_pWeight[i]=new ELEMENT_TYPE[nValueKind];

}
}




int CNShortPath::ShortPath()
{
unsigned int nCurNode=1,nPreNode,i,nIndex;
ELEMENT_TYPE eWeight;
PARRAY_CHAIN pEdgeList;

for(;nCurNode {
CQueue queWork;
eWeight=m_apCost->GetElement(-1,nCurNode,0,&pEdgeList);//Get all the edges

//对研究(四)中的图六所示的表,按列优进行遍历,把每个列的数据放到一个临时工作队列中
while(pEdgeList!=0 && pEdgeList->col==nCurNode)
{
nPreNode=pEdgeList->row;
eWeight=pEdgeList->value;//Get the value of edges
for(i=0;i {
if(nPreNode>0)//Push the weight and the pre node infomation
{
if(m_pWeight[nPreNode-1][i]==INFINITE_VALUE)
break;

//把行值(ROW)放入队列中,并且保证队列的排序是按Weight值从小到大排列

queWork.Push(nPreNode,i,eWeight+m_pWeight[nPreNode-1][i]);
}
else
{
queWork.Push(nPreNode,i,eWeight);
break;
}
}//end for
pEdgeList=pEdgeList->next;

}//end while

//Now get the result queue which sort as weight.
//Set the current node information
for(i=0;i {
m_pWeight[nCurNode-1][i]=INFINITE_VALUE;
}
//memset((void *),(int),sizeof(ELEMENT_TYPE)*);
//init the weight
i=0;

//临时工作队列中取出前面的一个,并记路路径长度的和
while(i {//Set the current node weight and parent
if(m_pWeight[nCurNode-1][i]==INFINITE_VALUE)
m_pWeight[nCurNode-1][i]=eWeight;
else if(m_pWeight[nCurNode-1][i] {
i++;//Go next queue and record next weight
if(i==m_nValueKind)//Get the last position
break;
m_pWeight[nCurNode-1][i]=eWeight;
}
m_pParent[nCurNode-1][i].Push(nPreNode,nIndex);
}
}//end for

return 1;
}

int CNShortPath::Output(int **nResult,bool bBest,int *npCount)
{//sResult is a string array

......
GetPaths(m_nVertex-1,i,nResult,bBest);

}

//获取分词输出路径。指研究(四)中的图四

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);
}
}
}


最终得到最短路么(0,1,2,3,6,9,11,12),里面的数值分别对应研究(四)中图四的下标,到此分词的第一大步就结束了,并形成最终结果:始##始/他/说/的/确实/在/理/末##末

2.
From http://qxred.yculblog.com/post.1204714.html

ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注

风暴红QxRed @ 2006-04-20 20:38


中科院分词系统概述

这几天看完了中科院分词程序的代码,现在来做一个概述,并对一些关键的数据结构作出解释


〇、总体流程

考虑输入的一句话,sSentence="张华平欢迎您"

总体流程:

一、分词 "张/华/平/欢迎/您"

二、posTagging "张/q 华/j 平/j 欢迎/v 您/r"

三、NE识别:人名识别,音译名识别,地名识别 "张/q 华/j 平/j 欢迎/v 您/r" "张华平/nr"

四、重新分词:"张华平/欢迎/您"

五、重新posTagging: "张华平/nr 欢迎/v 您/r"




技术细节

一、分词

分词程序首先在其头末添加开始符和结束符
sSentence="始##始张华平欢迎您末##末"

然后是分词,基本思想就是分词的得到的词的联合概率最大

假设 "张华平欢迎您" 分为 "w_1/w_2/.../w_k" 则
w_1/w_2/.../w_k=argmax_{w_1'/w_2'/.../w_k'}P(w_1',w_2',...,w_k')=argmax_{w_1'/w_2'/.../w_k'}P(w_1')P(w_2')...P(w_k')

细节:

首先给原句按字划分,所有汉字一个一段,连续的字母,数字一段,比如"始##始张华平2006欢迎您asdf末##末"被划为"始##始/张/华/平/2006/欢/迎/您/asdf/末##末"

接着找出这个句子中所有可能出现的词,比如"始##始张华平欢迎您末##末",出现的词有"始##始","张","华","平","欢","迎","您","末##末","欢迎"
并查找这些词所有可能的词性和这些词出现的频率。

将这些词保存在一个结构中,具体实现如下:

m_segGraph中有一个(PARRAY_CHAIN)m_pHead,是一个链

(PARRAY_CHAIN)p->row//记录该词的头位置
(PARRAY_CHAIN)p->col//记录该词的末位置
(PARRAY_CHAIN)p->value//记录该词的-log(出现的概率),出现的频率指所有该词的所有词性下出现的概率的总和。
(PARRAY_CHAIN)p->nPos//记录该词的词性,比如人名标记为'nr',则对应的nPos='n'*256+'r',如果该词有很多词性,则nPos=0
(PARRAY_CHAIN)p->sWord//记录该词
(PARRAY_CHAIN)p->nWordLen//记录该词的长度

举个例子:
"0 始##始 1 张 2 华 3 平 4 欢 5 迎 6 您 7 末##末 8"

对于"张"来说,
row=1
col=2
value=-log[("张"出现的频率+1)/(MAX_FREQUENCE)]
nPos=0//"张"有5种词性
sWord="张"
nWordLen=2

保存的顺序是按col升序row升序的次序排列

m_segGraph.m_pHead "始##始"
"张"
"华"
"平"
"欢"
"欢迎"
"迎"
"您"
"末##末"

m_segGraph.m_nRow=7
m_segGraph.m_nCol=8


然后是生成一幅给予各种组合情况的图,并按照出现的概率大小保存概率最大的前m_nValueKind个结果。

细节:

初始化,
(CNShortPath)sp.m_apCost=m_segGraph;
(CNShortPath)sp.m_nVertex=m_segGraph.m_nCol+1
(CNShortPath)sp.m_pParent=CQueue[m_segGraph.m_nCol][m_nValueKind]
(CNShortPath)sp.m_pWeight=ELEMENT_TYPE[m_segGraph.m_nCol][m_nValueKind]//m_pWeight[0][0]表示1处的weight

sp.ShortPath()函数中,
for(nCurNode=1;nCurNode{
CQueue queWork;//零时的CQueue
eWeight=m_apCost->GetElement(-1,nCurNode,0,&pEdgeList);//取出col=nCurNode的第一个PARRAY_CHAIN的value,比如nCurNode=6,则pEdgeList指向"欢迎",eWeight="pEdgeList->value
while(pEdgeList&&pEdgeList->col==nCurNode)//对每一个col=nCurNode的pEdgeList
{

for(i=0;i {
queWork.Push(pEdgeList->row,0,eWeight+m_pWeight[pEdgeList->row-1][i]);
//将所有col=nCurNode的pEdgeList按照其weight升序放到queWork中
}
}//比如
/*
"欢迎" m_pWeight[3][0]=0.2 eWight=0.2 =>queWork.Push(4,0,0.4);
"0 始##始 1 张 2 华 3 平 4 欢 5 迎 6 您 7 末##末 8"
"欢" m_pWeight[4][0]=0.5 eWight=0.1 =>queWork.Push(5,0,0.6);
m_pWeight[4][1]=0.6 eWight=0.1 =>queWork.Push(5,0,0.7);

queWork "欢迎" 0.4
"迎" 0.6
"迎" 0.7

*/
for(i=0;i while(ivalue
{
m_pWeight[nCurNode-1][i]=eWeight;//取前m_nValueKind个结果
m_pParent[nCurNode-1][i].Push(nPreNode,nIndex);//按照pEdgeList->value的升序,也就是P的降序放入m_pParent
}
}

得到m_pParent之后,按照m_pWeight[m_segGraph.m_nCol-1]的升序,生成path
CNShortPath::GetPaths(unsigned int nNode,unsigned int nIndex,int **nResult,bool bBest)
//nNode=m_segGraph.m_nCol,nIndex从0取到m_nValueKind-1,nResult输出结果,bBest=true只输出最佳结果
比如"始##始张华平欢迎您末##末"的结果为
nResult[0]={0,1,2,3,4,6,7,8,-1} "始##始/张/华/平/欢迎/您/末##末"
nResult[1]={0,1,2,3,4,5,6,7,8,-1} "始##始/张/华/平/欢/迎/您/末##末"
没有第三种结果

取出所有nResult[i]作为分词结果,结果保存在m_graphOptimum中,m_graphOptimum和m_segGraph结构一样,只不过只存nResult[i]中的结果:

如果m_nValueKind=1则
m_graphOptimum.m_pHead "始##始"
"张"
"华"
"平"
"欢迎"
"您"
"末##末"

m_graphOptimum.m_nRow=7
m_graphOptimum.m_nCol=8


如果m_nValueKind=2则

m_graphOptimum.m_pHead "始##始"
"张"
"华"
"平"
"欢"
"欢迎"
"迎"
"您"
"末##末"

m_graphOptimum.m_nRow=7
m_graphOptimum.m_nCol=8


见 bool CSegment::GenerateWord(int **nSegRoute, int nIndex)这里的nSegRoute=上面的nResult,是输入参数;nIndex表示第nIndex个分词结果


同时,CResult.m_Seg.m_pWordSeg[nIndex][k]中保存了第nIndex个结果的第k个词的信息:

CResult.m_Seg.m_pWordSeg[nIndex][k].sWord//词
CResult.m_Seg.m_pWordSeg[nIndex][k].nHandle//词性
CResult.m_Seg.m_pWordSeg[nIndex][k].dValue//-logP

至此,分词部分结束

二、posTagging


m_POSTagger.POSTagging(m_Seg.m_pWordSeg[nIndex],m_dictCore,m_dictCore);//对第nIndex个分词结果用标准的字典标注
方便起见,下面假设m_nValueKind=1


m_POSTagger用HMM对分词进行标注,这里输出概率为P(w_i|c_i),c_i为词性,w_i为词;转移概率为P(c_i|c_{i-1}),初始状态为P(c_0)即P("始##始"的词性)
用维特比算法求出一个c_1/c_2/.../c_k=argmax_{c_1'/c_2'/.../c_k'}P(w_1',w_2',...,w_k')

将句子分成若干段,每段以有唯一pos的w结尾,也就是分词中CResult.m_Seg.m_pWordSeg[0][k].nHandle>0的那些词

比如,举个例子
"0 始##始 1 张 2 华 3 平 4 欢迎 5 您 6 末##末 7"
pos1 pos1 pos1 pos1 pos1 pos1 pos1
pos2 pos2 pos2 pos2
pos3 pos3 pos3
pos4
pos5

则该句被划分为
"0 始##始"
"1 张 2 华 3 平 4 欢迎 5 您"
"6 末##末"
对每一段用维特比算法确定一个唯一的postag

细节:

首先P(w,c)的输出概率存储在dict中,比如dictCore,dictUnknow,通过dict.GetFrequency(char *sWord, int nHandle)函数获取 sWord pos为nHandle的函数
概率P(c)存储在context中,比如m_context,通过context.GetFrequency(int nKey, int nSymbol)函数获取 pos为nSymbol的函数,nKey=0
转移概率P(c|c')存储在context中,比如m_context,通过context.GetContextPossibility(int nKey, int nPrev, int nCur)函数获取 c'=nPrev,c=nCur的转移概率,nKey=0

重要的数据结构

m_nTags[i][k]表示第i个w的第k个pos
在GetFrom函数中表示 -log(第i个w的第k个pos的输出概率)
在CSpan::Disamb()函数中
m_dFrequency[i][k]表示 -log(从第0个w到第i个w的第k个pos的联合最大输出概率),比如


w_j w_{j+1}
m_dFrequency[j][0]-- m_dFrequency[j+1][0]
m_dFrequency[j][1] -- m_dFrequency[j+1][1]
--m_dFrequency[j+1][2]



则 图中的路径的权为W([j,0]->[j+1,2])=m_dFrequency[j][0]-log(m_context.GetContextPossibility(0,m_nTags[j][0],m_nTags[j+1][2]))
这样,选择
m_dFrequency[j+1][2]=min{W([j,0]->[j+1,2]),W([j,1]->[j+1,2])}


m_nCurLength表示当前段的w个数+1

在m_POSTagger.POSTagging中,以上面的例子为例
while(i>-1&&pWordItems[i].sWord[0]!=0)//将执行段的个数次,比如上例中将执行3次
{
i=GetFrom(pWordItems,nStartPos,dictCore,dictUnknown);//i=GetFrom(pWordItems,0,dictCore,dictUnknown)=1
//i=GetFrom(pWordItems,1,dictCore,dictUnknown)=6
//i=GetFrom(pWordItems,6,dictCore,dictUnknown)=7
//从nStartPos向前取w,一直取到一个有唯一pos的w为止,该过程中记录每个w的pos,保存在m_nTags中,记录log(w|c)输出概率保存在m_dFrequency中
GetBestPOS();//调用Disamb()函数,用维特比算法找出该段的最佳(联合输出概率最大)的标注,最佳路径保存在m_nBestTag中
通过读取m_nBestTag对pWordItems.nHandle进行赋值
}


三、NE识别:人名识别,音译名识别,地名识别

其基本思路和PosTagging一样,只不过词性c换成了role r,以人名识别为例,首先识别出人名的tag(即pos),见
"Chinese Named Entity Recognition Using Role Model"
在函数CUnknowWord::Recognition(PWORD_RESULT pWordSegResult, CDynamicArray &graphOptimum,CSegGraph &graphSeg,CDictionary &dictCore)中
每个被切开的段被识别完之后,用m_roleTag.POSTagging(pWordSegResult,dictCore,m_dict);对第一步分词的结果进行一次标记。
首先用dictUnknown.GetHandle(m_sWords[i],&nCount,aPOS,aFreq);获得m_sWords[i]在NE词典中的role,
接着用dictCore.GetHandle(m_sWords[i],&nCount,aPOS,aFreq);获得m_sWords[i]在标准词典中的tag,这里只要m_sWords[i]在标准词典中有tag,那么tag一律标记为0,该tag下的输出概率为P(w|c)=P(sum_{aFreq}|c=0)
接下来用SplitPersonPOS(dictUnknown)函数将其中tag为LH和TR的w拆成两个
比如"张/SS 华/GH 平欢/TR 迎/RC 您/RC"中"平欢"被拆成"平/GT" "欢/12"
接着在PersonRecognize(dictUnknown);函数中,用一些模板进行匹配,"SS/GH/TR"将匹配到"张华平"。匹配得到的片断保存在m_nUnknownWords中,其nHandle被设置为人名,地名,音译名中的一个
对第一步中的graphOptimum,加入m_nUnknownWords的边:
graphOptimum.GetElement(nAtomStart,nAtomEnd,&dValue,&nPOSOriginal);
if(dValue>m_roleTag.m_dWordsPossibility[i])//Set the element with less frequency
graphOptimum.SetElement(nAtomStart,nAtomEnd,m_roleTag.m_dWordsPossibility[i],m_nPOS);

四、重新分词

对上一步的graphOptimum,用第一步中对m_segGraph分词的方法,找出一个联合概率最大的分词结果:
m_Seg.OptimumSegmet(nCount);

五、重新标注

对于四中分好的结果,用标准词典对其进行posTagging:
for(nIndex=0;nIndex{
m_POSTagger.POSTagging(m_Seg.m_pWordSeg[nIndex],m_dictCore,m_dictCore);
}


最后,用Sort();对标注结果按照联合输出概率的大小降序排序,并按照用户的需求输出前几个

3.
From http://www.cnblogs.com/zhenyulu/articles/653254.html

(按:作者有点言过其实,制造噱头的嫌疑,^_^,以下未删节)

ICTCLAS分词系统是由中科院计算所的张华平、刘群所开发的一套获得广泛好评的分词系统,该版的Free版开放了源代码,为初学者提供了宝贵的学习材料。我们可以在“http://sewm.pku.edu.cn/QA/”找到FreeICTCLASLinux.tar的C++代码。

可是目前该版本的ICTCLAS并没有提供完善的文档,所以阅读起来有一定的难度,所幸网上可以找到一些对ICTCLAS进行代码分析的文章,对理解分词系统的内部运行机制提供了很大的帮助。这些文章包括:

1)http://blog.csdn.net/group/ictclas4j/;《ICTCLAS分词系统研究(一)~(六)》作者:sinboy。

2)http://qxred.yculblog.com/post.1204714.html;《ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注》作者:风暴红QxRed 。

按照上面这些文章的思路去读ICTCLAS的代码,可以比较容易的理顺思路。然而在我阅读代码的过程中,越来越对ICTCLAS天书般的代码感到厌烦。我不得不佩服中科院计算所的人思维缜密,头脑清晰,能写出滴水不漏而又让那些“头脑简单”的人百思不得其解的代码。将一件本来很简单的事情做得无比复杂...

ICTCLAS中有一个名为CDynamicArray的类,存放在DynamicArray.cpp与DynamicArray.h两个文件中,这个DynamicArray是干什么用的?经过一番研究后终于明白是一个经过排序的链表。为了表达的更明白些,我们不妨看下面这张图:



(图一)

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



(图二)

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



(图三)

在了解了这些内容的基础上,不妨让我们看看ICTCLAS中DynamicArray.cpp中的代码实现(这里我们只看GetElement方法的实现,其基本功能为给出row与col,然后将对应的元素取出来)。

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;
}
这里我先要说明的是程序中的m_bRowFirst变量,它表示是先按row大小排列还是先按col大小排列。如果m_bRowFirst为逻辑真值,那么链表就如上面图二所示,如果为假,则如图三所示。

除了这个外,看到上面长长的条件表达式,你一定会吓坏了吧!更让人吓坏的是调用这段程序的代码:

Copy Code对GetElement方法的调用

//来自NShortPath.cpp中ShortPath方法
eWeight = m_apCost->GetElement( -1, nCurNode, 0, &pEdgeList);

//来自Segment.cpp中BiGraphGenerate方法
aWord.GetElement(pCur->col, -1, pCur, &pNextWords);//Get next words which begin with pCur->col
 
先分析第一个调用
第一个调用给GetElement方法的nRow传递了-1,他想干什么呢?

假设这时候变量m_bRowFirst为true,并且传递过去的nCol!=-1,那么while (pCur != NULL && (nRow != - 1 && (int)pCur->row < nRow || (nCol != -1 && (int)pCur->row == nRow && (int)pCur->col < nCol))) 等价于while (pCur != NULL && ( (int)pCur->row == -1 && (int)pCur->col < nCol))) ,注意红色部分在程序运行时永远为false(因为根本就不存在row为-1的结点),因此,上面的表达式等价于while(false)!这对于该段程序没有任何意义!

因此我们可以得到这样一个结论:如果GetElement方法的nRow参数取-1,当且仅当m_bRowFirst为false时才有意义。这时候,代码中第二个while得到执行,让我们分析一下:

while (pCur != NULL && (nCol != - 1 && (int)pCur->col < nCol || ((int)pCur->col == nCol && nRow != - 1 && (int)pCur->row < nRow))) 在nRow为-1时等价于while (pCur != NULL && ((int)pCur->col < nCol ) ,这就容易解释的多了:在如图三所示的链表中查找col=nCol 的第一个结点。

My God!

再分析第二个调用
上面的第二个调用就更让人摸不着头脑了:将pCur->col传递给GetElement的nRow参数,并将-1传递给nCol参数,这想干什么呢?要想分析清楚这个问题,没有个把钟头恐怕不行(再次佩服这些中科院的牛人们)。

按照“分析第一个调用”中的结论可知,如果GetElement方法的nCol参数取-1,当且仅当m_bRowFirst为true时才有意义。因此链表排序一定是先按照行排(如图二),此时对DynamicArray的GetElement方法的调用可以简化成:

Copy Code对方法调用进行剥离和简化
//来自Segment.cpp中BiGraphGenerate方法
aWord.GetElement(pCur->col, -1, pCur, &pNextWords);

//======================================================================

ELEMENT_TYPE CDynamicArray::GetElement(int nRow, int nCol, PARRAY_CHAIN pStart, PARRAY_CHAIN *pRet)
// 经过调用后,上面的形参对应的值分别是:nRow:pStart->col, nCol:-1, pStart, &pNextWords
// 注意,为了和下面代码中的pCur以示区分,这里用了pStart这个变量名。
{
......

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

if (pCur != NULL && ((int)pCur->row == pStart->col)
//Find the same position
{
//Find it and return the value
if (pRet != 0)
*pRet = pCur;
return pCur->value;
}
return INFINITE_VALUE;
} 
此时的意义就比较明显了,其实就是找pCur->row == pStart->col的那个结点。

可有人会问,干吗把row和col扯到一起呢?这又是一个非常复杂的问题。具体内容可以参考sinboy的《ICTCLAS分词系统研究(四)--初次切分》一文。这里简单解释如下:

如图四,这是row优先排列的一个链表:



图四

用二维表来表示图四中的链表结构如下图五所示:



图五

然后找出相邻两个词的平滑值。例如“他@说”、“的@确”、“的@确实”、“的确@实”、“的确@实在”等。如果仔细观察的话,可以注意到以下特点:例如“的确”这个词,它的col = 5,需要和它计算平滑值的有两个,分别是“实”和“实在”,你会发现这两个词的row = 5。同样道理,“确”的col = 5,它也需要和“实”与“实在”(row = 5)分别计算平滑值。

其实,这就是为什么上面分析的找pCur->row == pStart->col的那个结点的原因了。最终得到的平滑值图可以表述成图六:



图六

到此为止才明白代码作者的真正用意:

Copy Code将该调用放到上下文中再次查看
//========= 来自Segment.cpp中BiGraphGenerate方法 ===========
...... 
//取得和当前结点列值(col)相同的下个结点
aWord.GetElement(pCur->col, -1, pCur, &pNextWords);
while(pNextWords&&pNextWords->row==pCur->col)//Next words
{
//前后两个词用@分隔符连接起来
strcpy(sTwoWords,pCur->sWord);
strcat(sTwoWords,WORD_SEGMENTER);
strcat(sTwoWords,pNextWords->sWord);
......
}

小结
想不到短短一个GetElement方法中竟然综合考虑了1)row优先排序的链表;2)col优先排序的链表;3)当nRow为-1时的行为(只有m_bRowFirst为false时才能这么做,代码中没有指,所以非常容易出错!);4)当nCol为-1时的行为;5)当nRow与nCol都不为-1时的行为。

这也难怪我们会看到诸如while (pCur != NULL && (nRow != - 1 && (int)pCur->row < nRow || (nCol != -1 && (int)pCur->row == nRow && (int)pCur->col < nCol))) 这样的逻辑表达式了!我们也不得不佩服代码书写者复杂的逻辑思维能力(离散数学的谓词逻辑一定学得超级好)和给代码阅读者制造障碍的能力!类似代码在ICTCLAS中比比皆是,看来我只能恨自己脑筋太简单了!

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

上篇文章《天书般的ICTCLAS分词系统代码(一)》 说了说ICTCLAS分词系统有些代码让人无所适从,需要好一番努力才能弄明白究竟是怎么回事。尽管有很多人支持应当写简单、清晰的代码,但也有人持不同意见。主要集中在(1)如果效率高,代码复杂点也行; (2)只要注释写得好就行;(3)软件关键在思路(这我同意),就好像买了一台电脑,不管包装箱内的电脑本身怎么,一群人偏在死扣那个外面透明胶带帖歪了(这我坚决不同意,因为只有好思路出不来好电脑,好电脑还要性能稳定,即插即用的好硬件;另外天书般的代码不仅仅是透明胶带 贴歪的问题,他甚至可能意味着电脑中的绝缘胶带失效了...)。

这两天在抓紧学习ICTCLAS分词系统的思路的同时,也在消化学习它的代码实现,然而我看到的代码已经不仅仅是为了效率牺牲代码清晰度的问题了,我看到的是连作者都不知道自己真正想要做什么了,尽管程序的执行结果是正确的!

为了说明这种情况的严重性,我们需要从CQueue.cpp这个文件着手。我对CQueue这个类颇有些微辞,明明是个Queue,里面确用的是Push、Pop方法(让人感觉是个Stack而不是Queue),而且Pop方法纯粹是个大杂烩,不过这些都不是原则性问题,毕竟每个人有每个人写代码的习惯。CQueue完成的工作是制造一个排序队列(按照eWeight从小到大排序),如图一:



(图一)

在了解了这些内容的基础上,让我们看看ICTCLAS中NShortPath.cpp中的代码实现(这里我们只看ShortPath方法的实现) ,为了让问题暴露得更清晰一些,我简化了代码中一些不相关的内容。

Copy Code来自NShortPath.cpp中的ShortPath方法
int CNShortPath::ShortPath()
{
......
for (; nCurNode < m_nVertex; nCurNode++)
{
CQueue queWork;

//此处省略的代码主要负责将一些结点按照eWeight从
//小到大的顺序放入队列queWork
......

//初始化权重
for (i = 0; i < m_nValueKind; i++)
m_pWeight[nCurNode - 1][i] = INFINITE_VALUE;

i = 0;
while (i < m_nValueKind && queWork.Pop(&nPreNode, &nIndex, &eWeight) != -1)
{
//Set the current node weight and parent
if (m_pWeight[nCurNode - 1][i] == INFINITE_VALUE)
m_pWeight[nCurNode - 1][i] = eWeight;
else if (m_pWeight[nCurNode - 1][i] < eWeight)
//Next queue
{
i++; //Go next queue and record next weight
if (i == m_nValueKind)
//Get the last position
break;
m_pWeight[nCurNode - 1][i] = eWeight;
}
m_pParent[nCurNode - 1][i].Push(nPreNode, nIndex);
}
}
......
}
上面的代码作者想干什么?让我们来分析一番:

变量queWork中存放的是一个按照eWeight从小到大排列的队列, 我们不妨假设里面有4个元素,其eWeight值分别是5、6、7、8。另外我们假设变量m_nValueKind的值为2,即查找最短的两条路径(注意:这种说法不完全正确,后面会解释为什么)。在此假设基础上,我们看看程序是如何运行的:

1)将所有m_pWeight[nCurNode - 1][i]初始化为INFINITE_VALUE。

2)在第一轮循环中,我们从queWork中取出第一个元素,其eWeight为5,注意表达式“if (m_pWeight[nCurNode - 1][i] == INFINITE_VALUE) ”没有任何作用,因为我们在第一步将所有m_pWeight[nCurNode - 1][i] 均初始化成了INFINITE_VALUE,所以第一轮循环该条件一定为true。

3)在第二轮循环中,我们从queWork中取出第二个元素,其eWeight为6,此时表达式“else if (m_pWeight[nCurNode - 1][i] < eWeight) ”似乎就没有什么作用了,因为queWork是经过排序的,第二个元素的eWeight不会小于第一个eWeight,对于我们这个例子来说, 该表达式一定为true,于是就让 i++。

4)紧接着你会发现程序重新进入了步骤2)的循环。

程序执行结果如图二:



(图二)

如果真是这样的话,上面的代码似乎可以简化成:

Copy Code简化后的程序
int CNShortPath::ShortPath()
{
......
for (; nCurNode < m_nVertex; nCurNode++)
{
CQueue queWork;

//此处省略的代码主要负责将一些结点按照eWeight从
//小到大的顺序放入队列queWork
......

//初始化权重
for (i = 0; i < m_nValueKind; i++)
m_pWeight[nCurNode - 1][i] = INFINITE_VALUE;

i = 0;
while (i < m_nValueKind && queWork.Pop(&nPreNode, &nIndex, &eWeight) != -1)
{
m_pWeight[nCurNode - 1][i] = eWeight;
m_pParent[nCurNode - 1][i].Push(nPreNode, nIndex);
i++;
}
}
......
}
对于上面这个案例,简化后的程序与ICTCLAS中的程序执行结果完全相同。可作者写出如此复杂的代码应当是有理由的,难道我们对代码的分析有什么问题吗?

是的!作者将一个最为重要的内容作为隐含条件放入了代码之中,我们只能通过 if 条件以及 else if 条件中的内容推断出这个隐含条件究竟是什么,而这个隐含的条件恰恰应当是这段代码中最关键的内容。如果没能将最关键的内容展现在代码当中,而是需要读者去推断的话,我只能说连作者自己都不清楚究竟什么是最关键的东西,仅仅是让程序执行没有错误而已。

那么究竟隐藏了什么关键的内容呢?那就是“m_pWeight[nCurNode - 1][i] = eWeight”这个条件。在ShortPath方法代码中,作者用了 if 条件、 else if 条件,但都没有提及等于eWeight时程序的执行行为,他将这个留给了读者去推敲,看出来这个隐含条件就看出来了,看不出来就只能怪你自己笨了。

我们更换一组数据来看看:假设queWork里面有4个元素,其eWeight值分别是5、6、6、7,还假设变量m_nValueKind的值为2,那么ICTCLAS中ShortPath程序执行结果是什么呢?读者可以根据代码自己推敲一下,然后再看看下面的结果,与你预期的一样不一样。如图三。



(图三)

这里m_Parent[nCurNode - 1][2]是一个CQueue,里面存入了eWeight为6的两个结点。这也是为什么我前文说,NShortPath中 N 如果取2,并不意味着只有两条路径。

如果那位有耐心看到这里,对ICTCLAS中的NShortPath.cpp代码有什么感觉呢?其实要想写出一个比较清晰的代码并不复杂,只要你真正了解究竟什么是最重要的东西,对于NShortPath.cpp中的代码,只要我们稍加修改,就可以让这天书般的代码改善不少。经过调整后的代码如下:

Copy Code重新改造后的代码
int CNShortPath::ShortPath()
{
......
for (; nCurNode < m_nVertex; nCurNode++)
{
CQueue queWork;

//此处省略的代码主要负责将一些结点按照eWeight从
//小到大的顺序放入队列queWork
......

//初始化权重
for (i = 0; i < m_nValueKind; i++)
m_pWeight[nCurNode - 1][i] = INFINITE_VALUE;

if(queWork.Pop(&nPreNode, &nIndex, &eWeight) != -1)
{
for(i=0; i < m_nValueKind ; i++)
{
m_pWeight[nCurNode - 1][i] = eWeight;
do
{
m_pParent[nCurNode - 1][i].Push(nPreNode, nIndex);
if(queWork.Pop(&nPreNode, &nIndex, &new_eWeight) == -1)
goto finish;
}while(new_eWeight == eWeight)

eWeight = new_eWeight;
}
}
}
finish:
......
}
经过改造的代码使用了一个do...while循环,并利用了goto命令简化代码结构,我想这样的代码读起来应当清晰多了吧。

小结
(1)软件关键在思路,只有真正了解思路的人才能写出清晰的代码。如果代码不清晰,说明思路根本不清晰。

(2)注释写得好不如代码结构清晰。

(3)除非经过测试,否则不要为了一点效率提升而损失代码的可读性。

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