首先请下载好这3篇paper
Minimization of Sequential Transducers
Direct Construction of Mimimal Structure Acyclic Subsequential Transducers
Direct Building of Mimimal Automation for Given List
总体说明：
(1)直接进入fst 原始算法，请看Direct Construction of Mimimal Structure Acyclic Subsequential Transducers 论文第3部分。
(2)需要预备知识，请看论文Direct Building of Mimimal Automation for Given List第2部分，并结合
Direct Construction of Mimimal Structure Acyclic Subsequential Transducers 第3部分
(3)深入认识FST，请看论文Minimization of Sequential Transducers
(4)Lucene4 FST就是对于的FST包了org.apache.lucene.util.fst
maven pom 的参考
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>og.apache.lucene</groupId>
<artifactId>lucene-core</artifactId>
<version>4.0.0-src-SNAPSHOT</version>
<name>lucene-core</name>
<description>lucene-core</description>
<packaging>jar</packaging>
<url>http://maven.apache.org</url>
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-source-plugin</artifactId>
<executions>
<execution>
<id>attach-sources</id>
<goals>
<goal>jar</goal>
</goals>
</execution>
</executions>
</plugin>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
<configuration>
<source>1.6</source>
<target>1.6</target>
<encoding>UTF-8</encoding>
</configuration>
</plugin>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-compiler-plugin</artifactId>
<configuration>
<source>1.6</source>
<target>1.6</target>
<encoding>UTF-8</encoding>
</configuration>
</plugin>
</plugins>
<resources>
<resource>
<directory>src/main/resources</directory>
<includes>
<include>***.properties</include>
</includes>
<filtering>true</filtering>
</resource>
</resources>
</build>
<dependencies>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.10</version>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.apache.lucene</groupId>
<artifactId>lucene-test-framework</artifactId>
<version>4.0.0</version>
<scope>test</scope>
</dependency>
</dependencies>
</project>
之后将lucene-core 对于的src 替换
call mvn -U eclipse:clean eclipse:eclipse -DdownloadJavadocs=true -DdownloadSources=true
生成的目录，基本上lucene-core 代码工程搞定。
0 Lucene FST
FST的实现是参考论文Direct Construction of Mimimal Structure Acyclic Subsequential Transducers！也即通过输入的有序term list（在lucene4里面string先转化为 byte[],生成byteRef，byteRef作为input用来生成FST），生成最小、无环、有向、最小自动机。单纯看算法伪码，看的懂流程，不一定看的懂原因和为何。整个代码逻辑是依据相关原理来组织的，并且lucene fst的实现者是一个有着10年coding经验、花销10天搞定的，对我等屌丝来说，首先得理解这个deep theroy，并结合代码学习。单纯从代码反推原理似乎非常无门路。
辅助知识：
1.生成最小、无环、有向、最小自动机
为什么是最小、最小如何定义、为什么无环、又为什么是自动机而不是hash or之前的前缀压缩
最小：就是没有冗余的状态信息，当然有最小就有非最小了，非最小对于空间、性能有损耗。从非最小到最小的转换首先是概念的描述、定义、形式化证明的过程，最后是代码实践。
最小定义：参加 Direct Building of Mimimal Automation for Given List 第2部分，实现最小化原理参考论文
Minimization of Sequential Transducers 第3部分。
为什么无环：有怀意味着转换时，会出现死胡同，没有最终状态，也就服务从输入映射一个输出
自动机：查找快速、数据结构紧凑
2.基本关系： FSA FST
FSA 可以简单理解，是说通俗的认识，就看做一个模型或者一种数据结构或者一颗树。当然看做一个图更贴切吧！ FST 相对FSA来说，多了一个输出信息。也就是当前状态 +输入 +输出--> 下个状态，而FSA 当前状态+输入--> 下一个状态。 FST 既有状态的转移信息，当前状态到下一个状态，更有当前输出信息到一个状态输出信息。前者是状态的关联，前后状态依赖弧上的char，后者的输出状态里面包含了前面的状态信息，是拼接的。也就是输出信息是结合，而状态只会唯一。
3.有向、最小自动机基本定义、原理
基本定义、基本原理是后面最小化、直接构造的前提。
这部分看 Direct Building of Mimimal Automation for Given List 论文的第2 部分，重点理解两块信息
状态转移原理、输出变换原理，然后是集合的操作符号的理解，之后结合Direct Construction of Mimimal Structure Acyclic Subsequential Transducers 论文的第2部分。
注意理解递归、结合Fig1 Fig2 来理解定理和证明过程！算法细节就不copy到这里了。
论文中几个符号提示
A\B 表示 属于集合A 单步属于集合B ，等同 A-B
(a,b) 是表示序偶，可以通俗理解从a 映射到b的关系，或者从a 转移到b的过程
∧ 这个符号是论文自定义的
到A 表示任意的意思
反E 表示存在的意思
Lucene&solr <wbr>4 <wbr>实践（4）表示集合的闭包
if only if 充分必要条件
4.算法伪码
Direct Construction of Mimimal Structure Acyclic Subsequential Transducers 论文第3部分
伪码是完成从输入有序list 到输出最小有向自动转换机FST，至于FST的输出如何使用起来没有进一步说明，在lucene4 的fst包里面 FST的输出直接影响着相关数据结构。
5.Lucene4 FST
在前面学习基础上接下来理解Lucene FST未完待续
http://lucene.472066.n3.nabble.com/SynonymFilter-FST-and-Aho-Corasick-algorithm-td3994656.html
