日汉电子词典结构的研究与实现

汤蓉 徐立军 尹宝生 年新 潘峰

沈阳航空工业学院人机智能研究中心 沈阳黄河北大街52202信箱 110034

E-mail:software@ge-soft.com

一、引

随着网络的不断普及和国际间信息交流的日益频繁,机器翻译技术的研究与实现越来越被人们所重视。就现有的机器翻译系统来说,还存在着很多不尽人意的地方。电子词典是机器翻译系统的最基本的组成部分,除作为机器翻译系统的一部分外,独立的电子词典产品也倍受广大用户的欢迎。因此,有效、合理地组织词典,加快查找过程,是电子词典必须解决的问题。

针对目前普遍存在的英汉电子词典来说,以日语为源语的日汉电子词典的组织结构要更为复杂。其中的日文汉字、假名混排、交错查找的现象是较为繁琐的问题,也就是说,在日汉电子词典中多数词条都存在着两个关键字。从时间和空间上有效解决日文汉字、假名的双重查询问题是日汉电子词典查询的关键。本文将主要针对这个问题介绍一种方便、实用的日汉电子词典组织结构。

二、源语言分析

       日语属于粘着语,它不同于其他语种,主要表现为:

1、  汉字、假名混合排列:

日文不同于中文,在同一篇文章中,汉字和假名同时存在,不同的用户根据个人的习惯,可同时使用汉字或假名书写同一个日文单词,这就要求词典应具备汉字、假名双重查询能力,例如:

わたしは学生です。

也可以写为: 私は学生です。

2、  部分单词书写格式唯一:

虽然日文存在汉字、假名混排现象,但还有大量单词只以汉字或假名一种形式出现,例如:

です、これ —→ 只以假名形式出现;

3、  存在大量同音词:即同音异义词,例如:

がくせい—→学生、楽聖、学制;

じしょ—→辭書、地所、自書、字書;

在词典中,存在大量的同音词,有的词甚至产生几十个同音词,如果词典以单词的读音(即假名)为关键字从词典中查找有关单词,只能找到其中一个,其他词都匹配不上;

4、  存在大量多义词:即读音不同的同形词,例如:

日本—>にほん/にっほん

同样,在词典中存在着大量这种多义词,且这些单词中有些是读音不同,语意相同的,有些是读音不同,语意也不相同的,如果词典以日文汉字为关键字建立索引进行查找,也只能找到其中的一个,其他的都匹配不上;

从上述日语现象分析,日汉电子词典如果分别以日文汉字和假名为关键字进行有序排列,采用日文汉字、假名相结合的查询机制进行搜索将是一种最佳的查询方案。

三、常用的电子词典组织结构

目前常用的电子词典结构有多种,但从其存储结构形式来看,可分为定长字段型,变长字段型和定长字段变长字段混合型三种;从数据组织形式来看,可分为无索引型、一级索引型、二级索引型和多级索引型等四种。

定长字段型词典结构适用于小规模词典,其优点是数据格式规整,计算机访问速度快,访问算法简单;其缺点是存储空间浪费严重,此种结构仅适用于实验系统或微型翻译系统,实用系统一般不采用此结构。

变长字段型词典结构适用范围较大,其主要优点就是可最大限度地节省空间;缺点是计算机访问速度慢,访问算法较复杂,访问得到的数据要进行整理后方可使用。

定长字段变长字段混合型词典结构实用较少,通常是词条信息中的第一个字段是词条,其长为定长,而其他字段是变长的,词条为定长是为了方便词条查找时的匹配,其他字段为变长则是为了节省空间。

最常用的词典结构是具有以词条(包括重复词条)为关键字的一级索引结构。这种词典存储方法被普遍使用和接受,通常被认为是比较好的词典组织结构。由于所有的词条都被有序地排列在索引文件中,任何一个词条的查询都可以通过“折半查找”来实现,但这就要求每个词条的索引信息是定长且有序。日文单词长度不一,有些长达15个字以上,为完整地存储任何一个单词,则必须设定所有词条字符串的长度都为最大单词长度,这样的索引,存储词条的空间会存在大量的冗余,造成存储空间的严重浪费。

除此以外,还有后来人们提出的“以领头字为关键字的一级索引结构”。它的主要思想是索引中只存储关键字的开头字,利用开头字定位查找单词在词典中的位置,然后进行顺序查找。该方法大大减少了索引文件的存储空间,同时采用定长的存储结构,加快了查找速度。但由于其索引文件的查找结果只能定位到以某字开头的第一个关键字的位置,还需在词典文件中进行顺序查找,所以虽然其词典中的信息可以是无序的,但以某领头字开头的词条的排列却是有序的。针对日文词典,我们需要建立日文汉字、假名双重索引结构,那么势必要以日文汉字和假名分别进行信息登录,造成大量的信息冗余。

四、隐关键字定长双索引的结构

通过上述分析,基于系统实用的思想,我们提出一种针对日汉词典的简单、高效的组织结构——隐关键字定长双索引存储机制。

(一)设计思想

根据日语的特殊性,我们分别以日文汉字和假名为关键字,按照各自关键字顺序建立由词条在词典中的偏移数值构成的索引。同时建立两个索引,存储空间就显得格外重要,所以我们不在索引文件中存储关键字信息,两个关键字仍旧保留在词典文件中,从而大大节省了索引文件的存储空间,同时也省去了以日文汉字和假名分别进行信息登录的麻烦。索引文件中采用定长数组直接存储相应关键字对应的词条在词典中的位置,达到提高词典查询速度的目的。

词典文件中的信息可以是无序的,两个索引文件分别按照各自的关键字有序排列。

(二)索引的建立

1、日汉电子词典的存储结构

日汉电子词典中每个词条包含日文假名、日文汉字及其相对应的汉语信息,每个词条各字段信息使用变长存储方式,整个词典无须排序。

词条1

日文假名关键字1

分割符

日文汉字关键字1

分割符

汉语信息

词条2

日文假名关键字2

分割符

日文汉字关键字2

分割符

汉语信息

……

……

……

……

……

……

词条k

日文假名关键字k

分割符

日文汉字关键字k

分割符

汉语信息

……

……

……

……

……

……

词条n

日文假名关键字n

分割符

日文汉字关键字n

分割符

汉语信息

图一:日汉电子词典的存储结构

       2、建立中间索引文件

       中间索引文件是包含关键字的索引文件,分别以日文汉字和假名为关键字建立两个中间索引文件。从词典文件中依次提取每个词条中的关键字及其相应的词条在词典中的偏移地址,并存入中间索引文件中。中间索引文件中的每个词条与词典文件中的每个词条是一一对应的。

 


假名关键字                                                                                                        汉字关键字

关键字1

 

词条1位置

 

词条1各字段信息

 
                                                                                   

 

 

 

 

 


……

 

……

 

 

 
                                                            

 

 


假名中间索引文件                      词典文件                        汉字中间索引文件

图二:中间索引文件的结构

(注明:假名中间索引文件中: 关键字2<关键字k<关键字n<关键字1

汉字中间索引文件中: 关键字k<关键字1<关键字n<关键字2

其中n>k,两个中间索引文件是无序排列,词典文件也是无序的)

3、建立索引

将两个中间索引文件分别按照关键字进行排序,提取其中存储词条位置的数据分别存入两个索引文件中,生成系统使用的双索引文件。      

 

 

 

 

 

 

 

 


假名索引文件                                     词典文件                                  汉字索引文件

图三:索引文件的结构

(注明:其中n>k,两个索引文件均为有序排列,词典文件是无序的)

       从图三中我们可以看到索引文件与词典文件的词条是一一对应的,也就是说随着词典文件词条的增加,索引文件也会不断地增加,如果一次性将索引读入内存,可能会占用过多的系统资源,同时为了进一步提高词典检索速度,我们为词典文件建立了二级索引。二级索引文件的建立采用常见的分段索引的方式,也就是将一级索引以一定数量进行分段,将每段开头的数据存入二级索引文件中,二级索引指向一级索引文件。

(三)查询步骤

由于索引文件是有序的,且与词典文件中的词条一一对应,所以可采用“折半查找”的方法进行查询:

1、  由查询单词串定位相应的一级索引文件(日文汉字索引或假名索引);

2、读取一级索引文件中的数据(这里省去二级索引文件的查找过程),由该数据定位到词典文件,提取相应的关键字串;

3、用词典中的关键字串与查询单词串进行比较,确定下一步“折半查找”的方向;

4、重复步骤23,直至查询单词串与词典文件中的关键字串相匹配或确定词典中没有该查询单词串为止。

五、综合效率分析

词典的综合效率要从时间和空间两方面进行评估。

为加快词典的查询速度,通常索引结构都是直接读到内存中进行处理的,这就要求索引文件要尽可能的小,节省内存空间。

以目前最常用的以词条为关键字的一级索引结构(暂称1号索引)为例与本文介绍的索引结构(暂称2号索引)进行比较:

我们假设日汉词典词条关键字最多字数为W,词条总数为N,每个日文字为2个字节,一个长整形数为4个字节,则:

1号索引所占内存空间为:(W×2+4+1)×N (其中1为分隔符占用字节数)

2号索引所占内存空间为:4×N

N=70000, W=15, 1号索引占用的内存空间为2号索引的8.75倍,采用双索引结构后1号索引占用的内存空间将为2号索引的17.5倍。

词典的查询速度主要取决于系统所采用的查询算法的复杂度以及访问词典文件的时间。两种索引均采用定长存储结构,其查询算法简单、快速。由于2号索引的关键字存在词典文件中,它访问词典的次数要多于1号索引,幸好目前微机技术发展迅速,词典文件的访问时间已逐渐可以忽略。

可见,从综合效率的角度分析,2号索引结构较1号索引结构要优越许多。

前面提到的“以领头字为关键字的一级索引结构”,由于日文假名数量有限,采用该种索引结构将有效地减少索引所占用的内存空间,但也由此使以同一假名为领头字的词条数量大大增加,顺序查找势必急剧减缓词汇的查找速度,从综合效率的角度分析,该种索引结构不适合日汉电子词典。

六、结束语

索引结构的组织建立直接影响电子词典的查找效率,有效、合理地组织词典,加快查找过程,是电子词典必须解决的问题。

       词典组织结构的关键始终是在时间和空间两个概念上寻找平衡,既要节省时间,加快查询速度,又要减少存储空间的占用量,尤其是针对日语这种极具特殊性的语言,其复杂度更进一筹。本文所采用的“隐关键字定长双索引存储机制”,其占用存储空间小,查询算法简单、快速,切合日文的特殊性,解决了其双索引查询的困难,达到了时间和空间的最佳组合状态,特别适合PDA等移动式设备上的词典工具的建立。我们希望这一索引结构对加快电子词典的应用和普及能有所帮助。

返回