首页 > 代码库 > CRF分词的纯Java实现

CRF分词的纯Java实现

与基于隐马尔可夫模型的最短路径分词、N-最短路径分词相比,基于随机条件场(CRF)的分词对未登录词有更好的支持。本文(HanLP)使用纯Java实现CRF模型的读取与维特比后向解码,内部特征函数采用 双数组Trie树(DoubleArrayTrie)储存,得到了一个高性能的中文分词器。

CRF简介

CRF是序列标注场景中常用的模型,比HMM能利用更多的特征,比MEMM更能抵抗标记偏置的问题。

技术分享

CRF训练

这类耗时的任务,还是交给了用C++实现的CRF++。关于CRF++输出的CRF模型,请参考《CRF++模型格式说明》。

CRF解码

解码采用维特比算法实现。并且稍有改进,用中文伪码与白话描述如下:

首先任何字的标签不仅取决于它自己的参数,还取决于前一个字的标签。但是第一个字前面并没有字,何来标签?所以第一个字的处理稍有不同,假设第0个字的标签为X,遍历X计算第一个字的标签,取分数最大的那一个。

如何计算一个字的某个标签的分数呢?某个字根据CRF模型提供的模板生成了一系列特征函数,这些函数的输出值乘以该函数的权值最后求和得出了一个分数。该分数只是“点函数”的得分,还需加上“边函数”的得分。边函数在本分词模型中简化为f(s‘,s),其中s‘为前一个字的标签,s为当前字的标签。于是该边函数就可以用一个4*4的矩阵描述,相当于HMM中的转移概率。

实现了评分函数后,从第二字开始即可运用维特比后向解码,为所有字打上BEMS标签。

实例

还是取经典的“商品和服务”为例,首先HanLP的CRFSegment分词器将其拆分为一张表:

1
2
3
4
5
商   null   
品   null   
和   null   
服   null   
务   null   

null表示分词器还没有对该字标注。

代码

上面说了这么多,其实我的实现非常简练:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 维特比后向算法标注
 * @param table
 */
public void tag(Table table)
{
    int size = table.size();
    double bestScore = 0;
    int bestTag = 0;
    int tagSize = id2tag.length;
    LinkedList<double[]> scoreList = computeScoreList(table, 0);    // 0位置命中的特征函数
    for (int i = 0; i < tagSize; ++i)   // -1位置的标签遍历
    {
        for (int j = 0; j < tagSize; ++j)   // 0位置的标签遍历
        {
            double curScore = matrix[i][j] + computeScore(scoreList, j);
            if (curScore > bestScore)
            {
                bestScore = curScore;
                bestTag = j;
            }
        }
    }
    table.setLast(0, id2tag[bestTag]);
    int preTag = bestTag;
    // 0位置打分完毕,接下来打剩下的
    for (int i = 1; i < size; ++i)
    {
        scoreList = computeScoreList(table, i);    // i位置命中的特征函数
        bestScore = Double.MIN_VALUE;
        for (int j = 0; j < tagSize; ++j)   // i位置的标签遍历
        {
            double curScore = matrix[preTag][j] + computeScore(scoreList, j);
            if (curScore > bestScore)
            {
                bestScore = curScore;
                bestTag = j;
            }
        }
        table.setLast(i, id2tag[bestTag]);
        preTag = bestTag;
    }
}

标注结果

标注后将table打印出来:

1
2
3
4
5
6
CRF标注结果
商   B  
品   E  
和   S  
服   B  
务   E

最终处理

将BEMS该合并的合并,得到:

1
[商品/null, 和/null, 服务/null]

然后将词语送到词典中查询一下,没查到的暂时当作nx,并记下位置(因为这是个新词,为了表示它的特殊性,最后词性设为null),再次使用维特比标注词性:

1
[商品/n, 和/cc, 服务/vn]

新词识别

CRF对分词有很好的识别能力,比如:

1
2
3
CRFSegment segment = new CRFSegment();
segment.enableSpeechTag(true);
System.out.println(segment.seg("你看过穆赫兰道吗"));

输出:

1
2
3
4
5
6
7
8
9
10
CRF标注结果
你   S  
看   S  
过   S  
穆   B  
赫   M  
兰   M  
道   E  
吗   S  
[你/rr, 看/v, 过/uguo, 穆赫兰道/null, 吗/y]

null表示新词。

CRF分词的纯Java实现