搜索引擎通常由信息收集和信息检索两部分组成，中文分词技术作为搜索引擎信息检索的核心技术之一，在保证分词的专业、准确、快速的同时，还要保证分词系统与搜索引擎系统内其他相关模块彼此之间良好的通信，从而达到分词系统具备高效性、专业性、适用性的目标。
现有的中文分词技术主要有三大类方法：基于字符串匹配的分词方法，基于理解的分词方法，基于统计的分词方法［１］。基于字符串匹配的分词方法，包括正向匹配法、最短路径法等，是利用已经建立起来的电子词典，对输入文本进行简单匹配，若在词典中到某个字符串，则匹配成功，该方法的优点是易于实现，但精度较低。基于理解的分词方法其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。这种分词方法需要使用大量的语言知识和基础信息资源，规则维护困难，但是切分准确率高。基于统计的分词方法通过对语料中相邻共同出现的各个字的组合频度进行统计，计算它们的互现信息，互现信息体现了汉字之间结合关系的紧密程度。这种方法只需对语料中的字组频度进行统计，不需要切分词典，能够较高效地识别未登录词，但是此方法需要大量原始文档，且计算量大，如果提取结果会有意义不完整的字符串，导致准确率不高。
对于一个成熟的中文分词系统来说，不可能单独依靠某一种算法来实现，需要综合不同的算法来处理具体的问题。本文在对现有中文分词技术研究的基础上，结合化工领域的应用背景，提出了一种改进的中文分词算法在化工专业领域应用的研究，从分词词典机制的设计，到对现有算法深入分析研究的基础上，提出了一种基于词典并结合改进的最短路径切分算法而实现的分词机制，它可以对含有大量化工类
专业词汇的中文文档进行高效的分词，实验验证取得了较好的效果，为网上化工类信息的快速准确获取提供了基础和前提。
１分词系统模型
系统主要包含两个重要的部分：词典机制以及分词机制，整体框架图如图１所示。
一种适用于专业搜索引擎的中文分词系统研究
王硕，尤枫，山岚，赵恒永
ＷＡＮＧＳｈｕｏ，ＹＯＵＦｅｎｇ，ＳＨＡＮＬａｎ，ＺＨＡＯＨｅｎｇ－ｙｏｎｇ
北京化工大学信息科学与技术学院，北京１０００２９
ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＣｈｅｍｉｃａｌＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ１０００２９，Ｃｈｉｎａ
Ｅ－ｍａｉｌ：ｏｚｚｙ＿００３＠ｓｏｈｕ．ｃｏｍ
ＷＡＮＧＳｈｕｏ，ＹＯＵＦｅｎｇ，ＳＨＡＮＬａｎ，ｅｔａｌ．ＲｅｓｅａｒｃｈｏｆＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎｓｙｓｔｅｍａｐｐｌｉｅｓｉｎｐｒｏｆｅｓｓｉｏｎａｌｓｅａｒｃｈｅｎｇｉｎｅ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（１９）：１４２－１４５．
Ａｂｓｔｒａｃｔ：ＴｈｉｓａｒｔｉｃｌｅｂａｓｅｄｏｎｔｈｅｒｅｓｅａｒｃｈｏｆｃｕｒｒｅｎｔｔｅｃｈｎｏｌｏｇｙｏｆＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎ，ｐｒｏｐｏｓｅｓａＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎｓｙｓｔｅｍｔｏｔｈｅｃｈｅｍｉｃａｌｆｉｅｌｄ，ｆｉｒｓｔｉｎｔｒｏｄｕｃｅｓｔｈｅｄｉｃｔｉｏｎａｒｙｍｅｃｈａｎｉｓｍｃｏｍｂｉｎｅｄｆｉｒｓｔｃｈａｒａｃｔｅｒｈａｓｈｉｎｄｅｘｉｎｇｗｉｔｈｂｉｎａｒｙｓｅａｒｃｈ，ｔｈｅｎｉｎｔｒｏｄｕｃｅｓａｎｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｌｅｖｅｌ－ｐａｔｔｅｒｎｓｈｏｒｔｅｓｔｐａｔｈｍｅｔｈｏｄｗｉｔｈｔｈｅｃｏｍｐｌｅｍｅｎｔａｒｉｔｙｏｆｔｈｅｐａｔｈｓｓｅｌｅｃｔｉｏｎｍｅｃｈａｎｉｓｍ，ａｔｌａｓｔ，ｂｙａｎａｌｙｚｉｎｇｔｈｅｅｘｐｅｒｉｍｅｎｔ’ｓｒｅｓｕｌｔ，ｔｈｉｓｓｙｓｔｅｍｓｈｏｗｓａｄｅｓｉｒｅｄｅｆｆｅｃｔｉｖｅｎｅｓｓａｓｗｅｌｌａｓｅｌｉｍｉｎａｔｉｎｇｔｈｅａｍｂｉｇｕｉｔｙｔｏｓｏｍｅｅｘｔｅｎｔ．
Ｋｅｙｗｏｒｄｓ：Ｃｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎ；ｓｅａｒｃｈｅｎｇｉｎ
ｅ；ｆｉｒｓｔｃｈａｒａｃｔｅｒＨａｓｈｉｎｄｅｘｉｎｇ；ｌｅｖｅｌ－ｐａｔｔｅｒｎｓｈｏｒｔｅｓｔｐａｔｈｓ；ｐａｔｈｓｓｅｌｅｃｔｉｏｎ
摘要：在对现有中文分词技术研究的基础上，提出了一种应用于化工专业领域的中文分词系统，先后介绍了首字哈希结合二分查的词典机制，以及结合路径选择机制而改进了的层进式最短路径切词算法，并经过实验分析，在保证切分效率的同时，在一定程度上达到了消除歧义的效果。
关键词：中文分词；搜索引擎；首字哈希；层进式最短路径；路径选择
ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２－８３３１．２００８．１９．０４３文章编号：１００２－８３３１（２００８）１９－０１４２－０４文献标识码：Ａ中图分类号：ＴＰ３９１
收稿日期：２００８－０２－０１修回日期：２００８－０４－
１８
水水壶水声水处理水处理剂
Ｅｎｔｉｒｅ
９９
表１
词典的物理结构
系统采用基于字符串正向匹配法对源语句进行初分，将初分后得到的语言信息采用层进式的最短路径法进一步处理，并结合一种计分机制作为最短路径法的路径选择理论依据，保证切分结果的准确。
词典机制是分词系统中一个重要的基础部分。系统在进行语言处理时需要频繁查询分词词典，如何有效地对分词词典进行快速查询将直接影响系统的整体性能。同时，网络搜索引擎处于一个大规模、开放的语言环境中，需要不断对词典进行添加新词、删除词条等维护工作，这就要求分词词典必须有一个灵活、快速的更新机制。本算法通过结合一个包含专业词汇的分词词典，并完成其数据结构的设计，达到词典在内存中的快速加载并作为后续的处理策略的基础。
分词机制是基于词典的最短路径法（即最少切分方法），分词输出使每一句中切出的词数最小。通过查询词典，出字符串中存在的所有词，构造一有向无环图，并采用层进式最短路径法来得到最后的切分结果。所谓最短路径法，其核心规则就是使切分出来的词数目最少，一般理解为指定长度内，到达终点所经过的路径最短，换一个角度，也可以理解为指定路径长度的情况下，跨过的顶点数最多。
２词典机制
２．１设计原则
由于文本的切词效果完全依赖于系统的基本词典，当基本词典的结构组织不合理或词典中存储的词条信息满足不了对某一专业领域信息查询的需要时，将影响到对信息的查全查准率。
在基于词典的词条模式匹配分词方法中，词条的组织和词典结构的设计是否合理是影响文本分词效率和信息查全查准率的一个重要因素［２］。理论上词典中的词条越多，切词的效果就越好。但是随着词条数的增加，切词过程需要过多的模式匹配，切词效率呈下降趋势；而词条过少，使得一些词语无法切分，影响对文本信息的查全，因此需要在词典的规模和质量之间进行权衡。另外，词典应考虑到具体分词算法的需要，进行一些特定的标识或是相关的统计信息，如应用于某一领域的垂直搜索的词典，需要对该领域的专业词汇做权重的标识，对于歧义处理要求较高的分词系统，需要对词典加入词频和词性的统计信息等等。
另一方面，由于在进行分词处理时需要频繁查询分词词典，如何有效地对分词词典进行快速查询将直接影响系统的整体性能，词典在内存中的加载策略和读取方式与具体的分词算法相互依托，因此，确定一种高效的词典内存组织形式，为分词提供准确有效的切分保证，是非常必要的［３］。
中文字符unicode查询综上所述，词典的设计原则，主要从词典的物理结构和词典加载于内存中的逻辑结构两方面来考虑。
２．２词典物理及逻辑结构
先引入两个概念：
定义１如果一个字不单独作为词使用，称其为半词。半词既包含了成词语素，也包含了不成词语素，后者一定
是半词，比如“民”，前者则要看它作为语素的使用频度高，还是作为单字词的使用频度高，例如“见”。
定义２如果一个字更倾向于自己成词而不倾向于和其他的字组成词，这种单字词称其为“整词”。
这类词就是一般说的单字高频成词语素，例如“人、
说、我”等。
分词词典的物理结构按照Ｊａｖａ内建的Ｕｎｉｃｏｄｅ码（从“一”到“龟”）顺序排列，首字相同的词条顺序排列，并为专业词汇加注一个标志位以标识其权重，从而提升该词汇在后续算法处理中的优先级别；同时，为了配合最短路径分词算法的路径选择策略，需要对词典的物理结构进一步扩充，将通过标识位
Ｅｎｔｉｒｅ，对词典中一些单字词进行半词或整词的标识，词典的最终物理结构如表１所示。
词典在内存中的数据结构ＷｏｒｄＤｉｃｔｉｏｎａｒｙ类采用双数组策略实现，即将所有首字相同的词条（ＷｏｒｄＥｎｔｒｙ类）构成数组作为一个词块（ＷｏｒｄＢｌｏｃｋ类），再通过将这些词块构成词块数组从而形成词典在内存中的数据结构。即对词典中的词条根据其首字内码相应地放入数组ＷｏｒｄＢｌｏｃｋ［ｉ］（ｉ为相应汉字的
Ｕｎｉｃｏｄｅ码）中，而每个ＷｏｒｄＢｌｏｃｋ［ｉ］中又包含有一个数量为ｎ的ＷｏｒｄＥｎｔｒｙ数组（ｎ为首字相同的词条个数），通过这种双数
组结构进行词典在内存中的管理和维护。
由于Ｕｎｉｃｏｄｅ码从１９９６８￣４０８６３所有汉字之中包含一些无意义的字，形如
，倘若不加筛选地一
次性加载，势必会造成空间的浪费、增加无效的匹配查询次数、加大维护的难度等问题。因此，要对加载到内存中的首字序列进行筛选，摒弃将词条不加任何处理而全部加载于内存的策略，只把词表中出现的首字词按序列码放入数据集合中。
经过筛选进而采用的双数组加载策略，结合Ｈａｓｈ结构构成最终的词典机制。最理想的是通过哈希函数———待匹配字符串的首字符一次即定位到查表中匹配元素，但在实际应用过程中还无法达到这种理想状态。因此，采用合理的方式来调节数据块的分配，控制均匀性，提高空间利用率，并尽可能地缩小查范围是哈希函数设计的首要原则。这里不是将绝对的
Ｕｎｉｃｏｄｅ码作为数组下标ｉ，而是将其与Ｕｎｉｃｏｄｅ码起始值
（‘一’－１９９６８）的差值作为数组的索引从而构成哈希算法，可以将每个词条首字作为哈希函数的索引项，即通过词条的首字哈希，结合二分查的策略即可索引定位到以该字为首字的所有词条。词典的逻辑结构如图２所示。
路径集合他／说／的／确实／在理他／说／的确／实／在理他／说／的确／实在／理
总分数
１＋１＋１＋１＋１＝５分１＋１＋１＋２＋１＝６分１＋１＋１＋１＋２＝６分
表２
评分结果
３分词机制
算法的基本思路是通过查询词典，通过正向匹配算法出
字符串中存在的所有词，进行源语句的初次切分，从而根据初分后的语言信息构造一个有向无环图，之后采用层进式的最短路径法对有向无环图进行处理，并依据一种计分机制来对处理过程中可能出现的多条路径选择情况进行判断，最终得到切分结果。
３．１源语句初分
算法策略首先要根据首字哈希结合二分查的字符串正
向匹配策略，对源语句进行初分，为构造有向无环图提供基础和前提。
初分的词语匹配过程是标准的二分查，若记ｎ为所有汉字作首字时的平均词数，假设每个词被查询的机会均等，则查一个词的计算复杂度为Ｏ（ｌｏｇｎ）［５］。
查某个特定的词条具体算法描述如下：
步骤１根据待查词条的首字符的Ｕｎｉｃｏｄｅ码利用Ｈａｓｈ方法，即计算词条首字符的与‘一’之间的Ｕｎｉｃｏｄｅ码差值作为索引，得到对应ＷｏｒｄＢｌｏｃｋ数组的首地址；
步骤２若待查词条为单字词，则查结果必定返回为完全匹配，并记录此单字词是否为整词或是半词的信息；
步骤３若待查词条非单字词（词条长度大于等于２），则对所有首字为该字的词条进行二分查。
步骤４在词典中查源字符串，若到，则返回索引号（即ＷｏｒｄＥｎｔｒｙ数组下标），并将查标志位置１；如果完全失配，则将查标志位置－１，返回０；如果部分匹配，则将查标志位置０，返回最接近的索引号。
经过正向匹配法的初分，为有向无环图的构造提供了必要的节点信息。
３．２初分后语言信息处理
经过基于正向匹配算法的源语句初分，就可以根据切分出
的各节点信息构造切分路径的有向无环图，进而通过最短路径算法得到分词最终的结果。
最短路径匹配算法是先根据与词典匹配后的分词信息，构造词语切分的有向无环图。这样，每个词对应图中的一条有向边。若付给相应的边长一个权值，然后针对该切分图，在起点和终点的所有路径中，求出长度值为最短的一条路径，这条路径上包含的词就是该句子的切分结果［６］
。
可以理解为指定长度内，到达终点所经过的路径最短，换一个角度，也可以理解为指定路径长度的情况下跨过的顶点数最多。
进一步说明，引入如下模型：
设Ｓ＝ｃ１ｃ２…ｃｎ为需要进行切分的字符串，其中ｃｉ（ｉ＝１，２，…，ｎ）为汉字字符，ｎ≥１为字符串的长度。对应每个汉字字符，建立一个节点，所有节点组成一个集合，对该集合作如下工作：
（１）根据其表示汉字字符在字符串中的位置，分别编号为：
Ｖ０，Ｖ１，Ｖ２，…，Ｖｎ。
（２）若Ｗ＝ｃｉｃｉ＋ｌ…ｃｊ是一个词，则可建立有向边＜Ｖｉ－１，Ｖｊ＞，边对应的词为Ｗ（０＜ｉ＜ｊ＜ｎ）。
（３）在该集合中定义全序关系：当ｉ＜ｊ时，Ｖｉ＜Ｖｊ。遵循以上规则，可以建立有向无环图。如图３所示。
定义３设定一个特征位ＭａｘＳｉｇｎａｌ，Ｌｉ为从Ｖ０到Ｖｉ最短路径的长度，使得当Ｌｉ≤ＭａｘＳｉｇｎａｌ时，终点序号在终点集合中最大，称由该终点和起点够成的路径为最佳路径。
可以理解为，从顶点Ｖｉ出发，在路径长度不超过Ｍａｘ－
Ｓｉｇｎａｌ的限制下，到达的顶点序号最大的路径。
层进式最短路径算法描述如下：
步骤１遍历每个可能的首字符，向字典查询其在当前字符串中的所有组词情况，来保证结果最佳；
步骤２同一首字符构成的所有词，都向后登记，也就是在相应边的终节点中，记录唯一的特征值和对应前驱节点位置；
步骤３从Ｌｉ＝ＭａｘＳｉｇｎａｌ时最大的到达节点回溯，即可得到最佳路径；
步骤４取出第一条边，对应输出一个分词结果，从集合中去掉已经输出的节点，更新起始节点。
采取同样的策略，计算最佳路径，依次取得以后的分词，当到达字符串结尾时，将路径中的边一次性输出，即可得到全部分词结果。最短路径是一个有向无环图，且节点之间存在全序关系，求解结果有很强的趋向性，最短路径方法采取的规则是使切分出来的词数最少，符合汉语自身的语言规律，可以取得较好的效果。但是，如果最短路径有多条，往往只保留其中一个结果，这对其他同样符合要求的路径是不公平的，而且很可能影响分词效果的准确性，因此需要进一步完善对于切分结果取舍的相关策略，本文提出一种了计分机制来改善这种情况。
３．３路径选择机制
路径选择机制的基本思想是：大多数单字在语境里如果能
组成合适的词就不倾向于单独使用，充分利用半词和整词的差别，尽量选择没有半词落单的分词方案。
在词信息构成的有向无环图中引入计分机制，采用如下计分规则：（１）每个词对应的边计１分；（２）每个半词对应的边另计１分；（３）一个分词方案的评分为它所对应的路径上所有边的分数之和；（４）分数越低，越可能是正确的分词。
以语句“他说的确实在理”为例进行分析，共产生３种切分路径，如图４所示。
由以上分析结果可得知，通过在词图中引入这种计分机制，可以在切分路径过多情况下出现的路径选择问题提供理论依据，保证了切词结果的准确性，
并且能够在一定程度上解决
０１２３４５６７８９
ｎｕｌｌ
“他”
“说”
“的”
“的确”
“实”
“确实”
“实在”
“在理”
“理”
－１
０
１
２
２
３
３
３
４
４
－１
０
１
２
２
４
３
４
６
７
０
１
１
１
１
２
１
１
１
２
０
１
２
１
２
１
１
１
０
０
ｎｕｌｌ
“说”
“的”、“的确”
“确实’
“实”、“实在”
“在理”
“在理”
“理”
ｎｕｌｌ
ｎｕｌｌ
ｉｎｄｅｘｅｎｔｒｙｌｅｖｅｌｓｔａｒｗｅｉｇｈｔ
ｎｕｍｂｅｒｅｎｔｒｙ
ｔａｉｌｓ
表３Ｎｏｄｅ数组状态表
分词方法
正向最大匹配法
最短路径法
本系统分词方法
词典类型
／空间／Ｍ
通用词典／２．１
通用词典／１．４
带标注的专
业词典／１．６
测试用例１
普通文本
速度：８４７词／ｓ
准确率：８９％
速度：６７３词／ｓ
准确率：９３％
速度：６１５词／ｓ
准确率：８８％
测试用例２
化工专业
速度：７６９词／ｓ
准确率：７４％
速度：７４２词／ｓ
准确率：８１％
速度：５８６词／ｓ
准确率：９２％
表４与其他两种分词算法的结果比较
交叉歧义。
４实验及结果分析
４．１典型语句切分结果
为了清晰地说明语句的典型实验结果，以“他说的确实在理”为例，并引入算法中记录路径节点信息的对象Ｎｏｄｅ，类图如图５所示，这里只对该对象的相关重要属性加以说明。
其中，ｅｎｔｒｙ为对应的词典条目；ｉｎｄｅｘ为该节点在数组中的索引；ｌｅｖｅｌ为节点与前驱组成的边在路径中的序号；ｓｔａｒｔ为当前节点的前驱（分词过程中，每个节点有且只有一个前驱）；ｔａｉｌｓ为ＡｒｒａｙＬｉｓｔ型对象，用来记录所在Ｎｏｄｅ对象的所有后驱的先入先出栈；ｗｅｉｇｈｔ为记录该节点权重值，当该节点代表的词条中还有半词时，将ｗｅｉｇｈｔ置２，否则置１；
源语句Ｓ＝｛“他说的确实在理”｝，Ｎｏｄｅ数组状态如表３所示。
最终，算法通过遍历Ｎｏｄｅ数组中各节点的信息，根据各节点ｌｅｖｅｌ值进行路径的划分，并且依据ｗｅｉｇｈｔ值进行最短路径的选择或舍弃，进而确定最终路径的输入结果Ｒ＝｛“他／说／的／确实／在理”｝。
４．２与常用切词方法的比较
根据以上实验结果可知，由于本系统的分词算法采取了层进式的最短路径的分词策略，并根据计分机制对切分后的路径进行筛选，处理过程上要比正向最大匹配分词算法以及单纯的最短路径切分法更加复杂，所以与其他两种方法在切分速度上相比略有不足；在切分准确率上面，对于普通文本来说，很大程度上取决于词典词条的完备性，在词典中词条数量相差不大的情况下，３种方法的切分准确程度相差不大，而对于化工专业的特定文本，由于本算法采用了专业词汇特定标识的方法，提升了专业词汇在切分匹配时的优先级，从而提高了化工专业词汇的识别率，并结合了路径筛选策略对切分结果存在多条路径的情况进行选择，而不是简单地舍弃，因而在准确率上相比其他两种方法取得了不错的效果。总而言之，根据实验结果可以得知，本分词算法在分词的速率和准确率之间进行了很好的平衡，基本上达到了专业搜索引擎的速度和精度要求，具备了一定的通用性和专业性。
５结论与展望
本文设计实现了一种改进的最短路径切分算法的中文分词系统，包括词典机制的设计，并基于常用的最短路径分词算法，提出了一种新的改进方法，更加准确地考虑了语境对分词的影响以及多条分词路径的取舍策略，同时保持了算法较高的时间效率。本文还有一些问题有待解决，比如，对一些特定组合歧义的处理和识别没有作精确的分析［７］；对于一些如人名、地名等命名实体的识别未做考虑等，还需要进一步深入地进行研究。
参考文献：
［１］邓宏涛．中文自动分词系统的设计模型［Ｊ］．计算机与数字工程，２００５，３３（４）：１３８－１４０．
［２］肖红，许少华，李欣．具有三级索引词典结构的中文分词方法研究［Ｊ］．计算机应用研究，２００６（８）：４９－５１．
［３］费洪晓，胡海苗，巩燕玲．基于Ｈａｓｈ结构的机械统计分词系统研究［Ｊ］．计算机工程与应用，２００６，４２（５）：１５９－１６１．
［４］欧振猛，余顺争．中文分词算法在搜索引擎应用中的研究［Ｊ］．计算机工程与应用，２０００，３６（８）：８０－８２．
［５］湛燕，陈昊，袁方，等．基于中文文本分类的分词方法研究［Ｊ］．计算机工程与应用，２００３，３９（２３）：８７－８９．
［６］朱巧明，李培峰．中文信息处理技术教程［Ｍ］．北京：清华大学出版社，２００６．
［７］罗智勇，宋柔．现代汉语通用分词系统中歧义切分的实用技术［Ｊ］．计算机研究与发展，２００６，４３（６）：１１２２－１１２８．

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。