如何高效学习trie、fsa和fst算法？

本文共计1447个文字，预计阅读时间需要6分钟。

FSA（有限状态自动机）：确定无环有限状态接收器，即FSA。一个FSA需要满足以下条件：+ 确定性：给定输入，最多只能转移到一个状态。+ 无环性：状态转换图没有环。

FSA（可为有序集合set）：

　　确定无环有限状态接收器(deterministic acyclic finite state acceptor)，即FSA。

　　一个FSA需要满足以下条件：

• • 　　确定性的。给定输入，最多只能转移到一个状态。
  • 　　无环的。不能反序遍历。
  • 　　接收器。FSA可以接收一系列特定的输入。

　　demo:

　　　　key作为FSA的状态转移。给定一个输入key，我们可以知道这个key是否在FSA中，如下图：

　　

　　　　如果集合中有3个key：jul、jun、mar，图如下：（FSA集合在添加jun时，其实没有新增状态节点，因为jun和jul共享了前缀ju）

　　　　　如果集合为这3个key：october，november，december，图如下：（因为有相同的后缀ber，在FSA中只需要编码一次就行了）

　　注意：判断一个key是否存在，受限于key的长度，而不是set的大小。

　　构建方案：

　　　　FSA和trie的区别在于，共享后缀。因此一个FSA的空间会比trie少很多，但是构建起来却更复杂。