第37卷第6期
1997年11月
大 连 理 工 大 学 学 报
Journa l of Da l ian Un ivers ity of Technology
Vol. 37, NO. 6
Nov. 1 9 9 7
一种机器翻译系统用词典的设计及其结构
X
黄德根 简幼良 蒙家玉
( 大连理工大学计算机科学与工程系 116024 )
摘要 提出了机器翻译系统的词典设计目标, 讨论了大型动态词典文件的
组织方法. 根据汉语词分布不均匀的特点, 提出一种扩充的B+ 树索引词典
文件结构, 并给出该词典的查询算法及词典结构的评估. 实践证明该词典
结构达到了机器翻译系统的要求, 其结构是合理的.
关键词: 人工智能; 信息处理?词典结构; 机器翻译; 电子词典
在机器翻译系统中, 词典占据极其重要的地位. 机器翻译的各个过程, 从自动分词、语法
分析、语义分析到译语生成等均需要频繁地访问词典. 词典结构及词条中所包含的信息量直
接影响整个机器翻译系统的效率. 词典的组织既要考虑到汉语分词, 又要照顾到分析与生
成; 既要考虑节省空间, 又要照顾系统的运行速度. 因此, 词典的设计对机器翻译系统至关
重要, 越来越受到人们的重视〔1、2〕. 本文阐述一种面向机器翻译系统的词典设计及其结构.
1 设计目标
词典是一种特定类型的数据库; 与一般数据库文件相似, 词典的组织与设计必须针对实
际系统的要求, 采取相应的文件组织方法. 在制定词典的组织结构时, 着重考虑了如下几个
问题.
1. 1 词条信息丰富、数据项不定长
考虑到词典必须为机器翻译的各个过程所利用, 在词典中收录了如下信息: 词法信息、
语法信息、概念信息、***起关系及译语信息等. 其中只有词法信息和概念信息为定长字段, 其
他均为不定长字段. 另外, 一个单词可能有多种词性, 每种词性下又可能有多个概念属性.
一个单词下的所有词性的内容都包括在同一词条中.
词条内的信息结构如图1所示. 其中, 记录的关键字由单词的汉字内码组成, 如果单词长
小于固定长度时, 不足部分填入空格; 基本信息由单词的频度信息、词法信息组成, 二者以固
定长度存储. 品词属性为变长字段, 存储了该品词下所有的语法信息、概念分类信息、***起信
图1 词条信息结构
息及相应的译语; 如果一个单词有多个品词属性
时, 品词之间通过指针连接在一起, 指针为- 1表
示该品词属性为最后一个节点.
1. 2 大规模动态特性
包括两方面的内容: 一是要求词典具有较大
的容量, 能容纳至少6万条单词, 并能扩充到10万
条左右. 由于每条词所包含的信息从几十个字节
到数百个字节不等, 存储词典信息的空间至少为
几兆字节, 信息量较大. 二是要求词典具有动态
修改特性; 词典生成后, 在操作中可“动态地”进行维护, 即根据用户的需要, 可对词典进行
插入、删除、修改操作.
1. 3 快速查询
查询算法和存储介质是制约词典访问速度的两个主要因素, 其中查询算法决定了单词的
查找速度; 而存储介质决定数据的存取时间. 在算法确定情况下, 若能改变词典的存储介质,
将词典存放到速度较快的介质上, 则可缩短数据存取时间, 提高词典的查询速度.
一般来说, 词典数据文件连同索引文件一起存放在外存上, 每次查词典时要访问若干次
外存; 尽管外存的存取速度已经有很大提高, 但速度仍以毫秒为单位, 远远低于以纳秒为单
位的内存存取速度. 在系统运行时, 若能将外存上的词典文件一次全部装入内存, 则查询时
访问外存的次数为零, 词典的速度就能得到很大提高. 因此, 设计中还要考虑目录区和数据
区空间的比例, 以使词典大小控制在合理的范围内, 便于实现词典常驻内存.
2 词典的索引结构
大型动态数据文件一般采用B+ 树结构〔3〕, 但是, 完全的B+ 树结构具有级数太多、索引区
大、空间利用率低的缺点. 为此, 本词典采用一种变形的B+ 树索引文件结构: (1) 树的级数
限制在3级. (2) 根结点至少有2个孩子. (3) 树中所有叶子都在同一级上. (4) 每个结点拥有
的孩子数没有限制. 其具体实现是: 将整个词典数据区划分成许多定长的数据块(1 024字
节) , 对应每个数据块有唯一的块号, 数据块中的单词按词条内码的增序顺序存放. 索引区采
用分类技术, 分成主、次两级索引, 其中主索引以表示汉字区间的单汉字为关键字, 将单词按
区间分成若干大类, 大类中的所有词条其首字均在同一汉字区间内; 次索引以数据块中最后
一个词条的内码为关键字, 记录单词所在的块号.
在主索引中, 词条内码有如下顺序关系:
大类1词条的首字< 大类2词条的首字< ?< 大类n 词条的首字
词典的索引逻辑结构见图2. 主索引和次索引中的目录项均按汉字内码的增序顺序排列,
每个大类(主索引的一个目录项) 中含有若干个数据块, 块的个数由区间内包含的词条数而
定. 在具体实现时, 先扫描整个文本词典文件, 对单词总数及首字相同的词条进行统计; 在
分类数固定的情况下, 计算出每一分类区间的起始汉字内码和终止汉字内码, 使各分类区间
内的词条数相近.
第6期 黄德根等: 一种机器翻译系统用词典的设计及其结构715
图2 词典索引结构
3 查找算法及词典结构的评估
3. 1 查找算法
基于上述结构的词典, 其查找算法可描述如下. 其中, K 代表词条的汉字内码, S 为词
条首字内码.
(1) 根据S 值, 访问主索引, 查找单词K 所属的分类区间, 获得相应的次索引指针P 及
该分类区间内包含的数据块个数.
(2) 以指向次索引的指针P , 访问词典的次索引, 按二分法查找单词K 所在的具体块号
B.
(3) 若块B 已经读入内存, 则转到(4) ; 否则, 根据块大小及块号B 计算块的磁盘物理地
址(即文件指针= 数据区起始地址+ 块号B ×块大小) , 将整个数据块一次读入内存.
(4) 对块内词条按顺序查询, 若块内有词条K , 则查找成功, 返回相应的单词信息; 若查
找失败, 返回空信息, 表示该词典中没有词条K.
3. 2 词典结构的评估
3. 2. 1 空间效率 本词典实际登录的汉语词有6万余条, 且词条信息不定长, 最长可达1 024
字节(即整个数据块为一条词) , 生成程序最后统计得到的词典信息总量为4 819 352字节, 平
均每条约占80字节. 实际生成的二进制词典文件将整个词典分成20个大类, ***5 883个数据
块; 词典实际大小为6 083 102字节. 词典各部分占用的空间为: 主索引占80字节(20×4) , 次
索引占58 830字节(5 883×10) , 数据块占6 024 192字节(5 883×1 024). 其中, 实际数据块所
占用的空间比词典信息所需的磁盘空间多出1 204 840字节, 是为方便词典扩充, 没有将数据
块填满, 预留出20% 的空间作为登录新单词使用的缘故.
两级索引目录区仅用58 910字节的磁盘空间, 约占词典信息总量的1. 18% , 小于80×86
中一个数据段所允许的最大空间(64 KB) , 可以将其放到内存中去, 减少访问磁盘的次数, 提
高查询速度. 而采用一级索引、对半检索的词典结构, 即使按最长单词为4个字计算, 其索引
区也要占60 000×(4×2+ 4) = 720 000字节. 其中, 一条单词占一个目录项, 每个目录项由表
示单词汉字内码的关键字(4×2字节) 和文件指针(4字节的长整型数) 组成. 可见, 完全采用
索引方式的词典, 索引区占用空间很大, 不适合常驻内存.
716 大连理工大学学报 第37卷
3. 2. 2 算法复杂度 考虑一般情况, 设词典有N 条单词, 分成M 个分类区间, 每个数据块
平均可存放L 条单词, 则每类平均有N ?M 条单词、需要N ?(M ×L ) 个数据块. 对任一词条
K , 访问主索引区的平均查找次数为进行M ?2 次整型数的比较, 相当于比较了M ?8 次单词
( 设词长为4个汉字) , 访问次索引区的平均次数为log2 (N ?M ) , 因此确定单词K 所在数据块
的平均查找次数为M ?8+ log2 (N ?M ). 由于主、次索引区常驻内存, 访问索引区是在内存中
进行的, 实际所需时间很少.
按上述词典规模: N = 60 000, M = 20, 查找存放单词K 的数据块平均需要进行14次内
存字符串的比较. 另外, 由数据块号到获得单词K 所有义项信息最多需要访问外存1次, 平
均进行4次字符串比较(块内查询). 因此, 查找一词条信息最多需要访问1次外存(可能为0
次) , 平均需要进行18次字符串(8字节长) 比较.
3. 2. 3 可维护性 对词典进行更新操作会引起词典数据发生变化, 并可能引发大量的磁盘
文件操作. 在本词典中, 数据以块为单位存储. 当删除一条单词时, 只需将单词从所属的数
据块中删除, 之后将该数据块重新写入数据区; 既不会发生磁盘数据的大量移动, 也不会引
起索引区的变更. 当登录新词时, 若数据块有足够的空间, 则登录操作仅在数据块内进行;
若数据块没有剩余空间, 则进行块分裂, 将原来的块一分为二, 前一块仍存放在原来的位置,
后一块需重新申请一个数据块空间, 并分配块号, 放在数据区末尾, 相应地, 在索引区插入
一个索引项. 由此可见, 无论是删除操作, 还是登录新单词, 均不会引起数据的大量移动, 对
词典的更新都是在局部范围内进行, 读写磁盘各为1次.
4 结束语
词典是机器翻译中的重要组成部分. 实际设计中既要考虑合理的空间开销, 又要考虑词
典数据的访问速度; 二者很难兼顾. 本文用统计方法对汉语词进行分类, 克服了一般Hash 方
法中由于汉语词分布不均匀所引起的一系列问题. 如数据块的负载相差很大, 容易导致数据
块溢出; 当发生溢出时, 访问磁盘的次数增加, 降低了词典的访问速度等. 索引区和数据区
的大小比例协调, 空间利用率高, 为实现整个词典装入内存创造了条件. 从分词阶段的实际
效果来看, 词典常驻内存后, 其分词速度提高了10倍以上, 大大提高了整个机器翻译系统的
效率.
Lex icon des ign and organ iza t ion of dict ionary of
mach ine tran sla t ion system
Huang Degen, J ian You liang, M eng J iayu
( Dep t. of Comput. Sci. and Eng. , Dalian U niv. of Techno l. , Ch ina )
Abstract The design goals of dict ionary u sed in m ach ine t ran slat ion system are p ropo sed.
The o rgan izat ion m ethod of large2scale dynam ic dict ionary f ile is discu ssed too. A cco rding to
the featu re of Ch inese wo rds’ non2equal dist ribu t ion, the paper p resen t s a k ind of st ructu re
of dict ionary based on ex tended b inary t ree index and a search algo rithm. F inally, the au2
tho rs summ arize the eff iciency of the dict ionary st ructu re.
Key Words: art if icial in telligence; info rm at ion p rocess? lex icon o rgan izat ion; m ach ine
t ran slat ion; elect ron ic dict ionary