有限状态转换器（FST）：概念、组成部分及其应用场景

有限状态转换器（FST）：概念、组成部分及其应用场景

引用

CSDN

1.

https://m.blog.csdn.net/xy2006860/article/details/141428160

有限状态转换器（Finite State Transducer，简称FST）是一种计算模型，它是有限状态自动机（Finite State Automaton，简称FSA）的扩展。FSA是一种理论计算模型，用于表示和处理正则语言，它包含一组状态和在这些状态之间的转换，通常用于模式匹配、文本搜索等任务。与FSA不同的是，FST不仅接受输入字符串，还能产生输出字符串，因此它可以用于建模输入和输出之间的关系，如字符串的转换和映射。

组成部分

FST具有以下几个主要组成部分：

1. 状态集合：包括一个或多个起始状态（也称为初始状态）和至少一个接受状态（也称为终止状态）。
2. 输入字母表：定义了可以接受的输入符号集合。
3. 输出字母表：定义了可以产生的输出符号集合。
4. 转换规则：定义了状态之间的转换，每个转换都与一个输入符号和一个输出符号（或符号串）相关联。
5. 转换函数：描述了在给定当前状态和输入符号时，自动机如何转移到下一个状态，并产生相应的输出符号。

应用场景

自然语言处理（NLP）

• 词形还原（Stemming）和词干提取：将单词从变化形式转换为基本形式。
• 词性标注（Part-of-Speech Tagging）：为文本中的每个单词分配词性标签。
• 语言模型：在自动语音识别和机器翻译中，用于预测下一个词或短语。
• 机器翻译：将一种语言的文本转换为另一种语言。

语音处理

• 语音识别：将语音信号转换为文字。
• 文本到语音（Text-to-Speech）：将文字转换为语音信号的发音指令。

编译器设计

• 词法分析：将源代码文本转换为标记（tokens）。
• 语法分析：在编译过程中，用于识别程序语言的语法结构。

文本处理

• 搜索和替换：在文本编辑器中用于查找和替换字符串。
• 数据清洗：在数据预处理中，用于规范化和转换数据格式。

信息检索

• 查询扩展：在搜索引擎中，用于将用户查询转换为更有效的搜索查询。
• 拼写校正：识别和建议更正拼写错误。

计算生物学

• 序列比对：在DNA和蛋白质序列分析中，用于比对序列和识别相似性。

信号处理

• 模式识别：在图像和声音信号中识别特定的模式或特征。

通信系统

• 编码和解码：在数据传输中，用于数据的压缩和解压缩。

字典应用

从字典树的角度理解FST，Trie树只是共享了前缀，而FST不仅可以共享前缀，还可以共享后缀，所以内存压缩上优势更加明显。

从数据结构角度理解，Trie树将字典压缩成了一棵树，而FST将可以将字典进一步压缩成有向无环图。

从是否携带Value的角度来讲，如果没有value，那就不需要transduce，FST就退化成了FSA（Finite State Automaton）。

例如，一个包含 mon,tues,thurs 的Trie树：

（图片来自参考文档，侵删）

一个包含key-value对 mon: 2,tues: 3, thurs: 5, tye: 99 的FST如下:

（图片来自参考文档，侵删）