一种改进的基于patricia树的汉语自动分词词典机制

《一种改进的基于patricia树的汉语自动分词词典机制》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、万方数据华南理工大学学报(自然料擘版)第32卷增刊JournalofSoulbChinaUniVersityofTechn0109yvol32suppl2004年11月(NamralscienceEdmon)November2004文章编号：lD00—565x(2004)s—0028—04一种改进的基于PATⅪcIA树的汉语自动分词词典机制+马哲(浙旺大学计算机系，姚敏浙江杭州310027)摘要：分词词典机制是影响自动分词的重要因素，而查找速度是衡量一个词典好坏的重要标准．吏中分析比较了现有的几种典型的词典机制．井在此基础上提

2、出了一种新的词典机制，即在pATRfc认tree的基础上加入Hash机制，从而在明显提高查找速度的同时，降低了构造和维护词典的复杂度．关键词：PATRIcIA树；汉语；自动分词；分词词典机制中图分类号：TP391文献标识码：A汉语的自动分词技术的应用十分广泛，如汉字的拼音输入、语音识别与合成、汉语分析与理解、中文句法分析、机器翻泽、中文文献自动标引、中文信息检索等等．分词技术的研究已有10多年的历史，取得了很大的进展．分词方法主要分为基于统计的机械分词法和基于规则的专家系统分词法．无论哪种方法，其最终目的都是快速精确地取得分词

3、结果．词典作为许多分词方法的重要工具，它的查询速度是制约分词速度的决定因素，又因为没有任何一个词典所收录的词是完备的，所以词典应该易于进行添加删除等维护工作．所以～个好的词媳机制应能提供快速查询，并且便于维护．根据分词系统特点，分词词典的查询方式大致分为三种．(1)确定词条查询：在分词词典中查找指定词w。(词在分词词典中的定位)．(2)最长词条查询：根据分词词典，在汉字串s中查找从某一指定位置f开始的最长词w⋯。(对应最大匹配分词方法)．(3)前缀词条查询：根据分词词典，在汉字串s中查找从某一指定位置f开始的所有词w。，w。，

4、收稿日期：2004—08—24·基金项目：国家自然科学基金资助项目(79970037)作着简介：马哲(1980一)，女，硕士生，主要从事数据挖掘和模糊信息处理的研究E·mail：mz·fcidan@sohu．com⋯，w。。。(对应全切分分词方法)l现有分词机制分析1．1基于Hash机制的分词词典机制(I)首字HaSh+索引表+整词二分机制，首字H“h+索引表+逐字二分机制”1．这龌种机制都是基于首字Hash+索引表．前～种分词机制比较适合确定词条查询，但是对于最长词条和前缀词条查询，其性能却不佳．后一种分词机制是在前一种上的

5、改进，吸取了基于TRIE的逐字比较的优势，对于最长和前缀词条查询方式有较大改善．这两种机制的优点是构造和维护简单，占用空间小．(2)首字Hash+TRIE索引树⋯机制，双字Hash+TRlE索弓I树”l，首字Hash+语词树”1机制这三种都是基于Hash+键树机制．键树”1，又称数字查找树，它是一棵度大于或等于2的树，树中的每个节点中不是包含一个或几个关键词．而是只含有组成关键词的符号．键树有两种存储结构，一种是以树的孩子兄弟链表来表示键树，应用于词典中即为语词树；另一种是以树的多重链表来表示键树，即TRIE树．这三种机制的好

6、处是查询速度快，但是数据结构复杂，浪费空间较大，J．2基于PATRIcIA树的词典机制”1PATRIcIA(Prac石calAlgorithmtoRetrieveIn-万方数据万方数据万方数据增刊马哲等：～种改进的基于PATRIcIA树的汉语自动分词词典机制3l圉3添加关键诵Fig．3Insenk。ywords凰4删除关键词升g4DeIetekeyword83基于首字Hash与PATRIcIAtree的分词词典机制的性能分析31空间特性与原来的PATRIcIAtree机制相比较。新机制摆当于把原来的～棵庞大的PATRIcIA仃

7、ee拆分为许多相对较小的PATRIcIAtree，由于词条数目不变，则内部节点数目不变，相当于增加了一个Hash散列表的空间．新机制所占的空间为Hash散列表+内部节点+叶子节点．3．2平均路径长度在进行查找时，Hash散列表和将进行查询的PATRIclA仳e都在内存中，不用进行I／O操作，比原PATRIclAtree机制的时间复杂度降低很多，(I)查找单字词无需比较；(2)根据文献[2】得到的统计结果，如表1所示．由于新机制查询词条相当于比原机制少查找一个字，所以相应的平均路径长度普遍下降．即查找三字词相当于查找二字词．则原

8、机制的平均路径长为21．94，而新机制的平均路径长约为1728，比最理想的log：77228m16．24次多1次，比原机制有很大改善．表1不同长度关键词的平均路径长度Table1AVaragepathlengthofdifferentkeywords(3)同理进行最长字串查询