汉语词典快速查询算法研究.doc

袃荿螁汉语词典快速查询算法研究薀蚇聿李江波周强陈祖舜芃肁薆(清华大学智能技术与系统国家重点实验室北京 100084)莈螇羃E-mail:******@.cn蚄葿薈摘要:汉语词典查询是中文信息处理系统的重要基础部分,对系统效率有重要的影响。本文对汉语词典查询算法研究作了简要回顾,设计实现了基于双数组TRIE机制的汉语词典查询算法,并提出了基于双编码机制的词典查询算法。最后对两种词典查询机制进行了实验分析。肇袇***关键词:汉语词典查询;双数组TRIE;双编码;中文信息处理。肅芁肅膀羇蚃引言节羃蕿在汉语信息处理系统中,汉语词典查询是一个重要的基础环节,在整个处理过程中都需要频繁地访问词典以获得汉语词语知识,因而汉语词典的快速查询是整个处理系统效率的关键所在。针对词典查询方法,前人作了大量工作,并形成了许多汉语词典组织结构和相应的查询算法。衿肆芆早期的词典组织构造主要是基于传统Hash方法,文献[1]中采用的方法就是一个典型应用,这种方法的关键技术是Hash函数的设计,采用合理的方式来调节数据块的分配,控制分布的均匀性,减少冲突,提高空间利用率,由于涉及到磁盘读取,这种方法在速度上存在较大局限。蚃莁蒅文献[2]指出了三种典型的词典查询方法:整词二分法、TRIE索引树法、逐字二分法。以下分别对这三种方法作简要介绍:(1)基于整词二分的词典机制:整词二分方法的词典结构分为词典正文、词索引表、首字散列表等三级。通过首字散列表的哈希定位和词索引表,很容易确定指定词在词典正文中的可能位置范围,进而在词典正文中通过整词二分进行定位。这种算法的数据结构简单、占用空间小,构建及维护也简单易行,但由于采用全词匹配的查询过程,效率较为低下。(2)基于TRIE索引树的词典机制:TRIE索引树是一种以树的多重链表形式表示的键树,基于TRIE索引树的词典机制由首字散列表和TRIE索引树结点两部分组成。TRIE索引树的优点是分词应用中,在对被切分语句的一次扫描过程中,不需预知待查询词的长度,沿着树链逐字匹配即可;缺点是它的构造和维护比较复杂,而且都是单词树枝,浪费了一定的空间。(3)基于逐字二分法的查询机制:基于逐字二分法的查询机制是对前两种词典机制的改进方案,一方面,从组织结构上,逐字二分与整词二分的词典结构完全一样;另一方面,逐字二分吸收了TRIE索引树的查询优势,即采用的是“逐字匹配”,而不是整词二分的“全词匹配”,这就一定程度地提高了匹配的效率。但由于采用的仍是整词二分的词典结构,使效率的提高受到很大的局限。蚈肆蒄文献[3]中提出了基于双字哈希机制的词典查询方法,该方法主要结合了词典中的多字词条(3字词以上)数量少,使用频度低的特点,对基于TRIE索引树的词典机制做出了改进,把TRIE索引树的深度限制为2。其三层结构分别是首字哈希索引,次字哈希索引,剩余字串组。这种查询机制相当于使2字词以下的短词用TRIE索引树机制实现,3字词以上的长词的剩余部分用线性表组织,从而避免了深度搜索,一定程度上提高了查询性能。肄膃蚁此外,文献[4]中提出了一种基于PATRICIAtree的汉语词典查询机制,这种方法首先使用词条的内码来作为一个关键词位串,然后通过位串比较构造出PATRICIAtree树,树的每个内部节点包括三个数据项:比较位、左指针、右指针,树的叶子节点代表一个词条。查询时根据内部节点选择后继路径,直到叶子节点,该方法的优点是引入了位比较,但是因为树的构造过程是基于内码而非字的,所以不可避免地导致树的深度大大增加,从而造成了效率降低和空间浪费。蒇膆蚈本文设计实现了基于双数组Trie(Double-ArrayTrie)原理的汉语查询词典;提出并实现了一种基于双编码机制的词典查询机制;最后对改进二分法,双数组Trie(Double-ArrayTrie),双编码方法三种方法进行了性能上的比较。下面的第二章介绍双数组Trie(Double-ArrayTrie)的数据结构和具体实现,第三章介绍双编码方法的编码思想和具体查询方式,第四章是对双编码思想进行的性能分析,第五章是对三种方法进行性能实验分析,第六章为全文的总结。蒅薁袄双数组Trie(Double-ArrayTrie)的数据结构与具体实现蒀芆膄Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构。Trie树本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态,根据变量的不同,进行状态转移,当到达结束状态或者无法转移的时候,完成查询。传统上的DFA一般用转换表方式来实现,表的列代表自动机的不同状态,行代表转换变量,但是对于词典查询来说,转换表的问题是数据稀疏导致严重地的空间浪费,其空间复杂度为O(n2)。Trie树的另一种实现方式是使用链表节点,这种