正则表达式与有限状态方法

基于正则语言的实用技术——使用正则表达式进行模式匹配，以及使用有限状态转换器进行字符串到字符串的映射——能够高效处理分词、规范化和形态分析。

Definition

有限状态方法是语言处理技术，其中模式和映射表示为正则表达式或有限状态自动机和转换器，从而保证高效的线性时间识别。

Scope

涵盖作为字符串模式语言的正则表达式，作为其计算实现的有限状态自动机和转换器，以及它们在文本规范化、分词、拼写和计算形态学中的应用。它包括语音和浅层处理中使用的加权有限状态方法。完整的音韵学理论和深层句法分析不在其范围之内。

Core questions

• 正则表达式如何精确地指定和提取文本模式？
• 有限状态转换器如何将表层形式映射到词汇分析，例如在形态学中？
• 为什么在分词和规范化中首选有限状态方法？

Key concepts

• 正则表达式
• 有限状态转换器
• 分词
• 文本规范化
• 形态分析
• 双层形态学
• 加权自动机
• 编辑距离

Key theories

形态学和音韵学的正则模型

音韵重写规则和形态交替可以编译成有限状态转换器，使得分析和生成成为一个高效的统一框架。

正则表达式与有限自动机的等价性

正则表达式、正则文法和有限状态自动机都精确地描述了正则语言，因此声明性模式可以被编译成高效的识别器。

History

正则表达式从克莱尼（Kleene）的工作进入计算机领域，并在文本工具中变得无处不在。在20世纪80年代，科斯肯涅米（Koskenniemi）的双层形态学以及卡普兰（Kaplan）和凯（Kay）将音韵规则编译成转换器的工作，确立了有限状态技术作为形态处理的主力，这种方法在比斯利（Beesley）和卡尔图宁（Karttunen）的手册中得到了巩固。

Debates

有限状态方法能扩展到何种程度？

有限状态技术效率极高，但仅限于正则现象；争论在于哪些语言处理任务仍最适合使用它们，而非更丰富的统计或神经网络模型。

Key figures

• Martin Kay
• Ronald Kaplan
• Kimmo Koskenniemi
• Lauri Karttunen

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

为什么在形态学中要使用有限状态转换器而不是仅仅使用查找表？

转换器能够紧凑地编码系统性交替，并且可以分析或生成它从未见过的词形，而查找表只存储其中明确列出的形式。