FST（Finite State Transducer）数据结构。

有限状态转换器（Finite State Transducer，FST）是一种用于处理字符串和文本的数据结构。它可以用来实现自动机、搜索引擎、拼写检查器和语音识别器等应用程序，它的主要思想是将输入的字符串映射到一组状态，并在状态之间进行转换。

FST通常由一个有向无环图（DAG）表示，其中每个节点表示一个状态，每条边表示一个字符或一组字符。在FST中，每个输入字符串都可以表示为从起始状态开始，沿着一系列转换到达结束状态的路径。这些路径可以用来实现精确匹配、前缀匹配、模糊匹配和自动纠错等功能。

FST的一个重要特点是它支持高效的搜索和查找操作。当一个新的字符串被添加到FST中时，它会自动与现有的状态进行比较，并选择最短的路径来表示该字符串。这种“最短路径优先”的策略可以大大提高搜索效率，并减少存储空间的使用。

FST是一种非常强大的数据结构，可以在各种语言处理和文本处理应用程序中发挥重要作用。它已经成为许多搜索引擎、拼写检查器和语音识别器的核心组件之一，并在实际应用中得到了广泛的应用。