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

汉语词典快速查询算法研究李江波 周强 陈祖舜(清华大学智能技术与系统国家重点实验室北京100084)E-mail: jiangbo摘要：汉语词典查询是中文信息处理系统的重要基础部分，对系统效率有重要的影响。本文对汉语词典查询算法研究作了简要回顾，设计实现了基于双数组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中提出了一种基于PATRICIA tree的汉语词典查询机制，这种方法首先使用词条的内码来作为一个关键词位串，然后通过位串比较构造出PATRICIA tree树，树的每个内部节点包括三个数据项：比较位、左指针、右指针，树的叶子节点代表一个词条。查询时根据内部节点选择后继路径，直到叶子节点，该方法的优点是引入了位比较，但是因为树的构造过程是基于内码而非字的，所以不可避免地导致树的深度大大增加，从而造成了效率降低和空间浪费。本文设计实现了基于双数组Trie（Double-Array Trie）原理的汉语查询词典；提出并实现了一种基于双编码机制的词典查询机制；最后对改进二分法，双数组Trie（Double-Array Trie），双编码方法三种方法进行了性能上的比较。下面的第二章介绍双数组Trie（Double-Array Trie）的数据结构和具体实现，第三章介绍双编码方法的编码思想和具体查询方式，第四章是对双编码思想进行的性能分析，第五章是对三种方法进行性能实验分析，第六章为全文的总结。二、 双数组Trie（Double-Array Trie）的数据结构与具体实现Trie树是搜索树的一种，来自英文单词Retrieval的简写，可以建立有效的数据检索组织结构。Trie树本质上是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。传统上的DFA一般用转换表方式来实现，表的列代表自动机的不同状态，行代表转换变量，但是对于词典查询来说，转换表的问题是数据稀疏导致严重地的空间浪费，其空间复杂度为O(n2)。Trie树的另一种实现方式是使用链表节点，这种方式在空间复杂度上降低为O(n)，但是问题在于数据结构复杂，查询效率较低5。为了让Trie实用的实现算法在空占用间较少的同时还要保证查询的效率，前人提出了一种用4个线性数组表示DFA的方法，并进一步提出了用3个线性数组表示Trie树的方式。在此基础上，文献6做出了进一步改进，用2个线性数组来进行Trie树的表示，即双数组Trie（Double-Array Trie）7。双数组Trie（Double-Array Trie）由两个整数数组构成，一个是base，另一个是check。设数组下标为i ,如果basei,checki均为0,表示该位置为空。如果basei为负值，表示该状态为词语。Checki表示该状态的前一状态，t=basei+a, checkt=i 。对于汉字词典，采用相同的思想。先把双数组的1-6768放置6768个常用汉字。对于每一个汉字，确定一个base值，使得对于所有以该汉字开头的词，在双数组中都能放下。例如，现在要确定“阿”字的base值，假设以“阿”开头的词的第二个字序列码依次为a1，a2，a3an，我们必须找到一个值i，使得basei+a1，checki+a1，basei+a2，checki+a2basei+an，checki+an均为0。一旦找到了这个i，“阿”的base值就确定为i。对于第二个字，第三个字也是类似。双数组构造完成以后，查询起来极为方便。待查词有几个字，就将汉字分别转换为对应的序列码，然后作几次加法，即可查到相应的词语，无须折半查找。由于汉语中常用词平均长度不到3个字，因此双数组查询算法的效率是极高的。下面举例说明双数组Trie（Double-Array Trie）的构造过程和查询过程。假定词表中只有“啊，阿根廷，阿胶，阿拉伯，阿拉伯人，埃及”这几个词，用Trie树可以表示为：阿廷人拉胶6啊12310埃4根5711及89伯我们首先对词表中所有出现的10个汉字进行编码：啊-1，阿-2，唉-3，根-4，胶-5，拉-6，及-7，廷-8，伯-9，人-10。然后在此基础上构建双数组Trie（Double-Array Trie），经过四次遍历，将所有的词语放入双数组中，然后还要遍历一遍词表，修改base值。因为我们用负的base值表示该位置为词语。如果状态i对应某一个词，而且Basei=0，那么令Basei=（-1）*i，如果Basei的值不是0，那么令Basei=（-1）*Basei。得到双数组如下：下标1234567891011121314Base-14400004-94-11-12-4-14Check0000000222381013词缀啊阿埃阿根阿胶阿拉埃及阿根廷阿拉伯阿拉伯人用上述方法生成的双数组，将“啊”，“阿”，“埃”，“阿根”，“阿拉”，“阿胶”，“埃及”，“阿拉伯”，“阿拉伯人”，“阿根廷”均视为状态。每个状态均对应于数组的一个下标。例如设“阿根”的下标为i=8，那么checki的内容是“阿”的下标，而basei是“阿根廷”的下标的基值。“廷”的序列码为x=8，那么“阿根廷”的下标为basei+x=base8+8=12。查询时相当于从一个状态找到另一个状态。例如查询“阿根廷”，先根据“阿”的序列码b=2，找到状态“阿”的下标2，再根据“根”的序列码d=4找到“阿根”的下标baseb+d=8，同时根据checkbaseb+d=b，表明“阿根”是某个词的一部分，可以继续查询。然后再找到状态“阿根廷”。它的下标为y=12，此时basey0，checky=baseb+d=8，表明“阿根廷”在词表中，查询完毕。最后对双数组Trie（Double-Array Trie）机制词典进行空间复杂度分析：该词典机制主要增加的辅助成分是双数组结构，约120,000个状态，另外考虑到实际应用中，还需要获得词条的下标，所以把双数组调整为三数组，共需要空间为，120,000*3*4=1,440,000字节；另外，主词典需要空间为50,000*113=5,650,000字节。总共占用空间：7,090,000字节。三、 双编码机制的词典查询算法1. 双编码的基本思想，GB-2312编码的常用汉字共有6768个，每个汉字都可以从唯一地从区位码映射到1-6768间的一个序列码，从而每个汉字串都可以唯一地映射到一个数字串，这样对于词语的查询可以转化为基于数字串的查询。双编码的查询思想就是首先将汉字区位码转换成序列码，从而使汉字序列转换成数码序列；然后将汉字序列对应的数码序列转换成数偶码（代表两个有理数）。将整个词表全部转换成数偶码表，排好序，供检索用。从数码序列到数偶码的转换主要是采用了欧几里德算法（辗转相除法）的思想8，保证了从数码序列和数偶码之间转换的唯一性，同时还达到了一定程度上数据压缩的目的。具体的转换算法如下：（1） 从序列码到数偶码的编码：假定输入数据序列存放在数组Seq中，其长度为n. 其中ai （i=1,2,n） 是汉字符的序码。P,Q是一对输出整数，代表一个既约有理数P/Q, 是输入数据序列的编码，叫数偶码。编码过程如下：赋初值：X0=0, Y0=1, X1=1, Y1=0递归求解：Xi=Seqi-2*Xi-1+Xi-2 i 1Yi=Seqi-2*Yi-1+Yi-2i 1获得数偶码：P= Xn+1Q=Yn+1（2） 从数偶码到序列码的解码算法：输入数据是整数偶. 输出数据是它所代表的汉字（对应的序码）的序列，放在Out中，该序列的长度为n。解码过程如下：为变量赋初始值：M0=Q X0=P循环辗转相除，将相除的结果保存进入数组Out，直到Mi为零，递归公式如下：Outi= (int)Xi/Mi Mi+1=Xi-Outi* MiXi+1=Mi 2. 索引机制的建立对整个词典进行编码之后，每个词语就对应着一对数偶码，其特点是随着词语的长度增加，数值会变得很大，所以必须建立相应索引，在这一点上本文进行了相应的多次探索，最后选择了分段索引方式。具体来说就是对P值小于0xFFFFFF的词语和大于0xFFFFFF的词语分别建立索引，这样做的原因是：1) 首先0xFFFFFF基本上是二字词与三字词的分界线，我们对使用的容量为49500条的词典进行统计，其中的单字词语有1650条，双字词语有31838条，共33488条，占67.65%。考虑到在具体应用中，多字词语不仅所占比例较小，而且它们出现的频率要远低于双字词和单字词，所以查询算法应该保证短词的查询速度更快。2) 另一方面，经过统计，在词典中，P码小于0xFFFFFF的词语个数为34243，而所有词语个数为49500，这样0xFFFFFF以下的P码的数值分布更为密集，所以我们应该对两段分别采用不同的机制构建索引。为了建立从双码到词语位置的Hash机制，我们还需要尽可能地保证唯一性，让每个生成的索引值尽量对应唯一的一个词语位置。查询的具体实现函数如下：QuerryWord（char* Word）首先对Word编码，生成数偶码P和Q;If （P 0xFFFFFF） 原理类似WordsListIndex1以一个具体查询的例子来说明具体查询过程：假设给定某一词语“祖国”，进行查询，首先将字串“祖国”根据内码转换为序列码存入Seq 数组，“祖”对应3736，国对应“936”，然后将序列数组转化为数偶码P, Q，其中P=0x356A59; Q=0x3A9，则索引Ind=0x56A59，经过查找，Index1Ind.mark=0，Index1Ind.pos=14593，查找到WordsList14592，经过验证WordsList14592.Valuep=P20，而且WordsList14592.Valueq=Q，则表明已经查询到了相应的词语，返回WordsList14592，完成查询。0x56A580x56A590x56A5A 145901459114592祖国3736936（P，Q）3. 双编码方法性能分析采用如上的哈希机制之后，可以保证较低的冲突概率。经过分析，对于P值0xFFFFFF的哈希表，同一索引值对应一个词的比例占88.31%，同一索引值对应两个词的比例占10.58%，同一索引值对应三个词的比例为1.02%。考虑到查询词中双字词约占76%，所以我们可以说，双编码的冲突概率很低，对于一个汉字串，经过编码后，基本上就能通过哈希表一次查到对应的词。 大于0xFFFFFF小于0xFFFFFF我们对双编码的机制进行相应的空间复杂度分析：主词典50000*113=5650000字节，索引（0xFFFFF+0xFFFF）*3=3342430字节，总共占用空间：8,992,330字节。从上面分析可以发现，双编码机制的查询效率主要是通过牺牲空间来获取的，我们针对词表分别分段构建的大小为0xFFFFF和0xFFFF的两个数组，被利用的索引值有46779个，其利用率为4.19%，利用率比较低，但考虑到大数组占用的内存空间（如上示，约3.3M）相对于当前计算机的性能而言已经不是什么问题，所以该方法是可行的。四、 实验分析为对双数组Trie（Double-Array Trie）查询算法和双数组查询算法作性能评测，我们选择了逐字二分法作为性能比较的参照算法。关于逐字二分法的原理，请参考本文的引言部分以及相关的引用文献。为模拟真实语境，实验主要是在切分的人民日报半年语料库的基础上进行的，分别在相同的硬件环境下，用三种查询机制对语料库中出现的所有词进行查询。实验分为三步：首先进行数据统计分析；然后对三种查询机制进行速度比较；最后对每一种查询机制的各个环节都进行了速度上的分解分析。1. 在速度评测之前，我们首先对语料库和三种算法的动态性能进行了相应的统计分析，作为问题分析的参考：1) 在人民日报语料库基础上对词典中的49500个词语进行统计。其中单字词2595个，在训练预料中出现2062393次，比例为；双字词31838个，在训练语料中共出现 2860757次；三字词7858个，在训练语料中共出现165044次；四字词7209个，共出现62829次。可见真实语境中单字词和双字词的出现频率远高于长词。2) 在人民日报半年切分预料库的基础上，我们对三种查询方法的动态性能分别进行了统计。对双编码机制的词典查询，经过统计分析发现，平均每次查询需要54.143次数值运算、1次字符串长度运算、16.548次读取数组运算；对双数组Trie（Double-Array Trie）机制的词典查询，经过统计分析发现，平均每次查询需要30.44次数值运算、1次字符串长度运算、1.857次读取数组运算；对逐字二分法机制的词典查询，经过统计分析发现，平均每次查询需要38.244次数值运算、8.268次数组读取运算、4.268次字符串比较运算、1次字符串copy运算。从上面的统计信息可以看出：双数组Trie（Double-Array Trie）机制的词典查询从算法复杂度上来说是最快的方法，双编码机制的词典查询在数值运算和读取数组运算上复杂度较高，逐字二分法机制的词典查询则因为增加了字符串比较、copy运算增加了算法复杂度。2. 接下来三种查询算法的实验测试比较查询算法名称花费时间 （s）相对比较改进二分法6.697100%双编码4.72570.6%双数组Trie（Double-Array Trie）1.40821.1%可见双数组Trie（Double-Array Trie）是性能最好的一种查询算法；双编码算法作为一种新的想法，查询过程完全基于数值运算，避免了字符串比较运算，相对改进二分法性能有所提高。3. 对三种方法进行各个时间环节的分解分析l 双编码机制的各个环节时间分析：内码转换为序列码序列码转换为数偶码产生索引值读取索引数组进行比较验证1.76040.67180.10561.29030.897237.26%13.21%2.23%27.31%19.99%从上面可以看出双编码机制查询的主要性能瓶颈是之一是内码到序列码的转换过程，经过分析，我认为这个地方的性能较低主要是因为生成序列数组，并进行了数据传递。另一个瓶颈是读取索引数组，因为我们为了保证索引的唯一性，作了一个较大的索引，这样在读取数组的时候，性能较低。l 双数组Trie（Double-Array Trie）机制的各个环节时间分析：第一个字第二个字第三个字第四个字0.6810.6060.0970.02448.4%43.0%6.9%1.7%从上面的分析可以看出，双数组Trie（Double-Array Trie）方法的各个环节时间消耗跟处理词语数目成正比，第一个字处理对应所有的词语处理，第二个字处理对应二字词以上的词语处理，如此类推。处理的主要方式是从当前字生成序列码，并通过加法来进行状态转移。l 改进二分法机制的各个环节时间分析：根据首字确定范围二分查找匹配词语0.90795.789113.56%86.44%改进二分法机制的主要时间耗费在二分查找匹配词语的过程中，因为要进行若干次字符串比较工作。4. 综合评价双数组Trie（Double-Array Trie）机制的词典查询算法中，若待查词长度为N，则将汉字分别转换为对应的序列码，经过N次加法，即可查到相应的词语，无须折半查找。另外由于汉语中常用词平均长度不到3个字，因此双数组查询算法的效率是极高的。这种方法缺点在于：构造调整过程中，每个状态都依赖于其他状态，所以当在词典中插入或删除词语的时候，往往需要对双数组结构进行全局调整，灵活性能较差。双编码机制的词典查询算法，基本思想是把汉字词语转换到数码的层次上，然后进行词典组织和词语查询。这种算法的优势在于避免了传统查询中的字符串操作，在哈希机制上更为灵活，有较大的改进空间；同时词典组织的方式是传统的线性表，调整起来十分方便；另外，在本算法中突出体现了短词优先的特性，提高了查询效率。这种算法的缺点在于，汉字词语转化到数码的压缩率还不够大，导致生成的数偶码较大，随着词语长度的增加，可能导致溢出，必须引入大数机制；另外，进行词典组织的时候需要构建一个较大的数组，限制了查询效率的提高。五、 结语本文在双数组Trie（Double-Array Trie）数据结构的基础上，实现了一种基于汉语的词典查询算法，它只需要进行若干次加法运算就可以完成查询，速度上相对其它词典查询机制有了明显的提高，同时相同前缀的词语在词典中也有逻辑上的关系，因此在分词中可以有很好的应用。它的缺点是构造过程复杂，插入删除每一条词语都会引发对整个词典的调整，因此，最好应用于实时性要求较高的封闭式词典中。本文还提出了双编码机制的汉语词典查询算法，该算法的特点是，通过算术编码，可以把任意字符串转化为有理数，从而一切查询工作可以基于有理数来进行，避免了二分法的字符串比较，在效率上有所提高，而且词典以线性表组织，调整起来也比较容易。这种方法的缺点是从字符串转化到有理数的过程较复杂，同时生成的有理数过大，建立索引难度比较大，既要尽可能地避免数据稀疏，同时还不能让索引过大，本文通过实验探索，找到了比较合适的索引机制。本词典相对改进二分法词典，性能有了较大的提高。这种算法改进的余地还比较大，可以在数码生成环节，哈希机制等环节作近一步的改进，可以应用于词语长度较小，对速度要求较高的开放式词典中。参考文献1王秀坤，李政，简幼良，刘剑基. 基于Hash方法的机器翻译词典的组织与构造. 大连理工大学学报，1996，（3）2孙茂松，左正平，黄昌宁. 汉语自动分词词典机制的实验研究. 中文信息学报，2000，（1）3李庆虎，陈玉健，孙家广. 一种中文分词词典新机制双字哈希机制. 中文信息学报，2003，（4）4杨文峰，陈光英，李星. 基于PATRICIA tree的汉语自动分词词典机制. 中文信息学报，2001，（3）5严蔚敏，吴伟民. 数据结构. 北京：清华大学出版社，19926Aoe,J. An Efficient Digital Search Algorithm by Using a Double-Array Structure. IEEE Transactions on Software Engineering. 1989，(9)7 Theppitak Karoonboonyanan. An Implementation of Double-Array Trie. 8 欧几里德算法. http:/www.nhyz.org/nhxi/suanfa/main.htm An Study on Rapid Algorithm for Chinese Dictionary QueryLI Jiang-boZHOU QiangCHEN Zu-shunThe State Key Laboratory of Intelligent Technology and Systems,Department of Computer Science and Technology, Tsinghua University.Beijing 100084E-mail: jiangboAbstract : The dictionary mechanism is the basic component of Chinese information processing systems, and its efficiency will greatly affect the performances of those systems. In this paper, we review the Algorithms for Chinese dictionary query, design and implement a Chinese dictionary based on Double-Array TRIE mechanism, present a new Chinese dictionary based on Double Coding mechanism. In the end of the Paper , we give the experiment result and conclusion of the two Dictionary query mechanism. Keywords: Chinese Dictionary Query; Double-Array TRIE; Chinese information processing