Finite State Transducers
一, 简介 Finite State Transducers 简称 FST, 中文名:有穷状态转换器。在自然语言处理等领域有很大应用,其功能类似于字典的功能(STL 中的map,C# 中的Dictionary),但其查找是O(1)的,仅仅等于所查找的key长度。目前Lucene4.0在查找Term时就用到了该算法来确定此Term在字典中的位置。 FST 可以表示成FST<Key, Value>的形式,我们可以用O(length(key))的复杂度,找到key所对应的值。除此之外,FST 还支持用Value来查找key以及查找Value最优的key等功能。 FST 如此强大,但是目前网上对其讲解的资料很少,中文的就更是微乎其微了。 二,数据结构 FST 是一种类似于Trie或自动机的数据结构,所以在学习之前您一定要对自动机有一个简单的了解,鉴于篇幅,自动机的内容本文不做介绍。 在查找最优的Value时,会用到求最短路径的Dijikstra算法,但建图过程于此无关。 三,创建FST 为了让大家对FST有一个初步的认识,我们举一个简单的例子来进行说明。 我们假设创建...
