汉语词典快速查询算法研究李江波周强陈祖舜(清华大学智能技术与系统国家重点实验室北京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]中提出了一种基于PA TRICIA tree的汉语词典查询机制，这种方法首先使用词条的内码来作为一个关键词位串，然后通过位串比较构造出PATRICIA tree树，树的每个内部节点包括三个数据项：比较位、左指针、右指针，树的叶子节点代表一个词条。
查询时根据内部节点选择后继路径，直到叶子节点，该方法的优点是引入了位比较，但是因为树的构造过程是基于内码而非字的，所以不可避免地导致树的深度大大增加，从而造成了效率降低和空间浪费。
本文设计实现了基于双数组Trie（Double-Array Trie）原理的汉语查询词典；提出并实现了一种基于双编码机制的词典查询机制；最后对改进二分法，双数组Trie（Double-Array Trie），双编码方法三种方法进行了性能上的比较。
下面的第二章介绍双数组Trie （Double-Array Trie）的数据结构和具体实现，第三章介绍双编码方法的编码思想和具体查询方式，第四章是对双编码思想进行的性能分析，第五章是对三种方法进行性能实验分析，第六章为全文的总结。
二、双数组Trie（Double-Array Trie）的数据结构与具体实现Trie树是搜索树的一种，来自英文单词"Re trie val"的简写，可以建立有效的数据检索组织结构。
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 ,如果base[i],check[i]均为0,表示该位置为空。
如果base[i]为负值，表示该状态为词语。
Check[i]表示该状态的前一状态，t=base[i]+a, check[t]=i 。
对于汉字词典，采用相同的思想。
先把双数组的1-6768放置6768个常用汉字。
对于每一个汉字，确定一个base 值，使得对于所有以该汉字开头的词，在双数组中都能放下。
例如，现在要确定“阿”字的base值，假设以“阿”开头的词的第二个字序列码依次为a1，a2，a3……an，我们必须找到一个值i，使得base[i+a1]，check[i+a1]，base[i+a2]，check[i+a2]……base[i+an]，check[i+an]均为0。
一旦找到了这个i，“阿”的base值就确定为i。
对于第二个字，第三个字也是类似。
双数组构造完成以后，查询起来极为方便。
待查词有几个字，就将汉字分别转换为对应的序列码，然后作几次加法，即可查到相应的词语，无须折半查找。
由于汉语中常用词平均长度不到3个字，因此双数组查询算法的效率是极高的。
下面举例说明双数组Trie（Double-Array Trie）的构造过程和查询过程。
假定词表中只有“啊，阿根廷，阿胶，阿拉伯，阿拉伯人，埃及”这几个词，用Trie树可以表示为：我们首先对词表中所有出现的10个汉字进行编码：啊-1，阿-2，唉-3，根-4，胶-5，拉-6，及-7，廷-8，伯-9，人-10。
然后在此基础上构建双数组Trie（Double-Array Trie），经过四次遍历，将所有的词语放入双数组中，然后还要遍历一遍词表，修改base值。
因为我们用负的base值表示该位置为词语。
如果状态i对应某一个词，而且Base[i]=0，那么令Base[i]=（-1）*i，如果Base[i]的值不是0，那么令Base[i]=（-1）*Base[i]。
得到双数组如下：用上述方法生成的双数组，将“啊”，“阿”，“埃”，“阿根”，“阿拉”，“阿胶”，“埃及”，“阿拉伯”，“阿拉伯人”，“阿根廷”均视为状态。
每个状态均对应于数组的一个下标。
例如设“阿根”的下标为i=8，那么check[i]的内容是“阿”的下标，而base[i]是“阿根廷”的下标的基值。
“廷”的序列码为x=8，那么“阿根廷”的下标为base[i]+x=base[8]+8=12。
查询时相当于从一个状态找到另一个状态。
例如查询“阿根廷”，先根据“阿”的序列码b=2，找到状态“阿”的下标2，再根据“根”的序列码d=4找到“阿根”的下标base[b]+d=8，同时根据check[base[b]+d]=b，表明“阿根”是某个词的一部分，可以继续查询。
然后再找到状态“阿根廷”。
它的下标为y=12，此时base[y]<0，check[y]=base[b]+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）从序列码到数偶码的编码：假定输入数据序列<a1,a2,…,a n>存放在数组Seq[]中，其长度为n. 其中a i（i=1,2,…,n）是汉字符的序码。
P,Q是一对输出整数，代表一个既约有理数P/Q, 是输入数据序列<a1,a2,…,a n>的编码，叫数偶码。
编码过程如下：赋初值：X0=0, Y0=1, X1=1, Y1=0递归求解：X i=Seq[i-2]*X i-1+X i-2i >1Y i=Seq[i-2]*Y i-1+Y i-2i >1获得数偶码：P= X n+1Q=Y n+1（2）从数偶码到序列码的解码算法：输入数据是整数偶<P,Q>. 输出数据是它所代表的汉字（对应的序码）的序列，放在Out[]中，该序列的长度为n。
解码过程如下：为变量赋初始值：M0=Q X0=P循环辗转相除，将相除的结果保存进入数组Out[]，直到M i为零，递归公式如下：Out[i]= (int)X i/M iM i+1=X i-Out[i]* M iX i+1=M i2.索引机制的建立对整个词典进行编码之后，每个词语就对应着一对数偶码，其特点是随着词语的长度增加，数值会变得很大，所以必须建立相应索引，在这一点上本文进行了相应的多次探索，最后选择了分段索引方式。