1 前言
ES现在已经被广泛的使用在日常的搜索中，Lucene作为它的内核值得我们深入研究，比如FST，下面就用两篇分享来介绍一些本文的主题：
下面开始第一篇
2 引言
“算法是计算机科学领域最重要的基石之一“
“编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。“——《算法的力量》
2.1 提出问题
2.1.1 案例一
设有一组N个数而要确定其中第k个最大者，我们称之为选择问题。常规的解法如下：
这两种算法编码都很简单，但是我们自然要问：哪个算法更好？哪个算法更重要？还是两个算法都足够好？使用N=30000000和k=15000000进行模拟将发现，两个算法在合理的时间量内均不能结束；每一种算法都需要计算机处理若干时间才能完成。
其实还有很多可以解决这个问题，比如二叉堆，归并算法等等。
2.2.2 案例二
输入是由一些字母构成的一个二维数组以及一组单词组成。目标是要找出字谜中的单词，这些单词可能是水平、垂直、或沿对角线上任何方向放置。下图所示的字谜由单词this、two、fat和that组成。
现在至少也有两种直观的算法来求解这个问题：
上述两种方法相对来说都不难编码，但如果增加行和列的数量，则上面提出的两种解法均需要相当长的时间。
以上两个案例中，我们可以看到要写一个工作程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要问题。
那么，使用自动机理论可以快速的解决这个问题，下一篇中给大家详细的分析。
3 数据结构与算法基础
3.1 数据结构基础
3.1.1 什么是数据结构
在计算机领域中，数据是信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号的总称。数据结构是指数据元素和数据元素之间的相互关系或数据的组织形式。数据元素是数据的的基本单位，数据元素有若干基本项组成。
3.1.2 数据之间的关系
数据之前的关系分为两类：
表示数据之间的抽象关系，按每个元素可能具有的前趋数和直接后继数将逻辑结构分为线性结构和非线性结构。逻辑关系或逻辑结构有如下特点：
- 只是描述数据结构中数据元素之间的联系规律；
- 是从具体问题中抽象出来的数学模型，是独立于计算机存储器的（与硬件无关）
逻辑结构的分类如下：
- 线性结构
- 树形结构
- 图状结构
- 其他结构
2)物理关系
逻辑关系在计算中的具体实现方法，分为顺序存储方法、链式存储方法、索引存储方法、散列存储方法。物理关系或物理结构有如下特点：
- 是数据的逻辑结构在计算机存储其中的映像；
- 存储结构是通过计算机程序来实现，因而是依赖于具体的计算机语言的；
物理结构分类如下：
- 顺序结构
- 链式结构
- 索引结构
3.2 算法基础
3.2.1 基础概念
算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。对于一个问题，一旦某种算法给定并且被确定是正确的，那么重要的一步就是确定该算法将需要多少诸如时间或空间等资源量的问题。如果一个问题的求解算法竟然需要长达一年时间，那么这种算法就很难能有什么用处。同样，一个需要若干个GB的内存的算法在当前的大多数机器上也是无法使用的。
3.2.2 数学基础
一般来说，估算算法资源消耗所需的分析是一个理论问题，因此需要一套数学分析法，我们先从数学定义开始。
- 定理1：如果存在正常数c和n0，使得当N>= n0时，T(N) =n0时，T(N) n0时，T(N) < cp(N)，则T(N) = o(p(N))。
这些定义的目的是要在函数间建立一种相对的级别。给定两个函数，通常存在一些点，在这些点上一个函数的值小于另一个函数的值，因此，一般宣称f(N)
