分词技术的研究与应用?

吴宏洲

摘要：该文主要论述一种快速分词技术的实现。对于GBK编码格式的原始文献，利用GBK可见汉字，建立内存常驻索引，按照最大匹配法查找外存分词词典库，从而将文章例句进行快速切分。理论上是目前最快的一种分词方法。

关键词：正向分词；逆向分词；GBK；字典索引

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）06-0179-04

4A Quick Word Segmentation Technology Research and Application

WU Hong-zhou

（The China Patent Information Centre， Beijing 100088， China）

Abstract：This paper mainly discusses the realization of a fast segmentation technology.For GBK encoding format of the original literature， the use of visible GBK Chinese characters， establishing resident memory index， according to the maximum matching method to find the external storage word segmentation dictionary library， which will be fast segmentation articles sentences.In theory it is at present a word segmentation method is the fastest.

Key words：positive word segmentation；reverse participles；GBK；the dictionary index

在专利信息技术中，专利文献信息检索、机器翻译、专利辅助自动文摘和CPC/IPC自动分类，都会用到一个基本的技术——分词技术。所谓分词，就是利用已有词库的词，来切分文章中的词的过程。切分的分词，用来确定在文献中的位置；用来统计特征词的频度；聚类、分类运算；相似度计算等。目前有很多应用场景已经使用了已有的技术产品。带来的好处是：引入语义分析、词性分析、语法分析等成熟技术，性能稳定，分词正确率高；加快软件产品开发使用，可移植性强。带来的问题是：受著作版权保护，须缴纳昂贵费用，加大应用软件的制作成本；由于词库数据结构的不公开，使维护变得困难；产品大多面向大众化读物，不能灵活地适应专业技术性强的不同领域对分词的不同要求；词库中分词需要标注词性，词性对于专业技术文献产生的作用并不明显，更新分词，须额外编辑词性，并审校，费时费力，词库的更新周期比较长。为了降低应用成本，迫使我们不得不自主研发一整套适合本领域的包括分词在内的相关基本技术。分词技术属于中国特色的信息处理技术之一。在西方语言中，拼音字母组合构成的单词，单词与单词之间有明显空格分隔，词是自然分隔的，无须分词。对于相形文字（如中日韩语言）来说，字词之间紧密连接，没有明显间隔。因此需要仿照西方语言来预先加工分词，使之明显分割。只有具备了分词分割字词的基础，才能够像西文那样轻松地建立数学模型，利用数学方法，来对文献进行分析利用。因此本文将讨论如何实现一种实用的快速分词方法。

1 分词技术的现状

分词技术目前已经非常成熟。常见的有三种方法：

1） 字符串匹配的分词方法；

2） 词义分词法；

3） 统计分词法。

1.1 字符串匹配的分词方法

这是一种常用的分词法，它主要利用已有词库中的词匹配文章句子中的词，来切分句子。常见的方法又有四种方法：

1） 正向最大匹配法；

2） 逆向最大匹配法；

3） 最短路径分词法；

4） 双向最大匹配法。

1.2 词义分词方法

一种机器语音判断的分词方法。在进行句法、语义分析时，利用句法信息和语义信息来处理歧义现象从而得到分词，这种分词方法，现在还不成熟，处在实验阶段。

引入词性协助分析词性在语法位置上的可能性，对词进行合理切分，目前国内产品出现的比较多。如中国科学院计算所的ICTCLAS产品。

1.3 统计分词法

根据词组的统计，就会发现两个相邻字出现的频率最多，那么这个词就很重要。就可以作为用户提供字符串中的分隔符来分词。

2 分词技术的实现

本文讨论的是属于字符串匹配的分詞方法。而且主要着重讨论正向最大匹配法和逆向最大匹配法。双向最大匹配法是前两种方法的结合，用于判断切分产生歧义时，是否需要人工干预来决定选择哪一种结果，或者，通过最佳路径分词法来自动选择一种。因此，设计好正向/逆向分词技术是分词技术实现的基础，也是本文主旨。本文重点是要实现一种高效的分词技术。由于分词技术是一种纯粹底层的引擎，因此提出的高效目标，既要保证分词的效率和效果，还要兼顾系统资源开销，将节省的资源尽可能多地用于其他方面，例如响应更多的客户端的服务请求。笔者利用内存和外存相结合的方法建立了一个驻留内存的字典索引和一对存放于外存的正向分词和逆向分词词库来实现高效分词技术。

2.1 分词库的构建

在外存建立词库，要对词库中词语的开头汉字、词语的汉字字数和结尾汉字这三项进行标注。将分词数据结构定义为定长记录：{分词char（30），首字char（2），首字编码char（4），尾字char（2），尾字编码char（4），分词汉字数int，位置号int}。

词库设计需要考虑在词库检索效率与词长选择之间求得平衡。如果词长过长，检索效率必然下降；如果词长过短，就会丢失正确的长词，使分词正确性得不到满足。考虑到化学、药物、微生物等领域的技术术语可能会有大量长词出现，因此，牺牲部分分词的访问效率，换来长词的满足也是不得已的，通常认为一个长词最长不超过15个汉字。

实验中我们建立了大约120万条分词的词典库，用以模拟专利文献词典的真实数据规模。

2.1.1 正向分词词库的构建

将词库文件按照{首字编码（正序）+词语的汉字字数（逆序）+尾字编码（正序）+分词（正序）}来排序，并得到一个正向分词库文件。每个记录行号填入“位置号”字段。样例参见表1。

2.1.2 逆向分词词库的构建

将词库文件按照{尾字编码（正序）+词语的汉字字数（逆序）+首字编码（正序）+分词（正序）}来排序，并得到逆向分词库文件。每个记录行号填入“位置号”字段。样例参见表2

2.2常驻内存字典索引表的构建

在内存建立一个字典索引表。由于分词库，对于正向分词是按照单词首字集中有序存放的，对于逆向分词也是按照单词尾字集中有序存放的。因此，字典索引，对于正向分词库来说，需要知道单词首字的起、止位置；同样，对于逆向分词库来说，需要知道单词尾字的起、止位置。

接下来选择什么样的字典作为索引就是一个关键。

通过考查GBK编码特征，GBK编码是双字节定长汉字编码。其编码与汉字区位相对应。笔者在GBK编码中筛选出21002个可见汉字建立字典索引码表。这是目前国内汉字编码比较多的，且与《汉语大字典》相一致。《汉语大字典》1993年版和1998年版，收录了21000个字头。字典索引码表中的字，对于专利文献领域的应用，我们认为也已经足够。如果要应用于其他方面，例如涉及古籍出版物的文献，这一方案还是不足以满足所需。例如《康熙字典》中的字头收录了多达47043个字头。其中大多是异形字和非常用字。

21002个可见汉字是如何从GBK编码表筛选的？

首先来看GBK编码分布图（参见图1）。

图1 GBK编码分布图

根据GBK编码分布图，我们将编码划分为两类编码：

1） 由汉字一区、汉字二区、扩展三区和扩展四区组成的字模汉字编码表，去掉其中不可见汉字字模编码，共收录21002个汉字。作为汉字编码。

2） 符号区字模编码和不可见汉字字模编码，作为非汉字编码。

另外除GBK编码外，还有一类西文ASCII编码。作为西文编码。

以可见汉字编码作为字典构建正向和逆向分词索引，其最大記录数约21002个。将数据结构定义为定长记录：{GBK编码char（4），汉字char（2），首字串字数int，尾字串字数int，首字开始int，首字结尾int，尾字开始int，尾字结尾int}。其记录格式参见表3。

表3 内存字典索引格式

1） 首先，对于停用字词要做特殊预处理，要么过滤掉，要么视同分隔符作用，进行特殊预切分，停用字词前后要添加空格分隔符。

2） 对于ascii编码的西文字母数字及其特殊符号，视同分隔符作用，不进行切分。原样输出。

3） 对于GBK编码的符号区和不属于字典索引表中识别汉字的编码，视同分隔符作用，不进行切分。原样输出。

4） 对于GBK编码属于字典索引表中可识别的汉字的连续字串，视同中文例句，要进行分词切分，切分分词前后要添加空格分隔符。切分的句子按照最大正向匹配法或最大逆向匹配法进行分词切分，切分出的分词或单字之间要以空格分隔符分隔。

分词切分算法包含：

正文切分句子算法、句子切分分词（分为最大正向分词匹配和最大逆向分词匹配）算法。

2.4.1 将正文切分成句子

正文切分句子，主要是对原始文件中的正文信息进行解析最粗的过程，首先要读入一个字，这里的字，是文字串中最小的逻辑单元，对于ASCII编码的字是单字节，而对于GBK编码的字是一个双字节。

要确定字的类型。主要有3种：

1：ASCII编码单字节表示的字，如西文字母数字及符号；

2：GBK编码双字节表示的字，不属于字典索引表中（21002个汉字）的部分，如符号区全角符号和一至四区不可见汉字编码；

3：GBK编码双字节表示的字，属于字典索引表中（21002个汉字）的部分，作为汉字编码。

读入的字的类型如果连续相同，则字的流构成同类字串，亦即短语，直至读到一个不同类型的字为止。如果属于1类或2类的短语，不处理，原样输出；如果属于3类的短语，要将短语句子作切分分词的细加工处理，处理后的分词流结果输出。重新继续构造新的类型的字串，直至全部读入的字串处理完为止。

算法：

T00； //首先确定已读类型T0为空

Y=X “”； // 句子样板串Y和已读字串X也清空

While（（T1getword（fdi，&C） ） > 0） {

T1getword（fdi，&C）； // 读入字C，类型T1

If（T1 ！= T0）{ //当读字节的类型T1与已读类型T0不一致时

If （ T1 == 3） // 句子是汉字串

X segment （X，direct） // 句子切分分词 ；direct正向/逆向

// 第一次，相当于只输出一个空，分词

Else If（T==2）

X X+ “ ”；

YY+X+ “ ”； // 句子样板串Y添加已读串S和空格（即Y=Y+X+ ）

X “”； //然后清空已读串X

T0T1； //重置新类型，T0取新类型T1

} else { //否则，T1与T0一致，拼接字串

XX+C； // 读入字C添加到已读字串X

}

}

2.4.2 句子切分分词

句子切分分词，主要有最大正向分词法和最大逆向分词法两种方法。

两种方法同时对句子进行切分分词，是一种混合方法，主要用来对句子切分分词结果进行互校时同时使用。如果两种切分句子结果出现歧义，则会引入另外一种，最短路径的方法，即计算切分分词数量最少优先自动判断方法。后两种方法在这里，就不进一步介绍。

算法：

If （Direct==1） { // 正向分词

// 进入最大正向分词处理

}else{ // 否则 ， 逆向分词

// 进入最大逆向分词处理

}

2.4.2.1 最大正向分词匹配

由于正向分词库的记录是按照字头（正序）、词长字数（逆序）、字尾（正序）排序，字典索引表中记录了正向分词库中字头和最大词长字数。切分例句时，通过字头、可能的最大词长来优先查找分词。可能的最大词长，是实际句子长度和字典字头对应的正向分词的最大长度两者中最小的长度，最小不能小于2，否则不成其为词，而为单字。例如：例句S：“最大正向分词法”，其句长SL：7。

最大正向分词匹配法，首先取字头“最”字。全程折半查找字典索引表，找到“最”字索引。“最”字对应正向分词库的局部起止范围[begin，end]，最大词长度WL=11。沿着起止范围[begin，end]对分词词库进行折半查找。查找分词“最大逆向分词法”，如果没有找到，则将查找词去掉一个汉字“法”，继续找“最大正向分词”，如果还没有找到，则继续去掉后面的字，直至“最大”，还没有找到，将“最”字，作为非分词字，输出。继续以“大正向分词法”为新句子，继續切分分词。如果找到分词，例如：找到“最大正向分词”，则输出“最大正向分词”，截断分词后的句子“法”作为新句子继续切分分词。直至，句子切分完毕。

算法：

Y “”； // 清空结果

// S=例句，传入参数

SLlength（S）； // 取例句长度

While（SL>0） { // 从例句首字开始切分分词

Hget（S，0，1）； // 取字头

Pbinary_search_gbk（0，GBKNUM-1，H）； // 折半查找字头

WLgbk[P].hml； // 取字典正向分词最大长度

begin gbk[P].hmb； // 分词库局部开始位置

end gbk[P].hme； // 分词库局部结尾位置

Lmin（WL，SL）； // 字典正向分词最大长度和句长较小者，作为最大试探长度

For（l=L；i>1；l--） { // 以最大试探长度依次缩小，

// 来截断句子试探是否存在最大分词

Csubstr（S，0，l）； //截取句子，取待查找分词

// 局部折半查找分词

If（（rcfinddict（C，begin，end，fid））>0） { // fid指定分词库句柄

Break； // 找到分词

}

}

Csubstr（S，0，l）； //截取句子分词

YY+C+ “ ”； // 输出分词 ，或 ，非分词单字

S substr（S，l，SL）； //截断分词后新句子

SL length（S）； // 取新句长度，继续

}

output（Y）//返回 输出结果

2.4.2.2 最大逆向分词匹配

由于逆向分词库的记录是按照字尾（正序）、词长字数（逆序）、字头（正序）排序，字典索引表中记录了逆向分词库中字尾和最大词长字数。切分例句时，通过字尾、可能的最大词长来优先查找分词。可能的最大词长，是实际句子长度和字典字尾对应的逆向分词的最大长度两者中最小的长度，最小不能小于2，否则不成其为词，而为单字。例如：例句S：“最大逆向分词法”，其句长SL：7。

最大逆向分词匹配法，首先取字尾“法”字，全程折半查找字典索引表，找到“法”字索引。“法”字对应正向分词库的局部起止范围[begin，end]，最大词长度WL=14。沿着起止范围[begin，end]对分词词库进行折半查找。查找分词“最大逆向分词法”，如果没有找到，则将查找词去掉一个汉字“最”，继续找“大逆向分词法”，如果还没有找到，则继续去掉后面的字，直至“词法”，还没有找到，将“法”字，作为非分词字，输出。继续以“最大逆向分词”为新句子，继续切分分词。如果找到分词，例如：找到“逆向分词法”，则输出“ 逆向分词法”，截断分词后句子“最大”，以新句子继续切分分词。直至，句子切分完毕。结果为“最大 逆向分词法”

算法：

Y””； // 清空结果

// S=例句，传入参数

SLlength（S）； // 取例句长度

While（SL>0） { // 从例句首字开始切分分词

T substr （S，SL-1，1）； // 取尾字

Pbinary_search_gbk（0，GBKNUM-1，T）； // 折半查找字尾

WLgbk[P].tml； // 取字典逆向分词最大长度

begin gbk[P].tmb； // 分词库局部开始位置

end gbk[P].tme； // 分词库局部结尾位置

Lmin（WL，SL）； // 字典逆向分词最大长度和句长较小者，作为最大试探长度

For（lL；i>1；l--） { // 以最大试探长度依次缩小，

// 来截断句子试探是否存在最大分词

C substr（S，SL-l，l）； //截取句子，取待查找分词

// 局部折半查找分词

If（（rcfinddict（C，begin，end，fid））>0） { // fid指定分词库句柄

Break // 找到

}

}

C substr（S，SL-l，l）； //截取句子分词

Y “ “+C+Y； // 输出分词 ，或 ，非分词单字，逆向粘接分词

S substr（S，SL-1，l）； //截断分词后新句子

SL length（S）； // 取新句长度，继续

}

output（Y）//返回输出 结果

2.5 分词切分试验效果

本文采用C语言实现，在lenovo T61，Intel（R）Core（TM）2 Duo CPU T7500 @2.20GHz2.17GHz，1.96GB内存。安装WindowsXP，同时安装SUSE linux server11。在SUSE下运行。

通过对正文文件的整个文件的单线程切分，测试实际切分效果，将国际专利分类号索引电子文档正文文件，分成八个大部的8个文件，分别切分。其效果由表4不难看出，逆向分词比正向分词平均快10%。

3 结论

本文给出分词算法的技术实现，在于推荐一种快速分词技术方案。该方案采用内外存相结合，通过内存构建GBK编码字典，快速查找到外存分词库的局部起止位置，通过缩小范围的局部折半查找来快速确定分词是否存在。通过提供的最大正向分词匹配法和或最大逆向分词匹配法，来对文章切分句子，对句子短语再进一步分线程双向切分，通过比对短语切分结果，当切分结果出现歧义时，采用分词数最少策略取其一种，记录歧义语句日志。双向匹配法产生的歧义的改进算法不在本文讨论之内。由于在本专利信息领域使用，考虑到一篇专利标题和文摘平均大约在5000字节以内，专利说明书和权利要求书等文献，在1万字之间，即便直接单线程切分文摘或全文也不足1秒，如果采用多线程并行多结点切分，其速度还可以进一步加快。可将分词效率提高到足以使分词服务响应拥塞现象能够消除为止，其性能是可控的。使得节省的时间能更多地用于其他方面。例如：统计词频、相似度比对运算等。由于最大正向分词匹配法和或最大逆向分詞匹配法同属于机械分词法，两种方法切分的结果都会产生错误率，而且同时出现错误的情况也在所难免。但是这并不影响该方法的使用。分词库与字典索引表是一个相互关联的数据结构，在运行期间需要相对稳定和保持静态不变。快速分词方法由于不涉及词性问题，新分词的增加，可通过获取新词的自动方法获得。自动获取新词并定期更新分词库及字典索引表，由于完全自主定义，而使得维护变得非常容易。技术实现通过socket提供的接口服务，可与Java、C#等语言通信，或者重新用其他语言编写，算法简约，不会存在移植性障碍。

参考文献：

[1] 庄新妍. 计算机中文分词技术的应用[J]. 呼伦贝尔学院学报，2010（3）.

[2] 李淑英. 中文分词技术[J]. 科技信息，2007（36） .

[3] 余战秋. 中文分词技术及其应用初探[J]. 电脑知识与技术，2004（32）.

[4] 刘红芝. 中文分词技术的研究[J]. 电脑开发与应用，2010（3）.