《基于分组hash与变长匹配的中文分词技术》-工学论文，计算机论文-论文范文参考-科学狗论文网

标题

基于分组hash与变长匹配的中文分词技术

范文

杨光豹杨丰赫毛贵军

摘要：中文分词是海量中文信息处理的基础任务，分词的准确性与分词速度是最为重要的。但是现有技术在分词时，准确性与分词速度却是无法调和的。为了提高中文分词的速度，同时又不因缩短初始字符串长度造成准确性降低，提出使用正则表达式进行变长字符串的截取与对词库进行分组散列的技术。通过理论分析，该技术在时间复杂度上从原来的o（n*n）下降到o（n），在精确度上又以句子长度作为动态变化的初始字符串长度，从而避免长词的丢失，保证了分词的准确性不受损失。

关键词：中文分词; 正则表达式; 散列; 时间复杂度

中图分类号：TP391? ? ? ? ? 文献标志码：A? ? ?文章编号：1006-8228（2019）04-52-04

Abstract： Chinese word segmentation is the basic task of mass Chinese information processing. The accuracy and speed of word segmentation are the most important. However， the accuracy and the speed of word segmentation cannot be reconciled with in the existing technologies. In order to improve the speed of Chinese word segmentation without the accuracy reduction caused by reducing the initial string length， this paper proposes the use of regular expressions to intercept variable-length strings and to hash word libraries. Through theoretical analysis， this technology reduces from the original O（n*n） to O（n） in terms of time complexity， and takes the sentence length as the dynamic initial string length in terms of accuracy， so as to avoid the loss of long words and ensure that the accuracy of word segmentation is not damaged.

Key words： Chinese word segmentation; regular expression; hash; time complexity

0 引言

中文分词技术是中文文本信息处理的基础，它的准确性与分词性能直接影响到后续的信息处理。在大数据与人工智能强劲发展的今天，中文分词技术在中文信息处理中起着至关重要的作用，尤其是在分词性能要求较高的海量中文信息处理系统中，比如搜索引擎等。现有的主流分词技术基本上都是基于“最大匹配算法”的思想。但其技术在设计与实现中一直存在分词准确性与分词性能相互制约的矛盾。两者不能兼顾。本文在中文分词技术上提出采用變长最大匹配与分组hash算法，能有效解除两者的矛盾关系，使分词准确性与分词处理性能都得到很大提高。

1 主流中文分词技术背景概述

现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法[1]。主流中文分词以字符串匹配为主，它的核心思想就是“最大匹配算法”，该算法的设计与实现技术包含两个核心内容：分词算法与词典结构[2]。在分词算法上出现各种流派：有正向最大匹配算法，逆向最大匹配算法，双向匹配算法，以及它们的各类改进型观点。比如双向匹配算法就是对正向最大匹配算法与逆向最大匹配算法的一个改进，其针对一个字符串，分别从两个方向进行处理 [3]。

而针对正（逆）向最大匹配算法的改进方向主要是优化词典结构，提升分词匹配效率。孙茂松设计并考察了三种典型的分词词典机制：整词二分、TRIE索引树及逐字二分，并且对它们的时间、空间效率进行了比较[4]。熊志斌等人后来提出了一种改进的TRIE树词典结构，根据词典中词语的长度调整字符串的相应长度，其目的就是为了减少匹配次数，提高中文分词速度[5]。

再如姚兴山提出的词的首字，次字，三字，四字HASH表、词索引表和词典正文的词典结构[6]。以及刘勇等人提出的根据不同首字设置恰当的最大词长以提升算法效率的双字哈希结构等，最大匹配算法的改进方法都是以减少无效匹配，提升分词性能为目的的[7]。

到目前为止，现有的分词技术均不可避免地存在一些共同的缺陷：

⑴ 准确度问题

所有的现有技术中都有一个共同特点就是它们在进行分词之前必须取一个初始字符串长度作为待处理的字符串进行分词。这将产生一个不可避免的缺陷就是常会将一个完整的长词分割掉。比如：假设确定初始字符串长度为8，则对字符串：“恰似一江春水向东流”这个词来说，它们将会被拆散了。而如果初始字符串取词库中最长的词长，则将出现大量的无效查询，从而会大大影响分词性能。

⑵ 性能问题

因为初始字符串长度越长，越能符合“最大匹配算法”思想，分词会越准确，但它却让分词过程的性能快速下降。由于对这个字符串进行分词要用双重循环对词库进行查询，假设这个字符串长度为n，词库记录数为m，在最坏情况，传统顺序查询的时间复杂度为O（n*n*m）;对按折半查询法来说，它的时间复杂度是O（n*n*log2n）。而对查询性能相对较好的hash表法来说，比如像姚兴山提出的技术，它对四字以内的词通过hash表间的级连进行查询，假如字典中四字以上的词数量是s个，则它的时间复杂度为O（n*n*（4+log2s））。从时间复杂度来看，这些技术都没有解决截取的初始字符串越长分词性能越低，初始字符串长度增加将使分词效率快速下降的问题。而且字符越长，无效的匹配运算将越多。

2 一种基于数组词库与变长匹配的中文分词技术

要提高分词的准确性与运算性能，在算法设计与实现上可从以下两方面展开：①改进词典结构与内容;②改进扫描方式。为了解决现有分词处理技术中的第一个缺陷，避免将一个词拆散掉，同时不错过任何一个长词，本文提出了变长最大匹配算法的设计思想。

2.1 变长最大匹配算法

这种方法的初始处理字符串的长度不再是一个固定长度的字符串，而是可变的，它是取一个处于标点符号之间的字符串。我们知道在标点符号之间取字符串，多数情况是一个完整的句子，由于中文的任何一个词都存在标点符号一侧，不可能将一个词分在标点符号的两侧，所以截取标点符号之间的字符串作为初始字符串，可以保证不会将一个词拆散掉。它不错过任何一个词库中有的长词！从而避免了把一个词拆散的可能性，能够最大程度地符合“最大匹配算法”的思想。

2.2 词库分组hash优化技术

通过变长最大匹配算法的设计思想从文章中截取字符串能保证词的完整性，也尽最大程度地符合中文分词的“最大匹配算法”的思想。但这种方法有可能会使分词处理的初始字符串很长（一个长句子）。如果采用传统的方法进行查询的话，在性能上有可能将是灾难性的后果！为此本文对词库采用了分组hash法进行优化。在理论上，该技术能将分词处理的内循环查询过程的时间复杂度降为O（1），总的时间复杂度降为O（n）。这样可以保证初始字符串无论取多大都不影响分词运算的总性能。因为时间复杂度为O（n）时，字符串的运算量是随字符串长度而线性增长，总运算量不会增加。词库结构设计方法如下（见图1）。

首先，以词的长度为分类依据对词库进行分类，将整个词库的所有词串分成多组记录，每组词的长度相同。加载词库时先以词库中最长词的长度作为数组的长度建立一个关联集合的数组，数组的各元素（分词库）分别存放词库中同组的记录;数组元素的下标=词库中的词的长度-1。依据这样的原则将词库中的记录按其包含中文字的个数分组加载到相应的数组分词库中去。结果是：词长度为1的词加载到数组下标为0的分词库中，长度为2的词加载到下标为1的分词库中……依次类推，将词库中长度为10的词加载到下标为9的词库中。这样就把每一个词的字符串的长度与数组的下标进行了一一映射。

如此一来，要查询字符串就变得非常直接简单，根据字符串的长度确定数组元素下标（分词库的外部索引），比如要查询长度为10的字符串，只需要去下标为9的分词库中查询，而不去其它分词库中去找，假设初始扫瞄的字符串长的长度为n，词库总词汇数为m，内循环一次，就是从最长的词查询到最短的一个字，如果词库内都采用最原始的顺序查询法，最坏情况下，用传统方法需要查询内循环就需要n*m次，而用分组词库法只需查询m次。

在词库加载时，各个分词库中的词都采用hash算法进行存储与查询。查询字符串时，字符串的长度决定外部索引，字符串hash值决定内部索引。这就是查询字符串的分组hash算法。

3 分词算法的执行过程

3.1 初始字符串的截取

截取字符串的方法可以通过正则表达式在循环处理分词之前进行。具体方法是：①设定待处理文章首字符指针;②设定一个正则表达式用于查询标点符号的位置;③将文章中出现在首指针后的第一个标点符号位置设定为尾指针;④将循环指针设定在首指针+数组长度的后一位置（初始字符串长度小于数组长度时设在尾指针）。这样在首指针与尾环指针之间就是我们要截取的初始字符串（见图1）。而在首指针与循环指针之间的字符串就是每一次内循环要查询的字符串。由于分词时应该是词越长越好，但并非初始字符串越长越好，有时候一个句子也只有四、五个字，如果采用固定长度的方法将会造成很多无效的匹配运算。而采用这种以标点符号为分隔标志的变长方法可以有效提升准确度，同时减少无效匹配。

3.2 分词的循环过程（见图1）

变长最大匹配算法也是按先查询最长的词，然后是次长的词这样的顺序进行匹配查询的，所以分词循环查询的内循环是使循环指针从后向首指针方向移动，而外循环是跳过已提取的词，使首指针向尾指针方向移动。刚开始循环指针从首指针+数组长度的后一位置开始循环，因为比这更长的字符串在词库中肯定是没有的，所以循环指针没有必要从尾指针开始循环。查询过程是：首次取首指针与循环指针之间的字符串（10个字），该字符串长度决定词库的外部索引（就是数组下标），该字符的hash值决定词库的内部索引。所以根据这个字符串可以直接到下标为9的词库中查询结果，它无需进行遍历查询。如果词库中没有查到，则将循环指针前移一个字符，取此前面的字符串（9个字），到下标为8的分词库中查询……依此类推。如果查询到词库中该字符串，则提取该词，之后将首指针往后跳到循环指针的位置，然后循环指针重置在首指针+数组长度的后一位置，但不超过尾指针。如果超过尾指针，则循环指针设定在尾指针位置即可。等内外循环都完成了，则该句子分词结束，然后再根据正则表达式截取下一个句子进行分词。

3.3 变长扫瞄分词技术的优势

首先，在取得的初始字符串较短时（小于词库中最长词的长度）。外循环指针每次后移都使待处理的字符串越来越短，内循环次数将随之减小，直到减少到只需一次。它减少了循环后期的匹配查询，但不会对分词准确性产生负面影响。处理一个长度不超过最大词长的句子，最坏情况用传统方法需要匹配n*n次，而采用變长初始字符串的分词法只需要匹配n*（n+1）/2次。因为传统方法每次内循环都要从最大词长开始，而本方法只顾及尾指针前的字符，不管尾指针后的字符，因为尾指针之后的字符应在处理后一个句子时该考虑。

其次，在取得的初始字符串很长时。由于超过数组长度，就意味着超长的字符串不在词库中，所以循环指针可以忽略掉这些字符串，而直接定位在与数组同长度的后一位置上（图1中的10的后一位置）。略去了超长词的无效匹配。

第三，在进行分词时，对初始字符串截取的长短不会影响性能，因为它对超过词库中最长词的长度的字符串会忽略不查，而对长度小于或等于词库中最长词的字符串，都是在各分词库中查询。在顺序查询最坏情况下，它的查询次数合计与在整个总词库中查询一次相当，换句话说就是采用分组词库时内循环中各次查询的累加与采用非分组词库的一次查询相同。

3.4 步进式双重扫瞄方法

由于单一的扫瞄方式不可避免会发生切分错误。为了减少分词的切分错误或歧义，本文采用“步进式”多次扫瞄的方式。方法是将分词过程进行两次循环：比如“当中华人民共和国成立的时候”这句话，第一次循环之后，切分结果是：（“当中”，“华人”，“民”，“共和国”，“成立”，“的”，“时候”），将结果存放到临时变量中;然后将首指针向后移动一个汉字进行第二次扫瞄分词，结果是（“當”，“中华人民共和国”，“成立”，“的”，时候），将结果存放到另一变量中，然后将两次分词的结果进行比较。依据最大匹配算法的思想，结果中长度越长，词的数量越少，则切分越科学，本文按长度优先，数量兼顾的原则来选择。由于最大长度第一次是3个字，而第二次是7个字，所以选择第二次扫瞄作为分词结果。通过步进式双重扫瞄的方式可以大大减少分词中的错误切割，提高分词的科学性。

4 结论

本文提出的将词库进行分组hash算法，同时通过正则表达式进行初始字符串的截取，以及采用步进式多重扫瞄技术。一方面可以将字符串长度和字符串hash值直接与词的索引地址映射，让分词循环运算的总的时间复杂度降低到O（n）。另一方面，可以提高分词的准确度，避免将词从中间拆散，减少词的歧义。这是本文在中文分词技术中的创新点。

本文存在的问题是采用hash表存储词库不可避免带来这样的问题：字符串的hash值的计算是通过hash函数计算获得的，这个过程需要时间，hash函数的性能会直接影响查询的性能;同时hash冲突的处理也会降低查询性能，所以实际的时间复杂将是大小o（n）。

参考文献（References）：

[1] 孙铁利，刘延吉.中文分词技术的研究现状与困难[J].信息技术，2009.7：187-189

[2] 奉国和，郑伟.国内中文自动分词技术研究综述[J].图书情报工作，2011.2：41-45

[3] 陈之彦，李晓杰，朱淑华，付丹龙，邢诒海等.基于Hash结构词典的双向最大匹配分词法[J].计算机科学，2015.42（s2）：49-54

[4] 孙茂松，左正平，黄昌宁.汉语自动分词词典机制的实验研究[J].中文信息学报，1999.14（1）：1-6

[5] 熊志斌，朱剑锋.基于改进Trie树结构的正向最大匹配算法[J].计算机应用与软件，2014.5：276-278

[6] 姚兴山.基于Hash算法的中文分词研究[J].现代图书情报技术，2008.3：78-81

[7] 刘勇，魏光泽.基于双字哈希结构的最大匹配算法机制改进[J].下电子设计工程，2017.25（16）：11-15

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。