用‘恶化技巧’高效编译字符串重写规则为有限状态转换器。
Compiling Rewrite Rules to Finite-State Transducers with the Worsening Trick
- 通过生成所有合法重写候选，再过滤更差选项来简化编译。
- 支持多上下文、加权、并行重写等复杂特性，结果与旧方法一致。
- 适合需要高效实现重写规则的计算语言学与NLP研究者。
有限状态转换器（FST）在计算语言学和自然语言处理中对音系与形态重写规则建模至关重要。对于形如 $A \to B / L \, \_ \, R$ 的一般重写规则（其中 $A$、$B$、$L$、$R$ 为任意正则语言），由于匹配重叠与上下文约束，编译过程复杂。传统方法（如Kaplan-Kay或Karttunen）依赖复杂的转换器组合及辅助标记。本文提出基于“恶化技巧”的紧凑编译方案：先生成所有合法重写候选，再筛选出被其他候选“恶化”的项。该方法已集成于PyFoma，支持多上下文、任意转换、标注、有向重写、权重及并行重写。生成的公式简短统一；当语义一致时，其结果与早期方法完全相同，且更易扩展。在大量重写语法和自动化回归测试集上验证，与foma结果精确匹配（仅状态编号不同）。
原文摘要 · Abstract (English)
Finite-state transducers (FSTs) are essential for modeling string rewriting in computational linguistics and natural language processing (NLP), particularly for phonological and morphological rewrite rules. Compiling general rewrite rules of the form $A \to B / L \, \_ \, R$, where $A$, $B$, $L$, and $R$ are arbitrary regular languages, is complex due to overlapping matches and context constraints. Traditional methods, such as those by Kaplan and Kay or Karttunen, rely on intricate transducer compositions with auxiliary markers. This paper presents a compact compilation scheme based on the "worsening trick'': generate all legal rewrite candidates, then filter candidates that are worse than another candidate for the same input. Implemented as the built-in rewrite compiler in PyFoma, the construction supports multiple contexts, arbitrary transductions, markup, directed rewriting, weights, and parallel rewriting. The resulting formulas are short and uniform, and where semantics coincide, they reproduce the same rule transducers as earlier approaches while remaining easier to extend. The implementation has been validated against foma on both a substantial collection of rewrite grammars and an automated regression suite covering the major rewrite modalities, with the resulting transducers matching exactly apart from state numbering.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。