现有匹配方法
• 基于树片段的穷举搜索
– 输入：句法树或森林F，翻译规则表R – 输出：匹配的翻译规则 – 步骤
• 对于F中每一个结点N
– 枚举其所有可能以N为根的子树片段 – 对于每一个子树片段G » 将其与rR中的左端相比较，匹配成功，则返回r

LOGO
Fast Translation Rule Matching for Syntax-based Statistical Machine Translation
基于句法的统计机器翻译的翻译规则 快速匹配方法
Hui Zhang, Min Zhang, Haizhou Li, Chew Lim Tan In EMNLP2009 骆卫华报告 2009-6-19

超图匹配算法
TOP 规则表 IP IP VP
句法森林
NP ADJP NP NN
VP
VP VV
NP NN
NP VP NP VV, ε
VP NP VV, NN
NP VP ADJ NP,ε ε, NP,ε

超图匹配算法(1)
TOP
IP
IP
VP
SFP:
• 翻译规则匹配算法
– 基于树片段的穷举搜索 – 基于规则的穷举搜索

规则表：
( CP ( IP ( VP ) ) ( DEC ) ) the | @_@ | of | @_@ 2:2 1:4 2.3854e-05 1e-07 0.000441261 0.0375863 -3.23683e-05 -0.000515897 -5.32183 -13.0477 1.29399 ( CP ( IP ( VP ) ) ( DEC ) ) to | @_@ | @_@ 1:2 2:3 0.000588023 1e-07 0.0118465 0.0968351 -0.000650801 -0.0136365 -5.32183 -9.75755 34.7395 ( CP ( IP ( VP ) ) ( DEC ) ) to | the | @_@ | @_@ 1:3 2:4 0.000483222 1e-07 0.00111862 0.0242182 -0.000552588 -0.00124435 -5.32183 -12.1175 3.28033 ( CP ( IP ( VP ) ) ( DEC 的 ) ) 's | @_@ 1:2 0.0139025 0.270723 0.00245631 0.00467418 -0.0402974 -0.0024043 -2.32674 -8.33583 143.969 ( CP ( IP ) ( DEC ) ) 's | @_@ | @_@ 1:2 2:3 0.000845534 1e-07 0.000491488 0.00467418 -0.000716712 -0.000572699 -3.86862 -11.4867 6.1641 ( CP ( IP ) ( DEC ) ) , | @_@ | @_@ 1:2 2:3 0.0016289 1e-07 0.00392479 0.0658115 -0.00162 -0.00435942 -3.86862 -9.40906 49.2236
现有匹配方法
• 基于规则的穷举搜索
– 输入：句法树或森林F，翻译规则表R – 输出：匹配的翻译规则 – 步骤
• 把rR的左端按照自顶向下，从左到右的次序分解 为超边序列H • 按次序取出H中的每个超边h：
– 按照自顶向下，从左到右的次序与F进行匹配 – 匹配成功，则返回r


动机 现有匹配方法 规则集的超树表示 基于超树的匹配算法 实验结果 总结

动机
• 基于森林的翻译
– 翻译规则匹配 – 基于已抽取规则的解码

动机
• 问题
– 规则匹配和解码非常耗时
• 规则数量巨大
– 在265w句对(树高度3)上生成规则文件大小30G(不过滤)
规则集的超树表示
TOP
超树(Hyper-tree)
超顶点(Hyper-node) 超路径(Hyper-path) 超顶点(Hyper-node) 超顶点(Hyper-node)
超顶点(Hyper-node)

规则集的超树表示
• 超结点的精简表示
– 如果超结点没有与之相连的规则，则从根结点 到该超结点的超路径不存在对应的翻译规则
– 解码算法优化
• Beam search with pruning • Cube pruning
– 规则匹配算法优化？
• ……

动机
• 改进匹配算法
– 提高匹配速度
• 改进规则表示方法
– 加载更多规则 – 放宽参数限制：树高度

现有匹配方法
NP
ADJP
NP
JJ
NN
有关
规定

现有匹配方法
• 基于树片段的穷举搜索
– h：句法压缩森林的一个结点 – f(h)：以h为根的可能的树片段数目
• f(h) = 0 如果h为叶结点
e为连接 h的超边 ci为e中第 i个孩子结点

(1 f (c ))
i
否则

IP => NP VP; NP => NP NP; NP => NN; NN => 声明

现有匹配方法
• 基于规则的穷举搜索
– 对于F中的每个结点需匹配所有规则 – R通常规模巨大 – 实际速度比基于树片段的搜索更慢

规则集的超树表示
• 基本思想
– 超树匹配
• 句法压缩森林和翻译规则集均表示为超树 • 超树的每个顶点只访问一次

规则集的超树表示
公共部分

规则集的超树表示
IP
NP VP
NP
NPΒιβλιοθήκη NNNN新华社声明

规则集的超树表示