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

开篇：润墨网以专业的文秘视角，为您筛选了一篇统计机器翻译基于赫夫曼编码的解码算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

[摘要]赫夫曼树编码是信息论中重要的数据编码方式。根据赫夫曼编码的算法构造最优二叉树，可以得到总长最短的二进制编码。本文首次依据赫夫曼编码的思想设计机器翻译中的解码算法，基本思想是：在栈解码的基础上，不再是在原有结点上扩展新的假设，而是合并原有的假设，最后构造一棵完整的二叉树。这种方法开辟了机器翻译解码的新途径，有望提高机器翻译解码的效率，节约存储空间。 [关键词]统计机器翻译；解码；赫夫曼编码；二叉树 [中图分类号]H059　[文献标识码]A　[文章编号]1671―511X(2011)06―0093-04

一、引言

解码(Decoding)是在统计机器翻译系统中与模型训练同等重要的模块。所谓解码，是指给定从语料中学习到的模型参数和待翻译的源语言句子，搜索使目标语言句子概率最大(或代价最小)的翻译结果的过程。主要的解码方法有栈解码、A*算法、贪心爬山算法和动态规划等。由于同一个源语言词语可能对应与不同的目标语言翻译，即使单个词语相同，词语的次序也有大量的组合方法，所以解码的全部搜索空间异常庞大，已被证明是一个NP完全问题。如果不引入优化方法，凭借目前计算机的速度和内存远不可能在有限时间和空间内完成整个解码过程。栈解码等主要解码方法并不是在全部空间上搜索，而是利用启发函数对搜索空间进行剪枝，在有限搜索空间中找到近似最优解。然而剪枝策略过早地舍弃了一些潜在的合理的翻译，Och等人的研究结果表明译文中近70％的错误都是来源于简化的解码算法“J。

赫夫曼编码算法是信息论中重要的数据编码理论。给定元素的权值，利用赫夫曼树可以快速地产生一种编码方案。本文将这种理论应用于机器翻译的解码，改变了以往在原有假设上不断增加新的词语的传统，首次通过合并构造翻译结果。

二、统计机器翻译研究概况

1949年，美国洛克菲勒基金会自然科学部门的负责人Warren Weaver发表了一份以《翻译》为题的备忘录，正式提出了机器翻译的问题，并首次提出使用统计技术实现自然语言的自动翻译。在这种翻译思想的指导下，1954年美国的乔治敦大学和IBM公司研制出了世界上第一个机器翻译系统。

上个世纪90年代以前，机器翻译的主流方法一直是传统的基于规则的翻译方法。规则以词汇、句法或语义转换为中心，通过双语词典确定原语的译词。由于自然语言的歧义性，规则方法生成的译文质量无法适应错综复杂的语言现象。规则系统需要由许多专家创建和维护，是一项十分琐碎而繁杂的工作。随着规则的规模不断扩大，新旧知识的发生冲突，修改时难免会牵一发而动全身，这些难题给系统的改进造成了极大的困难。人们逐渐认识到规则的局限性，终于在1990年，由IBM的Brown等人引入了噪声信道模型[3。]，实现了第一个基于大规模语料库的统计机器翻译系统。

在基于噪声信道模型的统计机器翻译中，翻译系统被看成是一个噪声信道，信道的输人对应于源语言句子，J一^，…，^，…，厂，信道的输出对应于目标语言句子sf―s，，…，¨…，g，。根据贝叶斯公式：

P(ef l爿)一―P(―d1)x万P刁(_f{一Id)

(1)

0、J1／

翻译过程就是根据语言模型和翻译模型，求解翻译概率最大的目标语言句子科，即

纠一argrna~IP(e{)×P(爿l口f)

(2)

这样，从源语言句子爿到目标语言句子ef的翻译过程被分解成三个基本问题：

(1)语言模型P(ef)的参数估计；