先解释一下问题,译码存在一个困难为同一个字可能被译为它的同音字,比如语音输入“我的手”,“的”可能对应于“的地得”,需要结合语境判断。
ps. 我看有些答案说这是 VITERBI 算法,可以自行了解。
问题a,解法是一个带备忘录的动态规划(过程类似于深度遍历),伪代码如下:
input:
v 图的节点列表
sigma 声音标签
s 声音序列
n = |v| //图V中节点数
k = |s| //声音序列长度
memo = [1..k, 1..n]
VITERBI(1, index of V0)
/**
* t 当前声音序列序号
* x 当前节点序号
*/
VITERBI(t, x)
if s.length = t
return x
if memo not null:
return memo[t, x]
for v[i] in v[x].outerNeighbor
if sigma(x, i) = s[t]
res = VITERBI((t+1, i)
if res != NO-SUCH-PATH
memo[t, i] = (v[x], res)
return memo[t, i]
return NO-SUCH-PATH
时间复杂度,计算备忘录需要 O ( k ∣ V ∣ ) O(k|V|) O(k∣V∣) 次递归函数调用,每次函数最多循环 ∣ V ∣ |V| ∣V∣ 次,所以总时间复杂度为 O ( k ∣ V ∣ 2 ) O(k|V|^2) O(k∣V∣2).
问题b,在问题a的基础上遍历全部可能,选出概率最大的:
PROB-VITERBI(1, index of V0)
PROB-VITERBI(t, x)
sols.seq = NO-SUCH-PATH
sols.prob = 0
if s.length = t
sols.seq = (x)
sols.prob = 1
return sols
if memo[t, i] not null:
return memo[t, i]
for v[i] in v[x].otterNeighbor
if sigma(x, i) = s[t]
res = PROB-VITERBI(k+1, i)
if p(v[0], v[1]) * res.prob >= sols.prob
sols.prob = p(v[x], v[i]) * res.prob
sols.seq = (v[x], res.seq)
return sols
时间复杂度同问题a