1. 前言

THULAC所采用的分词模型为结构化感知器（Structured Perceptron, SP），属于两种CWS模型中的Character-Based Model，将中文分词看作为一个序列标注问题：对于字符序列C=cn1，找出最有可能的标注序列Y=yn1。定义score函数S(Y,C)为在C的情况下标注序列为Y的得分。SP以最大熵准则建模score函数，分词结果则等同于最大score函数所对应的标注序列。记在时刻tt的状态为y的路径yt1所对应的score函数最大值为

那么，则有递推式

其中，wy′,y为转移特征(y′,y)所对应的权值，F(yt+1=y,C)为特征模板的特征值的加权之和：

其中，αi为特征fi(yt+1=y,C)所对应的权重。

2. 分解

以下源码分析基于最近lite_v1_2版本THULAC-Java 。

训练模型

seg_only模式（只分词没有POS）对应的训练模型的数据包括三种：权重数据cws_model.bin、序列标注类别数据cws_label.txt、特征数据cws_dat.bin。权重数据对应于类character.CBModel，其格式如下：

int l_size (size of the labels): 4

int f_size (size of the features): 2453880

int[] ll_weights // weights of (label, label):

-42717

39325

-33792

...

-31595

26794

int[] fl_weights //weights of (feature, label):

-4958

2517

5373

-2930

-286

0

...

训练模型中的标注类别（label）共有4类“0”, “2”, “3”, “1”（见文件cws_label.txt），分别对应于中文分词中的标注类别B、E、S、M；这一点可以在C++版的thulac_base.h找到映照：

enum POC{

    kPOC_B='0',

    kPOC_M='1',

    kPOC_E='2',

    kPOC_S='3'

};

但是，THULAC在解码时用到的label，则是BMES在特征数据文件的索引位置，因此标注类别B、M、E、S映射到整数0、3、1、2；这些映射可以在后面的构建label转移矩阵labelTransPre及Viterbi解码的代码中找到印证。那么，则B转移到B的权重wB,B=w0,0=−42717，B转移到E的权重wB,E=w0,1=39325，B转移到S的权重wB,S=w0,2=−33792。此即与实际情况相对应，B只能会转移到M和E，而不可能转移到S。

权重数据中标识对应于特征模板的feature共有2453880个。那么，label与label之间的组合共有4×4=16种，即ll_weights的长度为16；feature与label之间的组合共有4×2453880=9815520种，即fl_weights的长度为9815520。

特征数据则是用双数组Trie树DAT来存储的，对应于类base.Dat，其格式如下：

int datSize: 7643071

Vector<Entry> dat：

0 0

0 1

0 51

0 52

...

25053 0

5 25088

...

datSize为dat的长度，等于7643071；类Entry表示双数组中的的base与check值。那么，问题来了：一是特征长什么样？二是知道特征如何得到对应的权重？三是为什么DAT的长度远大于字符特征的个数2453880？

特征

首先，我们来看看特征长什么样，参看特征生成方法CBNGramFeature::featureGeneration：

public void featureGeneration(String seq, Indexer<String> indexer, Counter<String> bigramCounter){

  ...

  for(int i = 0; i < seq.length(); i ++){

    mid = seq.charAt(i);

    left = (i > 0) ? (seq.charAt(i-1)) : (SENTENCE_BOUNDARY);

    ...

    key = ((char)mid)+((char)SEPERATOR) + "1";

    key = ((char)left)+((char)SEPERATOR) + "2";

    key = ((char)right)+((char)SEPERATOR) + "3";

    key = ((char)left)+((char)mid)+((char)SEPERATOR) + "1";

    key = ((char)mid)+((char)right)+((char)SEPERATOR) + "2";

    key = ((char)left2)+((char)left)+((char)SEPERATOR) + "1"; // should be + "3"

    key = ((char)right)+((char)right2)+((char)SEPERATOR) + "1"; // should be + "4"

    ...

  }

}

特征模板共定义7个字符特征：3个unigram字符特征与4个bigram字符特征。在处理特征时，字符后面加上了空格，然后在加上标识1、2、3、4，用以区分特征的种类。值得指出的是Java版作者写错了最后两个bigram特征，应该是加上数字3、4；在C++版的函数NGramFeature::feature_generation可找到印证。通过特征模板定义，我们发现THULAC既考虑到了前面2个字符(各种组合)对当前字符标注的影响，也考虑到了后面2个字符的影响。

接下来，为了解决第二个问题，我们来看看用Viterbi算法解码前的代码——THULAC先将特征值的加权之和F(ti,C)计算出来，然后按label次序逐个放入values[i*4+label] 中。主干代码如下：

/**

 * @param datSize DAT size

 * @param ch1 first character

 * @param ch2 second character

 * @return [unigram字符特征的base + " ", bigram字符特征的base + " "]

 */

public Vector<Integer> findBases(int datSize, int ch1, int ch2) {

  uniBase = dat.get(ch1).base + SEPERATOR;

  biBase = dat.get(ind).base + SEPERATOR;

}



/**

 * 按label 0,1,2,3 将特征值的加权之和放入values数组中

 * @param valueOffset values数组偏置量，在putValues中调用时按步长4递增

 * @param base unigram字符特征或bigram字符特征的base加上空格的index

 * @param del 标识'1', '2', '3', '4' -> 49, 50, 51, 52

 * @param pAllowedLable null

 */

private void addValues(int valueOffset, int base, int del, int[] pAllowedLable) {

  int ind = dat.get(base).base + del; // 加上标识del后特征的index

  int offset = dat.get(ind).base; // 特征的base

  int weightOffset = offset * model.l_size; // 特征数组的偏移量

  int allowedLabel;

  if (model.l_size == 4) {

    values[valueOffset] += model.fl_weights[weightOffset];

    values[valueOffset + 1] += model.fl_weights[weightOffset + 1];

    values[valueOffset + 2] += model.fl_weights[weightOffset + 2];

    values[valueOffset + 3] += model.fl_weights[weightOffset + 3];

  }

}



public int putValues(String sequence, int len) {

  int base = 0;

  for (int i = 0; i < len; i++) {

    int valueOffset = i * model.l_size;

    if ((base = uniBases[i + 1]) != -1) {

      addValues(valueOffset, base, 49, null); // c_{i}t_{i}

    }

    if ((base = uniBases[i]) != -1) {

      addValues(valueOffset, base, 50, null); // c_{i-1}t_{i}

    }

    if ((base = uniBases[i + 2]) != -1) {

      addValues(valueOffset, base, 51, null); // c_{i+1}t_{i}

    }

    if ((base = biBases[i + 1]) != -1) {

      addValues(valueOffset, base, 49, null); // c_{i-1}c_{i}t_{i}

    }

    if ((base = biBases[i + 2]) != -1) {

      addValues(valueOffset, base, 50, null); // c_{i}c_{i+1}t_{i}

    }

    if ((base = biBases[i]) != -1) {

      addValues(valueOffset, base, 51, null); // c_{i-2}c_{i-1}t_{i}

    }

    if ((base = biBases[i + 3]) != -1) {

      addValues(valueOffset, base, 52, null); // c_{i+1}c_{i+2}t_{i}

    }

  }

}

注意：49对应于数字1的unicode值，50对应于数字2等。从上述代码中，我们发现特征数组fl[4*i+j]对应于特征的base为i，label为j。拼接特征的流程如下：先得到unigram或bigram字符特征，然后加空格，再加标识。在拼接过程中，按照DAT的转移方程进行转移：

base[r] + c = s

check[s] = r

最后，我们回到第三个问题——为什么DAT的长度远大于特征数？这是因为在构建DAT时，需要存储很多的中间结果。

解码

THULAC用于解码的类character.CBTaggingDecoder，Viterbi算法实现对应于方法AlphaBeta::dbDecode；CBTaggingDecoder的主要字段如下：

public char separator;

private int maxLength; // 定义的最大句子长度20000

private int len; // 待分词句子的长度

private String sequence; // 待分词句子的深拷贝

private int[][] allowedLabelLists; // 根据标点符号及句子结构，判断当前字符允许的label: int[len][]

private int[][] pocsToTags; // index -> allow-labels: int[16][2,3,4]



private CBNGramFeature nGramFeature;

private Dat dat; // 字符特征DAT

private CBModel model; // 权重



private Node[] nodes; // 分词DAG邻接表

private int[] values; // 特征模板F(t_i,X)的加权之和: int[i*4+label]

private AlphaBeta[] alphas; // 解码时用来记录path, [i, j]指c_{i}的标注为t_{j}的前一结点

private int[] result; // 分词后的标注数组

private String[] labelInfo; // ["0", "2", "3", "1"]

private int[] labelTrans; // 

private int[][] labelTransPre; // 可能情况的前labels: int[4][3]

public int threshold;

private int[][] labelLookingFor;

其中，二维数组pocsToTags为index与allow labels之间的映射，内容如下：

[null, [0, -1], [3, -1], [0, 3, -1], 

[1, -1], [0, 1, -1], [1, 3, -1], [0, 1, 3, -1], 

[2, -1], [0, 2, -1], [2, 3, -1], [0, 2, 3, -1], 

[1, 2, -1], [0, 1, 2, -1], [1, 2, 3, -1], [0, 1, 2, 3, -1]]

该数组的index表示了当前字符具有某些性质，比如：

• 1（[0]）表示词的开始，即标注B；
• 2（[3]）表示词的中间字符，即标注M；
• 4（[1]）表示词的结尾，即标注E；
• 8（[2]）表示标点符号，即标注S；
• 9（[0,2]）表示某一个词的开始，或者能单独成词，即标注BS；
• 12（[1,2]）表示词的结束，即标注ES；
• 15（[0,1,2,3]）为默认值。

在分词前，THULAC根据标点符号等特征，给一些字符加入allow labels以提高分词准确性。比如，根据书名号确定里面为一个词，

val sentence = "倒模，替身算什么？钟汉良、ab《孤芳不自赏》抠图来充数"

val poc_cands = new POCGraph

val tagged = new TaggedSentence

val segged = new SegmentedSentence

val segmenter = new CBTaggingDecoder

val preprocesser = new Preprocesser

val prefix = "models/"

segmenter.init(prefix + "cws_model.bin", prefix + "cws_dat.bin", prefix + "cws_label.txt")

segmenter.setLabelTrans()

segmenter.segment(raw, poc_cands, tagged)

segmenter.get_seg_result(segged)

println(segged.mkString(" "))

// 倒模 ， 替身 算 什么 ？ 钟汉良 、 ab 《 孤芳不自赏 》 抠 图 来 充数

3. 参考资料

[1] Li, Z., & Sun, M. (2009). Punctuation as implicit annotations for Chinese word segmentation. Computational Linguistics, 35(4), 505-512.