一种快速中文分词词典机制.pdf

万方数据

一种快速中文分词词典机制*聂晓峰21传统词典机制吴晶晶1’2荆继武2’王平建2通过研究目前中文分词领域各类分词机制，注意到中文快速分词机制的关键在于对单双字词的识别，在这一思想下，提出了一种快速中文分词机制：双字词一长词哈希机制，通过提高单双字词的查询效率来实现对中文分词机制的改进．实验证明，该机制提高了中文文本分词的效率．关键词文本实时处理，中文分词，词典法分词，双字词一长词哈希机制中图分类号TP391．1随着中文网络的大规模发展，包含中文信息的网络数据也快速膨胀．对于海量中文网络数据的实时分析处理成为新一代中文信息处理技术必须关注的问题．而作为中文信息处理基础的分词技术，已经被广泛应用于中文信息检索、人机交互、信息提取、文本挖掘等领域中⋯．成功的中文分词机制需要同时具有较高的词汇切分准确性和快速的词汇切分能力．其中，前者需要解决未登录词汇(out．of-vocabulary)识别和词汇歧义切分等难题，目前主要采用字符串频度统计，语料字词标注沼31等机器学习方法；而快速词汇切分能力是关系到整个中文信息处理系统，特别是实时处理类应用系统可用性的关键技术，目前主要通过设计高效的分词词典机制来实现速度提升．此类快速分词机制一般基于传统的词典分词方法hlo】，依靠已有的特征词典作为文本切分匹配依据，设计简单，实现容易，算法效率很高，词典法分词机制中与分词速度相关的有2个要素：词典构造方法和词汇匹配方法，这2个方面相互关联．常见的词汇匹配方法有前向匹配、后向匹配、最大匹配、逐字匹配等．目前研究认为，采用前向最大匹配是分词速度最高的匹配方法b】．本文不研究匹配方法造成的分词速度差异，主要通过研究不同词典的构造方法来实现高速的分词机制．文中第1部分简单描述了几种经典分词词典机制；第2部分详细介绍几种改进词典机制；在第3部分介绍作者提出的一种快速中文分词词典构造机制：双字词和长词哈希索引机制(double．character．and—long-vocabulary—hash．indexing)；第4部分通过分析和实验说明新体制与原有体制相比具有的优势．最为典型的分词词典机制有以下3类：整词二分法、TRIE索引树法和逐字二分法．第26卷第5期2009年9月中国科学院研究生院学报JW，Niesegmentation[J]．Journal摘要文章编号：1002．i(1中国科学技术大学电子工程与信息科学系，合肥230027；2中国科学院研究生院信息安全国家重点实验室，北京100049)(200S年10月16日收稿；2009年4月21日收修改稿)WuJJ，JingmechanismAcademySciences，2009，26(s)：703—711．*国家高技术研究发展计划(863)(2006AA012454)、国家信息安全242计划(2005823)和国家自然科学基金(60573015)资助t通讯联系人。E—mail：jjwu@is．∞．c11JournaloftheGraduateSchoolChineseSciencesV01．26No．5September2009175(2009)05-0703-09XF，eta／．Fastdictionaryforword
万方数据

圈圈1f、、、、‘≥＼＼。1．2基于T砒E索引树的词典机制1．1整词二分法的查询机制1．3基于逐字二分法的查询机制整词二分法的词典结构分为词典正文、词索引表、首字散列表等3级．通过首字散列表的哈希定位和词索引表，很容易确定指定词在词典正文中的可能位置范围，进而在词典正文中通过整词二分进行定位．基本的机制结构如图1．～k＼TRIE索引树是一种以树的多重链表形式表示的键树，基于TRIE索引树的词典机制由首字散列表和TRIE索引树结点2部分组成．TRIE索引树的优点是分词应用中，在对被切分语句的一次扫描过程中，不需预知待查询词的长度，沿着树链逐字匹配即可；基本的机制结构如图2(a)所示．基于逐字二分法的查询机制是对前2种词典机制的改进方案，一方面，从组织结构上，逐字二分与整词二分的词典结构完全一样；另一方面，逐字二分吸收了TRIE索引树的查询优势，即采用的是“逐字匹配”，而不是整词二分的“全词匹配”，这在一定程度上提高了匹配的效率，如图2(b)．以上3种基本的词典机制是该方向研究中的经典机制，但他们的缺点也十分突出．整词二分法完全采用全词匹配的查询过程，效率明显较为低下；TRIE索引树法的构造和维护比较复杂，而且都是单词树枝，浪费了一定的空间；而逐字二分法由于采用的仍是整词二分的词典结构，虽然采用了较为高效的匹配方法，但并没有改进“整词二分”的数据结构，使得匹配过程并不是完全意义上的逐字匹配，这使效率中国科学院研究生院学报第26卷l词索引表Il词典正文图1整词二分法的