基于HMM2-Trigram字符序列标注的中文分词器Java实现

谈起基于Character-Based Generative Model的中文分词方法，普遍的印象是在Bakeoff上的成绩好，对OOV的识别率高。HanLP中实现的CRF分词器其实就是这种原理的分词器，然而CRF分词缺点也是很明显的：

一）模型体积大占内存。一个可供生产环境用的CRF模型至少使用前中后3个字符的组合做特征模板，在一两百兆的语料上训练，模型体积至少上百兆（有的分词器用gzip压缩过，看起来稍小），加载后更耗资源。HanLP原本使用DAT储存CRF中的特征函数，然而内存实在吃不消，降级为BinTrie后才维持了100MB的体积。

二）速度慢。相较于基于词语的BiGram分词器，一个拖速度的地方是特征函数的查询次数多、速度慢，另一个弱点则是概率图的节点更多（4倍文本长度个节点，4是bmes标签的个数），于是跑Viterbi的速度也慢下来了。

三）无法修改。有时候用户对分词结果不满意，却无法方便地修正它。据我所知，只有基于词语的NGram词典和词频词典可以轻松修改，包括CRF在内的其他模型都需要重新训练，或者修改代码。

有读者问我HanLP为什么不选择基于字符的HMM-BiGram作为主要的分词方法，我回答后觉得不够满意，所以利用一天的时间实现了一个基于HMM²-TriGram字符序列标注的分词器，与其他分词器（CRF分词器，基于词语的HMM-BiGram分词器）做个直观的比较，以飨读者。

毕竟水平有限，文章中有关术语可能不准确，欢迎提出宝贵意见。

二阶HMM

二阶HMM对应三阶文法模型，两个称呼的阶数相差一个，经常搞混。如果一篇文章用BiGram、二维转移矩阵做二阶隐马分词，那就不用看了。

不同于一阶HMM，二阶HMM中每个状态的概率都与前两个状态有关。

t3是当前状态，同理定义t1和t2。

训练

训练其实就是以3个顺序词语为一个视窗，统计123-Gram的频次。

/**
 * 让模型观测一个句子
 * @param wordList
 */
public void learn(List<Word> wordList)
{
    LinkedList<char[]> sentence = new LinkedList<char[]>();
    for (IWord iWord : wordList)
    {
        String word = iWord.getValue();
        if (word.length() == 1)
        {
            sentence.add(new char[]{word.charAt(0), 's'});
        }
        else
        {
            sentence.add(new char[]{word.charAt(0), 'b'});
            for (int i = 1; i < word.length() - 1; ++i)
            {
                sentence.add(new char[]{word.charAt(i), 'm'});
            }
            sentence.add(new char[]{word.charAt(word.length() - 1), 'e'});
        }
    }
    // 转换完毕，开始统计
    char[][] now = new char[3][];   // 定长3的队列
    now[1] = bos;
    now[2] = bos;
    tf.add(1, bos, bos);
    tf.add(2, bos);
    for (char[] i : sentence)
    {
        System.arraycopy(now, 1, now, 0, 2);
        now[2] = i;
        tf.add(1, i);   // uni
        tf.add(1, now[1], now[2]);   // bi
        tf.add(1, now);   // tri
    }
}

有了tri的频次，按照二阶隐马的概率最大化公式：

原本就可以计算的，然而按照Thorsten Brants的说法，由于数据的稀疏性，导致tri-gram的实例数目不够，无法达到令人满意的效果。所以他提出了TnT(Trigrams'n'Tags)标注器，将uni和bi补充进来起平滑作用：

其中三个系数，可以通过如下算法在线性时间内计算出来：

在HanLP中对应如下代码：

/**
 * 观测结束，开始训练
 */
public void train()
{
    double tl1 = 0.0;
    double tl2 = 0.0;
    double tl3 = 0.0;
    for (String key : tf.d.keySet())
    {
        if (key.length() != 6) continue;    // tri samples
        char[][] now = new char[][]
                {
                        {key.charAt(0), key.charAt(1)},
                        {key.charAt(2), key.charAt(3)},
                        {key.charAt(4), key.charAt(5)},
                };
        double c3 = div(tf.get(now) - 1, tf.get(now[0], now[1]) - 1);
        double c2 = div(tf.get(now[1], now[2]) - 1, tf.get(now[1]) - 1);
        double c1 = div(tf.get(now[2]) - 1, tf.getsum() - 1);
        if (c3 >= c1 && c3 >= c2)
            tl3 += tf.get(now);
        else if (c2 >= c1 && c2 >= c3)
            tl2 += tf.get(now);
        else if (c1 >= c2 && c1 >= c3)
            tl1 += tf.get(now);
    }

    l1 = div(tl1, tl1 + tl2 + tl3);
    l2 = div(tl2, tl1 + tl2 + tl3);
    l3 = div(tl3, tl1 + tl2 + tl3);
}

这部分详细的理论请参考《TnT — A Statistical Part-of-Speech Tagger .pdf》。

标注

转移矩阵是三维的，在实现的时候（主要参考了snownlp的Python代码），采用了动态计算的方式计算转移概率：

/**
 * 求概率
 * @param s1 前2个状态
 * @param s2 前1个状态
 * @param s3 当前状态
 * @return 序列的概率
 */
double log_prob(char[] s1, char[] s2, char[] s3)
{
    double uni = l1 * tf.freq(s3);
    double bi = div(l2 * tf.get(s2, s3), tf.get(s2));
    double tri = div(l3 * tf.get(s1, s2, s3), tf.get(s1, s2));
    if (uni + bi + tri == 0)
        return inf;
    return Math.log(uni + bi + tri);
}

有了转移概率，之后就可以Viterbi解码了。

由于转移概率与前两个状态有关，所以需要为每个状态准备一个二维的dp数组（原Python代码用了一个dict存路径，虽然代码短，但运行起来真的奇慢无比），另外加上状态本身的下标，dp数组一共3维：

// link[i][s][t] := 第i个节点在前一个状态是s，当前状态是t时，前2个状态的tag的值
int[][][] link = new int[charArray.length][4][4];

不过，第一个字和第二字有些特殊，它们的前2个状态不存在，越界了。所以这时候特殊处理，使用bos状态替代不存在的状态计算概率：

// 第一个字，只可能是bs
for (int s = 0; s < 4; ++s)
{
    double p = (s == 1 || s == 2) ? inf : log_prob(bos, bos, new char[]{charArray[0], id2tag[s]});
    first[s] = p;
}

// 第二个字，尚不能完全利用TriGram
for (int f = 0; f < 4; ++f)
{
    for (int s = 0; s < 4; ++s)
    {
        double p = first[f] + log_prob(bos, new char[]{charArray[0], id2tag[f]}, new char[]{charArray[1], id2tag[s]});
        now[f][s] = p;
        link[1][f][s] = f;
    }
}

从第三个字开始就好办了：

// 第三个字开始，利用TriGram标注
double[][] pre = new double[4][4];
for (int i = 2; i < charArray.length; i++)
{
    // swap(now, pre)
    double[][] _ = pre;
    pre = now;
    now = _;
    // end of swap
    for (int s = 0; s < 4; ++s)
    {
        for (int t = 0; t < 4; ++t)
        {
            now[s][t] = -1e20;
            for (int f = 0; f < 4; ++f)
            {
                double p = pre[f][s] + log_prob(new char[]{charArray[i - 2], id2tag[f]},
                                                new char[]{charArray[i - 1], id2tag[s]},
                                                new char[]{charArray[i],     id2tag[t]});
                if (p > now[s][t])
                {
                    now[s][t] = p;
                    link[i][s][t] = f;
                }
            }
        }
    }
}

循环结束后，now矩阵中对应16条路径的最终得分，从中挑出得分最高的那一条，通过link数组还原该路径：

double score = inf;
int s = 0;
int t = 0;
for (int i = 0; i < 4; i++)
{
    for (int j = 0; j < 4; j++)
    {
        if (now[i][j] > score)
        {
            score = now[i][j];
            s = i;
            t = j;
        }
    }
}
for (int i = link.length - 1; i >= 0; --i)
{
    tag[i] = id2tag[t];
    int f = link[i][s][t];
    t = s;
    s = f;
}
return tag;

二阶HMM分词

bmes合并

有了标签，合并就很简单了。我采用了正向合并的方式：

char[] tag = model.tag(sentence);
List<Term> termList = new LinkedList<Term>();
int offset = 0;
for (int i = 0; i < tag.length; offset += 1, ++i)
{
    switch (tag[i])
    {
        case 'b':
        {
            int begin = offset;
            while (tag[i] != 'e')
            {
                offset += 1;
                ++i;
                if (i == tag.length)
                {
                    break;
                }
            }
            if (i == tag.length)
            {
                termList.add(new Term(new String(sentence, begin, offset - begin), null));
            }
            else
                termList.add(new Term(new String(sentence, begin, offset - begin + 1), null));
        }
        break;
        default:
        {
            termList.add(new Term(new String(sentence, offset, 1), null));
        }
        break;
    }
}

return termList;

你可能会很奇怪，怎么只看到了b和e标签，s和m标签在哪里呢？

这是因为，HMM标注的结果不一定是合法的（甚至连CRF的标注结果都不一定合法），所谓的不合法，指的是可能出现bbse这种不闭合的现象。如果严格按照b开始，m入栈，e出栈的逻辑来是会出问题的。

直观评测

我一直很反对用封闭测试集测成绩，同时我又拿不到较好的开放测试集，所以只是从直观的结果做一个评测：

HanLP.Config.ShowTermNature = false;    // 关闭词性显示
Segment segment = new HMMSegment();
String[] sentenceArray = new String[]
        {
                "HanLP是由一系列模型与算法组成的Java工具包，目标是普及自然语言处理在生产环境中的应用。",
                "高锰酸钾，强氧化剂，紫红色晶体，可溶于水，遇乙醇即被还原。常用作消毒剂、水净化剂、氧化剂、漂白剂、毒气吸收剂、二氧化碳精制剂等。", // 专业名词有一定辨识能力
                "《夜晚的骰子》通过描述浅草的舞女在暗夜中扔骰子的情景,寄托了作者对庶民生活区的情感",    // 非新闻语料
                "这个像是真的[委屈]前面那个打扮太江户了，一点不上品...@hankcs",                       // 微博
                "鼎泰丰的小笼一点味道也没有...每样都淡淡的...淡淡的，哪有食堂2A的好次",
                "克里斯蒂娜·克罗尔说：不，我不是虎妈。我全家都热爱音乐，我也鼓励他们这么做。",
                "今日APPS：Sago Mini Toolbox培养孩子动手能力",
                "财政部副部长王保安调任国家统计局党组书记",
                "2.34米男子娶1.53米女粉丝 称夫妻生活没问题",
                "你看过穆赫兰道吗",
                "乐视超级手机能否承载贾布斯的生态梦"
        };
for (String sentence : sentenceArray)
{
    List<Term> termList = segment.seg(sentence);
    System.out.println(termList);
}

// 测个速度
String text = "江西鄱阳湖干枯，中国最大淡水湖变成大草原";
System.out.println(segment.seg(text));
long start = System.currentTimeMillis();
int pressure = 1000;
for (int i = 0; i < pressure; ++i)
{
    segment.seg(text);
}
double costTime = (System.currentTimeMillis() - start) / (double)1000;
System.out.printf("HMM2分词速度：%.2f字每秒\n", text.length() * pressure / costTime);
// 与其他分词器作比较
System.gc();
DemoBasicTokenizer.main(null);
System.gc();
DemoHighSpeedSegment.main(null);

结果

速度

HMM2分词速度：             22172.95字每秒
BasicTokenizer分词速度： 1785145.04字每秒
SpeedTokenizer分词速度：17241379.31字每秒

同一台机器（AMD A10-5800K）上，其他分词器的速度要快很多。（注：由于HMM2模型很大，所以跑这个例子必须给足内存）

效果

HMM2:

[HanLP是由一系列, 模型, 与, 算法, 组成, 的, Java工具, 包, ，, 目标, 是, 普及, 自然, 语言, 处理, 在, 生产, 环境, 中, 的, 应用, 。]
[高锰酸钾, ，, 强氧化剂, ，, 紫红色, 晶体, ，, 可, 溶于, 水, ，, 遇乙醇, 即, 被, 还原, 。, 常, 用作, 消毒, 剂, 、, 水, 净化剂, 、, 氧化剂, 、, 漂白剂, 、, 毒气, 吸收, 剂, 、, 二氧化碳, 精制剂, 等, 。]
[《, 夜晚, 的, 骰子, 》, 通过, 描述, 浅, 草, 的, 舞女, 在, 暗夜, 中, 扔骰子, 的, 情景, ,, 寄托, 了, 作者, 对庶民, 生活区, 的, 情感]
[这个, 像, 是, 真的, [, 委屈, ], 前面, 那个, 打扮, 太, 江, 户, 了, ，, 一点, 不, 上品, ., ., ., @, hankcs]
[鼎泰丰, 的, 小笼, 一点, 味道, 也, 没有, ., ., ., 每样, 都, 淡淡, 的, ., ., ., 淡淡的, ，, 哪, 有, 食堂, 2A, 的, 好次]
[克里斯蒂娜·克罗尔, 说, ：, 不, ，, 我, 不是, 虎妈, 。, 我, 全家, 都, 热爱, 音乐, ，, 我, 也, 鼓励, 他们, 这么, 做, 。]
[今日, APPS, ：, Sago Mini Toolbox培养, 孩子, 动手, 能力]
[财政部, 副部长, 王保安, 调任, 国家, 统计局, 党组, 书记]
[2, ., 34, 米, 男子, 娶, 1, ., 53, 米, 女, 粉丝,  称夫妻, 生活, 没问题]
[你, 看过, 穆赫, 兰, 道, 吗]
[乐, 视, 超级, 手机, 能否, 承载, 贾布斯, 的, 生态, 梦]

对比DemoCRFSegment的输出：

[HanLP, 是, 由, 一系列, 模型, 与, 算法, 组成, 的, Java, 工具包, ，目标, 是, 普及, 自然, 语言, 处理, 在, 生产, 环境, 中, 的, 应用, 。]
[高锰酸钾, ，强氧化剂, ，紫红色, 晶体, ，可, 溶于, 水, ，遇, 乙醇, 即, 被, 还原, 。常, 用作, 消毒剂, 、, 水, 净化剂, 、, 氧化剂, 、, 漂白剂, 、, 毒气, 吸收剂, 、, 二氧化碳, 精制剂, 等, 。]
[《, 夜晚, 的, 骰子, 》, 通过, 描述, 浅草, 的, 舞女, 在, 暗夜, 中, 扔, 骰子, 的, 情景, ,寄托, 了, 作者, 对, 庶民, 生活区, 的, 情感]
[这个, 像, 是, 真的, [, 委屈, ], 前面, 那个, 打扮, 太, 江户, 了, ，一点, 不, 上品, ., ., ., @, hankcs]
[鼎泰丰, 的, 小笼, 一点, 味道, 也, 没有, ., ., ., 每样, 都, 淡淡的, ., ., ., 淡淡的, ，哪, 有, 食堂, 2, A, 的, 好次]
[克里斯蒂娜·克罗尔, 说, ：, 不, ，我, 不是, 虎妈, 。我, 全家, 都, 热爱, 音乐, ，我, 也, 鼓励, 他们, 这么, 做, 。]
[今日, APPS, ：, Sago,  , Mini,  , Toolbox, 培养, 孩子, 动手, 能力]
[财政部, 副部长, 王保安, 调任, 国家, 统计局, 党组, 书记]
[2.34, 米, 男子, 娶, 1.53, 米, 女, 粉丝,  , 称, 夫妻, 生活, 没问题]
[你, 看过, 穆赫兰道, 吗]
[乐, 视, 超级, 手机, 能否, 承载, 贾布斯, 的, 生态, 梦]

可以看出从分词效果来看，HMM2分词器倾向于将未知的单字粘合到一起，显然HMM没有CRF那么聪明，很多地方都粘错了。

结论

无论是从速度还是效果来看，我都认为二阶HMM不适合用来分词。CRF由于效果突出，所以在对速度要求不高的场合还有一点用武之地，但是二阶HMM显然是个尴尬的角色。更不用提一阶HMM的效果了，那些执着于“单字发射概率”的分词器，应当向高阶HMM乃至CRF发展。这就是我对基于字符标注的中文分词器的一点浅显看法，欢迎指正。

关于HanLP

HanLP目前的分词器架构如下：

HanLP希望做成所有分词器的超集，通过比较各种分词算法、各种NLP模型、各种数据结构，最终得出一个趋向于完美的汉语言处理工具。欢迎大家fork，提出宝贵意见！

Reference

TnT — A Statistical Part-of-Speech Tagger .pdf

Which is More Suitable for Chinese Word Segmentation the Generative Model or the Discriminative One.pdf

 知识共享署名-非商业性使用-相同方式共享：码农场 » 基于HMM2-Trigram字符序列标注的中文分词器Java实现