一种汉英双语句子自动对齐算法_王占军
第26卷 第2期计 算 机 仿 真2009年2月 文章编号:1006-9348(2009)02-0329-05
一种汉英双语句子自动对齐算法
王占军,姚卫东
(中国航天工程咨询中心,北京100037)
摘要:双语语料库建设及其自动对齐研究对计算语言学的发展具有重要的意义。双语对齐技术是加工双语文本的核心,对
齐效果的好坏直接影响了以后工作(诸如机器辅助翻译)的进行。基于汉英双语的实际情况,提出了一种新的句子对齐混
合算法,该算法主要采用一种新的基于长度的对齐算法,并结合基于词典的对齐算法,通过正反双向对齐,进一步提高了句
子对齐的准确率。最后通过100个文件,5000多句英汉双语对该算法进行了验证,从对齐效果可以发现,结果比较理想,因
而可以证明,该算法在实际工作中是可行的。
关键词:双语语料库;句子对齐;混合算法
中图分类号:TP30116 文献标识码:A
An A lgor ith m for Auto ma ti c Sen tence A li gnm en t
of English and Ch i n ese Para llel Corpora
WANG Zhan-jun,Y AO W ei-dong
(China Aer os pace Engineering Consultati on Center,Beijing100037,China)
ABSTRACT:B ilingual cor pus and its aut omatic align ment are of great significance t o the devel opment of computa2
ti onal linguistics.A s the key technol ogy during the course of building cor pus,bilingual align ment technol ogy has a
direct i m pact on the future work(such as computer-assisted translati on)p r ocess.Based on the actual situati on of
Chinese-English bilingual,this paper p r oposes a ne w hybrid algorith m for sentence align ment,which is mainly
based on the length-based method and combined with the lexicon-based method.Thr ough the p r os and cons of t w o
-way align ment,this algorith m further i m p r oved the accuracy of the sentence align ment.Finally,by using100doc2
u ments,more than5,000English-Chinese bilingual sentences,the algorith m was verified,and fr om the effects of
align ment it can be f ound that the results are satisfact ory,and the algorith m in p ractical work is feasible.
KE YWO R D S:B ilingual cor pus;Sentence align ment;Hybrid algorith m
1 引言
近年来,在语言信息处理的研究和开发中,单语和多语语料库(以双语语料库居多)的作用日益突显出来。特别是在机器翻译研究中,人们提出了多种基于双语语料库的新方法,例如采用所谓的基于实例(Exa mp le-Based)的或基于存储(Translati on Me mory)的机器翻译方法,可以直接使用经过对齐的双语语料改善机器译文的质量。此外,也可以通过统计模型从双语语料库中获取双语词典和翻译模式,从而改进传统的机器翻译方法。除中文信息方面的应用之外,双语语料库的建设对于双语词典编纂、跨语言的对比研究也具有重要价值。
国内外很多研究机构都致力于双语语料库的建设,并利用这些语料库进行广泛的研究。在国外,加拿大议会议事录语料库(Canadian Hansards),其来源于加拿大议会保存的辩论记录,是非常著名的英法双语语料库;由O sl o大学构建英语一挪威语平行语料库(The English-Nor wegian Parallel Cor pus);还有M I LLE语料库,它包含三个双语平行语料(Punjabi/English,,Sylheti/English,Chinese/English),由M cEnery等人于1998年在Lancaster大学的M I L LE项目中开始构建,为了调查和研究英国的非本土少数民族语言的语料库资源的发展。在国内,在有关汉外双语语料库建设研究方面,香港科技大学收集和加工了香港立法委员会的会议记录,形成汉英双语语料库。此外,北京大学、东北大学、哈尔滨工业大学的研究人员也建立了一定规模的汉英双语语料库。但目前汉外双语语料库规模比较小,加工规范也不统
收稿日期:2008-01-09 修回日期:2008-01-17
一,从而影响了双语语料库知识获取的研究。
实现各个层次的对齐是双语语料库建设的一项重要内容。本文主要讨论汉英双语句子级对齐技术。句子对齐方法基本可以分为三类:
●基于长度的方法:这种方法基于一个最基本的判断:一种语言里较长句子的译文也较长,较短句子的译文也较短。这种算法利用统计学的算法,一般不需要额外的词典信息,被认为是独立于语言的。最初是由B r own和Gale提出的,他们在英法双语的加拿大议会会议录上取得了较好的对齐效果;清华大学和哈尔滨工业大学的研究人员分别将基于长度的方法应用于M icr os oft NT315Server安装指南和法律文献的汉英双语句子对齐,获得的试验结果。
●基于词汇的方法:它通过每个双语片断中的词汇匹配信息来计算其互为翻译的概率。该方法又分两种情况,一种方法通过找出在两种语言中存在历史关系而导致单词拼写比较相似的词汇信息;另一种基于词汇信息的句子对齐方法运用不同语言中存在着的相同的记号,如数字符号、日期或技术术语等,这些记号在不同的语言中的表现形式是相同的,利用这些记号可以大大的提高对齐的准确率。前者当中,一个成功的例子就是Si m ard提出的使用英法语言中普遍存在的同源词(cognate)现象来进行双语句子对齐的方法,这种外在拼写上的相似关系能够不需用访问额外双语字典而通过匹配策略直接确定。
●混合方法:基于长度的对齐方法模型简单,独立于语言知识和其他外部资源,但鲁棒性不好,容易造成错误蔓延。基于词汇的对齐方法相对可靠精确,但计算相当复杂。研究人员试图将这两种方法结合起来进行句子对齐。香港大学W u通过创建特殊词表来对基于长度方法进行了改进,并对在香港立法委员会会议记录上做了对齐试验,取得较好结果。
以上对齐研究大都是围绕单一领域或者某一文献、手册的双语文本进行,本文工作面向多领域,多题材,采用优化基于长度算法的基础上,结合基于词典方法中的相同词的混合方法,并对如何进一步提高对其精度进行了探讨和研究。新的算法不同于我们已经收集到的对齐方法,在最大程度提高准确率的目标下,牺牲了部分召回率,并且在航天四创软件公司CAT软件语料库建设工程中得到了应用,并取得了不错的效果。
2 算法理论基础
2.1 句字对齐的形式化描术
“对齐”这个词,既用于表示不同语言文本之间互译片断相互匹配的过程(A lign),也常常用于表示该过程获得的最后匹配结果(A lign ment)。由于根据上下文很容易判断其意义,所以本文在以后的章节中不会对这两种含义严格区分。一个表示匹配结果意义上的对齐可以形式化定义如下:假设一段文本S以及其译文T,S和T分别是m和n个有序句子的集合,表示为S={S
1
,S2,…S m},T={T1,T2,…T n}设对齐A为笛卡尔积集ρ(S)×ρ(T)一个子集,ρ(S),ρ(T)分别是S,T的子集。三元组(S,T,A)称为双语文本(bitext),对齐A中的每一个元素(有序的),被称作双语片断(biseg ment)或双语句对。
2.2 句字对齐的评价方法
对齐的评价方法分为两种,一种是有参照对齐的评价;另一种是无参照对齐的评价。也就是说,前者在评价一个对齐之前,事先已经具有一个作为参照的对齐,然后每个对齐通过与该对齐的比较来确定这个对齐的好坏程度。而后者只能通过对齐之间的比较来判断对齐的好坏。有参照的对齐评价方法常常用于评价一个对齐算法的优劣,通过对对齐算法输出的对齐结果与事先做好的参照对齐的比较来评价该对齐算法。无参照的对齐方法常用于对齐算法实现过程中的对齐结果选择。有参照的对齐评价方法事先有一个参照对齐(Reference A lign ment)。所谓参照对齐是用于评估其他对齐的一个标准的正确的对齐,它通常通过人工干预而产生,是计算机自动对齐想要达到的最理想的结果。在此,采用有参照的对齐。
根据Isabelle和Si m ard在1996年文献中给出的定义声明,用召回率(Recall)和准确率(Precisi on)对某一个给定的对齐算法依照特定参考对性能进行评价。它们的计算公式如下:
假设已知一段双语文本(S,T,A r)和一个已知对齐A。根据参照对齐A r(A r为所有正确片断组合的全集),对齐A 召回率Recall(A,A r)是在对齐中正确双语片断数(相对于参照对齐A r)与所有正确双语片断数的比值,公式如下:
Re ca ll(A,A
r
)=|A∩A
r
|/|A r|
由上式不难看出,0≤R e call(A,A
r
)≤1,Recall(A,A r)越大,说明A中正确对齐片断的绝对数量越多;若Re call
(A,A
r
)=0,表明A中没有正确的对齐片断,如果Re call(A, A r)=1,表明A中包含所有的正确对齐片断。
对齐的准确率是在某一对齐中正确的双语片断数(相对于参照对齐A r)与该对齐中所有双语片断数的比值,公式如下:
Pr ecision(A,A
r
)=|A∩A
r
|/|A|
同样,0≤P r ecisi on(A,A
r
)≤1,Precisi on(A,A r)越大,说
明A中正确对齐片断的相对数量越多;若Pr ecisi on(A,A
r
) =0,表明A中没有正确的对齐片断,如果Pr eci on(A,A r)= 1,表明A中包含全部正确的对齐片断。
虽然召回率和准确率都是衡量句子对齐的标准,但根据不同的领域方向,召回率和正确率的优先级也可以不同。本文的目的是为双语语料库提供双语语句对,则优先考虑对齐的准确率,即尽量少的产生错误的双语句对。
在实际的应用中,还经常使用一种F一评估法作为衡量对齐性能的指标,它综合应用了准确率和召回率的性能指标,是对齐准确率和召回率的调和平均值。
F (A,A r )=23
Re ca ll (A,A r )3Pr ecision (A,A r )Re ca ll (A,A r )+Pr ecion (A,A r )
F (A,A r )的取值范围仍然为,0≤F (A,A r )≤1,F (A,A r )的值越大,对齐A 的综合评价就越好。
3 本文采用的算法
3.1 算法分析
正如引言中所说,本文的算法主要是建立在基于长度的扩展方法的基础之上的。Gale 认为,基于长度的双语对齐算法只适用与印欧语系内部,而不适用于亚洲语言(特别是汉语和日语)与西方语言的对齐。对于英语(或者说印欧语系),每个词都用空格分开,因而分词是简单的;但是对于汉语(甚至对于亚洲语系)来说,没有明显的分词标志,因此对语料进行分析时,无法使用词的个数作为量度,而只能用字进行量度;汉语中每个字有两个字节,英语中单个字母有一个字节,可以考虑用单字节的基本单位即字符(char )作为其长度比较的量度。
这样就拥有了两种分析的方法,第一种是分析英语中词的个数与汉语中字的个数的对应关系来进行长度算法;第二种是通过汉英双语间的字节说进行计算。通过对一系列的数据进行了分析,发现用第一种方法的方差分布图。
试验语料是两千句已经对齐好的汉英语句对,希望通过对它的分析来比较两种方法的优劣。在进行分析前,先做几个设定:
设en_char_len 代表英文句子字节数, en_word_len 代表英文句子词数, cn_char_len 代表中文句字字节数,
cn_word_len 代表中文句字字数(为cn_char_len 的一半)
。
图1
中英文字长度对比图
图2 中英子长比值随英文字长变化图
其中在图1中x =en_word_len,y =cn_word_len (图中x,y 均
为相对值,以下同),图2中,x =en_word_len,y =
cn_word_len
en_word_len
如果采用第二种方法,经分析可得到以下两个图
:
图3 中英文字节长对比图
在图3中,x =en_char_len,y =cn_char_len,图4中x =en _char_len,y =
cn_char_len
en_char_len
经以上分析,从直观上可以发觉,两张基于长度的方法都可以达到比较准确的效果(途中可以发现大量的聚集点),而且从这几张图的聚合程度上来看,它们效果相似。在经过数学方差分析之后,可以得到如下结果:
图4 中英文字节长比值随英文字节长变化图
表1 各种方法测出结果对比表
样本空间均值方差相对标准差cn_word_len/en_word_len11738012773013030 en_word_len/cn_word_len016221010315012851 cn_char_len/en_char_len015720010411013545 en_char_len/cn_char_len118972012697012738
cn_word_len en_word_len +
cn_char_len
en_char_len
213101013539012575
en_word_len cn_word_len +
en_char_len
cn_char_len
215193013288012276
其中后两种样本空间是我试图将两种基于长度的对齐方法结合起来,结果发现效果要比单一使用某种方法好(相对标准差比较小),而相较而言,最后一种方法效果最好,即将英文字数与中文字数的比和英文字数术语中文字节数的比之和更为稳定。
综上,已经找到一个合理的基于长度的对齐算法,即将基于字数和基于字节数的长度对齐算法结合起来。由上述的分析可以得到一个阈值p。当然要想得到一个合理的阈值p,需要综合各种情况考虑,还要以已存在的对齐语句作为资料样本进行分析,比如,经分析,发现有85%的语料中中英文语句是一一对应的。
3.3 算法流程
以下详细介绍算法的流程。首先假定所对齐文本的段落是对齐的(段落对齐可看成另一种形式的句字对齐的,可以通过结合基于词汇的对齐算法中的锚点来做到),并通过
断句得到两个中英文语句数组。设r=en_word_len
cn_word_len
+
en_char_len cn_char_len ,设定基准值j,偏离范围p=
r-J
J
偏离的域基准
值D。在这里运用了回溯算法,回溯它的基本思想是:为了
求得问题的解,先选择某一种可能情况向前探索,在探索过
程中,一旦发现原来的选择是错误的,就退回一步重新选择,
继续向前探索,如此反复进行,直至得到解或证明无解。
具体算法如下:首先得到两个汉英语句组,从首句开始
即en=en[0],cn=cn[0],计算p值p0,如果p<0,英文句组
指针向下移一句en1=en[0]+en[1],cn1=cn[0],如果p>
0,汉语句组指针向下移(即cn=cn[0]+cn[1])再次计算p
值p1,如果|p0|<|p1|则认为en[0],cn[0]为一对对齐的语
句组;反之,继续向下校验……当p i<0时,英文句组指针下
移,p i>0时汉语句组指针下移,直到出现|p i+1|<|p i|。则
完成一组对齐后,继续下一组对齐。一直到最后一句为止。
为了提高准确率,从正向对齐一遍后,再逆向对齐一遍,方法
相同,然后取出两个集合的交集,即为该文本中正确的对
应集。
3.3 试验结果和分析
在航天四创CAT软件中,对上述算法做了实现和进一
步改进,主要是在结合基于词典的相同词对齐算法中找到一
系列锚点,然后根据锚点进行分割,然后再按照基于长度算
法进一步进行匹配。采用的测试文件内容包括:网站新闻类
〔经济、政治、法律、趣闻、学习、寓言故事等)、联合国会议记
录(政治、救助等)、政府报告(II T O、法律)等,还从新概念英
语中找了几篇文章。
句字对齐的实验效果如表2所示。
表2 实验结果
文件数100实际句字数5867
对齐句字数1112正确句字数1101
准确率0199召回率011876
F值0131
由以上结果可以看出,通过正反双向的算法在精确率上
取得了令人满意的结果,而这是以牺牲召回率为代价的。在
实际操作中,我们发现,特别是对一些诗歌、散文类的文章,
召回率是极低的,但令人可喜的是,即使是对于这些翻译方
式变化多样的文章,它的准确率也是值得信赖的。
4 结束语
本文提出了关于句子对齐的一种新的混合的对齐算法
的研究,应用,它使大规模的建库成为可能,为以后的机器辅
助翻译打下了坚实的基础。其在航天四创CAT软件在建库
过程中得到了应用,取得了不错的效果,证明了该方法是可
行的。该算法为了追求精确率,牺牲了召回率,但在建库过
程中由于对精确率的极其强调,因此这也是值得的,特别是
在网上这么多粗糙文本存在的前提下。当然,如果能进一步
提高召回率,并通过更大数据量的操作调节阈值,同时更紧
密结合基于词典的方法,效果应当会更好!
参考文献:
[1] W A G ALE,K W CHURCH.A Pr ogra m f or A ligning Sentences in
B ilingual Cor pora[J ].Computati onal L inguistics,1993,19(1):75-102.
[2] M Kay &K Roescheisen .Text -Translati on A lignment[J ].Com 2
putati onal L inguistics,1993,19(1):121-142.
[3] 刘昕,周明,朱胜火,黄昌宁.基于自动抽取词汇信息的双语句
子对齐[J ].计算机学报,1998,
21(8):51-158.
[4] 王斌,刘群.汉英双语库自动分段对齐研究[J ].软件学报,
2000,11(11):1547-1553.
[5] 常宝宝,詹卫东,柏晓静,吴云芳,张化瑞.服务于汉英机器翻
译的双语语料库和短语库建设[C ].第二届中日自然语言处理专家研讨会论文集,20021147-154.
[6] 翁富良,等.计算语言学导论[M ].北京:中国社会科学出版
社,1998.
[作者简介]
王占军(1982-),男(汉族),河北省邢台市人,硕
士生,研究方向:自然语言处理。
姚卫东(1964-),男(汉族),山西运城人,研究
员,研究方向:自然语言处理研究,数据挖掘。
(上接第235页)
图7 实例结果
6 结束语
符合Delaunay 准则的三角形具有很好的数学性质,非常适合在仿真中应用。因此要求封闭的中空面的三角形都是Delaunay 三角形。通过该方法法得出的封闭面均是Delaunay 的三角形。同时该算法简单,特别适用于带多孔洞的多边形剖分,孔洞越多剖分的效果越好。因此该方法能够很好的应用在各种面模型的切割仿真中。参考文献:
[1] V J D Tsai .Delaunay Triangulati ons in TI N Creati on:an Overvie w
and a L inear -ti m e A lgorithm [J ].I nt .J.of GI S .1993,7(6):501-524.
[2] 武晓波,王世新,肖春生.Delaunay 三角网的生成算法研究
[J ].测绘学报,1999,28(1):28-35.
[3] M I Sha mos and D Hoey .Cl osest -point Pr oblem s[C ].Pr oceed 2
ings of the 16th Annual Sy mposium on the Foundati ons of Computer Science,19751151-162.
[4] B A Le wis and J S Robins on .Triangulati on of Planar Regi ons with
App licati ons,The Computer Journal[J ].1978,21(4):324-332[5] P J Green and R Sibs on .Computing D irichlet Tessellati ons in the
Plane .The Computer Journal[J ].1978,21(2):l88-173.[6] 丁永祥,夏巨谌,王英,肖景容.任意多边形的Delaunay 三角剖
分[J ].计算机学报,1994,17(4):270-275.
[7] 秦绪佳,欧宗瑛,侯建华.医学图像三维重建模型的剖切与立
体视窗剪裁[J ].计算机辅助设计与图形学学报,2002,14(3):
275-279.
[8] 孙家广,杨长贵著.计算机图形学[M ].北京:清华大学出版
社,19951390-391.
[9] Donald Hearn,M Pauline Baker .计算机图形学[M ].北京:电
子工业出版社,20061353-356.
[10] 纪小刚,龚光容.三维重构中任意平面多边形轮廓的自适应
Delaunay 三角剖分[J ].计算机应用,2006,23(3):167-169.
[11] 吕庆礼,程建川.基于约束Delaunay 三角剖分进行数模建构
[J ].江苏交通科技,2003,2:41-44
[12] 蒲浩,宋占峰,詹振炎.一种快速的逐点插入算法构建DT M
[J ].铁路计算机应用,2001,10(9):27-30.
[13] 李水乡,陈斌,赵亮,刘曰武.快速Delaunay 逐点插入网格生
成算法[J ].北京大学学报(自然科学版),2007,43(3):302
-306.
[14] 陈向平,应遒宁.统一于N I P 的多边形三角剖分算法[J ].计
算机学报,1989,12(3):194-199.
[15] 李衷怡,赵新方.三角网格剖切算法的研究[J ].计算机与数
字工程,2007,35(3):4-4,32.
[16] 甄鑫,周凌宏,王卓宇,陈超敏.Delaunay 三角剖分在放射治疗
计划轮廓线重建中的应用[J ].仪器仪表学报,2007,28(8):
1518-1521.
[作者简介]
徐 敏(1983-),男(汉族),山东泰安市新泰人,
硕士研究生,主要研究方向:虚拟人体建模与手术仿真。
王 钰(1963-),男(汉族),山东省青岛市人,副
教授,硕导,主要研究方向:虚拟人体建模与手术仿真,计算机辅助协同设计。
于素平(1982-),女(汉族),山东威海市人,硕士研究生,主要研究
方向:虚拟人体建模与手术仿真。