💬 NLP

Compiling Rewrite Rules to Finite-State Transducers with the Worsening Trick

本文介绍了一种基于“恶化技巧”（worsening trick）的紧凑且统一的有限状态转换器编译方案，该方案通过生成所有合法的重写候选对象并过滤掉次优对象，在保持与既有方法完全等价的同时，简化了 PyFoma 工具中复杂重写规则的实现。

原作者： Mans Hulden, Michael Ginn

发布于 2026-06-10

📖 1 分钟阅读☕ 轻松阅读

原作者： Mans Hulden, Michael Ginn

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

核心理念：用“变差”过滤器修复文本

想象你是一位严厉的编辑，正在试图修正书中的错别字。你有一条规则：“如果你看到两个 a 之间有一个 b，就把它改成 p。”

在计算机世界（特别是语言学领域）中，这被称为重写规则（rewrite rule）。挑战在于，计算机是非常死板的。如果你有一串长字符如 abababa，计算机会感到困惑：

它应该改第一个 b 吗？
它应该改第二个 b 吗？
它应该把两个都改了？
如果改变其中一个 b 产生了一个新的模式，而这个新模式看起来也需要被修改，该怎么办？

作者 Mans Hulden 和 Michael Ginn 提出了一种更简单的新方法，教计算机如何应用这些规则，而不会陷入循环或错过最佳方案。他们将这种方法称为**“变差技巧”（Worsening Trick）**。

旧方法：“标记”迷宫

以前，计算机科学家尝试通过构建一个复杂的迷宫来解决这个问题。他们会在文本中插入隐形的“标记”（就像小旗子）来表示：“嘿，这个位置是一个可以修改的候选点。”然后，他们会构建一个巨大的机器来检查这些旗子是否在正确的位置，进行修改，最后再尝试移除这些旗子。

作者说，旧方法就像是先给每一块砖头涂上不同的颜色，检查油漆，然后再把油漆磨掉来盖房子。虽然可行，但既混乱、复杂，又难以更新。

新方法：“变差”过滤器

作者提出了一个更加简洁的三个步骤过程。把它想象成一场才艺表演选秀，评委们非常严格。

第一步：生成所有可能性（“开放麦”）

首先，计算机生成文本可能发生改变的每一种可能方式。它现在还不担心规则问题。

类比： 想象一个挤满了人的房间。每个人都举着一个牌子，上面写着：“我认为我应该修改这个词。”有些人为第一个词举牌，有些人为第二个词，有些人则为两者都举牌。这是一个混乱的房间，包含了所有可能的修改组合。

第二步：检查上下文（“场地规则”）

接下来，计算机检查这些修改是否符合规则（即“上下文”）。

类比： 场馆经理走进来宣布：“只有当一个词位于两个 'a' 之间时，你才能修改它。”任何为不在两个 'a' 之间的词举牌的人都被请了出去。
现在，房间里只剩下持有“合法”修改想法的人。但可能还是会有太多人。也许一个人想只改第一个词，而另一个人想把两个都改了。

第三步：“变差”技巧（“严厉的评委”）

这是本文的核心秘诀。计算机问道：“有没有一种方法能让这个修改想法变得‘更差’？”

逻辑： 如果你有一个“什么都不改”的候选方案，那么相比于一个“必须进行修改”的候选方案，它是“更差”的（如果规则规定必须修改）。如果你有一个只修改第一个词的候选方案，但你本可以同时修改第一个和第二个词，那么这个“仅修改第一个”的方案就是“更差”的。
技巧： 计算机构建了一个特殊的过滤器（“变差器”），它能将一个“好”的候选方案变成一个“坏”的候选方案，方法是移除一次修改。
- 类比： 想象严厉的评委手里拿着一把魔法橡皮擦。如果一个人在房间里举着代表某种修改的牌子，评委会尝试擦掉它。
- 如果评委能够擦掉一个牌子，且那个人看起来仍然是一个有效的候选人，那么原本那个人就是“次优的”（他们错失了修改的机会）。他们会被踢出去。
- 最终留下来的人是那些无法被变得更差的人。这些人完成了所有应该完成的修改，达到了最好的效果。

为什么这意义重大

简洁明了： 作者使用的数学公式比旧有的“标记”方法要短得多，也更清晰。这就像是用 3 个清晰的步骤而不是 2 篇混乱的段落来写一份食谱。
灵活性高： 这种同样的“变差技巧”适用于各种复杂的规则：
- 多重规则： 同时将 b 改为 p 并且将 d 改为 t。
- 偏好设置： “修改你看到的第一个”（最左侧）或“修改你看到的整个最长部分”（最长匹配）。
- 权重： 如果某些修改消耗更多的“能量”，这种方法也能处理。
行之有效： 作者将他们的新方法与已建立的旧方法（称为 foma）进行了对比测试。他们发现结果是完全一致的。计算机产生的输出完全相同，只是内部编号有所不同。

“扩散”带来的惊喜

论文还提到一个关于“扩散”（spreading）规则（例如，一个元音音素如何影响后缀中元音的情况）的有趣副作用。

通常，规则检查的是输入（你输入的文本）。
但有时，你需要检查输出（你刚刚创造的内容）。
作者展示了通过简单地交换他们步骤的顺序，这种“变差技巧”可以自然地处理这种“扩散”行为，这对于像芬兰语元音和谐（Finnish vowel harmony）这样的现象非常有用。

总结

这篇论文介绍了一种优雅的新方法，教计算机如何编辑文本。它不再通过构建复杂的标记迷宫，而是生成所有可能性，过滤掉非法的选项，然后利用“变差技巧”来剔除任何不是最优的选项。这是一种更简单、更强大的方式，解决了语言学家们面临数十年的难题。

技术摘要：利用恶化技巧（Worsening Trick）将重写规则编译为有限状态转换器

问题陈述
有限状态转换器（FSTs）是建模计算语言学中字符串重写的基础，特别是对于形式为 $A \to B / L \_ R$ 的音系学和形态学规则。在这里，属于正则语言 $A$ 的字符串在正则语言 $L$ 和 $R$ 的上下文中被替换为 $B$ 。由于存在重叠匹配、多重上下文以及需要处理各种偏好（例如：最左侧、最长或最短匹配），将此类通用规则编译为 FSTs 在计算上非常复杂。传统的编译方法（如 Kaplan 和 Kay 或 Karttunen 的方法）依赖于涉及辅助标记的复杂组合，以约束重写位置。这些方法往往导致复杂的、非统一的公式，难以扩展到高级特性，如并行重写、任意转换或加权规则。

方法论
作者提出了一种基于“恶化技巧”（worsening trick）的编译方案，该策略此前已被应用于正则集合和转换。该方法通过三个透明阶段来编译规则 $A \to B / L \_ R$ ：

候选生成 ( $T_{base}$ )：系统通过对潜在转换位置进行括号化，生成所有可能的重写候选。这是通过构建一个基础转换器来实现的，该转换器允许来自输入字母表 $\Sigma$ 的符号原样通过，或者在代表转换 $A:B$ 的括号 $< \dots >$ 内被替换为字符串 $B$ 。词边界通过 # 显式标记，以便统一处理边缘上下文。
上下文限制 ( $L_{context}$ )：过滤掉处于非法上下文中的候选项。为了处理多个上下文，作者没有使用指数级的公式，而是采用了“点位技术”（dotted-position technique，由 Yli-Järvi 和 Koskenniemi 提出）。使用辅助符号 · 来标记单个重写位置，并构造一个语言 $K$ ，该语言表示被合法上下文（ $L$ 和 $R$ ）所包围的带有该标记位置的字符串。合法上下文与候选集的交集即为合法的、可选的重写集合。
偏好过滤（恶化）：为了强制执行义务性重写和特定偏好（例如：最左侧、最长或最短），系统定义了一个“恶化”转换器 ( $W$ )。该转换器通过移除或移动重写括号（例如：撤销一次重写或缩短跨度）将一个“较好”的候选对象映射为一个“较差”的候选对象。最终的转换器通过过滤掉任何可以通过应用 $W$ 而变得严格更差的候选对象来构建。从数学上讲，对于候选集 $C$ 和恶化器 $W$ ，最优集合为 $C \cap \neg \text{range}(C \circ W)$ 。

该框架在 PyFoma 中实现，并支持：

多重上下文：通过点位语言中的并集进行处理。
定向重写：通过特定的恶化转换器（ $W_{left}$ 、 $W_{long}$ 、 $W_{short}$ ）对偏好进行编码。
任意转换：输入 $T$ 不需要是简单的笛卡尔积；它可以是任何 FST。
并行重写：使用索引括号处理多个规则，并对每个索引分别进行上下文限制和恶化处理。
权重：该构造在热带半环（tropical semiring）内工作，因为恶化器在过滤候选对象时不会改变其分配的权重。
空字符（Epsilon）处理：一种特定的过滤器防止连续出现空的括号对，以将空字符插入限制为每个边界单个位置。

核心贡献

统一性与紧凑性：论文提出了一种公式化表达，其编译逻辑与传统的、依赖大量标记或多带（multitape）的方法相比，具有显著更短且更统一的公式。
可扩展性：该构造自然地扩展到复杂模态（并行规则、权重、标记、输出侧上下文检查），而无需引入新的规则类型或辅助机制。
实现与验证：作者在 PyFoma 中实现了该编译器。通过使用 31 个语法（427 条规则）以及一个包含 2,217 个案例的自动化回归套件，对已建立的基于 C 语言的 foma 编译器进行了验证。
等价性：在所有语义一致的测试案例中，生成的转换器在结构上与 foma 生成的转换器完全相同（仅在状态编号上有所不同），证实了基于恶化的方法的正确性。

意义与主张
论文声称，恶化技巧为有限状态音系学中的程序化选择任务提供了一种稳健的代数替代方案。通过生成正则候选集并通过恶化关系进行过滤，复杂的偏好顺序可以以声明式的方式编码在正则演算中。作者断言，这种方法不仅能够重现经典编译器的既定语义，而且简化了重写系统的理论和实际扩展。该技术不仅被视为一种编译工具，更被视为一种通用的有限状态设计模式，用于提取正则语言和关系（例如：极小或极大代表元）的优选子集。这项工作强化了恶化技巧在有限状态最优理论（Optimality Theory）之外的应用价值，证明了其在处理经典重写规则全谱模态方面的有效性。