本文主要介绍使用CRF(Conditional Random Field，条件随机场)来进行中文分词的工作，着重介绍解码器的实现。

什么是CRF

CRF是现在比较流行的序列标注算法，其他的序列标注算法例如HMM(Hidden Makov Model，隐马)/MEMM(Maximum-entropy Markov model，最大熵)，三者主要的差别在于HMM考虑转移概率(transition probability)和生成概率(emission probability)，二者分布的计算是独立的；MEMM和HMM类似，但是其转移概率是基于输出的条件概率；CRF更为复杂，其特征抽取自全部篇幅(具体由特征函数确定)，标注的考量更全局化。具体训练上，HMM比较容易，使用最大似然在语料中进行统计即可。
上面三种方法都可以进行序列标注，序列标注在NLP里有很多应用，比如中文分词，词性标注，命名实体分析，chunk（分块？不知道这个中文一般是怎么翻译的）等等。CRF一个比较显著的优点在于对于未登录词的识别效果不错，这里可能有一个比较容易混淆的点，未登录词指的是训练语料中没出现的词，并不是所谓的“新词”（比如网络流行语）。假如新词的构词法和训练语料不太相似，我认为识别的效果不会太理想。（新词的识别有一些其他的方法）

工具与模型训练

本文介绍的方法使用到的工具方法如下，
语料：北大人民日报语料，6个月，其中前5个月用于训练，第6个月做测试
工具：crf++用于训练模型，java写了一个解码和分词的程序，python脚本用于把语料组织成crf++的格式。

crf++网上有不少教程，其本身也比较容易上手，就不多介绍了。
crf++训练过程中的内存管理其实是有一些问题的，我感觉应该是词语统计过程中有一部分内存没有释放，c++基础也不太好，没去深究代码，在一台内存大点的机器上跑就好了。还可以考虑的一个trick是训练时候使用 -f 参数，过滤掉频率过小的特征。
训练结果为一个模型文件，模型包含5个部分：
1. 文件头，包含模型信息，比如maxid是模型中特征的数量
2. 标签集合，在分词这个任务里我使用了5个tag，B/E/M1/M2/S
3. 特征模板，最后一个如果是B表示使用Bigram特征
4. 特征索引，为一个整数和一个特征。比如 345 U00:严 的意思是特征 U00:严 的索引开始于345，即F(B|U00:严)=feature_values[345]，同理，2中的下一个标签E在这个特征上对应的值的索引是346
5. 特征对应的值，为一个浮点数。通过上面的索引来查找。

一个可能的训练模型看起来是这样的,

version: 100
<br>cost-factor: 1
<br>maxid: 6512970
xsize: 1

B
E
M1
M2
S

U00:%x[-2,0]
U01:%x[-1,0]
U02:%x[0,0]
U03:%x[1,0]
U04:%x[2,0]
U05:%x[-2,0]/%x[-1,0]/%x[0,0]
U06:%x[-1,0]/%x[0,0]/%x[1,0]
U07:%x[0,0]/%x[1,0]/%x[2,0]
U08:%x[-1,0]/%x[0,0]
U09:%x[0,0]/%x[1,0]
B

0 B
25 U00:_B-1
30 U00:_B-2
35 U00:±
40 U00:·
45 U00:×
50 U00:—
55 U00:‘
60 U00:’
65 U00:“
70 U00:”
75 U00:…
80 U00:‰
85 U00:℃
...

0.0001855083586074
-0.0000550467674851
-0.0000523310422437
-0.0000072055131253
-0.0000045287760644
0.0001191120946419
-0.0000618634324638
-0.0000507848415768
-0.0000074019745383
-0.0000044408072127
0.0001244910548052
-0.0002948948488240
-0.0002653346476889
-0.0000384288559099
-0.0000228130525827
0.0006214713986071
-0.0000890289555236
...

根据输入和特征模板怎么生成特征我就不细说了，看一下就明白了。B_1表示句首的前一位。

解码

因为公司的系统是用Java开发的，所以为了分词专门用Java写了一个分词器，主要就是模型的解码。

解码首先要把模型读入内存中，这其实是一个比较tricky的问题，网上也没有太多的介绍。存储要能实现o(1)的查找速度，这样才能保证分词的效率。对于序列标注问题来说，使用比较多的方法是用DATrie来实现，但是我考虑了一下，我要查找的内容(形如U00:丛)比较规则，除了前面特征模板的索引以外(U00)，剩下的部分比较短（最长三个字），如果构建Trie树，其形状也是很扁平的。所以影响效率更主要的因素还是哈希函数的效率。最终我没使用DATrie(懒得写了。。。)，而是设计了一种查找结构，首先对特征模板的索引进行区分(只有10个特征模板)，针对每一个特征模板，使用一个哈希表来储存其中的字符和其对应的整数索引。每一个哈希表大概有10w个键值对，对性能的提高可以直接根据键值对的数量来优化哈希函数。

模型读入以后就比较容易了。对一个输入句子进行分词包含以下步骤，
1. 句子字符进行预处理。数字的处理，标点的处理，半角全角的转换。
2. 根据特征模板对每一个字符生成一系列特征。
3. 初始化一个m*n的矩阵，m为句子中字符的数量，n为tag的数量。
4. 根据特征函数计算矩阵中每一个node的得分/概率。
5. 如果有bigram feature，计算输出tag的序列，可以使用viterbi算法，很简单。
6. 输出tag序列，根据序列提供分词结果。

然后给公司里的编辑们写一个GUI。。。不得不说，Java写出来的GUI蛮丑的。

评估

分词速度比较一般，查找的部分还有可以优化的地方。
现在的分词速度大概是40字符/ms左右，一般情况下够用了。
（不够用的时候，开两个进程，反正内存消耗也不大，还不够？开五个。。。）
使用人民日报第6个月的语料进行测试，
字标注的准确率97.57%；词语的准确率和召回都是97.16%左右。看起来还不错。

好久没写Java了写起来看着。。。好长。