统计机器翻译基于赫夫曼编码的解码算法.doc

统计机器翻译基于赫夫曼编码的解码算法.doc统计机器翻译基于赫夫曼编码的解码算法
［摘要］赫夫曼树编码是信息论中重要的数据编 码方式。根据赫夫曼编码的算法构造最优二叉树，可 以得到总长最短的二进制编码。本文首次依据赫夫曼 编码的思想设计机器翻译中的解码算法，基本思想是: 在栈解码的基础上，不再是在原有结点上扩展新的假 设，而是合并原有的假设，最后构造一棵完整的二叉 树。这种方法开辟了机器翻译解码的新途径，有望提 高机器翻译解码的效率，节约存储空间。［关键词］统 计机器翻译；解码；赫夫曼编码；二叉树［中图分类 号］H059 ［文献标识码］A ［文章编号］1671- 511X(2011)06-0093-04
、引言
解码(Decoding)是在统计机器翻译系统中与模型 训练同等重要的模块。所谓解码，是指给定从语料中 学****到的模型参数和待翻译的源语言句子，搜索使目 标语言句子概率最大(或代价最小)的翻译结果的过程。
主要的解码方法有栈解码、A*算法、贪心爬山算法和 动态规划等。由于同一个源语言词语可能对应与不同
的目标语言翻译，即使单个词语相同，词语的次序也 有大量的组合方法，所以解码的全部搜索空间异常庞 大，已被证明是一个NP完全问题。如果不引入优化 方法，凭借目前计算机的速度和内存远不可能在有限 时间和空间内完成整个解码过程。栈解码等主要解码 方法并不是在全部空间上搜索，而是利用启发函数对 搜索空间进行剪枝，在有限搜索空间中找到近似最优 解。然而剪枝策略过早地舍弃了一些潜在的合理的翻 译，Och等人的研究结果表明译文中近70%的错误都 是来源于简化的解码算法“J。
赫夫曼编码算法是信息论中重要的数据编码理论。 给定元素的权值，利用赫夫曼树可以快速地产生一种 编码方案。本文将这种理论应用于机器翻译的解码， 改变了以往在原有假设上不断增加新的词语的传统， 首次通过合并构造翻译结果。
二、统计机器翻译研究概况
1949年，美国洛克菲勒基金会自然科学部门的负 责人Warren Weaver发表了一份以《翻译》为题的备 忘录，正式提出了机器翻译的问题，并首次提出使用 统计技术实现自然语言的自动翻译。在这种翻译思想 的指导下，1954年美国的乔治敦大学和IBM公司研制 出了世界上第一个机器翻译系统。
上个世纪90年代以前，机器翻译的主流方法一直 是传统的基于规则的翻译方法。规则以词汇、句法或 语义转换为中心，通过双语词典确定原语的译词。由 于自然语言的歧义性，规则方法生成的译文质量无法 适应错综复杂的语言