放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

CRF分词的纯Java实现

目录

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

开源项目

本文代码已集成到HanLP中开源:http://www.hankcs.com/nlp/hanlp.html

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分词器将其拆分为一张表:

商	null	
品	null	
和	null	
服	null	
务	null	

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

代码

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

/**
 * 维特比后向算法标注
 *
 * @param table
 */
public void tag(Table table)
{
    int size = table.size();
    int tagSize = id2tag.length;
    double[][] net = new double[size][tagSize];
    for (int i = 0; i < size; ++i)
    {
        LinkedList<double[]> scoreList = computeScoreList(table, i);
        for (int tag = 0; tag < tagSize; ++tag)
        {
            net[i][tag] = computeScore(scoreList, tag);
        }
    }

    if (size == 1)
    {
        double maxScore = -1e10;
        int bestTag = 0;
        for (int tag = 0; tag < net[0].length; ++tag)
        {
            if (net[0][tag] > maxScore)
            {
                maxScore = net[0][tag];
                bestTag = tag;
            }
        }
        table.setLast(0, id2tag[bestTag]);
        return;
    }

    int[][] from = new int[size][tagSize];
    for (int i = 1; i < size; ++i)
    {
        for (int now = 0; now < tagSize; ++now)
        {
            double maxScore = -1e10;
            for (int pre = 0; pre < tagSize; ++pre)
            {
                double score = net[i - 1][pre] + matrix[pre][now] + net[i][now];
                if (score > maxScore)
                {
                    maxScore = score;
                    from[i][now] = pre;
                }
            }
            net[i][now] = maxScore;
        }
    }
    // 反向回溯最佳路径
    double maxScore = -1e10;
    int maxTag = 0;
    for (int tag = 0; tag < net[size - 1].length; ++tag)
    {
        if (net[size - 1][tag] > maxScore)
        {
            maxScore = net[size - 1][tag];
            maxTag = tag;
        }
    }

    table.setLast(size - 1, id2tag[maxTag]);
    maxTag = from[size - 1][maxTag];
    for (int i = size - 2; i > 0; --i)
    {
        table.setLast(i, id2tag[maxTag]);
        maxTag = from[i][maxTag];
    }
    table.setLast(0, id2tag[maxTag]);
}

标注结果

标注后将table打印出来:

CRF标注结果
商	B	
品	E	
和	S	
服	B	
务	E

最终处理

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

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

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

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

新词识别

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

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

输出:

CRF标注结果
你	S	
看	S	
过	S	
穆	B	
赫	M	
兰	M	
道	E	
吗	S	
[你/rr, 看/v, 过/uguo, 穆赫兰道/null, 吗/y]

null表示新词。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » CRF分词的纯Java实现

分享到:更多 ()

评论 17

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #9

    您好:我想问一下您生成crf模型,是用crf++生成的吗?您的用于训练的数据在哪里可以找到?谢谢。

    大道至公6个月前 (01-04)回复
  2. #8

    你好 ,有个问题。下载1.2.7的代码,和包。 int index = ArrayTool.binarySearch(child, node); 多处ArrayTool这个工具的方法,报错,显示参数不匹配。还有 MathTools.calculateWeight(from, to) MathTools这个工具也是报错参数不匹配 请问是什么原因啊?还有能否给下 hanlp.jar 的源码? 盼望回复!

    啦啦啦2年前 (2015-12-02)回复
    • 应该是你的编译器JDK有问题,请在https://github.com/hankcs/HanLP/issues 上提问,并详细描述编译环境。

      hankcs2年前 (2015-12-02)回复
  3. #7

    博主,在tag方法中,利用维特比方法计算字符串的标注路径时,有一段代码是if (matrix[pre][now] <= 0) continue; 为什么tag的转移概率<0,就略过了呢?

    starkingout2年前 (2015-08-24)回复
  4. #6

    博主,tag方法中,直接设置int preTag = bestTag,并将其用于计算下一个位置的标记,这样得到的整个标记,有可能不是全局最有解吧?

    inteldt2年前 (2015-07-11)回复
  5. #5

    博主你好,看完了你的博客 我有个问题,请问怎么用crf加自定义字典结合的方法来实现分词,自定义词典包括歧义词,停用词与普通词典

    刘泽锦2年前 (2015-06-25)回复
    • 这个比较麻烦,这里的CRF是基于字的,除非你想一种算法出来,从训练的时候就开始利用词典

      hankcs2年前 (2015-06-28)回复
  6. #4

    博主好!我根据实验任务的需要,对crf的基本模型进行了修改,但是不知道如何去实现。能否提供一些思路?谢谢!

    县长2年前 (2015-06-09)回复
  7. #3

    无意中发现了贵站,震憾于博主的才能,更震憾于博主在浮躁盛行的今天能静心学习。
    贵站已收藏。
    友情提醒:CRFSegment的enableSpeechTag方法已被更新为“enablePartOfSpeechTagging”
    同时也有疑问需要请教:
    /**
    * 创建一个分词器<br>
    * 这是一个工厂方法<br>
    * 与直接new一个分词器相比,使用本方法的好处是,以后HanLP升级了,总能用上最合适的分词器
    *
    * @return 一个分词器
    */
    public static Segment newSegment()
    {
    return new ViterbiSegment(); // Viterbi分词器是目前效率和效果的最佳平衡
    }
    该方法在类中没有被调用,对于使用HanLP的开发人员来说,也有点多余,严格意义上,这也并不是一个工厂方法。
    个人觉得,可以为HanLP设定一个默认的分词器(如:ViterbiSegment),然后为使用HanLP的开发人员提供一个自定义分词器的方法,但HanLP真正执行分词操作的是StandardTokenizer,有点费解。
    见笑。

    另外,很详尽的注释,赞一个。 [good]

    Runner2年前 (2015-05-20)回复
    • 过奖了,谢谢提醒。

      其实newSegment()一直在被广泛调用,比如StandardTokenizer中

      /**
      * 预置分词器
      */
      public static final Segment SEGMENT = HanLP.newSegment();

      几乎所有XYZTokenizer都用这个方法新建分词器。这个方法的目的就是统一整个库的默认分词器。
      如果自定义分词器的方法指的是override的话,那么就得考虑用户的代码的副作用,他会不会把text的charArray改动了?他会不会把中间结果放到类的域里面导致分词器不再线程安全?之类的问题还是挺麻烦的。所以HanLP更多地是提供enableXYZ的配置方法,也更多地“面向过程”(运行效率高,容易保证线程安全性)。
      如果你有兴趣的话,欢迎fork一份尝试重构一下,然后向我提交pull request。

      hankcs2年前 (2015-05-21)回复
      • 好吧,我当真了。有时间请查一下,欢迎拍砖 [呵呵]

        Runner2年前 (2015-05-21)回复
        • 感谢pull request,开源就是征求大家的意见,互相学习 [握手]

          hankcs2年前 (2015-05-21)回复
  8. #2

    还是没看懂!!!!~~~~~~~~~~~~~~~

    刘璟2年前 (2015-05-05)回复
  9. #1

    代码有吗?

    付超3年前 (2014-12-22)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机