用于汉语文献自动标引的词典结构研究，本文主要内容关键词为：汉语论文,词典论文,文献论文,结构论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
摘要 用于汉语文献自动标引的词典组织结构对自动标引的效率有很大影响，自动标引中运用的词典查找算法有其自身的特点，符合这种特点的词典结构能提高自动标引过程中分词的速度。本文在分析了几种常用的词典结构的空间效率和时间效率之后，提出了一种通用而高效的词典组织方法。采用这种方法的词典，其体积可以减小到原来的0.4倍，分词速度提高到原来的2.5倍。
Study of the Dictionary Structure Used for Automated Indexing System of Chinese Document
Liu Yongdan
(Airforce Political University)
Abstract The dictionary structure used for automated indexing systemof Chinese document can produce a great impact on the indexing efficiency.The searching algorithm used in automated indexing processhas a style of its own，so，the dictionary structure making full use of the style can increase the speed of the separating word.Afteranalysing the space and time efficiency of some dictionary structures，the article puts forward a general and efficient method.Using themethod，the volume of dictionary can be cut down to 0.4 times of it，and the speed of separating word will be increased to 2.5 times.
1 前言
汉语文献自动标引的基础是汉语自动分词技术。汉语自动分词的基本方法可分为三类：形式分词法、语法分词法和语义分词法①。目前比较成熟的自动分词方法有：①最长匹配法；②逆向最长匹配法；③最短匹配法和逆向最短匹配法；④增字法；⑤减字法；⑥逐词须字比较法；⑦设立切分标志法；⑧链接表法。以上方法均不对中文句子做语法分析和语义分析，属于形式分词法，共同点是都装备词典②，可见词典在自动分词中的重要。正在发展中的语法分词法和语义分词法同样离不开词典，因为不管采用何种方法，对切分到的词都必须和词典对照，以确定其是否有意义，必须建立相应的词典。
一般地，一种分词方法需要建立一个结构与之对应的词典，所以，各种自动分词方法建立的词典的结构不会完全一样。但是，有些词典的结构却具有一定的通用性。这是因为：切分出一个词的过程包括两步，即切词过程和判断过程。切词过程对应于分词法中的扫描算法，判断过程指的是在词典中查找切词过程中分离出的字串是否存在的过程。两种不同的分词方法的切词过程不同，但却可能有完全一样的判断过程，如最长匹配法和逆向最长匹配法。那么，这两种分词方法当然可以采用结构一致的词典。实际上，以上列出的八种方法中的大部分方法都可以采用相似甚至完全相同的词典结构。
汉语文献自动分词研究的目的可以分为两种：一种是用于汉语文献的自动标引，即从汉语文献中自动切分出符合组成主题词的词语；另一种用于汉语语言的处理和研究（机器翻译、语言理解）③。对于面向汉语语言处理和研究的自动分词技术功能的要求，比面向自动标引的自动分词技术的要求高，例如要有相当高的准确率，要解决形歧切分问题，要进行语法和语义分析等。用于自动标引的分词法更关心能否从文献中切出实义词，允许一定的误差，但要求较高的分词效率。所以，在汉语文献自动标引中一般采用相对简明的分词法。
本文讨论的词典，指的是采用主题表法或关键词词表法进行自动标引中使用的存储中文词的词典，用于在其中查找切分出的字串，从而判断该字串是否可以成为一个备选的标引词。对词典结构研究的目的在于改善它的空间效率和时间效率，提高主题表法和关键词词表法的自动标引速度，同时，对于其他自动标引方法也有一定启发，如北京文献服务处在进行自动标引过程中，采用了后缀链接字典切词和主题词典匹配并用的方法。
2 词典的物理结构
词典的存储结构，最常采用的方法是散列表法和B+树两种。
散列表法的查找速度非常快，这是以损失一定的空间效率换取的，适用于要求快速匹配的算法。但对散列表法的一些关键参数要仔细设置，否则不仅浪费空间，查找速度也会降低，维护很不方便。散列表法是层次数据库常用的索引方法。
B+树的空间效率很高，时间效率比散列表法稍差，但查找速度也相当的快，并且可维护性好，因此是目前所有关系数据库采用的索引技术。
通常认为，对于大型词典最好采用散列表法，以节省查找时间。但使用经验表明，这种看法应该改变，无论对于大词典还是小词典，B+树都能胜任。这应该归功于个人计算机硬件性能的迅速提高和关系数据库软件技术的日益成熟。
目前个人计算机上速度最快的数据库系统FoxPro V2.5，对索引文件采用B+树结构，并使用了一种称之为Rashmore的数据存取技术，大大地提高了数据存取速度。采用B+树和Rashmore技术允许FoxPro在索引数据库中快速完成数据的提取，支持建立复合索引文件中的多个标志，用压缩索引格式生成较小的索引文件，以加快对数据的搜索，可以在很短的时间内对百万个记录的大型数据库的查询做出反应。本文所有的测试工作均在FoxPro环境下完成，各种结构词典文件的索引都由数据库系统维护。
3 词典的逻辑结构
词典的逻辑结构对数据库系统来说就是数据库结构。
下面列出几种词典的数据库结构，并加以分析和对比，其中包括一些我们认为并不实用的方案，目的在于引申出更好的结构。为了便于比较，在分析过程中考虑了以下因素：
(1)词典的空间效率。词典中应能存储大量的中文词，而且中文词有长有短，如何减少存储空间的浪费是非常重要的因素；
(2)词典的时间效率。词典的结构必须便于查找，不能单纯为了提高空间效率使查找算法复杂化；
(3)词典信息的保真度。提出这一点是因为存在一些算法，可以节省较多的空间，但会有少量的信息失真。
3.1 方案一
最简单的词典结构如图1所示。
图 1
这种方案最容易实现和维护，其优缺点也是明显的：具有很快的查找速度；空间效率极差，因为采用定长字段（如8字节）存储了不定长的中文词，库中必然浪费大量空间；索引文件大，因为键值的长度与记录等长。
此方案适合于小型词典。
3.2 方案二
为了提高方案一的空间效率，可以将词典按词长分库，建立二字词库，三字词库，四字词库，多字词库等。
图1所示的词典结构可划分为图2。
图 2
方案二可以有效地解决方案一中存在的空间浪费问题，随之而来的是管理的不方便，即必须建立多个数据库文件和相应索引文件；查找时要在各个库之间切换，增加了部分系统开销，速度不如方案一快。
3.3 方案三
方案一和方案二的共同点是直接在库中存放完整的中文词，词典的体积将随着词的数量呈线性增长。我们认为这两种方法存在着很大的冗余度，如下列几个词：
自动、自从、自动化、自动标引、自动分词、……
首字都相同，若加以集中存储，还可以进一步节省空间，加快存取相关数据的速度。
我们称中文词的第一个（最后一个）字为首（尾）字，剩下的为尾（首）字串。各尾字串之间用一个空格分隔。
图 3
这种方案有较高的空间效率，采用可变长字段（备注字段）解决了词长不均的问题。更吸引人的是词典库的记录数不再呈线性增长，即记录数量不等于中文词数量，而是中文字的数量。索引文件不再对词建立索引，而只对字建立，这意味着索引文件变得非常小，而且几乎不增长。
令人担心的是时间效率，因为空间效率的提高往往是以损失时间效率获得的。但测试表明，方案三的时间效率在大部分基于词典的自动分词算法中是最好的，其原因在于它非常有效地满足了分词过程中词典查找“首字成族，连续判断”的特点。
以最长匹配法为例，K=8。最长匹配法在判断一个字串不能为备选词的时候，下一步是在此字串的基础上减少一个字再进行判断，如扫描句子“自动分词研究的目的在于……”，先切出字串“自动分词研究的目”，在词典中取出所有以“自”为首字的尾字串集合，并在尾字串集合中查找子串“动分词研究的目”，没有成功，则在尾字串集合中查找子串“动分词研究的”，……，直得查到子串“动分词”。在这个过程中，取出尾字串集合的速度非常快，因为B+树的索引键一般不超过2000个（即首字的总个数）。更重要的是，不必每切出一个字串就到库中查询，而是用高效的内部函数在内存中查找。
其他的分词法与此类似，如逆向最长匹配法只要将首字改为尾字、尾字串集合改为首字串集合即可。
3.4 方案四
上一个方案的空间利用率还不理想，尾字串之间设置了分隔符，每增加一个词就至少浪费一个字节。图4所示的就是不要分隔符的方案。
图 4
显然，这种方案的空间效率更好一些，速度也会有所提高，但却使一部分词典信息失真。采用这种结构的词典当然可以切出“自动标引”这样的词，同时，它会认为“自动从动”也是一个词，尽管这个无意义的字串出现的可能性不大。实际上，“无意义字串的出现频率低”正是指出此方案的一个重要依据，但这种方法得不偿失，不宜采用。
3.5 方案五
能否既不浪费一个字节的分隔符的空间又可以分隔各个尾字串呢？
计算机存储一个汉字需要两个字节，这两个字节的最高位都为1，对于我们知道词典中存储的都是汉字这一事实来说，“这两个最高位都是1”已成为冗余信息，因此可以充分利用它们的空间。方法如下：将尾字串的最后一个汉字的第二个字节最高位改为“0”，即可做为尾字串之间的分隔符。如“中国”的尾字中“国”的内码和变换后的编码见表1。
表 1
二进制十六进制
内码
10111001 11111010B9 FA
编码
10111001 01111010B9 7A
从表1中可以看出，变换后的编码形式是将汉字的第二字节十六进制高位减去8（如“B9FA”中的“F”减去“8”变为“B97A”）。
当在词典中查找“自动分词”时，先对尾字串“动分词”进行变换，将最后一个字“词”的第二个字节最高位的值改置为0，即将“B6AF B7D6 B4CA”变换为“B6AF B7D6 B44A”，然后在“自”的尾字串中查找“B6AF B7D6 B44A”，如图5所示。
图 5
另一个改进是增加一个“最大词长”字段，以减少无谓的切分，如图6所示。
图 6
在扫描句子“自动分词研究的目的……”时，可以得知以“自”为首字的词最长不超过4，即从前4个字“自动分词”开始分词，大量减少匹配次数。
经过如此改进后，空间效率不仅与方案四相当，而且不会使词典的信息失真，代价是在查找之前的一个字节的“预处理”。这点代价是相当值得的，因为它比方案三有更好的时间效率。
4 测试与结论
很显然，方案一与方案二基本上可归为一种类型，方案三至方案五可归为另一种类型。一种类型之内几乎只通过分析就能比较出方案之间空间效率和时间效率的差别，如方案五明显优于方案三和方案四。真正需要实际测试的是方案一与方案五，我们希望得出“方案五最优”的结论，测试的结果也确实证明了这一点。
测试采用了一个五千词规模的小词典，分词法选用了最长匹配法。测试环境：Compaq 386/25，内存4兆，操作系统DOS 6.0，中文环境UCDOS 3.0，数据库管理系统FoxPro 2.5。结果见表2、表3。
表2 空间效率对比
表3 时间效率对比
句子长度（字）
14 23 55 128 193259 326
方案一（秒）0.646
1.089
1.983
3.938
5.356
6.554
7.637
方案五（秒）0.472
0.796
1.350
2.030
2.301
2.744
3.056
分词速度之比1:1.37 1:1.37 1:1.47 1:1.94 1:2.33 1:2.39 1:2.50
从数据中可以看出，方案一的词典有一个大的库文件和大的索引文件，而方案五的索引文件非常小，主要信息存放在可变长的备注文件中，使得词典体积压缩了一倍以上。实际上，由于备注文件中块因子(Block Size)的存在，词典含有的词汇量越大，空间利用率越高。现在计算机的外存越来越大，使人们转向对词典的时间效率更加重视。而事实上，这种方案除了可以节省磁盘空间之外，若把这种方法应用于内存中组织中小型词典，将可以轻而易举地把整个词典装入内存，极大地提高自动分词速度。此方法将另文介绍。
方案五的时间效率也明显高于方案一，其原因有三：①索引小，键值短；②一次读出一个字为首字（尾字）的中文词的所有信息，然后基本上只在内存中查找；③存储了词长的区间，减少盲目切分和查找。可以看出，随着句子长度的增加，方案五的分词速度与方案一相比，稳定在2.3-2.5倍左右。测试的目的在于两种方案在同一环境下的对比，因而没有采用高级语言替代FoxPro的内置语言来提高分词速度。
从本文的分析和测试中可以看出，方案五无论在空间效率和时间效率上都达到了很高的水准，是一种高效而通用的组织汉语文献自动分词的词典的方法。结构与算法总是密不可分的，本文针对这种词典结构相关的分词算法也做了一些探讨。