中文分词算法技术对索引网页库信息进行预处理包括网页分析和建立倒序文件索引两部分，分词算法技术是网页分析的前提。文档由被称作特征项的索引词（词或者字）组成，网页分析是将一个文档表示为特征项的过程。在提取特征项时，中文又面临了与英文处理不同的问题。中文信息和英文信息有一个明显的差别：英语单词之间用空格分隔；而在中文文本中，词与词之间没有天然的分隔符，中文词汇大多是由两个或两个以上的汉字组成的，并且语句是连续书写的。这就要求在对中文文本进行自动分析前，先将整句切割成小的词汇单元，即中文分词（或中文切词）。
用具体例子来说明，就是如何把“我的笔记本”这样连续书写的语句切分为“我”，“的”和“笔记本”三个词汇单元。 在检索和文档分类系统中，自动切词系统的速度直接影响整个系统的效率。中文信息的检索主要有两种：基于字的检索和基于词的检索。基于单字的检索系统建立单字索引。
在检索时得到每个单字的索引，而后加以适当的逻辑运算，得到检索结果。而基于词汇的检索系统对词汇建立索引，检索词汇时一次命中。TSE系统采用基于词的索引，具有较快的速度和较高的准确性，同时能够减少索引信息对磁盘空间的占用。
本节从介绍切词软件的原理开始，讲到真正切词软件的实现，此切词软件中使用的基本词典包括108,782个词条及其对应词频。词典和切词源程序可以在[ChSeg,2003]获得，运行在Red Hat Linux 8.0以上的系统中。
中文分词算法介绍
自动分词的基本方法有：基于字符串匹配的分词方法和基于统计的分词方法，更多关于语言学的知识可以参考北大计算语言研究所网站 http://icl.pku.edu.cn 内的相关内容，本节以下部分内容直接引自该网站提供的资料。
1、基于字符串匹配的分词方法
这种方法又称为机械分词方法，它是按照一定的策略讲代分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。
- 按照扫描方法不同，串匹配分析方法可以分为正向匹配和逆向匹配。
- 按照不同长度优先匹配的情况，可以分为最大或最长匹配，和最小或最短匹配；
- 按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。
常用的几种机械分词方法如下：
- 正向最大匹配；
- 逆向最大匹配；
- 最少切分（使每一句中切出的次数最小）。
还可将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245（这可能是因为汉语的中心语靠后的特点）。
对于机械分析方法，可以建立一个一般的模型，形式地表示为ASM（d,a,m）即 Automatic Segmentation Model。其中：
- d：匹配方向，+表示正向，-表示逆向；
- a：每次匹配失败后增加或减少字串长度（字符数），+为增字，-为减字；
- m：最大或最小匹配标志，+为最大匹配，-为最小匹配。
例如，ASM(+, -, +)就是正向减字最大匹配法（Maxim
oach，MM），ASM(-, -, +)就是逆向减字最大匹配法(简记为RMM方法)，等等。对于现代汉语来说，只有m=+是实用的方法。
2、基于统计的分词方法
从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。计算汉字X和Y的互现信息公式为：
其中，P（X,Y）是汉字X、Y的相邻共现频率，P（X）、P（Y）分别是X、Y在语料中出现的概率，互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。
但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 词汇切分算法最重要的指标是准确，在兼顾准确性的情况下也要考虑时间复杂性。下面具体介绍正向减字最大匹配法。
正向减词最大匹配法
正向减字最大匹配法切分的过程是从自然语言的中文语句中提取设定的长度字串，与词典比较，如果在词典中，就算一个有意义的词串，并用分隔符分隔输出，否则缩短字串，在词典中重新查找（词典是预先定义好的）。 算法要求为：
- 输入：中文词典，待切分的文本d，d中有若干被标点符号分割的句子s1，设定的的最大词长MaxLen。
- 输出：每个句子s1被切为若干长度不超过MaxLen的字符串，并用分隔符分开，记为s2，所有s2的连接构成d切分之后的文本。
正向减字最大匹配法流程
该算法的思想是：事先将网页预处理成每行一个句子的纯文本格式，从d中逐句提取，对于每个句子s1从左向右以MaxLen为界选出候选字串w，如果w在词典中，处理下一个长为MaxLen的候选字段；否则，将w最右边一个字去掉，继续与词典比较；s1切分完之后，构成词的字符串或者此时w已经为单字，用分隔符隔开输出给s2。从s1中减去w，继续处理后续的字串。s1处理结束，取T中的下一个句子赋给s1，重复前述步骤，直到整篇文本d都切分完毕。
考虑到词典的条目较多，而且每切一个词都要比较，采用STL中的map容器作为存储词典的数据结构。map容器采用的数据结构是“红黑树”，“红黑树”是一种较常用的查找效率较高的平衡二叉搜索树[Cormen, et al.,2001]。在实际应用中可以采用hash表数据结构存储获得更快速的查找。算法的主程序流程如图4-4所示，切词程序CutWord如图4-5所示。
其中MaxLen是一个经验值，通常设为8个字节（即4个汉字），MaxLen过小，长词会被切断；过长，又会导致切分效率低。 为进行算法分析，先给出算法的伪码实现。
切词算法流程图
vpid SegmentAFile（T） //对文件进行分词处理的函数
1 while（getASentenceFromFile（T,S1X）） //循环读入文件中的每一行
2 S2 = CutWord(s1) // 调用句子分词处理函数
3 OutputSentence (s2) // 将分词结果写入目标文件
string CutWord ( s1 )
4 PreProcess(s1) //跳过非汉字部分字符串
5 While (s1 != “”) //如果输入不为空
6 W = s1.substr ( 0, MaxLen ) // 取等于最大词长的候选词
7 While( length（W）> 1 )
8 If( FindInRBTree (W)= alse) //如果不是词并且不是单字
9 then W = W – 1 //将W最右边的一个字去掉
10 s2 = W + “/” // 将找到的词用分隔符隔开
11 s1= s1 – W // 去掉找到的词，继续分析
12 return s2
算法分析
设文本文件含有句子的数目为m，句子的平均长度为k，词典的条目为n，实际中m和k远远小于n，整个算法复杂度中起决定作用的步骤在于n相关的语句。
行1，O(m)
行2，O(klogn) //通过对第4到12行子程序CutWord的复杂度分析得知
行3，O(1) 行4，O(1)
行5，O(k)
行6，O(1)
行7，O(1)
行8，O(logn)
行9，O(1) 行10，O
行11，O(1)
行12，O(1)
整个算法的时间复杂度为 O（mklogn）。
上面是对效率的分析，考虑到切词的效果，本算法还可以采用“回溯”思想作改进。即除了上述从左到右切分一偏句子，还从右到左切分一遍，对于两遍切分结果不同的字符串，用回溯法重新处理。例如“学历史知识”顺向扫描的结果是：“学历/ 史/ 知识/”，通过查词典知道“史”不在词典中，于是进行回溯，将“学历”的尾字“历”取出与后面的“史”组成“历史”，再查词典，看“学”，“历史”是否在词典中，如果在，就将分词结果调整为：“学/ 历史/ 知识/”。
最新评论