computer-science - 什么是有限状态传感器？

Question

有人可以告诉我什么是有限状态传感器吗？

我已经阅读了维基百科的文章，但什么都不懂。

Answer 1

有限状态转换器 (FST) 是一种有限状态自动机 (FSA, FA)，它产生输出和读取输入，这意味着它可用于解析（而“裸”FSA 只能用于识别，即模式匹配）。

FST 由有限数量的状态组成，这些状态由标记有输入/输出对的转换链接。FST 从指定的起始状态开始，根据输入跳转到不同的状态，同时根据其转换表产生输出。

FST 在 NLP 和语音识别中很有用，因为它们具有很好的代数特性，最值得注意的是它们可以在组合下自由组合（形成代数），它在规则关系上实现关系组合（认为这是非确定性函数组合），而保持非常紧凑。FST 可以在线性时间内将常规语言解析为字符串。

例如，我曾经将形态解析实现为一堆 FST。我对动词的主要 FST 会将常规动词（例如“walked”）变成“walk+PAST”。我还有一个用于动词“to be”的 FST，它将“is”变成“be+PRESENT+3rd”（第三人称），对于其他不规则动词也是如此。使用 FST 编译器将所有 FST 组合成一个单独的 FST，该编译器生成的 FST 远小于其各部分的总和，并且运行速度非常快。FST 可以由各种接受扩展正则表达式语法的工具构建。

Answer 2

有限状态转换器本质上是在两个（或更多）磁带上工作的有限状态自动机。考虑传感器的最常见方式是一种“翻译机”。他们从其中一盘磁带中读取并写入另一盘磁带。例如，这是一个将as 转换为bs 的转换器：

a:b在弧处意味着在这个过渡中，换能器a从第一个磁带读取并写入b第二个磁带。

参考：有限状态传感器

Answer 3

用尽可能简单的术语来说，我理解 FST 本质上是一种“事物”，它基于输入磁带从一个状态移动到下一个状态并写入不同的输出磁带。磁带本质上是一组输入，例如字符串中的字符。

The entire FST is represented by a set of states and links between them. A link is "activated" when its input condition is correct and then gives then next state the adjusted tape.

For example let's say an FST starts with the tape abc at state 1. A link to state 2 matches a and changes that to b. This would get activated, set the output tape to just b, and pass the remaining bc to state 2. As you can see, each state is only activated if there is a link to it whose input condition was correct, passes the remaining input to the next state, and writes to a separate output tape. Each FST runs across the tape once and output to another tape once.

为了更清楚地了解它们，请阅读并查看本文中的图表（原始断开链接）。