分词方法分类

中文分词大致分为三类：

  • 基于字符串匹配：最大正向匹配法、逆向最大匹配法、最少切分法、双向匹配法等
  • 基于统计：基于词频度统计的分词方法
  • 基于规则：基于知识理解，利用神经网络等分词方法

语言模型

基于词图的最大概率分词方法源于概率统计语言模型。
从统计思想的角度来看，分词问题的输入是一个字串C=C1,C2,……,Cn，输出是一个词串S=W1,W2,……,Wm，其中m<=n。对于一个特定的字符串C，会有多个切分方案S对应，分词的任务就是在这些S中找出概率最大的一个切分方案，也就是对输入字符串切分出最有可能的词序列。

$$Seg(c)argmax_{S \epsilon G} P(S|C)=argmax_{S \epsilon G}\frac{P(C|S)P(S)}{P(C)}
$$

例如对于输入『小红马上下来』，切分可能有：

  • S1: 小红/马上/下来
  • S2: 小红马/上/下来
  • S3: 小红马/上下/来
  • ……

计算条件概率P(S1|C)，P(S2|C)和P(S3|C)，然后采用概率大的值对应的切分方案。根据贝叶斯公式：

$$P(S|C)=\frac{P(C|S)P(S)}{P(C)}$$

其中P(C)是字符串在语料库中出现的概率为一固定值，从词串恢复到汉字串的概率只有唯一的一种方式，所以P(C|S)=1。因此，比较P(S1|C)和P(S2|C)的大小变成比较P(S1)和P(S2)的大小。
概率语言模型分词的任务是：在全切分所得的所有结果中求某个切分方案S，使得P(S)最大。为了容易实现，假设每个词之间的概率是上下文无关的。（注意此处）

$$P(S)=P(W_1,W_2,W_3 \ldots)=P(W_1)*P(W_2)* \cdots*P(W_m)$$

计算任意一个词出现的概率如下：

$$P(W_i)=\frac{W_i在语料库中出现的次数n_i}{语料库中总词数N}$$

词典

词典中存储了词的text，出现次数，词性等信息，结构如下：

词 出现次数 词性
小红马 113 nr
巴塞尔 113 nr
巴塞爾 113 nr
文明史 113 nr

为了能够快速查找字典采用双数组Trie树来存储，关于Trie树相关内容请自行百度。

构建词图

根据字典构建的trie树，扫描待分词句子生成DAG（有向无环图），就是对待分词句子，根据给定的词典进行查词典操作，找出所有可能的句子切分。
如果待切分的字符串有m个字符，考虑每个字符左边和右边的位置，则有m+1个点对应，点的编号从0到m。把候选词看成边，可以根据词典生成一个切分词图。例如『小红马上下来』形成的词图如下：

WordSeg
WordSeg

路径1： 0-3-4-6 小红马/上/下来
路径2： 0-2-4-6 小红/马上/下来
……
切分词图中的边都是词典中的词，边的起点和终点分别是词的开始和结束位置。

计算最大概率

因为假设每个词之间的概率是上下文无关的，因此满足动态规划求解所要求的最优子结构性质和无后效性。求出值最大的P(Si)后，利用回溯的方法直接输出Si。图用邻接矩阵存储，伪代码如下：

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

type Token struct {
	//分词的字串
	text []byte
	//该分词概率
	Prod float32
	// 词性标注
	pos string
	//分词开始节点的概率
	PredProd float32
    
}

segmentWords(byte []s) []Segment{
    for i:=0; i<len(s); i++ {
        // 从Trie树中得到以当前字元开头的所有分词
        tokens = dict.getPrev(i)
        
        for j:=0; j<len(token); j++ {
            newProd := token[j].PrevProd + token[j].Prod
            if(newProd > dis[token.end].prod) {
                dis[token.end].prod = newProd
                dis[token.end].token = token[j]
            }
        }
        
    }
    //从右向左扫描
    numSegments := 0
	for index := len(text) - 1; index >= 0; {
	
		location := index - len(dis[index].token.text) + 1
		numSegments++
		index = location - 1
	}
	output := make([]Segment, numSeg)
    for index:=len(s)-1; index>=0; {
        location := index - len(dis[index].token.text) + 1
		numSegments--
		output[numSegments].text = dis[index].token.text
		index = location - 1
    }
}

从右向左扫描是因为汉语句子的重心经常落在后面，这种扫描方式能提高分词的准确性。

最后

该模型有一个前提条件：『假设每个词之间的概率是上下文无关的』，这一点是不严谨的，一句话当中相邻词之间上下文无关很难做到。

搜索引擎中的中文分词十分复杂，分词的过程中需要考虑：

  • 切分的正确性
  • 粒度的合理性
  • 切分的一致性
  • 词条关系分析
  • 词条属性分析
  • 歧义词处理
  • ……