用于统计机器翻译的解码方法、统计机器翻译方法及装置

摘要

本申请公开了一种用于统计机器翻译的解码方法，同时公开了一种用于统计机器翻译的解码装置，以及一种统计机器翻译方法及相应装置。所述用于统计机器翻译的解码方法包括：根据源语言句子包含的词序列，初始化由对应各跨度词序列的节点组成的解码空间；采用如下方式拓展所述解码空间中的每个节点：从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中，直至所选翻译候选的数目不小于预设阈值K；从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于前N位的翻译候选，并构建所述源语言句子的翻译结果。采用本技术方案，可以加快解码过程、并缩减对内存的占用，实现轻量解码。

说明书

技术领域

本申请涉及机器翻译领域，具体涉及一种用于统计机器翻译的解码方法。本申请同时涉及一种用于统计机器翻译的解码装置、一种统计机器翻译方法、以及一种统计机器翻译装置。

背景技术

统计机器翻译是当今机器翻译界的主流技术，其中基于形式化句法的统计机器翻译得到了比较广泛的应用。统计机器翻译系统通常包含线上解码以及线下训练模块两大部分，请参考图1示出的统计机器翻译的架构图。

其中，线下训练部分，包括调序模型、翻译模型、语言模型，这些模块构成了机器翻译系统的基础。线上解码部分，包括前处理、解码器、后处理，其中解码器构成了机器翻译系统最为核心的模块。解码器接收待翻译的句子，经过整合翻译模型、调序模型、语言模型，得到对应的翻译结果。解码的过程，其实就是在一个句子长度的指数级空间中进行搜索最优的翻译候选的过程。为了能够满足线上服务的实时性要求，解码器通常会采用各种剪枝方法，将指数级的空间缩减到可以接受的范围，以求最快得到翻译结果。剪枝方法的好坏直接影响了解码器的速度以及翻译质量。

下面以基于括号转录语法(BTG)的机器翻译系统为例，对目前统计机器翻译的解码及剪枝过程作简要说明。其中，解码算法多采用CYK算法，请参考图2给出的基于CYK算法的解码空间的示意图，解码的策略采用自底向上逐渐拓展的方式，首先生成第1行，然后利用已经生成的内容拓展生成第2行，直到(1,5)节点拓展完毕。而解码过程中的剪枝则多采用针对每种组合方式进行局部剪枝再进行全局筛选的方式，仍以图2为例，对于(1,3)这个节点，可以由两种组合方式(1,1)(2,2)和(1,2)(3,1)生成，首先，针对第一种组合方式(1,1)(2,2)，选择其中得分最高的K个候选，然后针对第二种组合方式(1,2)(3,1)，选择其中得分最高的K个候选。最后，(1,3)这个节点对这2K个候选进行全局排序，选择其中得分最高的K个作为自己的翻译候选结果。

在实际应用中，基于上述剪枝方式的解码方法，在句子长度比较小的时候，通常可以表现出令人满意的速度和性能。然而，随着句子长度不断增大，由于解码过程生成的翻译候选数目呈现暴增式增长，而生成每一个翻译候选都需要耗费时间以及占用内存，因此整个翻译过程耗费的时间和占用的内存也相应呈现暴增式增长，特别是句长超过40以后，翻译时间出现指数级增长，效率低下，难以满足线上服务的实时性要求。

发明内容

本申请实施例提供一种用于统计机器翻译的解码方法和装置，以解决现有基于局部剪枝的解码方法随着句子增长性能大幅降低、并且耗用大量内存的问题。本申请实施例还提供一种统计机器翻译方法和装置。

本申请提供一种用于统计机器翻译的解码方法，包括：

根据源语言句子包含的词序列，初始化由对应各跨度词序列的节点组成的解码空间；

拓展所述解码空间中的每个节点，以生成每个节点的翻译结果集合；

从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于前N位的翻译候选，并构建所述源语言句子的翻译结果；

其中，所述拓展所述解码空间中的每个节点包括：从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中，直至所选翻译候选的数目不小于预设阈值K；所述翻译候选的翻译分数是根据预先生成的用于统计机器翻译的模型计算得到的。

可选的，所述从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中，直至所选翻译候选的数目不小于预设阈值K，包括：

构建根据其他节点生成当前节点的各种组合方式；

将每一种组合方式下的优选子翻译组合对应的翻译候选添加到优先级队列中，所述优选子翻译组合是指生成所述组合方式的各节点在其翻译结果集合中处于高序位的子翻译候选的组合；

从所述优先级队列中选取翻译分数处于高序位的翻译候选，添加到当前节点按照翻译分数排序的翻译结果集合中；

选择所选翻译候选对应的子翻译组合的邻居，并将所述邻居对应的翻译候选添加到优先级队列中；

判断当前节点从优先级队列中选取的翻译候选的数目是否小于K，若是，转到所述从所述优先级队列中选取翻译分数处于高序位的翻译候选的步骤执行。

可选的，所述子翻译组合的邻居是以下成员的组合：子翻译组合中的一个子翻译候选，在另一子翻译候选所在翻译结果集合中与所述另一子翻译候选相邻且处于低序位的子翻译候选。

可选的，所述初始化由对应各跨度词序列的节点组成的解码空间，包括：

构建由对应各跨度词序列的节点组成的解码空间；

根据翻译模型生成所述源语言句子所包含各短语的翻译候选，并将所述各短语的翻译候选添加到所述解码空间中相应节点的翻译结果集合中。

可选的，处理所述解码空间中的每个节点时，在判断出针对当前节点所选翻译候选的数目不小于预设阈值K之后，在处理下一个节点之前，执行下述操作：

将处于当前节点翻译结果集合中的翻译候选按照翻译分数从高到低排序；

选择序位处于高位的K个翻译候选作为当前节点的翻译结果集合。

可选的，在所述从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选之后，执行下述操作：

记录所述翻译候选与生成所述翻译候选的各节点中的相应子翻译候选的对应关系；

所述构建所述源语言句子的翻译结果包括：根据已记录的所述对应关系逐层查找生成所述翻译候选的各层子翻译候选，并依据找到的子翻译候选生成所述源语言句子的翻译结果。

可选的，所述预先生成的用于统计机器翻译的模型包括翻译模型、调序模型、和语言模型。

可选的，所述调序模型包括：最大熵调序模型。

相应的，本申请还提供一种用于统计机器翻译的解码装置，包括：

初始化单元，用于根据源语言句子包含的词序列，初始化由对应各跨度词序列的节点组成的解码空间；

拓展解码单元，用于拓展所述解码空间中的每个节点，以生成每个节点的翻译结果集合；

翻译结果构建单元，用于从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于前N位的翻译候选，并反向构建所述源语言句子的翻译结果；

其中，所述拓展解码单元包括：

解码控制子单元，用于选择所述解码空间中的每个节点，并针对每个节点触发节点拓展子单元工作；

节点拓展子单元，用于从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中，直至所选翻译候选的数目不小于预设阈值K。

可选的，所述节点拓展子单元，包括：

组合方式构建子单元，用于构建根据其他节点生成当前节点的各种组合方式；

优先级队列初始化子单元，用于将每一种组合方式下的优选子翻译组合对应的翻译候选添加到优先级队列中，所述优选子翻译组合是指生成所述组合方式的各节点在其翻译结果集合中处于高序位的子翻译候选的组合；

翻译候选选取子单元，用于从所述优先级队列中选取翻译分数处于高序位的翻译候选，添加到当前节点按照翻译分数排序的翻译结果集合中；

邻居添加子单元，用于选择所选翻译候选对应的子翻译组合的邻居，并将所述邻居对应的翻译候选添加到优先级队列中；

拓展判断子单元，用于判断当前节点从优先级队列中选取的翻译候选的数目是否小于K，若是，触发所述翻译候选选取子单元工作。

可选的，所述初始化单元包括：

解码空间构建子单元，用于构建由对应各跨度词序列的节点组成的解码空间；

短语翻译候选初始化子单元，用于根据翻译模型生成所述源语言句子所包含各短语的翻译候选，并将所述各短语的翻译候选添加到所述解码空间中相应节点的翻译结果集合中。

可选的，所述节点拓展子单元包括：

选择子单元，用于从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中；

数目判断子单元，用于判断所述翻译候选的数目是否不小于预设阈值K，并在小于时触发选择子单元工作；

所述节点拓展子单元还包括：

翻译候选排序子单元，用于在所述数目判断子单元的输出为是时，将处于当前节点翻译结果集合中的翻译候选按照翻译分数从高到低排序；

翻译候选筛选子单元，用于从所述翻译候选排序子单元排好序的翻译候选中，选择序位处于高位的K个翻译候选作为当前节点的翻译结果集合。

可选的，所述节点拓展子单元包括：

选择子单元，用于从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中；

数目判断子单元，用于判断所述翻译候选的数目是否不小于预设阈值K，并在小于时触发选择子单元工作；

所述节点拓展子单元还包括：

对应关系记录子单元，用于在所述选择子单元选取翻译分数处于高序位的翻译候选后，记录所述翻译候选与生成所述翻译候选的各节点中的相应子翻译候选的对应关系；

所述翻译结果构建单元具体用于，从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于前N位的翻译候选，根据已记录的所述对应关系逐层查找生成所述翻译候选的各层子翻译候选，并依据找到的子翻译候选生成所述源语言句子的翻译结果。

此外，本申请还提供一种统计机器翻译方法，包括：

训练用于统计机器翻译的翻译模型、调序模型和语言模型；

对待翻译原文进行预处理，获取由词序列组成的源语言句子；

利用所述翻译模型、调序模型和语言模型，采用如权利要求1所述的解码方法，对所述源语言句子进行解码，获得对应于源语言句子的目标语言句子；

对所述目标语言句子进行后处理，获取对应于待翻译原文的目标译文。

可选的，所述训练用于统计机器翻译的翻译模型、调序模型和语言模型，采用如下方式实现：

利用针对源语言和目标语言的双语语料库训练翻译模型和调序模型，利用针对目标语言的单语语料库训练语言模型。

可选的，所述对待翻译原文进行预处理，获取由词序列组成的源语言句子包括：

通过分句操作，将待翻译原文切割为独立的源语言句子；

通过分词操作，将所述源语言句子转换为由词组成的序列。

可选的，所述对所述目标语言句子进行后处理，获取对应于待翻译原文的目标译文，包括：

将所述目标语言句子组合为对应于待翻译原文的目标译文。

相应的，本申请还提供一种统计机器翻译装置，包括：

模型训练单元，用于训练用于统计机器翻译的翻译模型、调序模型和语言模型；

预处理单元，用于对待翻译原文进行预处理，获取由词序列组成的源语言句子；

解码单元，用于利用所述翻译模型、调序模型和语言模型，采用如权利要求10所述的用于统计机器翻译的解码装置，对所述源语言句子进行解码，获得对应于源语言句子的目标语言句子；

后处理单元，用于对所述目标语言句子进行后处理，获取对应于待翻译原文的目标译文。

可选的，所述模型训练单元具体用于，利用针对源语言和目标语言的双语语料库训练翻译模型和调序模型，利用针对目标语言的单语语料库训练语言模型。

可选的，所述预处理单元包括：

分句子单元，用于通过分句操作将待翻译原文切割为独立的源语言句子；

分词子单元，用于通过分词操作将所述源语言句子转换为由词组成的序列。

可选的，所述后处理单元具体用于，将所述目标语言句子组合为对应于待翻译原文的目标译文。

与现有技术相比，本申请具有以下优点：

本申请提供的用于统计机器翻译的解码方法，首先根据源语言句子包含的词序列，初始化由对应各跨度词序列的节点组成的解码空间；然后拓展所述解码空间中的每个节点：从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中，直至所选翻译候选的数目不小于预设阈值K；最后从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于前N位的翻译候选，并构建所述源语言句子的翻译结果。采用上述解码方法，由于在拓展每个节点的时候，没有采用分别在每一组合方式内部进行剪枝的方式，而是同时考量各种可能的组合方式，并从所有组合方式中选择翻译分数处于高序位的翻译候选，即采用的是全局的剪枝方式，从而可以减少解码过程中生成的翻译候选的数目，最大限度加快解码过程、并缩减对内存的占用，实现了轻量解码过程，特别是在句子长度增长到较大规模时，效果尤为明显，能够实现翻译速度的大规模提升。

附图说明

图1是统计机器翻译的架构图；

图2是基于CYK算法的解码空间的示意图；

图3是本申请提供的一种用于统计机器翻译的解码方法的实施例的流程图；

图4是本申请实施例提供的拓展每个节点的处理流程图；

图5是本申请实施例提供的翻译候选对应的子翻译组合的邻居示意图；

图6是本申请提供的一种用于统计机器翻译的解码装置的实施例的示意图；

图7是本申请提供的一种统计机器翻译方法的实施例的流程图；

图8是本申请提供的一种统计机器翻译装置的实施例的示意图。

具体实施方式

在下面的描述中阐述了很多具体细节以便于充分理解本申请。但是，本申请能够以很多不同于在此描述的其它方式来实施，本领域技术人员可以在不违背本申请内涵的情况下做类似推广，因此，本申请不受下面公开的具体实施的限制。

在本申请中，分别提供了一种用于统计机器翻译的解码方法、一种用于统计机器翻译的解码装置、一种统计机器翻译方法，以及一种统计机器翻译装置，在下面的实施例中逐一进行详细说明。为了便于理解本申请提供的技术方案，在对实施例进行详细描述之前，先对本申请的技术方案作简要说明。

本申请所述的解码空间，通常由对应于各跨度词序列的节点组成，而跨度大于1的词序列通常可以由更小跨度的词序列组合而成，因此也称为某个节点可以由其他节点组合生成。在解码时通常对解码空间中各节点进行如下处理：根据能够组合生成本节点的其他节点的翻译结果集合、生成本节点的翻译结果集合，并最终从覆盖整个源语言句子的节点的翻译结果集合中选择最优翻译。

上述对节点的处理过程也称为对节点的拓展过程，拓展生成的翻译结果集合中通常包含多个翻译候选，每个翻译候选都有与之对应的翻译分数，而解码的过程就是搜索覆盖整个源语言句子的、翻译分数最高的翻译候选的过程。在拓展某个节点时，由于根据其他节点翻译结果集合中的翻译候选生成本节点翻译候选的可能性通常很多，因此需要采用适当的剪枝方式，以提高解码效率。

传统的解码方法，在拓展每个节点时采用的是局部剪枝方法，即，针对生成当前节点的每种组合方式先分别选择翻译分数处于高序位的K个翻译候选，然后再对各种组合方式的全部翻译候选进行全局排序，并从中选择处于高序位的K个翻译候选。

而本申请的技术方案，提出了一种融合全局剪枝方法的解码方法，即在拓展每个节点时，让生成该节点的各种组合方式的翻译候选一起参与竞争，并从中选择翻译分数处于高序位的K个翻译候选，从而减少解码过程中生成的翻译候选的数目，实现轻量解码。

本申请提供的上述解码方法可以应用于统计机器翻译领域，特别适用于基于形式化句法的统计机器翻译过程，例如：基于括号转录语法的统计机器翻译、或者基于层次化短语的统计机器翻译。在下面的实施例中以基于括号转录语法的统计机器翻译为例进行说明。

在实际应用中，只要是采用上述节点(代表不同跨度词序列)拓展方式的统计机器翻译过程都可以采用本申请提供的技术方案，为了便于理解，本实施例基于CYK算法描述本申请提供的解码方法，并采用自底向上的方式拓展该空间的各个节点。下面对本申请的技术方案进行详细说明。

请参考图3，其为本申请的一种用于统计机器翻译的解码方法的实施例的流程图。所述方法包括如下步骤：

步骤301、根据源语言句子包含的词序列，初始化由对应各跨度词序列的节点组成的解码空间。

待翻译的源语言句子通常会被分成由若干词组成的词序列，本步骤根据输入的源语言句子包含的词序列，初始化解码空间，所述解码空间包含多个节点，每个节点对应不同跨度的词序列。

本实施例初始化基于CYK算法的二维解码空间。在具体实施时，可以包含以下两个子步骤：

步骤301-1：构建基于CYK算法的二维解码空间。

所述CYK算法是一个用来判定任意给定的字符串是否属于一个上下文无关文法的算法，在统计机器翻译领域中通常使用该算法进行自底向上的解码过程。请参考图2，其为包含5个词的源语言句子的CYK解码空间的示意图。所述解码空间中的每个节点对应于源语言句子中某一跨度(span)上的词序列，横坐标代表该跨度左侧第一个词的位置，纵坐标代表该跨度包含的词个数，例如：(1，3)节点表示从第一个词开始，跨度为3的词序列，而(1,5)节点则表示从第一个词开始，跨度为5的词序列，即：(1,5)节点是覆盖整个源语言句子的顶部节点。

在具体实施时，该解码空间可以用二维数组实现，即：解码空间中的每个节点与二维数组中的一个成员相对应，与该节点对应的信息，例如对应于该节点的翻译结果集合等信息都存储在二维数组中的对应成员中，从而可以高效、有序地执行自底向上的解码过程。

步骤301-2：根据翻译模型生成所述源语言句子所包含各短语的翻译候选，并将所述各短语的翻译候选添加到所述二维解码空间中相应节点的翻译结果集合中。

源语言句子通常是由词序列组成的，而覆盖不同跨度的词序列可以组成短语，所述短语可以是语言学意义上的短语，也可以是不包含任何语言学知识的形式化短语。本步骤对于所述源语言句子中的每个可能的短语，查找根据翻译模型得到的双语短语表，对于找到的短语，将与其对应的翻译候选添加到所述二维解码空间中相应节点的翻译结果集合中。

同时，还可以根据预先训练的翻译模型和语言模型计算每个翻译候选的翻译分数，具体可以依据翻译模型获取两个方向的短语翻译概率、两个方向的词汇化概率等，依据语言模型获取翻译候选的语言模型概率，然后根据上述概率计算翻译候选的翻译分数。此外，还可以同时兼顾短语惩罚、单词惩罚等其他因素，共同计算所述翻译候选的翻译分数。

在具体实施时，上述根据多个模型计算翻译分数的过程，可以采用对数线性模型(log-linear model)实现。采用对数线性模型，可以将上述多个用于计算翻译分数的模型看成一系列特征函数，这样不仅可以方便地为各个特征函数设定相应的权重系数(不同的权重系数可以反映不同特征函数在翻译分数计算过程中的重要程度)，有助于提高翻译质量，而且可以以特征函数的形式添加其他影响翻译质量的模型，即可以方便灵活地添加其他可供考量的因素，为进一步提高翻译质量提供便捷途径。在后续步骤302中针对每个节点计算翻译候选的翻译分数时，也可以采用对数线性模型实现，在此一并说明，后续不再赘述。

对于二维解码空间中的每个节点来说，可能存在与之对应的短语，也可能不存在对应的短语。对于存在对应短语的情况，其翻译候选的数目通常也是不确定的，例如：5个、10个或者30个，在具体实施时，可以设定与短语对应的翻译候选的最大数目，例如10个，当某短语的翻译候选数目大于所述最大数目时，可以从中选择翻译分数处于高序位的所述最大数目的翻译候选。

步骤302、拓展所述解码空间中的每个节点，以生成每个节点的翻译结果集合。

本步骤拓展所述解码空间中的每个节点，即针对每个节点执行下述处理：根据能够组合生成本节点的其他节点的翻译结果集合、生成本节点翻译结果集合，最终得到覆盖整个源语言句子的节点的翻译结果集合，则整个拓展过程完毕。

如果采用基于CYK算法的解码方式，由于CYK算法是一个自底向上的广度优先的遍历过程，通常首先拓展解码空间中第一行的各个节点；然后拓展解码空间中第二行的各个节点，......，以此类推，直至拓展到解码空间的顶部节点，自底向上的拓展过程完毕。由于采用自底向上的拓展方式，每当拓展上层节点时，下层节点的翻译结果集合已经生成，因此上层节点可以直接利用生成该节点的各组合方式对应的下层节点(也称为子节点)的翻译结果集合，生成自己的翻译结果集合，从而实现自底向上的解码过程。

CYK解码空间中的节点通常可以由子节点的多种组合方式生成，而本申请提供的技术方案在拓展每个节点的时候，没有采用分别在每一种组合方式内部进行局部剪枝、再进行全局重排筛选的方式，而是采用了基于全局的剪枝方式(也称为基于全局的立方图剪枝方式)：综合考量各种可能的组合方式，并从所有组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中，直至所选翻译候选的数目不小于预设阈值K。

为了实现融合上述剪枝方式的高效解码过程，在具体实施时，可以采用优先级队列实现每个节点的拓展过程，具体包括步骤302-1至步骤302-5，下面结合图4对每个节点的拓展过程作进一步说明。

步骤302-1、构建根据其他节点生成当前节点的各种组合方式。

由于某一跨度的词序列通常可以采用多种方式分割为子词序列，而将各子词序列的翻译候选通过特定方式(例如保序或者逆序)组合起来，就可以得到原词序列的翻译候选。基于上述原理，所述CYK解码空间中某节点的翻译候选通常可以由不同子节点的翻译候选通过不同的组合方式生成，在本实施例中简称为某节点由不同组合方式生成。

仍以图2所示的包含5个词序列的解码空间为例，其中(1,3)节点可以通过以下两种方式组合生成：(1,1)(2,2)，(1,2)(3,1)；(1,5)节点可以通过以下四种方式组合生成：(1,1)(2,4)，(1,2)(3,3)，(1,3)(4,2)，(1,4)(5,1)。本步骤采用上述方式构建可以生成当前节点的各种可能的组合方式。

步骤302-2、将每一种组合方式下的优选子翻译组合对应的翻译候选添加到优先级队列中。

拓展当前节点时，每种组合方式对应的其他节点的翻译结果集合通常都已经生成(如果尚未生成则可以先生成所述其他节点的翻译结果集合)，每个翻译结果集合中都包含了按照翻译分数从高到低排序的子翻译候选，此处之所以称为子翻译候选，是相对于当前节点的翻译候选而言的。

所述优选子翻译组合是指生成所述组合方式的各节点在其翻译结果集合中处于高序位的子翻译候选的组合，例如处于第一位的子翻译候选的组合。本步骤将优选子翻译组合对应的翻译候选添加到优先级队列中。

为了便于理解，此处用基于CYK解码的具体例子进行说明，以图2中的(1,3)节点为例，生成该节点的两种组合方式分别为(1,1)(2,2)和(1,2)(3,1)，其中子节点(1,1)的翻译结果集合中包含按照翻译分数从高到低排序的K个子翻译候选，分别是A₁、A₂、A₃、A₄......A_k，同理，子节点(2,2)、(1,2)、(3,1)的翻译结果集合中也各自包含K个排好序的子翻译候选，如表一所示：

表一、子节点的翻译结果集合中包含的子翻译候选示例

对于第一种组合方式来说，在子节点(1,1)的翻译结果集合中处于第一位的子翻译候选为A₁，在子节点(2,2)的翻译结果集合中处于第一位的子翻译候选为B₁，那么第一种组合方式的优选子翻译组合可以为A₁和B₁的组合。

考虑到源语言和目标语言的语序可能存在差异，因此在翻译为目标语言时，优选子翻译组合中的两个子翻译候选存在调整先后顺序的可能性，因此优选子翻译组合对应的翻译候选通常包括两个：A₁B₁和B₁A₁，可以将A₁B₁和B₁A₁添加到优先级队列中。

同样的道理，对于第二种组合方式来说，优选子翻译组合可以为C₁和D₁的组合，该组合对应的翻译候选也包括两个：C₁D₁和D₁C₁，同样也可以将C₁D₁和D₁C₁添加到优先级队列中。

由于A₁和B₁以及C₁和D₁都是在各自翻译结果集合中处于高序位的子翻译候选，因此它们彼此之间的组合将成为当前节点的翻译候选的有力竞争者，所以将对应的翻译候选添加到优先级队列中，也就是说将两种组合方式中的有力竞争者都添加到优先级队列中进行竞争。

步骤302-3、从所述优先级队列中选取翻译分数处于高序位的翻译候选，添加到当前节点按照翻译分数排序的翻译结果集合中。

在向优先级队列中添加翻译候选时，可以计算被添加的翻译候选的翻译分数，所述翻译分数可以代表当前节点对应的词序列被翻译为所述翻译候选对应的目标词序列的概率大小，通常翻译分数越高，代表所述概率越大，而解码的过程就是寻找得分处于高序位的翻译候选的过程。在具体实施时，该分数通常利用指数对数形式进行计算，添加到优先级队列中的翻译候选的翻译分数可以采用以下三个分数求和得到：

1)组成翻译候选的两个子翻译候选的翻译分数之和；

2)重排序分数；

3)由于子翻译候选组合(也称为合并)产生的语言模型的增量。

其中，第一项中涉及的子翻译候选的翻译分数，通常在拓展所述子翻译候选对应的节点时已经得到，只需要将两个子翻译候选的翻译分数相加即可；第二项分数则可以利用预先训练好的重排序模型计算得到，优选的，可以采用基于最大熵的重排序模型，通过引入不同的特征以及训练相应的权重参数，可以使得重排序模型计算得到的分数更为准确；第三项分数可以利用预先训练好的语言模型进行计算，例如，可以采用N-gram语言模型，N的值可以设置为3。

通过上述方式，每次向优先级队列中添加翻译候选时，都可以为所述翻译候选计算相应的翻译分数。本步骤则从所述优先级队列中选择翻译分数处于高序位的翻译候选，例如：处于第一位的翻译候选，添加到当前节点的翻译结果集合中，所述翻译结果集合是按照其中翻译候选的翻译分数从高到低排序的。具体实施时，可以在每次向翻译结果集合中添加翻译候选时，就按照翻译分数的高低进行排序，也可以在从优先级队列中选出K个翻译候选后，统一对翻译结果集合中的翻译候选进行排序。

需要说明的是，从优先级队列中选取分数位于高序位的翻译候选添加到翻译结果集合时，可以携带所述翻译候选对应的翻译分数(后续拓展其他节点时可能会利用该信息)，而且由于所述翻译候选已经竞争胜出，因此可以从所述优先级队列中将其删除，在具体实施时可以通过将所述翻译候选出队列的处理过程来实现。

步骤302-4、选择所选翻译候选对应的子翻译组合的邻居，并将所述邻居对应的翻译候选添加到优先级队列中。

在上述步骤302-3中，从优先级队列中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中。考虑到所选翻译候选的翻译分数是比较高的，那么与其对应的子翻译组合的邻居对应的翻译候选的翻译分数通常也会比较高，也是进入本节点的翻译结果集合的有力竞争者，因此本步骤将所述邻居对应的翻译候选添加到优先级队列中。

所述翻译候选对应的子翻译组合的邻居，是以下两个成员的组合：

1)子翻译组合中的一个子翻译候选；

2)在另一子翻译候选所在翻译结果集合中与所述另一子翻译候选相邻且处于低序位的子翻译候选。

此处仍沿用上述拓展(1,3)节点的具体例子进行说明，如果步骤302-3从优先级队列中选择翻译分数处于高序位(例如第一位)的翻译候选为A₁B₁，该翻译候选对应的子翻译组合为A₁和B₁的组合，该组合有两个邻居，其中一个邻居为子翻译候选A₁与B₂的组合，其中B₂是B₁所在翻译结果集合中与B₁相邻且处于低序位的子翻译候选；另一个邻居为子翻译候选A₂与B₁的组合，其中A₂是A₁所在翻译结果集合中与A₁相邻且处于低序位的子翻译候选。

为了更形象地描述邻居的选取方式，请参见图5，图中的黑色方框表示步骤302-3所选的翻译候选对应的子翻译组合A₁和B₁，灰色方框代表该子翻译组合的两个邻居：A₁与B₂的组合、以及A₂与B₁的组合。同样的道理，如果后续从优先级队列中选出的翻译候选对应的子翻译组合为A₁和B₂，那么图中用斜线填充的两个方框则代表该子翻译组合的两个邻居，即：A₁和B₃，以及A₂和B₂。

本步骤将所选邻居对应的翻译候选添加到优先级队列中。仍沿用上述具体例子，如果步骤302-3从优先级队列中选择的翻译候选为A₁B₁，对于由A₁与B₂组合而成的邻居，可以将保序的A₁B₂、以及逆序的B₂A₁这两个翻译候选添加到优先级队列中；对于由A₂与B₁组合而成的邻居，可以将保序的A₂B₁、以及逆序的B₁A₂这两个翻译候选添加到优先级队列中。同样的道理，如果步骤302-3从优先级队列中选取的翻译候选为C₁D₁，那么本步骤可以将翻译候选C₁D₂、D₂C₁、C₂D₁和D₁C₂添加到优先级队列中。

由此可见，步骤302-3从优先级队列中选择一个翻译候选添加到翻译结果集合中，而本步骤则根据该翻译候选向优先级队列中加入4个新的翻译候选进行竞争。

通过上述从优先级队列中选取翻译候选出队列、以及向优先级队列中加入新翻译候选的队列操作过程可以看出，本实施例在拓展节点的时候，并不是局限于在每种组合方式内部选择翻译分数处于高序位的翻译候选，而是同时观察所有组合方式下具有竞争力的翻译候选(即：翻译分数处于高序位的翻译候选)，并通过优先级队列维持有竞争力的翻译候选的集合。也就是说，对于一个节点来说，各组合方式之间并不是完全隔离的，每一种组合方式的翻译候选都要和其他所有组合方式的翻译候选进行竞争，从而减少了为每个节点生成翻译候选的数目，实现轻量解码过程。

步骤302-5、判断当前节点从优先级队列中选取的翻译候选的数目是否小于K，若是，执行步骤302-3，若否，本节点拓展完毕。

解码过程中的剪枝操作会将部分翻译候选剪除，由于语言的复杂性以及各模型自身的局限性，不排除可能存在将正确翻译候选剪除的可能性，为了尽量降低这种可能性，解码过程通常会为每个节点都生成K个最优的翻译候选，从而尽量保证正确的翻译候选能够得以保留。考虑到采用过大的K值往往会影响解码性能，因此在实际应用中，可以兼顾生成翻译结果的正确性和效率两个方面，设置适当的K值，例如可以设置为20、50甚至100都是可以的。

本步骤判断从优先级队列中生成的翻译候选的数目是否达到K值，若未达到，则执行步骤302-3继续从优先级队列中选取翻译分数处于高序位的翻译候选，否则本节点拓展完毕。

为了保证本技术方案的高效执行，为每个节点生成的翻译结果集合通常是按照翻译候选的翻译分数从高到低排序的，如果在拓展节点的过程中、向翻译结果集合中加入翻译候选时没有按照上述要求进行排序，那么可以在本步骤判断出本节点拓展完毕时，对翻译结果集合中的翻译候选进行排序。

如果在步骤301进行解码空间的初始化时，在短语表中找到了与当前节点对应的短语及其翻译候选，并将翻译候选添加到该节点的翻译结果集合中，那么当该节点拓展完毕时，可以对翻译结果集合中的翻译候选，包括：初始化时添加的翻译候选、以及从优先级队列中竞争胜出的K个翻译候选按照翻译分数从高到低进行全局排序，并从中选择处于高序位的K个翻译候选作为当前节点的翻译结果集合。

需要说明的是，本实施例描述的节点拓展过程，采用了基于优先级队列的实施方式，在其他实施方式中，也可以采用其他数据结构组织参与竞争的翻译候选，只要在拓展每个节点时采用全局的剪枝方式，综合考量各种组合方式并选取翻译分数处于高序位的翻译候选，就同样可以实现本申请的技术方案，同样在本申请的保护范围之内。

步骤303、从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于前N位的翻译候选，并构建所述源语言句子的翻译结果。

步骤302完成对解码空间中每个节点的拓展后，本步骤构建所述源语言句子的翻译结果。

在具体实施时，在步骤302拓展每个节点时，在从根据其他节点生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选(例如，从优先级队列中选取了所述翻译候选)之后，可以记录所述翻译候选与生成所述翻译候选的各节点中的相应子翻译候选的对应关系，例如，可以为所述翻译候选定义指针，每个指针分别指向生成所述翻译候选的不同子翻译候选，那么本步骤就可以根据已记录的对应关系，从覆盖整个源语言句子的节点出发，构建最终的翻译结果。

对于基于CYK算法的解码过程来说，本步骤可以从解码空间的顶部节点出发，先从翻译结果集合中选择翻译分数处于前N位的翻译候选，然后针对每个翻译候选采用如下方式反向构建对应的翻译结果：根据已记录的所述对应关系自顶向下查找生成当前翻译候选的两个子翻译候选，然后再分别继续查找生成每个子翻译候选的子翻译候选，......，依次类推，直至找到的子翻译候选是具体的目标语言短语，然后用找到的所述子翻译候选构建生成所述源语言句子的翻译结果，即：目标语言句子。

具体实施时，从线上应用的角度出发，可以从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于第一位(即，N＝1)的翻译候选，即翻译分数最高的翻译候选，然后通过上述方式构建所述源语言句子的翻译结果，得到最优的目标译文；从进一步优化统计机器翻译过程的角度出发，也可以从所述顶部节点的翻译结果集合中选择N个(N大于或者等于2)翻译分数靠前的翻译候选，然后通过上述方式构建所述源语言句子的N个翻译结果，即通常所述的N-best译文列表，所述N-best译文列表可以用于进行统计机器翻译系统的最小错误率训练。

至此，对本申请提供的用于统计机器翻译的解码方法的实施例进行了详细描述。下面对本申请提供的解码方法与传统采用局部剪枝的解码方法的性能进行分析。为了便于比较，参与分析的两种解码方法都是基于CYK算法的。

传统的采用局部剪枝的CYK解码方法，其局部性体现在，每一种可能的组合方式在搜索最优翻译候选时，只能看到当前自己局部的搜索空间，而看不到其他可能组合方式的搜索空间。以句长为N的源语言句子为例，在拓展CYK算法最顶端的节点时，总共有N-1种组合方式，每一种组合方式都会生成K个翻译候选，因此为了拓展生成该节点，须要生成(N-1)*K个翻译候选，同理对于CYK解码空间中的每一个节点都要生成相应数目的翻译候选。将CYK解码空间中所有节点的翻译候选数目进行累加，得到解码过程中生成的翻译候选总数目Number1，如公式1所示：

------公式1

而本申请提供的用于统计机器翻译的解码方法，在拓展CYK解码空间中的每个节点时，为了尽快得到最优的K个翻译候选，采用了全局的立方图剪枝方法，其全局性体现在拓展每个节点时，同时观察所有组合方式下的最优翻译候选，每一种组合方式的翻译候选都要和其他所有组合方式的候选进行竞争，组合方式之间能互相看到并且互相竞争。基于上述机制，在解码过程中生成的翻译候选总数目Number2如公式2所示：

------公式2

在上述公式1以及公式2中，M是常量，N代表句长，K代表为每一个节点生成的翻译候选的数目。相对于公式1而言，公式2生成的翻译候选数目大大降低了。以N＝15，K＝20，M＝10为例，Number1＝22970，Number2＝4770。由此可见，本申请提供的融合了基于全局剪枝方式的解码方法，比基于局部剪枝方式的传统解码方法高效得多。

综上所述，本申请提供的用于统计机器翻译的解码方法，由于在拓展每个节点的时候，没有采用分别在每一组合方式内部进行剪枝的方式，而是同时考量各种可能的组合方式，并从所有组合方式中选择翻译分数处于高序位的翻译候选，即采用的是全局的剪枝方式，从而可以减少解码过程中生成的翻译候选的数目，最大限度加快解码过程、并缩减对内存的占用，实现了轻量解码过程，特别是在句子长度增长到较大规模时，效果尤为明显，能够实现翻译速度的大规模提升。

在上述的实施例中，提供了一种用于统计机器翻译的解码方法，与之相对应的，本申请还提供一种用于统计机器翻译的解码装置。请参看图6，其为本申请的一种用于统计机器翻译的解码装置的实施例示意图。由于装置实施例基本相似于方法实施例，所以描述得比较简单，相关之处参见方法实施例的部分说明即可。下述描述的装置实施例仅仅是示意性的。

本实施例的一种用于统计机器翻译的解码装置，包括：初始化单元601，用于根据源语言句子包含的词序列，初始化由对应各跨度词序列的节点组成的解码空间；拓展解码单元602，用于拓展所述解码空间中的每个节点，以生成每个节点的翻译结果集合；翻译结果构建单元603，用于从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于前N位的翻译候选，并反向构建所述源语言句子的翻译结果；

其中，所述拓展解码单元包括：

解码控制子单元，用于选择所述解码空间中的每个节点，并针对每个节点触发节点拓展子单元工作；

节点拓展子单元，用于从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中，直至所选翻译候选的数目不小于预设阈值K。

可选的，所述节点拓展子单元，包括：

组合方式构建子单元，用于构建根据其他节点生成当前节点的各种组合方式；

优先级队列初始化子单元，用于将每一种组合方式下的优选子翻译组合对应的翻译候选添加到优先级队列中，所述优选子翻译组合是指生成所述组合方式的各节点在其翻译结果集合中处于高序位的子翻译候选的组合；

翻译候选选取子单元，用于从所述优先级队列中选取翻译分数处于高序位的翻译候选，添加到当前节点按照翻译分数排序的翻译结果集合中；

邻居添加子单元，用于选择所选翻译候选对应的子翻译组合的邻居，并将所述邻居对应的翻译候选添加到优先级队列中；

拓展判断子单元，用于判断当前节点从优先级队列中选取的翻译候选的数目是否小于K，若是，触发所述翻译候选选取子单元工作。

可选的，所述初始化单元包括：

解码空间构建子单元，用于构建由对应各跨度词序列的节点组成的解码空间；

短语翻译候选初始化子单元，用于根据翻译模型生成所述源语言句子所包含各短语的翻译候选，并将所述各短语的翻译候选添加到所述解码空间中相应节点的翻译结果集合中。

可选的，所述节点拓展子单元包括：

选择子单元，用于从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中；

数目判断子单元，用于判断所述翻译候选的数目是否不小于预设阈值K，并在小于时触发选择子单元工作；

所述节点拓展子单元还包括：

翻译候选排序子单元，用于在所述数目判断子单元的输出为是时，将处于当前节点翻译结果集合中的翻译候选按照翻译分数从高到低排序；

翻译候选筛选子单元，用于从所述翻译候选排序子单元排好序的翻译候选中，选择序位处于高位的K个翻译候选作为当前节点的翻译结果集合。

可选的，所述节点拓展子单元包括：

选择子单元，用于从生成当前节点的各种组合方式中选取翻译分数处于高序位的翻译候选，添加到当前节点的翻译结果集合中；

数目判断子单元，用于判断所述翻译候选的数目是否不小于预设阈值K，并在小于时触发选择子单元工作；

所述节点拓展子单元还包括：

对应关系记录子单元，用于在所述选择子单元选取翻译分数处于高序位的翻译候选后，记录所述翻译候选与生成所述翻译候选的各节点中的相应子翻译候选的对应关系；

所述翻译结果构建单元具体用于，从覆盖整个源语言句子的节点的翻译结果集合中选择翻译分数处于前N位的翻译候选，根据已记录的所述对应关系逐层查找生成所述翻译候选的各层子翻译候选，并依据找到的子翻译候选生成所述源语言句子的翻译结果。

在上述的实施例中，提供了一种用于统计机器翻译的解码方法以及一种用于统计机器翻译的解码装置，此外，本申请还提供一种统计机器翻译方法。请参考图7，其为本申请提供的一种统计机器翻译方法的实施例的流程图，本实施例与上述用于统计机器翻译的解码方法实施例步骤相同的部分不再赘述，下面重点描述不同之处。本申请提供的一种统计机器翻译方法包括：

步骤701、训练用于统计机器翻译的翻译模型、调序模型和语言模型。

统计机器翻译的核心是解码过程，而解码的过程通常是整合翻译模型、调序模型和语言模型，在句子长度的指数级空间中进行搜索最优的翻译候选的过程。本步骤的任务即为训练所述翻译模型、调序模型和语言模型，具体实施时，可以利用针对源语言和目标语言的双语语料库训练翻译模型和调序模型，利用针对目标语言的单语语料库训练语言模型。

所述双语语料(也称平行语料)是指一种语言的文本及其对应于另一种语言译文的集合，通常也称为双语语料库，双语语料库的规模从几千万到数亿个词不等，具体实施时可以自行收集双语语料库，也可以从网上获取已公开的双语语料库。

利用所述双语语料库，通过句子对齐获取双语语料库中的每个双语句对，然后在句对中建立词对齐关系，并抽取与词对齐一致的短语对，最后利用统计的方法将这些短语对转换成概率化的短语翻译表，所述概率可以包括：两个方向的短语翻译概率、两个方向的词汇化翻译概率等，从而完成对所述翻译模型的训练。

调序模型的训练过程主要是获取对短语进行位置调整的概率，所述训练过程也可以利用所述双语语料库实现。所述调序模型可以是基于距离的调序模型，也可以是词汇化的调序模型，本实施例则选用最大熵重排序模型，该模型将重排序看作是一个分类问题，利用从实际双语语料中训练的最大熵分类器预测不同情况下进行顺序调整的可能性。具体实施时，可以采用如下三个步骤训练最大熵调序模型：1)重排序实例的抽取；2)重排序特征的提取，即：从重排序实例中提取最大熵分类器所要用到的特征，所述重排序特征包括：词汇特征和/或组合特征；3)构建最大熵分类器，即估计特征的权重。

通过使用语言模型，可以使翻译系统在生成与源语言句子意思相同的目标词序列的基础上，能够将这些目标词组合成流利的目标语言句子。语言模型的训练过程主要包括统计每个目标语言句子在文本中出现的概率大小，所述训练过程可以利用针对目标语言的单语语料库实现。语言模型可以包括多种，本实施例采用n元(n-gram)文法语言模型，具体可以通过统计单词之间相互跟随出现的可能性来建模。

需要说明的是，针对特定的源语言和目标语言，一旦翻译模型、调序模型和语言模型训练完毕，每一次接收到待翻译原文，直接利用所述模型执行后续步骤702至步骤704即可，不用每次都对上述模型进行训练。

步骤702、对待翻译原文进行预处理，获取由词序列组成的源语言句子。

待翻译原文通常包括若干个段落，每个段落通常包括若干个句子，本步骤对所述对待翻译原文进行预处理，从而获取一系列由词序列组成的源语言句子。

所述预处理操作包括：通过分句切句操作，将所述待翻译原文切割为一系列独立的源语言句子；通过分词操作，将每个独立的源语言句子转换为由若干词组成的序列。在具体实施时，还可以在进行分句操作之前，进行大小写转换、垃圾字符清理等处理。

步骤703、利用所述翻译模型、调序模型和语言模型，采用融合全局剪枝方式的解码方法，对所述源语言句子进行解码，获得对应于源语言句子的目标语言句子。

本步骤利用预先训练好的翻译模型、调序模型和语言模型，采用融合了全局剪枝方式的解码方法，即在本申请第一个实施例中提供的用于统计机器翻译的解码方法，对步骤702中获取的每个由词序列组成的源语言句子进行解码，获取对应于每个源语言句子的翻译结果。如果对应于每个源语言句子的翻译结果有多个，则可以从中选择翻译分数最高的翻译结果，作为对应于所述源语言句子的目标语言句子。

步骤704、对所述目标语言句子进行后处理，获取对应于待翻译原文的目标译文。

本步骤对已获取的目标语言句子进行后处理，所述后处理包括：将已获取的目标语言句子组合为对应于待翻译原文的目标译文。在执行上述组合操作之前，还可以对目标语言句子中的词进行大小写转换等处理，以使得目标语言句子符合目标语言的语法习惯。

本申请提供的统计机器翻译方法，由于采用了融合全局剪枝方法的解码方法，减少了为每个节点生成翻译候选的数目，不仅减少了对内存空间的占用，而且极大地缩减了解码过程中的搜索空间，能够缩短每个源语言句子的翻译时间，从而使得翻译速度整体得到显著提升，与现有的基于形式化句法的统计机器翻译方法相比较，整体翻译速度提升5倍。

需要说明的是，本申请提供的上述方法虽然是针对统计机器翻译提出的，但是其应用领域并非局限于单纯的统计机器翻译系统，在组合了其他机器翻译方法的机器翻译系统中也可以采用本方法。例如，在结合了统计机器翻译与基于规则或者模板的机器翻译方法的系统中，通常可以在预处理阶段根据规则或模板替换源语言句子中的部分词，然后采用本申请提供的方法基于统计规律获取最终的翻译结果。

在上述的实施例中，提供了一种统计机器翻译方法，与之相对应的，本申请还提供一种统计机器翻译装置。请参看图8，其为本申请的一种统计机器翻译装置的实施例的示意图。由于装置实施例基本相似于方法实施例，所以描述得比较简单，相关之处参见方法实施例的部分说明即可。下述描述的装置实施例仅仅是示意性的。

本实施例的一种统计机器翻译装置，包括：模型训练单元801，用于训练用于统计机器翻译的翻译模型、调序模型和语言模型；预处理单元802，用于对待翻译原文进行预处理，获取由词序列组成的源语言句子；解码单元803，用于利用所述翻译模型、调序模型和语言模型，采用如权利要求10所述的用于统计机器翻译的解码装置，对所述源语言句子进行解码，获得对应于源语言句子的目标语言句子；后处理单元804，用于对所述目标语言句子进行后处理，获取对应于待翻译原文的目标译文。

可选的，所述模型训练单元具体用于，利用针对源语言和目标语言的双语语料库训练翻译模型和调序模型，利用针对目标语言的单语语料库训练语言模型。

可选的，所述预处理单元包括：

分句子单元，用于通过分句操作将待翻译原文切割为独立的源语言句子；

分词子单元，用于通过分词操作将所述源语言句子转换为由词组成的序列。

可选的，所述后处理单元具体用于，将所述目标语言句子组合为对应于待翻译原文的目标译文。

本申请虽然以较佳实施例公开如上，但其并不是用来限定本申请，任何本领域技术人员在不脱离本申请的精神和范围内，都可以做出可能的变动和修改，因此本申请的保护范围应当以本申请权利要求所界定的范围为准。

在一个典型的配置中，计算设备包括一个或多个处理器(CPU)、输入/输出接口、网络接口和内存。

内存可能包括计算机可读介质中的非永久性存储器，随机存取存储器(RAM)和/或非易失性内存等形式，如只读存储器(ROM)或闪存(flash RAM)。内存是计算机可读介质的示例。

1、计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。按照本文中的界定，计算机可读介质不包括非暂存电脑可读媒体(transitory media)，如调制的数据信号和载波。

2、本领域技术人员应明白，本申请的实施例可提供为方法、系统或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。