加权有限自动机 | Codeboy's Blog

形式陈述

加权有限自动机保留有限状态自动机的带标签状态图，但为每个字输出一个半环元素。固定半环 $(S,\oplus,\otimes,0_S,1_S)$ ，本文的无 ε-边模型由有限状态集 $Q$ 、有限字母表 $\Sigma$ 、有限转移多重集 $E$ 、边权函数 $\mathrm{wt}:E\to S$ ，以及初始和终止权函数 $\lambda,\rho:Q\to S$ 组成。每条边 $e:p\xrightarrow{a}q$ 恰好读取一个 $a\in\Sigma$ ；多重集允许起点、标签、终点完全相同的多条边，各条仍是独立的路径选择。不参与起始或终止的状态分别赋权 $0_S$ 。

给定 $w=a_1\cdots a_L$ ，记 $\mathcal P(w)$ 为所有标签依次为 $a_1,\ldots,a_L$ 的边路径。路径可以重复经过状态。若 $\pi=(q_0,e_1,q_1,\ldots,e_L,q_L)$ ，其贡献及自动机输出定义为

\mathrm{wt}(\pi)=\lambda(q_0)\otimes\mathrm{wt}(e_1)\otimes\cdots\otimes\mathrm{wt}(e_L)\otimes\rho(q_L), \qquad A(w)=\bigoplus_{\pi\in\mathcal P(w)}\mathrm{wt}(\pi).

乘法因子的顺序就是运行的时间顺序；半环乘法不必交换。这里 $A:\Sigma^*\to S$ 是字的取值函数，不只是一个接受集合。没有匹配路径时，空和为 $0_S$ 。空字在每个状态各有一条零边路径，因此

A(\varepsilon)=\bigoplus_{q\in Q}\lambda(q)\otimes\rho(q).

有环并不妨碍定义：长度为 $L$ 的输入只能走 $L$ 条边，所以求和总是有限的。若允许 ε-环，一个固定输入就可能对应无限多条路径；那需要额外规定哪些无限和存在，不能直接沿用本页的有限求和理由。

对每个字母定义转移矩阵

M_a(p,q)=\bigoplus_{e:p\xrightarrow{a}q}\mathrm{wt}(e).

把 $\lambda$ 写成行向量、 $\rho$ 写成列向量，用半环运算作矩阵乘法，便有

A(a_1\cdots a_L)=\lambda M_{a_1}\cdots M_{a_L}\rho.

空矩阵乘积取单位矩阵，因此该式也覆盖空字。平行边先在同一矩阵条目中相加；分配律保证随后展开乘积时，各条边的贡献仍被保留。

直觉

一条路径描述对输入的一种完整解释。沿路径串联步骤用 $\otimes$ ，把互为替代的解释汇总用 $\oplus$ ：自然数半环累加带重数的解释，热带半环寻找最小代价解释，布尔半环只保留有没有解释。于是非确定性有限自动机可以看作布尔情形：初态、接受态与现有边赋真，其余赋假，整字输出为真恰好表示存在接受运行。

直接列举路径可能很贵，但读完同一前缀、到达同一状态的路径具有相同的后续选择。它们可以先合并成一个半环元素，再共同处理下一符号。这就是动态规划在这里能够复用结果的原因，而分配律保证这种合并不改变答案。

令 $v_i(q)$ 表示读完前 $i$ 个符号后的状态权重。前向算法取 $v_0(q)=\lambda(q)$ ，每一步更新

v_{i+1}(q)=\bigoplus_{p\in Q}v_i(p)\otimes M_{a_{i+1}}(p,q), \qquad A(w)=\bigoplus_{q\in Q}v_L(q)\otimes\rho(q).

其不变量是： $v_i(q)$ 恰为所有读取前缀 $a_1\cdots a_i$ 、结束于 $q$ 的路径的“初始权乘各边权”之和，此时尚未乘终止权。 $i=0$ 时只剩 $q$ 上的零边路径，其值为 $\lambda(q)$ ，所以不变量成立。归纳时，每条新路径都有唯一的最后一条边 $p\xrightarrow{a_{i+1}}q$ ；按这条边划分路径，把此前各条路径的贡献在右侧乘该边权，再相加，有限分配律恰好给出递推式。整个证明没有交换乘法因子，因而也适用于非交换半环。

最后按末状态在右侧乘 $\rho(q)$ ，就恢复定义中的每条完整路径贡献。这既证明前向算法，也证明矩阵公式。终止权只在整个输入结束后附加；中途经过具有非零终止权的状态，不会提前结束本次运行。

例子与边界

同一输入的三种求值

取状态顺序 $(s,p,f)$ 、字母表 $\{a,b\}$ ，仅 $s$ 的初始权与 $f$ 的终止权为 $1_S$ ，其他初始、终止权均为 $0_S$ 。图中恰有五条边， $f$ 没有出边。

三状态加权自动机：s 上的 a/2 自环、s 到 p 的 a/3、p 上的 a/5 自环、s 到 f 的 b/11，以及 p 到 f 的 b/7 — 输入 aab 恰有三条从 s 到 f 的图路径。边标签为输入符号/权重；图中数字先按自然数解释，入箭头与双圆分别表示初始权和终止权为 1。

先在自然数半环中计算。对应的两个矩阵是

M_a=\begin{pmatrix}2&3&0\\0&5&0\\0&0&0\end{pmatrix}, \qquad M_b=\begin{pmatrix}0&0&11\\0&0&7\\0&0&0\end{pmatrix}.

输入 aab 恰有以下三条从 $s$ 到 $f$ 的图路径。初始、终止单位权不改变各路径值：

状态路径	自然数：沿路相乘	热带：沿路相加
$s,s,s,f$	$2\cdot2\cdot11=44$	$2+2+11=15$
$s,s,p,f$	$2\cdot3\cdot7=42$	$2+3+7=12$
$s,p,p,f$	$3\cdot5\cdot7=105$	$3+5+7=15$

自然数前向计算逐步给出

(1,0,0)\xrightarrow{a}(2,3,0) \xrightarrow{a}(4,21,0) \xrightarrow{b}(0,0,191).

第二步 $p$ 上的 $21=2\cdot3+3\cdot5$ 汇合了两种前缀；最后得到 $4\cdot11+21\cdot7=191$ ，与逐路相加 $44+42+105$ 相同。这里的 $191$ 是带重数的计数：例如权重 $3$ 表示该局部步骤有三种选择。图上实际只有三条成功路径；只有把每条显示边的权重都改成 $1$ ，输出才是图路径数 $3$ 。

再把相同边上的数字解释为热带半环 $(\mathbb R\cup\{\infty\},\min,+,\infty,0)$ 中的代价。此时初始和终止的单位权是实数 $0$ ，缺失边与不活跃状态用 $\infty$ ，不是实数 $0$ 。前向计算变为

(0,\infty,\infty)\xrightarrow{a}(2,3,\infty) \xrightarrow{a}(4,5,\infty) \xrightarrow{b}(\infty,\infty,12).

例如第二步 $p$ 的值为 $\min(2+3,3+5)=5$ ，最终为 $\min(4+11,5+7)=12$ 。这与表中三个路径代价取最小值一致，最优路径是 $s,s,p,f$ 。

最后改用布尔半环，把每条显示边赋真，缺失边赋假；只有 $s$ 的初始权和 $f$ 的终止权为真。向量依次为 $(1,0,0)$ 、 $(1,1,0)$ 、 $(1,1,0)$ 、 $(0,0,1)$ ，所以输出为真。三次计算共享图与输入，但对权值和运算作了明确的不同解释，不能把它们当作任意半环之间都存在的保数值同态。

零值与读完输入的含义

这台机器对空字输出 $0_S$ ，因为没有状态同时具有非零初始权和终止权。对 aaba 也输出 $0_S$ ：读到 aab 后到达 $f$ ，但 $f$ 没有可读最后一个 a 的出边。这个值在自然数、热带与布尔解释中分别是 $0$ 、 $\infty$ 与假；中途到达终态不能挽救未读完的输入。

一般半环中，输出为零并不必然意味着不存在图路径。边本身可能带零权，非零因子的乘积可能为零，不同路径贡献也可能相消。例如整数环也是半环，两条匹配路径贡献 $1$ 与 $-1$ 时总值为 $0$ 。所以“忽略权重后有哪些接受路径”与“哪些字取非零值”是不同问题，只有附加合适的代数条件才能将二者对应。

权重也不自动是概率：本例的自然数权重没有归一化，热带权重表示代价。若要建立概率解释，必须另行给出非负性、归一化及终止机制。普通 NFA 的子集构造只追踪状态是否出现，丢掉了这里的数值；加权确定化不能仅凭这张图便照搬子集构造。

推论与应用

实现前向算法时，准备两个长度为 $n=|Q|$ 的数组。对下一字母，先把新数组清零；遍历具有该标签的每条边 $e:p\to q$ ，执行“新 $v(q)\gets$ 新 $v(q)\oplus(v(p)\otimes\mathrm{wt}(e))$ ”；这一轮结束才交换新旧数组。若在原数组上边读边写，自环或本轮刚写入的值可能被再次使用，相当于一个输入符号走了多条边，破坏前缀不变量。

设 $m=|E|$ 、输入长度为 $L$ 。以每次半环加法和乘法为单位代价，初始化和最终求和需 $O(n)$ ，逐轮清零及遍历边给出总成本 $O(n+L(n+m))$ ；按标签索引边可以进一步只访问当前字母的边。额外工作空间为两个向量的 $O(n)$ ，不含机器与输入的存储。使用稠密转移矩阵则需 $O(n+Ln^2)$ 次半环操作。这些写法也包含 $L=0$ 的情形，不会误把空字求值的成本记成零。

这是代数操作数，不是位复杂度。自然数权重下，即使图固定，分支计数也可能随输入长度指数增长；例如一状态、两条权重为 $1$ 的同标签自环，长度 $L$ 的字得到 $2^L$ ，存储结果就需要 $L+1$ 位。因此固定数量的状态不意味着整数计算始终具有固定字长成本。

这一接口把有限状态匹配与计分分开：状态和标签限制哪些解释有效，半环决定如何评价它们。候选分析的计数、具有有限状态约束的最小代价匹配，以及仅判断可行性的识别，都可以采用同一前向递推；正确性依靠的是有限路径分解、分配律与因子顺序，而不是某一种特定的数值运算。

参考资料

Mehryar Mohri, Weighted Automata Algorithms, in Handbook of Weighted Automata, 2009，§§1.1–1.2（PDF 第 2–4 页）：半环、转移多重集与路径权重。原文允许 ε-边；本文限制为每边读取一个符号，以使固定字的路径和总是有限。
Benedikt Bollig and Marc Zeitoun, Weighted Automata, MPRI lecture notes, February 7, 2011，Chapter 1 §2（印刷页 2–3）：非交换半环与自然数、布尔、热带及矩阵半环示例。

形式陈述 ​

同一输入的三种求值 ​

零值与读完输入的含义 ​

反向链接

形式陈述

同一输入的三种求值

零值与读完输入的含义