论文部分内容阅读
摘要：该文主要论述一种快速分词技术的实现。对于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至表3可以看出，字典索引中的首字开始和首字结尾，分别对应于正向分词库中的开始位置号和结尾位置号。字典的字对应分词首字相同的分词主要集中在正向分词库的某个局部范围。例如：以“一”开始的分词，集中在正向分词库的747042～752041的起止位置，有连续4999个分词，其最长分词有12个汉字。同样，字典索引中的尾字开始和尾字结尾，分别对应于逆向分词库中的开始位置号和结尾位置号。字典的字对应分词尾字相同的分词主要集中在逆向分词库的某个局部范围。例如：以“一”结尾的分词，集中在逆向分词库的760739～761220的起止位置，有481个，其最长分词有10个汉字。
2.3 分词库查找的效率
查找一个分词的过程首先确定分词的字头或者字尾，查找字典，再根据字典索引查找正向词库或逆向词库。接下来看查找的时间效率和空间效率。
2.3.1 时间效率
字典查找，“一”索引，其时间效率为最多（log221002 ≈）14.4次比较。
正向分词查找，“一”开始的分词，其时间效率最多为（log24999≈）12.3次比较。
逆向分词查找，“一”结尾的分词，其时间效率最多为（log2481≈）8.9次比较。
由于字典索引与分词库的设计安排，对于一个百万级的分词库来说，使用了字典索引给出的局部范围，使得查找的范围大大缩小。从而加快了折半查找的效率。如果采用完全折半查找词库，其时间效率最多为（log21200000≈）20.2次比较。局部折半查找最差也可以节省0.4～0.6倍的时间。
另外，采用内存与外存相结合，将字典索引21002个记录驻留在常驻内存中，使字典索引的运算直接在内存中完成，其运算时间几乎可以忽略不计，只需考虑局部折半查找外存文件定长记录所需的时间开销即可。因此，内存字典索引折半查找算法与外存分词库局部折半查找算法相结合，是一种非常快的分词查找方案。
2.3.2 空间效率
字典索引记录长度30字节，共21000个记录，实际空间615.3Kbyte。
分词词典记录长度50字节，目前有1200000个记录，实际空间57.22Mbyte。
字典索引常驻内存，占用小于1M的空间，是可以接受。而分词词典几十兆空间，不宜放在内存中实现，因而保存在外存文件中。内存只需3个数据结构共150字节即可，因此，空间效率也是很小的。
2.4分词切分算法
首先对正文中哪些可切分，哪些不可切分，作一个规定： 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，
关键词：正向分词；逆向分词；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至表3可以看出，字典索引中的首字开始和首字结尾，分别对应于正向分词库中的开始位置号和结尾位置号。字典的字对应分词首字相同的分词主要集中在正向分词库的某个局部范围。例如：以“一”开始的分词，集中在正向分词库的747042～752041的起止位置，有连续4999个分词，其最长分词有12个汉字。同样，字典索引中的尾字开始和尾字结尾，分别对应于逆向分词库中的开始位置号和结尾位置号。字典的字对应分词尾字相同的分词主要集中在逆向分词库的某个局部范围。例如：以“一”结尾的分词，集中在逆向分词库的760739～761220的起止位置，有481个，其最长分词有10个汉字。
2.3 分词库查找的效率
查找一个分词的过程首先确定分词的字头或者字尾，查找字典，再根据字典索引查找正向词库或逆向词库。接下来看查找的时间效率和空间效率。
2.3.1 时间效率
字典查找，“一”索引，其时间效率为最多（log221002 ≈）14.4次比较。
正向分词查找，“一”开始的分词，其时间效率最多为（log24999≈）12.3次比较。
逆向分词查找，“一”结尾的分词，其时间效率最多为（log2481≈）8.9次比较。
由于字典索引与分词库的设计安排，对于一个百万级的分词库来说，使用了字典索引给出的局部范围，使得查找的范围大大缩小。从而加快了折半查找的效率。如果采用完全折半查找词库，其时间效率最多为（log21200000≈）20.2次比较。局部折半查找最差也可以节省0.4～0.6倍的时间。
另外，采用内存与外存相结合，将字典索引21002个记录驻留在常驻内存中，使字典索引的运算直接在内存中完成，其运算时间几乎可以忽略不计，只需考虑局部折半查找外存文件定长记录所需的时间开销即可。因此，内存字典索引折半查找算法与外存分词库局部折半查找算法相结合，是一种非常快的分词查找方案。
2.3.2 空间效率
字典索引记录长度30字节，共21000个记录，实际空间615.3Kbyte。
分词词典记录长度50字节，目前有1200000个记录，实际空间57.22Mbyte。
字典索引常驻内存，占用小于1M的空间，是可以接受。而分词词典几十兆空间，不宜放在内存中实现，因而保存在外存文件中。内存只需3个数据结构共150字节即可，因此，空间效率也是很小的。
2.4分词切分算法
首先对正文中哪些可切分，哪些不可切分，作一个规定： 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，