摘 要 中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、自然语言理解等中文信息处理领域的基础。目前中文分词" />
免费阅读期刊
论文发表、论文指导
周一至周五
9：00&22：00
警务应用中基于双向最大匹配法的中文分词算法实现
　　摘 要 中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、自然语言理解等中文信息处理领域的基础。目前中文分词依然是中文信息处理的瓶颈之一，本文对常见中文分词算法进行研究，并针对警务应用的场景，在经典的Jieba中文分词算法的逆向匹配法基础上提出双向最大匹配法，最后验证改进后的算法在中文分词准确度方面的提升。 中国论文网 /1/view-7234083.htm　　【关键词】中文分词 双向最大匹配法 警务应用 　　1 研究背景 　　公安机关日常工作中采集到的数据，大多为碎片化数据，具多源、量大、且又离散如何有效提取这些非结构化数据中的有效信息以方便警务应用系统进行进一步分析处理，为案件侦破、情报分析等提供服务，关键技术就是利用中文分词算法将这些描述性的中文语句转变为结构化数据。 　　2 中文分词技术简介 　　2.1 中文分词算法分类 　　中文分词技术属于自然语言处理技术范畴，现有分词算法分为基于规则的分词方法、基于统计的分词算法和基于理解的分词方法。 　　基于规则的分词方法中占主流地位的是正向最大匹配法和逆向最大匹配法。由于汉语单字成词的特点， 正向最小匹配和逆向最小匹配一般很少使用。逆向匹配的切分精度一般高于正向匹配，遇到的歧义现象也比较少。由大数据量的统计表明正向和逆向最大匹配的错误率分别为1/ 169和1/ 245，但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。 　　基于统计的方法是基于多个汉字同时出现的概率， 通过对语料库有监督或无监督的学习， 得到描述一种语言的语言模型 （常用一阶隐马尔可夫模型（ 1stHMM） ） ，该方法优点是只要有足够的训练文本即可降低未登录词的影响。 　　2.2 Jieba分词算法 　　Jieba分词算法基于规则与统计相结合，利用前缀词典实现高效的词图扫描，生成句子中所有可能成词情况所构成的有向无环图 （DAG），要生成有向无环图必须有语料库的辅助，语料库中每条记录会包含词、词频、词性等属性。Jieba分词试图查找树结构中的最大概率路径， 找出基于词频的最大切分组合；对于未登录词，采用基于汉字成词能力的 HMM 模型，使用 Viterbi 算法。 　　Jieba分词在HMM中有两种状态，一种是具有决定性的隐含状态，另一种的显性输出的状态。在Jieba分词中状态有4种，分别是B，M，E，S，对应于一个汉字在词语中的地位即是B（开头），M（中间 ），E（结尾），S（独立成词），而输出就是一个汉字。 　　在HMM中还有三种概率分别是状态分布概率，状态转移概率和发射概率（发射概率是一个条件概率，表示在某一状态下得到某一输出的概率）。图1为二状态的马尔科夫模型。 　　要对一串汉字进行分词，首先使用Viterbi 算法判断这串汉字最有可能的BMES组合形式。在Jieba分词中作者经过大量的实验在文件中中预存好了汉语的一些概率值。prob_start.py 中预存了每种状态的概率。 　　对于一个中文语句，第一个汉字的状态概率称为初始概率，可以用贝叶斯公式得到： 　　其中P（i1）表示第一个字的状态概率，P（i2）表示第二个字的状态概率，P（i2|i1）表示状态i1到i2的转移概率，P（k2|i2）表示发射概率。 　　以此类推，由于每一个状态都有4种选择，所以根据每种选择导致的状态转移路径计算得出的概率值也不同，Viterbi算法的目的是找出概率最大的一种转移路径。如果语句长度为2，那么算法的目的就是使上面的P（i2）最大化。到达某一种中间状态的路径可能有多条，如在第三个节点到达状态M可能路径有 S->B->M、B->M->M等，Viterbi 算法在中间这一步中就进行“剪枝”，只记住路径中概率最大的那条。 　　3 警务应用系统中对Jieba分词算法的改进 　　警务应用系统对分词算法准确度的要求远远高于对分词算法速度的要求。本文基于Python3.4+Jieba0.37分词包，选择在中文词库、最大匹配算法等方面进行改进以提高分词准确度。 　　3.1 词库优化 　　词库是中文自动分词的基础，词库机制的优劣直接影响到分词的速度和准确度。 　　（1）枪械，盗窃，抢劫这些事警务应用中的常见词汇，通过合理调高这些词的比重，能够快速将其识别提取。 　　（2）利用二次分词法可以提高城市名、路名、车牌号、时间等警务应用中较为关心的词汇的识别度。在基本词库中添加当地地名和地址库，地名地址词库保存城市特有地名、路名、机构名、小区名、兴趣点和大地名。通用词主要用于对词典中有重复的词或是分词后的具有歧义或不准确的词进行修复，如“华夏二路”在词典并不存在，但是“华夏”却在词典中，“二”为数量词，所以自动分词结果为华夏/二/路。这时可对地址进行二次查找，当有单字存在于地名通名词典中时，将其与前面未登录单词合并。如“路”存在于通用地址库中，可将其和前面的单词“二”合并，分词结果为华夏/二路。同理，对于某些特殊格式的词，如车牌“沪XXXXXX”、时间等，由于词库不能枚举所有车牌或日期，同样可采取二次提取，将特定格式的字符串整合。如“沪XXXXXX”按常规分词会分为“沪/XXXXXX”，利用二次提取，将所有省简称与后面跟着非汉字字符串长度为7的字符串合在一起成为新词，即可被识别为车牌信息。 　　3.2 双向最大匹配法 　　最大匹配算法主要原理是切分出单字串，然后和词库进行比对，如果确定是一个词就记录下来，否则通过增加或者减少一个单字，继续比较，直到剩下一个单字为止，如果该单字串无法切分，则作为未登录词处理。 　　据SunM.S. 和 Benjamin K.T.的研究表明，中文中90.0%左右的句子，正向最大匹配法和逆向最大匹配法完全重合且正确，只有大概9.0%的句子两种切分方法得到的结果不一样，但其中必有一个是正确的（歧义检测成功），只有不到1.0%的句子，或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的，或者正向最大匹配法和逆向最大匹配法切分不同但两者都错（歧义检测失败）。
　　本文提出的双向最大匹配法将正向和逆向最大匹配法得到的分词结果进行比较，决定正确的分词方向。首先对语句正反向各进行切分，然后根据大颗粒度词越多越好，单字词越少越好的原则，选择一种合适的方式输出。即在切分数不同时，优先取切分数少的那一个结果；切分数相同时，优先取单字少的那种；在切分数，单字数都相同时，因为逆向最大匹配法统计来说相对准确率较高，取逆向为结果。流程图如图2所示。 　　以下两例是双向最大匹配法的应用场景： 　　例一：“我们在野生动物园玩”（如表1） 　　可以看出在使用双向最大匹配算法可以在单纯使用正向与逆向匹配算法结果不同时，选择更合适的一个，保证了更高的分词准确度。 　　3.3 性能测试 　　根据国际中文分词测评的标准中对汉语分词进行测试的方法，在第二届国际汉语分词测评中共使用了四家单位提供的测试语料（Academia Sinica、 City University 、Peking University 、Microsoft Research）， 本文基于Peking University提供的语料，利用语料库自带的分词脚本进行测试。以下的测试结果显示双向最大匹配法比起Jieba算法的最大逆向匹配，虽然消耗更多计算时间和计算资源，却提升了分词准确度（如表3）。 　　召回率指在分词标答中，分出正确的词语所占的比例；准确率指分词结果中，分出正确的词语所占的比例。召回率和准确率一般是此消彼长的关系，所以常用11种召回率下准确率的平均值（综合指标）来衡量一个分词系统的精度。将这两个度量值融合成一个度量值，如F度量，如图3、图4所示。 　　对于警务应用系统，针对警用词汇的词库改进后，能以更准确的提取所需词汇。以接警信息作为对象进行测试，例如在接警信息中出现“报警人”、“虹口分局”、地址、日期等词汇时，在原程序下会变成“报警 人”“虹口 分局”无法正确识别。摘取部分实际测试结果如图5、图6。 　　4 小结 　　本文针对警用领域的分词进行了一定的研究，寻找在杂乱无序的碎片文件中以较高准确度提取关键词的方法。中文分词是识别、提取出关键词进行分析应用的基础，本文提出的词库优化和匹配算法改进能够提升原Jieba算法的准确度，由于语料库规模限制以及参数设置等因素的影响，实验结果还存在可提高的空间。 　　参考文献 　　[1]冯书晓，徐 新，杨春梅.国内中文分词技术研究新进展[J].情报杂志，2002（11）：29-30. 　　[2]宗成庆.统计自然语言处理[M].北京：清华大学出版社，2013（08）. 　　[3]（美）Wesley J.Chun（陈仲才）著，杨涛，王建桥，杨晓云，高文雅，等译.python 核心编程[M].北京：机械工业出版社，2001（08）. 　　[4]结巴中文分词项目[EB/OL].（ ）[].https：//github.com/fxsjy/jieba. 　　作者单位 　　上海市公安局静安分局 上海市 200040
转载请注明来源。原文地址：
【xzbu】郑重声明：本网站资源、信息来源于网络，完全免费共享，仅供学习和研究使用，版权和著作权归原作者所有，如有不愿意被转载的情况，请通知我们删除已转载的信息。
xzbu发布此信息目的在于传播更多信息，与本网站立场无关。xzbu不保证该信息（包括但不限于文字、数据及图表）准确性、真实性、完整性等。没有更多推荐了，
不良信息举报
举报内容：
从头开始编写基于隐含马尔可夫模型HMM的中文分词器之一 - 资源篇
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！因为本科毕业设计的课题是中文分词，与此结缘，研究生入学后也就继续在这个方向上学习与实践。这篇文章是以我现有的已实现分词算法为基础而编写的，介绍基于感知器实现一个中文分词算法的基本原理。
基于字标注的分词方法基于字标注的方法的实际上是构词方法，即把分词过程视为字在一串字的序列中的标注问题。由于每个字在构造成词的时候，都有一个确定的位置。也即对于词中的一个字来说，它只能是词首字、词中字、词尾字或单字词一个身份。
以常用的4-tag标注系统为例，假如规定每个字最多有四个构词位置，即：
S（单独成词）
这里的$\lbrace B, M, E, S\rbrace$就是4-tag标注系统中的四个位置标注。
那么对于任意一个已经过分词的句子，我们都可以用这4个标注组成的序列，表示原来的分词结果。例如：
分词结果：我/爱/北京/天安门/。/
字标注形式：我/S 爱/S 北/B 京/E 天/B 安/M 门/E 。/S
需要指出的是，这里的”字”不只限于汉字，它可以是文本中出现的任何一个字符。因为在真实中文语料中，不可避免地会包含一些数量的非汉字字符，这里所说的”字”也包括外文字母、阿拉伯数字和标点符号等字符。所有这些字符都是构词的基本单元。
基于字标注的方法，把分词从原本的切分问题转化成一个序列标注问题。对于一个含有n个字符的句子$c_1^n=c_1 c_2 … c_n$，可以用下面的公式表示分词原理：
$$P(t_1^n|c_1^n) = \prod_{k=1}^n P(t_k|t_1^{k-1},c_1^n) \approx \prod_{k=1}^n P(t_k|t_{k-1},c_{k-2}^{k+2})$$
其中，$t_k$表示第k个字的标注，即$t_k \in \lbrace B,M,E,S \rbrace$。而$c_{k-2}^{k+2}$表示取词窗口的大小为5。
而把分词过程视为字的标注问题的一个重要优势就是，它能够平等的对待词表词（In-Vocabulary）和未登录词（Out-of-Vocabulary）。
这样，文本中的词表词和未登录词都是用统一的字标注过程来实现的。在学习架构上，既可以不必要专门强调词表词信息，也不用专门设计特定的未登录词识别模块。
机器学习的模型算法可以专注地从文本语料中学习规律，仔细想想这其实更类似于人类早期学习语言的过程。基于字标注的方法也是目前最主流的中文分词方法。
感知器算法感知器算法是一个可以解决二分类问题的线性分类模型，其模型对于我这样一个初学者来说都是很容易就可以理解的。基础的二分类感知器这里不再多做介绍，我们把目光转向分词算法所需的多类感知器算法身上。
多类感知器是感知器算法用于解决多类分类问题时的一个扩展，它的主要思想是：用多个感知器去进行多类分类，但每个感知器只将一类目标视为正例，而其他的目标均视为负例。
如上图，假设现有一个c类感知器，可用于c个类别的分类。$X^i$（i=1,2,…,N）是一个样本，感知器有4个权重向量$\theta_j$（j=1,2,…,c），则样本$X^i$的类别决策可由如下公式得到：
$$C^i=arg \max_{j=1,2,…,c}{\theta_j^TX^i}$$
而多类感知器的更新规则也与原始感知器稍有不同。首先给出多类感知器的代价函数（Cost function）：
$$J_p(\theta)=\sum_{k=1}^N( \max_{j=1,…,c} \theta_j^T x^{(k)}-\theta_{y^{(k)}}^T x^{(k)} )$$
参数的更新规则（Parameter update rule）：
$$\theta_j:=\theta_j-\alpha ( 1\lbrace j=C^{(k)}\rbrace - 1\lbrace j=y^{(k)}\rbrace )x^{(k)}$$
这里的$$C^{(k)}=arg \max_{j=1,…,c} {\theta_j^Tx^{(k)}}$$
而根据$C^{(k)}$和$y^{(k)}$的关系，又可以细化为：
用简单一句话来说就是，对于错分类样本，让错的感知器权重缩小一点，让应该对的感知器权重增大一点。这样“此消彼长”，经过几次迭代后就可以正确分类这一个样本了。
基于感知器的中文分词算法将感知器用于分词多类感知器已经可以应付多类分类的问题了，那么它和中文分词有什么联系呢？连接中文分词与多类感知器的桥梁，就是基于字标注的分词方法。
应用基于字标注的分词方法，分词由切分问题转化为序列标注问题。每个字都有一个标注，也就是说每个字属于一个类别，那么给出一个字的标注的过程其实是一个分类过程。所以，利用多类感知器我们可以解决这样一个问题。
接下来，将要解决的问题就是如何进行特征表示，将文本语料转化成可用于感知器训练的特征向量。
特征模板特征模板是抽取语料特征的模式，是词特征学习的基础。（The feature template is the pattern of feature extraction from corpus, and the basis of corpus lexical feature learning.）
句子中的每一个字都会根据特征模板生成特定的特征，我对这些出现的特征进行统计记录，并生成了特征空间。
我的算法所使用的特征模板如下：
(1)$C_n (n=-2,-1,0,1,2)$(2)$C_n C_{n+1} (n=-2,-1,0,1)$(3)$C_{-1} C_1$
其中，$C_n$表示处于第n个位置的字。当n=0时，表示当前字。
仍旧以句子『我爱北京天安门。』为例。假设$C_0$为北，则按照模板将产生以下特征：
我，爱，北，京，天
我爱，爱北，北京，京天
以上三组分别对应特征模板中的(1),(2)和(3)，可以看到特征模板(1)抽取出了一元特征（unigram）,（2)和(3)抽取出了二元特征（bigram）。这些字以及字和字的二元组合就构成了不同的特征，之后采取一定的特征表示方法，将这些字符信息转化成数字信息构建特征向量就可以制作可供感知器训练使用的数据了。
在这里，我采用的方法简单粗暴，就是按照unigram和bigram分类，分别统计出现过的不同特征，并给每个特征一个序号，这个序号就是特征向量的维度信息。当然，特征表示的方法不唯一。
Viterbi算法求解最优标注结果是一种动态规划算法。它用于寻找最有可能产生观测事件序列的-维特比路径-隐含状态序列。这本是常出现于中的术语，不过Viterbi算法也常被用于寻找观察结果最有可能解释相关的动态规划算法。
在基于字标注的中文分词中，每个字常常以某个概率被标注为标注集中的某个tag。若以每个字最大概率的标注的序列作为一句话的标注结果时，其结果的准确率和分词的效果往往不好，有时可能还会出现不符合分词规则的结果，比如标注”B”后一个标注为”S”。所以，就需要在以句子为整体，在序列上求得最优的标注结果。为此，我想到了利用Viterbi算法求解这个标注结果。
为了应用Viterbi算法，我们需要一些定义一些模型参数，这里借鉴了隐马尔可夫模型。我们将4-tag标注系统中的标注集$S=\lbrace B, M, E, S\rbrace$当作隐含状态集，而可观察状态的序列就是未分词的句子。
假定从语料中统计得到，初始状态i的概率为$\pi_i$，从状态i转移转移到状态j的转移概率为$\alpha_{i,j}$（这两部分的概率矩阵是通过对训练语料的标注统计得到的。）。
现有一句中文语句$C^{1:N}=c_1 c_2 … c_N$作为观察状态序列，产生此观察状态序列的最有可能的隐含状态序列（标注序列）$T^{1:N}=t_1 t_2 … t_N$可由以下递推关系给出：
定义$\delta_i(n)$为部分最大似然概率，即序号从1~n的字符子串的最大似然值，目表是求解出$T^{1:N} = arg \max_{T^{1:N}}P(C^{1:N}|T^{1:N})$，$\delta_i(t)$满足：
(1)$\delta_i(1)=P(c_1|t_1=i) \cdot \pi_i$(2)$\delta_i(n)=P(c_n|t_n=i) \cdot \max_{j\in S}( \delta_j(n-1) \alpha_{j,i})$
其中$n\le N$，$\delta_i(n)$是以i状态为结尾的前t个观测结果最有可能对应的隐含状态的序列的概率。通过保存向后指针记录上面(2)式中用到的状态j可以获得维特比路径。令$Ptr(n,i) = arg \max_{j\in S}( \delta_j(n-1) \alpha_{j,i})$，表示n时刻的状态i是由n-1时刻哪个状态转移而来的，可得到：
$t_N = arg \max_{j\in S}( \delta_j(n-1) \alpha_{j,i})$$t_{n-1} = Ptr(n,t_n)$
这里我们使用arg max的标准定义。算法的时间复杂度为$O(N\times \left|{S}\right|^{2})$。
由上面的这些公式可以看到，目前不能从语料中通过统计得到的就是$P(c_n|t_n=i)$，这其实是HMM中的发射概率。在我的算法中，这部分概率是由多类感知器给出的：多类感知器对当前字进行分类，输出它分别属于四个类别的概率。利用这个概率完成上述的计算。
如上图中，图中箭头所示路径代表的序列”S\S\B\E\B\M\E\S”为该句最优的标注结果。
例句『我爱北京天安门。』对应的可能标注序列为$4^{\left|C\right|}=4^8$个，其中还包括不符合分词规范的可能序列。使用暴力方法去求得最优标注序列实在是难为计算机了，为了求解出该序列，就需要使用维特比算法了。
总结至此，一个基于感知器算法的中文分词算法的基本原理和关键算法已经讲述完毕。整个分词算法的基本思路与基于HMM或CRF的分词算法大体类似，只是在发射概率的计算上使用了多类感知器的分类结果的概率输出，而不是HMM给出。
在模型复杂度上，多类感知器比HMM或CRF简单不少，实现难度也低了不少。最后，我们使用SIGHAN2005(icwb2-data)的语料数据进行了分词实验。作为对比，我们使用同样的特征模板和语料，用工具训练了基于CRF的中文分词器（这部分的具体操作方法请看：）。以下是两个分词器的效果对比：
表1 PKU语料库上性能指标比较
F1-Measure
OOV-Recall
表2 CITYU语料库上性能指标比较
F1-Measure
OOV-Recall
表3 MSR语料库上性能指标比较
F1-Measure
OOV-Recall
表4 AS语料库上性能指标比较
F1-Measure
OOV-Recall
表格中，CWSP表示基于感知器的中文分词算法，CRF表示使用CRF++工具训练的分词算法。可以看到，基于感知器的中文分词算法的performance与基于更复杂模型CRF的分词算法相比相差不到1个百分点，是可以接受的结果。
感知器分词算法新进展改进的特征模板上面讲到，使用基本的特征模板我们可以得到与基于CRF++工具训练的分词模型差距不大的分词效果。所使用的特征模板为：
(1)$C_n (n=-2,-1,0,1,2)$(2)$C_n C_{n+1} (n=-2,-1,0,1)$(3)$C_{-1} C_1$
我称这个特征模板为10-feat，在此基础上添加字典信息和字符类别信息特征：
(1)$C_n (n=-2,-1,0,1,2)$(2)$C_n C_{n+1} (n=-2,-1,0,1)$(3)$C_{-1} C_1$(4)$MWL_0,t_0$(5)$C_nt_0 (n=-1,0,1)$(6)$T(C_{-2})T(C_{-1})T(C_0)T(C_{1})T(C_{2})$
其中(4)、(5)是字典信息特征，$MWL_0$指当前字在字典中匹配的最长词的长度,$t_0$表示当前字在字典最长词中对应的标注；(6)是字符类别信息，$T(C_n)$得到当前字符的类别，一共有五个类别，“1”类为中文数字类，“2”类为日期类（“日”，“月”，“年”），“3”类为英文字母类，“4”类为中国人名常用姓类，“5”类为其他字符。
使用此特征模板得到的最新分词结果如下：
表5 PKU语料库上性能指标比较
F1-Measure
OOV-Recall
表6 CITYU语料库上性能指标比较
F1-Measure
OOV-Recall
表7 MSR语料库上性能指标比较
F1-Measure
OOV-Recall
表8 AS语料库上性能指标比较
F1-Measure
OOV-Recall
改进的特征表示方式最新版本的感知器分词算法中，使用了新的记录方式表示特征。但所使用的特征模板不变，仍旧是：
(1)$C_n (n=-2,-1,0,1,2)$(2)$C_n C_{n+1} (n=-2,-1,0,1)$(3)$C_{-1} C_1$(4)$MWL_0,t_0$(5)$C_nt_0 (n=-1,0,1)$(6)$T(C_{-2})T(C_{-1})T(C_0)T(C_{1})T(C_{2})$
其中，特征(1)是一元特征(unigram)，特征(2)是二元特征(bigram)，特征(3)是简化表述的三元特征(trigram)。三元特征的信息对于分词的特征表示有着十分重要的作用，然而其特征数目巨大。
以往的特征表示方式，是将特征(2)(3)记录在一个记录表内，统一分配特征序号。而按照这种方式，结合特征向量的生成方式得到的向量空间十分庞大（unigram*5+bigram*5+dict_feat*4+5^5），而导致特征维度急剧膨胀的原因是trigram的数目巨大且因与bigram数目相加乘以5。
于是，为了解决这个问题，我将trigram特征独立出来，使用单独的变量存储，使得特征空间的维度大幅缩小。并且，感知器分词算法的性能没有受到很大影响，模型训练速度也有所提升，模型文件大小也缩小了不少。
如下表，给出了改进前后的特征空间大小对比，其中old表示原有的特征表示方式，new表示上诉新的特征表示方式：
表9 各语料库上不同特征表示方式特征维度对比
可以看到，特征空间维度的缩减十分明显(44%左右)。下面给出使用新的特征表示方式后，感知器分词算法在四个语料库上的performance：
表10 PKU语料库上性能指标比较
F1-Measure
OOV-Recall
表11 CITYU语料库上性能指标比较
F1-Measure
OOV-Recall
表12 MSR语料库上性能指标比较
F1-Measure
OOV-Recall
表13 AS语料库上性能指标比较
F1-Measure
OOV-Recall
可以看到在特征空间维度缩减近一半的情况下，F1-Measure平均降低0.4%，在总体上看是可以接受的。但是具体看到OOV-Recall指标和IV-Recall指标，这两项指标的下降有些过于明显。所以该种改进方法是否可取，需要看具体使用环境而定。
使用C++编写的分词器在研究这个算法的初始阶段，我使用Python编写了一个基础的算法模型，用于验证和实验。Python版本的感知器分词程序（以下简称CWSP-py）在一定程度上证明了基于感知器的分词算法的可行性，但又有着一些设计和实现上的不足，如速度较慢、句子边界处理不完善，特征表功能不完整等等。
在意识到使用Python编写的感知器分词程序的不足之后，我着手使用C++编写了一个更快、语料处理规则更完善的感知器分词算法（以下简称CWSP-cpp）。CWSP-cpp与CWSP-py的不同之处主要有以下几个部分：
语料预处理中有关句子边界的处理
特征表对于未记录特征的处理
接下来，我将分别对这三个不同进行详细的解释。
特征模板在最后一版CWSP-py中，所使用的特征模板为：
(1)$C_n (n=-2,-1,0,1,2)$(2)$C_n C_{n+1} (n=-2,-1,0,1)$(3)$C_{-1} C_1$(4)$MWL_0,t_0$(5)$C_nt_0 (n=-1,0,1)$(6)$T(C_{-2})T(C_{-1})T(C_0)T(C_{1})T(C_{2})$
其中，特征(1)~(3)是从语料中直接抽取得到的字特征；特征(4)(5)是结合字典信息产生的特征；特征(6)中的$T(C_n)$是一个将字符映射为类别号的函数，共包含5个类别，分别是：日期（Dates）、汉字数字（Nums）、英文字母（Letters）、中国人名常用字（Names）及其他（Others）。
而在CWSP-cpp中，我讲以上特征模板扩展为：
(0)$P(C_0)$(1)$C_n (n=-2,-1,0,1,2)$(2)$C_n C_{n+1} (n=-2,-1,0,1)$(3)$C_{-1} C_1$(4)$MWL_0,t_0$(5)$C_nt_0 (n=-1,0,1)$(6)$T(C_{-1})T(C_0)T(C_{1})$(7)$N(C_{-1})N(C_0)N(C_{1})$(8)$F(C_{-1})F(C_0)F(C_{1})$
特征(0)是标点特征，特征(1)~(5)与CWSP-py的特征模板中对应项的意义相同，特征(6)是类型特征，特征(7)是中国人名特征，特征(8)是外国人名特征。
表14 字符类别号
特征(6)中，$T(C_n)$是一个将字映射为类别号的函数，现在共有6个类别，分别是：阿拉伯数字（ANum）、中文数字1（CNum1）、中文数字2（CNum2）、英文字母（EngLetter）、日期（Date）及其他（Others）。
表15 中国人名用字类别号
Frequency Surname
Common Surname
Given Name
特征(7)中，$N(C_n)$是一个将字映射为中国人名用字类别的函数，现在共有6个类别，分别是：0.常见姓（Frequency Surname）、1.普通姓（Common Surname）、2.人名用字（Given Name）、3.both 0+2、4.both 2+3 及 5.其他（Others）。
表16 外国人名用字类别号
Noncommmon FNameChar
Commmon FNameChar
特征(8)中，$F(C_n)$是一个将字映射为中国人名用字类别的函数，现在共有2个类别，分别是：非外国人名常用字（Noncommon FNameChar）及外国人名常用字（Common FNameChar）。
句子边界在基于字标注的分词方法中，特征的产生是基于一个滑动窗口的。这个窗口有一个固定的长度，一般为奇数。本算法中使用的窗口长度为5，即对于窗口中心的字来说，取其前二及后二字与其组合形成特征。
由于窗口的长度是固定的，所以在处理句子边界（句子第一个字或最后一个字）处的字符时，就会有窗口中字符不满的情况发生。为了避免这种情况的发生而导致特征抽取失败，一般的做法是在句子首位处添加特殊字符，之后窗口的起始位置还是在原来句子的第一个字符处。
例如，对于句子“我爱北京天安门。”，窗口中心位于“我”、“爱”、“门”和“。”处时，都会发生窗口不满的情况。这时，我们就在句子的首尾各添加两个特殊符号，如在CWSP-py中是用字符“#”，句子发生变化：
我爱北京天安门。 ——& #/#/我/爱/北/京/天/安/门/。/#/#
句中用“/”分隔开的每个字，在算法中都是一个独立的单位。窗口开始的位置仍旧在“我”字处。
与此不同的是，在CWSP-cpp中，句子首尾添加的特殊符号被扩展成了一个集合$\lbrace B_0, B_1, E_0, E_1 \rbrace$，从而改变了处理过后的句子：
我爱北京天安门。 ——& $B_1$/$B_0$/我/爱/北/京/天/安/门/。/$E_0$/$E_1$
未登录特征在中文分词领域，有一个问题始终困扰着人们，那就是未登录词（out-of-vocabulary）识别。未登录词之所以难以识别，是因为它从未在训练语料中出现过，自然有关它的特征不会被模型发现收集并用于训练。
但当其出现在训练语料中时，算法仍会按照规则抽取特征，此时抽取的出的特征模型从未见过，自然在模型的特征表中不会有它的记录。这就会导致严重的错误发生：因为没有特征记录，于是无法生成特征向量，导致模型识别能力的下降。我称这一现象为特征丢失。
例如，假设现有一个未登录词“天安门”，窗口中心位于“安”，由于特征表中没有关于这些字的特征，所以特征“天安”、“安门”、“天门”都无法找到对应的特征号，从而丢失了这一部分的数据，抽取出的特征可能只包含了一元特征和一些类别信息特征。
对于一个训练好的模型，并不能随意将减到的未登录特征添加至记录表，因为这可能会导致特征空间的变化，从而导致模型的失效。于是为了防止特征丢失，我们在原始的特征表中预留了一个位置给没见过的特征通用，记为“Unknow”特征。注意，这并不是解决OOV的方案，只是一个小技巧，防止了特征丢失，保证了特征向量的内容数量。
这一个小技巧在CWSP-py中是没有使用的，所以我见过一个未登录词中某个字的特征只剩下了类别特征而其余都丢失了。在CWSP-cpp中，我使用自定义的特征表结构，实现了对于“Unknow”特征的支持。
CWSP-cpp实验结果实验结果对比在完成了CWSP-cpp的编写之后，我对其在Bakeoff-05标准数据集上进行了封闭分词实验，并将结果与目前state-of-the-art的算法进行了对比，结果如下：
表17 CWSP-cpp与state-of-the-art算法结果对比
(Tseng et al., 2005)
(Zhao et al., 2006)
(Zhang and Clark, 2007)
(Zhang et al., 2013)
(Chen et al., 2015)
(Li et al., 2015)
(Wang et al., 2009)
(Wang et al., 2010)
Huihsin Tseng, Pichuan Chang, Galen Andrew, Daniel Jurafsky, and Christopher Manning. 2005. A conditional random field word segmenter for sighan bake-off 2005. In Proceedings of the fourth SIGHAN workshop on Chinese language Processing, volume 171.
Hai Zhao, Chang-Ning Huang, and Mu Li. 2006. An improved Chinese Word Segmentation system with conditional random field. In Proceedings of the Fifth SIGHAN workshop on Chinese language Processing, volume 1082117.
Yue Zhang and Stephen Clark. 2007. Chinese segmentation with a word-based perceptron algorithm. In ACL.
Longkai Zhang, Houfeng Wang, Xu Sun, and Mairgup Mansur. 2013. Exploring representations from unlabeled data with co-training for Chinese word segmentation. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing.
Xinchi Chen, Xipeng Qiu, Chenxi Zhu, Pengfei Liu, and Xuanjing Huang. 2015. Long short-term memory neural networks for Chinese word segmentation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
Xiaoqing Li, Chengqing Zong and Keh-Yih Su. A Unified Model for Solving the OOV Problems of Chinese Word Segmentation. ACM Transactions on Asian and Low-Resource Language Information Processing (TALLIP), Vol. 14, No. 3 (June 2015), Article 12, 29 pages
Kun Wang, Chengqing Zong, and Keh-Yih Su. Which is More Suitable for Chinese Word Segmentation, the Generative Model or the Discriminative One? In Proceedings of the 23rd Pacific Asia Conference on Language, Information and Computation (PACLIC 23). 3-5 December 2009, Hong Kong. Pages 827-834
Kun Wang, Chengqing Zong and Keh-Yih Su. A Character-Based Joint Model for Chinese Word Segmentation. In Proceedings of the 23rd International Conference on Computational Linguistics (COLING), Beijing, China, August 23-27, 2010. Pages