一种适用于移动搜索的中文分词算法

贺菲菲， 贺 炎， 齐静娜

(1.中兴通讯股份有限公司 西安研发中心，陕西 西安 710114；2.西安邮电大学 计算机学院, 陕西 西安 710121)

一种适用于移动搜索的中文分词算法

贺菲菲1， 贺 炎2， 齐静娜2

(1.中兴通讯股份有限公司 西安研发中心，陕西 西安 710114；2.西安邮电大学 计算机学院, 陕西 西安 710121)

针对现有中文分词算法无法为移动搜索提供用户兴趣偏好信息的现状，提出一种改进的正向最大匹配中文分词算法。该算法基于逐字二分的分词词典机制，添加词分类信息，在词典中存储了每个词条的分类信息，分词时采用改进的次字区位码哈希非均匀分段机制进行正向最大匹配分词。实验结果表明，与逐字二分法相比，改进的分词算法其存储空间增加了13%，但时间效率提高了20%左右，且分词后可同时提取出词条的分类信息。

中文分词；词典机制；词分类信息

随着网络信息资源的飞速增长以及移动设备的普及，越来越多的用户习惯使用移动设备随时随地进行搜索。由于用户常常不能准确表达自己的查询意图，以及网络资源过于丰富导致信息迷失等原因，移动搜索给用户反馈了过多无用的信息。如何找出用户真实的查询意图，使用移动设备快捷地从海量网络资源中筛选出真正满足用户需求的信息，即个性化信息服务成为当代移动搜索引擎的主要发展方向[1-3]。

移动搜索引擎的首要任务就是进行中文分词，分词精确度对搜索引擎的查询结果将产生很大影响[4]。中文分词算法种类众多，大致可分为3大类。(1)基于字符串匹配的分词方法[5-8]：采用正向最大匹配、逆向最大匹配等策略将汉字字符串与词典中的词条进行机械式匹配，如果找到该字符串，则识别出一个词条。该分词法对词典的依赖性很强，词典中未登录词条和新词都无法被切分出来，且无法根据文档的上下文语义来分词。(2)基于理解的分词方法[6]：通过机器学习方法训练计算机的思维能力，模拟人脑对句子的理解过程，在大量句法信息、语法信息的基础上对句子进行句法、语法分析，处理歧义现象并理解句子。由于中文的复杂性与模糊性，现有技术很难把海量知识准确转化成机器可识别的表达形式，分词准确率不高。(3)基于统计的分词方法[9]：不需要词典等先验知识，通过统计字与字同时出现的概率来判断是否构成词。基于概率统计的分词系统在评测中优于基于字符串匹配和基于理解的分词系统。但这种方法经常将一些高频度、但并不是词的常用字组合为词条，导致分词错误，且计算开销较大，分词效率较低。

目前，移动搜索引擎大多采用上述中文分词算法。但这些算法往往不能满足移动搜索轻量级、执行速度快、分词精确性较高等要求，也不能提供可以反映用户真实搜索意图或兴趣偏好的个性化信息。为了提高分词效率，并在分词的同时提取能在一定程度上反映用户真实搜索意图的信息，便于从中提取用户的兴趣偏好，本文提出一种改进的正向最大匹配分词算法，通过改进逐字二分法分词词典机制，为每个词条添加了分类信息，并采用次字区位码哈希非均匀分段机制，进行正向最大匹配分词处理。

1 逐字二分的分词词典机制

逐字二分的分词词典[10]由首字哈希表、词索引表和词典正文3部分组成。通过首字哈希表的定位，结合词索引表，可以很方便地指定词在词典正文中可能的位置范围，进而采用逐字二分法在词典正文中进行定位。其基本结构[10]如图1所示。

图1 逐字二分法的基本结构

2 改进的分词词典机制和分词算法

为了提高分词效率，并在分词的同时提供词分类信息，方便从中提取用户的兴趣偏好，对逐字二分的分词词典机制和正向最大匹配分词算法进行改进。

2.1 基于词分类信息的词典机制

主要从两个方面对逐字二分的分词词典机制进行改进。

(1)词条分类设计，添加分类信息

在改进的分词词典中，词条根据内容进行三级分类，按照由上而下的顺序给各类别名分配两位十进制数进行编码，并按照“主类在前子类在后”的方式将代表词条分类信息的编码以及词频等信息作为词条的属性存入词典中。

(2) 增加次字区位码分段哈希索引表

为了提高次字查询效率，可直接使用次字哈希方法或多字哈希机制[11-12]，但这种方法会使次字哈希表的长度过长，或造成次字哈希表难于构建，导致词典的存储结构复杂。

在逐字二分的分词词典中增加一张次字区位码分段哈希索引表。对原始词库中所有词条的次字分布范围进行统计，根据统计结果对次字进行非均匀分段，将首字相同的词条按照次字的区位码进行哈希运算，分别映射到不同的分段内(段号为：1-20)，使各段内词条数目大致相同，从而通过增加少量存储空间达到缩小次字查找范围的目的。

改进的词典结构包括首字哈希表F_hash、次字区位码非均匀分段哈希索引表S_hash、次字索引表S_index和词典正文Last_table 4个部分，其逻辑结构如图2所示。

图2 词典逻辑结构

2.2 改进的正向最大匹配法

基于改进的词典结构，采用与之相适应的改进的正向最大匹配分词法，其分词过程如图3所示。

改进的分词算法主要在以下两个方面对正向最大匹配分词算法进行改进。

(1)基于改进的词典结构，次字 W2 采用次字区位码哈希非均匀分段机制进行查找。首先，根据W2的区位码进行哈希处理，得到其分段号wordIndex；然后，根据wordIndex的值在首字 W1 对应的S_hash表内进行次字区间regionIndex的定位，进而实现在regionIndex对应的S_index表内对次字的查找。

(2)在次字定位后，可得到 W1W2 对应的Last_table表。改进的分词算法根据Last_table表中存储的词条长度动态截取当前中文字符串，将截取到的字符串与Last_table表中相应的词条进行匹配，并综合考虑切分词长及词频选取最优的切分结果。在该分词过程中，词的切分长度由待匹配词长动态决定，避免了传统最大匹配法中匹配词长固定所造成的效率低下或错误切分。

图3 分词过程

3 实验结果及分析

(1)实验环境

系统服务器端操作系统为Windows Server 2008，开发语言采用Java ，开发工具采用JDK 6.0，MyEclipse 8.5，Tomcat 6.0，数据库系统采用MySQL5.5。

(2)实验内容

为了验证改进的分词词典机制和分词算法的有效性，分别使用逐字二分法和改进的分词算法对测试文本(总大小为31KB)进行分词处理，并从时间、空间复杂度和分词后所能显示的词分类信息这两个方面进行对比。

(3)实验结果及分析

在分词过程中，逐字二分法占用的空间大小为3 553 068 字节，分词时间为156ms，而改进的分词算法占用的空间大小为4 014 108字节，分词时间为125ms。可以看出，由于在词典中存储了词分类信息，改进的算法比逐字二分法增加了13%的存储空间；同时，改进的分词算法采用次字区位码哈希非均匀分段机制，缩小了次字的查找范围，使得测试文本分词的时间效率提高了20%左右，且分词后可同时提取出词分类信息。举例如下：输入以下待分词的字符串“计算机网络是计算机技术与通信技术结合的产物”，其输出结果如图4所示。

图4 分词结果测试

图4中切分出来的第一个词是“计算机网络”，其所属分类为“031 402,031 404,032 001”，表明该词属于“工程应用类”下的“计算机技术”子类。

4 结束语

改进的最大匹配分词算法结合次字区位码哈希非均匀分段机制，将首字相同的词条根据次字区位码进行非均匀分段，缩小了分词过程中次字的查找范围，提高了分词速度。随着词典中词条数目的增加，该方法的优越性会更为显著。同时，该分词词典中添加了词条的分类信息，分词后可同时获取所有词条的分类信息。实验结果表明，与逐字二分法相比，改进的分词算法在存储空间上虽然有所增加，但时间效率却提高了20%左右。分词后提取出的词条分类信息可用于进行查询的扩展，实现个性化的搜索查询。通过分析用户历史查询词条的分类信息，可以提取出用户在一段时间内的兴趣偏好，为搜索结果的个性化推荐提供一种有效方法。

[1] 梁琛，王忠民，范琳. 移动搜索终端用户行为调查研究[J].西安邮电大学学报，2014，19(2):108-112.

[2] 贺炎，杨爽，王忠民. 我国移动搜索产业共赢合作模式探讨[J].西安邮电大学学报，2013，18(6):95-99.

[3] 王忠民，史育兰，张荣，等. 一种移动智能搜索个性化客户端[J].西安邮电大学学报，2013，18(3):71-75.

[4] 赵川，杜玲，岳鹏，等.基于中文的自然语言理解初探[J].现代电子技术，2007(6):82-85.

[5] 梁喜涛，顾磊 .中文分词与词性标注研究[J].计算机技术与发展，2015,25(2):175-180.

[6] 林冬盛.中文分词算法的研究与实现[D].西安：西北大学，2011:7-16,19-22.

[7] 杨毅，王禹桥. 中文分词词典机制：次字拼音首字母哈希机制[J].计算机工程与设计，2010,31(6):1369-1375.

[8] 焦娇. 基于二次哈希并逐字二分匹配的中文分词改进算法[J]. 信息与电脑，2010(9):113.

[9] 李惠. 组合型中文分词方法的研究[D].广州：广东工业大学，2014:7-12.

[10]吴晶晶，荆继武，聂晓峰，等. 一种快速中文分词词典机制[J].中国科学院研究生院学报，2009,26(5):703-711.

[11]罗洋.一种基于双哈希二叉树的中文分词词典机制[J].计算机应用与软件，2013，30(5):251-253.

[12]周俊，郑中华，张炜. 基于改进最大匹配算法的中文分词粗分方法[J].计算机工程与应用，2014，50(2):124-128.

[责任编辑：祝剑]

A chinese word segmentation algorithm for mobile search

HE Feifei1, HE Yan2, QI Jingna2

(1. ZTE Corporation, Xi’an R & D Center, Xi’an 710114, China; 2.School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

As existing Chinese word segmentation algorithm can’t provide user interest information for mobile search, an improved FMM segmentation algorithm is proposed. Based on a new dictionary mechanism which contains words’ classified information, the algorithm performs Forward Maximum Matching by the improved second word area code hash non-uniform segmentation mechanism. Experimental results show that compared with the Verbatim dichotomy, the storage space of the improved algorithm is increased by 13%, but the time efficiency is improved by about 20%, and the words’ classified information is extracted simultaneously.

chinese word segmentation, dictionary mechanism, words’ classified information

10.13682/j.issn.2095-6533.2015.04.013

2015-03-20

国家自然科学基金资助项目(61373116)；西安邮电大学青年基金资助项目(ZL2014-27)

贺菲菲(1980-)，女，硕士，工程师，从事移动终端软件开发、数据业务等研究。E-mail：he.feifeixa@zte.com.cn 贺炎(1980-)，女，硕士，讲师，从事机器学习、移动搜索等研究。E-mail：heyan0220@xupt.edu.cn

TP391.1

A

2095-6533(2015)04-0062-04