搜索引擎中相似字符串查找那些事儿

首先从字符串相似查找谈起。相似字符串查找，顾名思义即查询与目标字符串在物理上词形相似的字符串集合，在搜索引擎中有很多应用。其中比较常见的有2个：模糊搜索 (Fuzzy Search)和 拼写纠错(Spelling Check或Spelling Correction)。

• 模糊搜索

模糊搜索，或者叫做模糊查询，在搜索引擎中一般指在用户搜索意图不明确时，搜索引擎将用户的查询（query）与待检索的内容（doc）进行模糊匹配，找出与查询相关的内容。例如，查询名字Smith时，模糊查询方式就会找出与之相似的Smithe， Smythe， Smyth， Smitt等。这在克服少无结果搜索时尤其有用。注意本文讨论的模糊搜索特指查询query与待检索内容在文本字符串物理词形上的相似为目标，语义相似的模糊查询不在本文讨论范围内。

• 拼写错误

拼写纠错，或者叫拼写检查功能在搜索引擎中一般指的是：用户将查询的关键词提交给搜索引擎之后，搜索引擎便开始分析用户的输入，检查用户的拼写是否有错误，如果有的话，给出正确的拼写建议。例如用户在搜索引擎检索框中输入faeebook， 搜索引擎能给出拼写纠错建议facebook等。

搜索引擎中解决模糊搜索和拼写纠错本质上都是字符串文本相似匹配和度量问题。用户给搜索引擎输入了查询query字符串a,如何在待检索内容全集中遍历每一个字符串b，并迅速确定a和b是否相似，最终把所有与字符串a最相似的topN个字符串集合作为目标返回供进一步扩展召回或作为纠错建议的基础就成为解决问题的关键。

• 编辑距离

如何量化两个字符串之间的相似程度呢？有一个非常著名的量化方法，那就是编辑距离（Edit Distance）。

编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。

编辑距离有多种不同的计算方式，比较著名的有莱文斯坦距离（Levenshtein distance）和最长公共子串长度（Longest common substring length）。其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。

• Levenshtein Distance 和 Damerau Levenshtein Distance 定义

注意:为了简化表述，本文以下都非正式地将Levenshtein Distance简称为LD，将Damerau Levenshtein Distance简称为DLD。

Levenshtein Distance，参考维基百科上Levenshtein Distance （来自参考文献1）给出的定义如下：

维基百科对Damerau Levenshtein Distance（来自参考文献2） 给出的定义如下：

通过维基百科上关于Levenshtein Distance和Damerau Levenshtein Distance的描述可知DLD与LD的区别仅在于：如果字符串a和b的某处前后两个相邻字符前后互换位置后相同时， LD认为是经过2次变化，编辑距离是2；然后DLD认为这是一次变化，编辑距离是1。

本文接下来将由浅入深地从如下3个层次依次讨论利用编辑距离LD或DLD解决搜索引擎中查找相似字符串问题的实践技术细节：

1. 单纯计算两个字符串间的编辑距离问题

2. 在搜索引擎场景中如何快速找出与目标字符串a最相似的前N个候选字符串集合问题

3. 构造正确有效的Levenshtein DFA和Damerau Levenshtein DFA 高效求解搜索引擎中查找相似字符串问题

利用LD和DLD度量字符串相似程度，首先面临要解决一个基础问题：

问题：对于任意给定的2个字符串a和b，如何用快速的算法求解a和b的LD和DLD？

在理解了维基百科中关于LD和DLD的定义后，解决这个问题并不困难。可以分2个层面逐步深入理解这个问题。

第一个层面：最朴素的思路是采用蛮力法递归求解。一种Levenshtein Distance的Java实现代码示例如下：

public static int RecurLevenshteinDistance(String a, int lenA, String b, int lenB) {    if (lenA == 0)         return lenB;    if (lenB == 0)        return lenA;
    int cost = (a.charAt(lenA-1) == b.charAt(lenB-1) ? 0 : 1);
    int dist1 = RecurLevenshteinDistance(a, lenA - 1, b, lenB) + 1;    int dist2 = RecurLevenshteinDistance(a, lenA, b, lenB - 1) + 1;    int dist3 = RecurLevenshteinDistance(a, lenA - 1, b, lenB - 1) + cost;
    return Math.min(Math.min(dist1,dist2),dist3);  }
public static void main(String[] args) {    String a = "kitten";    String b = "sitting";    int re = RecurLevenshteinDistance(a, a.length(), b, b.length());    System.out.println(re);//输出：3}

显然递归的蛮力法求解效率低下，因为有大量重复的计算过程，其时间复杂度可以被证明是指数级的，不可取。

第二个层面考虑：为避免递归带来的大量重复计算过程，很容易得出求解LD和DLD的最快算法就是自底向上迭代求解的动态规划算法。容易分析得出动态规划算法计算LD和DLD的时间复杂度都是O(m*n)。其中m和n分别是字符串a和b的长度。

动态规划实现也非常简单，下面给出一种Levenshtein Distance动态规划Java实现，仅供参考：

public static int LevenshteinDistance(String a, String b) {    int[][] dist = new int[a.length()+1][b.length()+1];    for (int i = 0; i <= a.length(); i++)        dist[i][0] = i;    for (int j = 0; j <= b.length(); j++)        dist[0][j] = j;
    for (int j = 1; j <= b.length(); j++) {        for (int i = 1; i <= a.length(); i++) {            int cost = (a.charAt(i-1) == b.charAt(j-1) ? 0 : 1);            int dist = Math.min(dist[i - 1][j] + 1, dist[i][j - 1] + 1);            dist[i][j] = Math.min(dist, dist[i - 1][j - 1] + cost);        }    }    return dist[a.length() - 1][b.length() - 1];}
public static void main(String[] args) {    String a = "kitten";    String b = "sitting";    int dist = LevenshteinDistance(a, b);    System.out.println(dist); //输出：3}

可以得出结论：单纯求解两个字符串的LD或DLD，动态规划解法的时间复杂度O(mn)就是最快解法了。然后我们要解决得是搜索引擎场景下的大规模模糊查询中频繁用到的相似字符串查找，有其特殊性。于是进入第二个层次考虑问题。

• 搜索引擎场景下查找相似字符串是存在一个数量确定的候选字符串集合，用以进行与目标字符串a的相似性判断筛选，该候选集合一般是搜索引擎倒排索引的term词典集合；并且该倒排term词典集合规模一般可能很大，比如千万或上亿规模；
• 搜索引擎场景下查找相似字符串操作的次数可能非常频繁，比如用户的每一个模糊查询请求都将引发一次倒排term词典集合的相似字符串查找筛选过程，几千甚至上万的qps，就意味着每秒就要发生几千甚至上万次查找相似字符串的操作；
• 在搜索引擎场景下，我们往往只关心与目标检索串非常相似，也即编辑距离非常小的情形。比如参考流行开源搜索引擎es的做法是只关心编辑距离<=2,即0或1或2三种编辑距离的候选词。因为在搜索引擎场景下，我们很难想象提供一个与用户输入的检索目标词很不相似或很不相关的结果给用户是明智的。

遍历搜索引擎索引倒排term词典集合中的全部 term,对其任意一个倒排 term字符串b，都以动态规划方法计算b与目标字符串a的LD或DLD编辑距离值，最后取结果编辑距离值最大的前N个倒排 term输出即可。

1. 依次遍历倒排term词典集合过程比较耗时
   考虑到一般搜索引擎索引中倒排term词典集合规模通常很大，经常达到千万或上亿规模，而查询请求又可能很频繁，如果对每一次模糊查询请求，都要依次从头到尾遍历倒排term词典集合可能比较耗时。
   于是很自然的优化目标是：能否做到不必遍历倒排term词典集合中的所有的term？换句话说，是不是能对这个大规模的倒排term字符串集合做个预处理，使其按照某种特定的内存布局预先存储好，比如类似trie树一类的tree数据结构，这样一来，遍历这样的tree类数据结构存储的大规模倒排term词典集合时，有可能在一些正确的理论指导下，可以避开tree类数据结构中的某些根本不需要遍历的分支，从而减少遍历term数量，以提高遍历效率。这个过程可以被形象地称为"减枝"。
   经过调研我们发现：这个存储倒排term词典集合的类似trie树一类的数据结构，在流行开源搜索引擎es的内核实现组件lucene的较新的版本（lucene4以后）中已经有实现，叫做FST（Finite State Transducer）词典，是一种有限状态机，lucene 4中有java代码的开源实现。
   FST有两个优点：1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；2）查询速度快。O(len(str))的查询时间复杂度。
   FST的原理和实现细节网络上能够轻松搜索得到，不是本文论述的重点。本文略过不表。
   那么，现在问题演变为：

   基于FST词典表达的倒排term表，该有怎么样的“剪枝”策略，以应对大规模连续判断每个term字符串b是否与给定的目标字符串a足够相似，即编辑距离LD或DLD足够小，比如小于预先设定好的阈值1或者2？

   该问题的解决方案是提升搜索引擎中查找相似字符串效率的重要手段，是非常有价值的思路，限于篇幅本文暂时不讨论该主题，留待后续系列文章另行论述。
   大规模计算每一个候选倒排term字符串b与目标字符串a的编辑距离比较耗时
   如前文提到的，动态规划方法求解字符串a和b间的LD/DLD，时间复杂度是O(m*n).( m和n分别是a和b的长度)，因为动态规划要自底向上依次迭代计算a、b字符串的每一种前缀子串对组合间的编辑距离。这个过程在大规模遍历倒排词典集合每次都要计算时显得效率较低。怎么优化这个过程呢？
   如前文所提到，考虑到在搜索引擎场景下，我们往往只关心与目标检索串非常相似，也即编辑距离非常小的情形（比如参考流行开源搜索引擎es的做法是只关心编辑距离<=2,即0或1或2三种编辑距离的候选词）的特点，于是把问题限定到：在只需要迭代筛选找出与目标词a编辑距离LD/DLD是0、1、2的所有候选词的前提下，如何快速大规模筛选相似的候选字符串呢?
   显然，如果依然采用朴素的遍历倒排词典集合中每一个词b，都与目标词a用动态规划先求出编辑距离，然后判断是否<=2，如果是就保留否则就丢弃的做法，显然显得不那么明智。因为如果编辑距离大于2的字符串，其实是没有必要耗费O(m*n)的时间先计算编辑距离的，因为显然可以基于某种判断提前终止计算，因为这些编辑距离>2的候选字符串明显不那么相似。
   于是解决问题思路演变为：
   如何加速判断字符串a和b是否非常相似，即编辑距离LD或DLD是否<=2, 而不是缓慢地用动态规划去先计算编辑距离 再判断？
   稍作调研就会发现：该问题解决方案很明确–引入自动机(Automaton),具体来说是引入确定有限状态自动机（deterministic finite automaton, DFA）。LD和DLD两种编辑距离对应两种不同的确定有限状态自动机(DFA）。这两种DFA实现差别比较大，难度差别也很大。具体来说Damerau Levenshtein DFA 实现复杂程度 远高于 Leveshtein DFA。
   经过大量调研互联网或其他公开的资料途径，我们发现：
   1）Leveshtein DFA的编程实现相对容易，可参考的实现过程也比较多。但理论论证Leveshtein DFA实现正确性的公开资料也及其匮乏，或者不够系统；
   2）Damerau Levenshtein DFA的编程实现几乎没有，即使有一些不多的开源实现过程都是漏洞百出，正确性存疑。当然理论论证Damerau Leveshtein DFA实现过程正确性的公开文章资料亦是寥寥无几。
   有鉴于此，于是正式引入本文要重点论述的主题，也是本文提出的技术创新点所在：

   本文将创造性地提出Damerau Levenshtein DFA构建方法论和伪代码实现，并且以定理论证方式给出Leveshtein DFA和Damerau Levenshtein DFA构建和实现方法正确性的理论证明。

   
   
   
   

4.1 熟悉自动机和DFA

1. 有限自动机FA(Finite Automata)
   我们一般提到的自动机都是指有限自动机（或者叫有穷自动机）。
   在计算机科学中有穷自动机分为DFA和NFA：
• 确定的FA (Deterministic finite automata, DFA)
• 非确定的FA (Nondeterministic finite automata, NFA)
有穷自动机 ( Finite Automata，FA )由两位神经物理学家MeCuloch和Pitts于1948年首先提出，是对一类处理系统建立的数学模型
这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）
系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变
2.确定的有穷自动机DFA(Deterministic Finite Automata)
M = ( S，Σ ，δ，s0，F )
• S：有穷状态集
• Σ：输入字母表，即输入符号集合。假设ε不是 Σ中的元素
• δ：将S×Σ映射到S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态。
• s0：开始状态 (或初始状态)，s0∈S
• F：接收状态（或终止状态）集合，F⊆ S
  例如下图所展示的一个DFA

3. 非确定的有穷自动机NFA(NonDeterministic Finite Automata)
   M = ( S，Σ ，δ，s0，F )
   例如下图所展示的一个NFA
   

• S：有穷状态集
• Σ：输入符号集合，即输入字母表。假设ε 不是Σ中的元素
• δ：将S×Σ映射到2S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合
• s0：开始状态 (或初始状态)，s0∈S
• F：接收状态（或终止状态）集合，F⊆ S

有穷状态自动机解决问题的思路，本质上就是: 在预处理阶段我们生成一个包含: 要素1）一系列抽象出来的状态集合S，（当然S里包含初始状态s0和可以被接受的状态的集合F,这二者能够被确定）；要素2）一个包含所有可能输入符号的输入符号集合Σ；和要素3）对于任意属于状态集合S的任意元素s, 以及属于输入符号集合Σ的任意符号c，能够明确转换生成新状态的状态转换函数 δ(s,c) 。

当具备了这三要素后，就可以在后续大量判别过程中，从头到尾依次迭代给定的每个输入符号序列，比如给定的目标字符串a, 然后不断地 转化生成新的状态 ，并且同步判断每一步产生的新状态是否可被接受，直到输入符号序列迭代结束。通过这样的方式 一般能在线性时间甚至更快的时间复杂度内快速解决问题。

4.2 DFA应用于搜索引擎中查找相似字符串的直观理解

• 如何快速确定某个字符串b与目标字符串a是否最相似，即编辑距离LD或DLD<=2？

• 所有可能的有限的状态集合S,初始状态S0，能被接受的所有状态集合F；
• 输入符号集合Σ ：表明所有可能输入的符合的集合；
• 状态转换函数δ：Convert(State s, Char c) -> newState

PRE-PROCESS(a)            //预处理生成目标字符串a对应的dfa结构1 dfa <- a              
CHECK-SIMILAR-STRINGS (dfa,b) //判断b是否与a相似      1 s0 <- dfa.initState()     2 s  <- s0                   //以dfa的初始状态S0初始化状态s3 n  <- length[b]4 for i <- 1 to n            //依次遍历待判断字符串b的每个字符c5     do c <- b[i]           6        s <-dfa.Convert(s,c)7        if null == s         //无状态，返回false,提前终止流程8           then return false9           else if dfa.IsAccept(s)    10                  then return true //字符c被接受，完成判断11                  else continue

• 预处理过程生成目标字符串a的dfa，时间复杂度是O(length[a]) 。后文我们会详细分析该过程的时间复杂度。
• 第6行dfa状态转化过程耗费常量时间。因为dfa内部的所有States都被提前缓存好了，转化过程只是一个逻辑判断过程而已。
• 第4~11行迭代遍历待check字符串b，可能在第8行或者第10行提前终止迭代过程，因此最大迭代length[b]次，因此每次判断时间复杂度是O(length[b])。

4.3 Levenshtein DFA

4.3.1 分析 Levenshtein DFA

• 状态：跟状态有关的要素有3个分别是：S是状态集合，s0是初始状态，F是接受状态集合；

•  转换函数：而δ是定义在S和Σ上的转换函数，能生成一个新的状态。

•  输入符号：此外Σ 是输入符号集合；

那么Levenshtein DFA中这5个要素该如何定义呢？怎么直观感性理解呢？

本质上来看，我们是要对目标字符串a预处理以构造编辑距离LD<=最大编辑距离maxEdit(2或1)的DFA，下面我们以目标字符串a为“woof",编辑距离LD <=1为例来说明Levenshtein DFA的构造过程。

首先我们直观思索一下Levenshtein DFA的状态应该是什么结构或怎么定义能满足我们解决问题的诉求，我们的诉求是：对任意给定的字符串b,比如wof，判断b和目标字符串a，即 wof 和 woof 的LD编辑距离是否满足<=1的条件。按照前文提到的动态规划法自底向上解决问题的思路，我们可能的做法应该是：

1. 依次迭代列出b串和a串的所有前缀子串。

2. 自底向上迭代求出每一个前缀子串组合见的编辑距离。

如下面伪代码所示：

#a是目标字符串，b是待判断字符串for i <- 0 to length[b]    do for j <- 0 to length[a]           do 计算b[..i] 与 a[..j] 前缀子串间的 编辑距离dist[i,j]              #而 dist[i,j] 跟dist[i-1,j],dist[i,j-1],dist[i-1,j-1]以及a[i]和b[j]是否相等有关系

{
  { 0,1,2,3,4 },
  { 1,0,1,2,3 },
  { 2,1,0,1,2 },
  { 3,2,1,1,1 }
}

Start(String a )
1   n <- length[a]
2   State s = {0,1,...,n}
3   return s

IsMatch(State s, maxEdit)1   n <- length[s]2   return s[n-1] <= maxEdit

状态集合S由{  { 0,1,2,3,4 },  { 1,0,1,2,3 },  { 2,1,0,1,2 },  { 3,2,1,1,1 }}演变为：{  { 0,1,2,2,2 },  { 1,0,1,2,2 },  { 2,1,0,1,2 },  { 2,2,1,1,1 }}

基于对Levenshtein DFA 中状态值可以定义为 编辑距离LD值的集合的认识, 再参考第1节中提到的维基百科中对LD的定义，借助动态规划方法思想，容易写出在上一个状态s前提下，Levenshtein DFA 处理新读入任何字符c 生成新状态的“步进函数”Step 伪代码。（Step函数作用为：在上一个状态基础上，读入一个新字符，转换到下一个状态)

 Step(String a,  State s,  Char c)
 1   State snew = [s[0] + 1 ]
 2   for i <- 1 to length[a]
 3       do  cost = (a[i-1] == c ? 0 : 1)
 4           dist = Min(s[i-1] + cost, s[i] + 1, snew[i-1] +1 ) 
 5           snew.append(Min(dist, maxEdit+1))//根据定理1，maxEdit+1能代表所有无效的编辑距离值  
 6   return snew

• 状态转换函数 δ

• 输入符号集合Σ

 Step(String a,  State s,  Char c1)
 1   State s1 = [s[0] + 1]
 2   for i <- 1 to length[a]
 3       do  cost = (a[i-1] == c1 ? 0 : 1)
 4           dist = Min(s[i-1] + cost, s[i] + 1, s1[i-1] +1 ) 
 5           s1.append( Min(dist, maxEdit+1) ) 
 6   return s1

 Step(String a,  State s,  Char c2)
 1   State s2 = [s[0] + 1]
 2   for i <- 1 to length[a]
 3       do  cost = (a[i-1] == c2 ? 0 : 1)
 4           dist = Min(s[i-1] + cost, s[i] + 1, s2[i-1] +1 ) 
 5           s2.append( Min(dist, maxEdit+1) ) 
 6   return s2

Transitions(String a)
1   Set(a) <- a所有包含的字符组成的集合
2   c0     <- 为任意 不属于Set(a)的抽象字符
3   return { Set(a), c0}

Transitions(String a)
1   Set(a) <- a所有包含的字符组成的集合
2   Set(a) <- Set(a).RemoveDuplicate()   #元素去重
3   c0     <- 为任意 不属于Set(a)的抽象字符
4   return { Set(a), c0}

注意，根据定理5,Transtions()函数的前提条件又多了2个，即：任意上一个状态s 和 最大编辑距离：maxEdit。

Transitions(String a, State s, int maxEdit)
1    n <-length[a]
2    resultChars = {}    #结果字符集合，初始化为空集
3    for i <- 0 to n-1 
4        do if s[i] <= maxEdit
5              then resultChars.Append(a[i])
6    resultChars <-  resultChars.RemoveDuplicate()   #集合去重
7    c0     <- 为任意 不属于resultChars 的抽象字符
8    resultChars.Append(c0)
9    return resultChars

 Step(String a,  State s,  Char c) 1   State snew = [0] 2   for i <- 1 to length[a] 3       do  cost = (a[i-1] == c ? 0 : 1) 4           dist = Min(s[i-1] + cost, s[i] + 1, snew[i-1] +1 )  5           snew.append( Min(dist, maxEdit+1) )  6   return snew

dist = Min(s[k], s[k+1] + 1,  snew[k] + 1)

dist = Min(maxEdit + 1, s[k+1] + 1,  snew[k] + 1)

dist = Min(s[k], s[k+1] + 1,  snew[k] + 1)

dist = Min(maxEdit + 1, s[k+1] + 1, snew[k] + 1

dist = Min(s[k] + 1, s[k+1] + 1,  snew[k] + 1)

dist = Min(maxEdit + 1, s[k+1] + 1,  snew[k] + 1)

注意：本文为了简化讨论，只讨论单字节字符的情况。对于多字节字符比如汉字字符有关的Levenshtein问题解决方案我们后续另行系列文章讨论。

4.3.2 构建 Levenshtein DFA和性能分析

1   Class State {2   public:3      int hash(); 4      int equal(const State& rhs);5  6   private:7      Arrays[0..n]    m_edits;  //编辑距离值的数组，长度为n+1，n = length[a]8   }

HashMap< State, HashMap<Char, State>  >  cachedStatesMap;

1. 定义Levenshtein DFA
   Levenshtein DFA 伪代码示意如下：
   
   

   1   Class LevenshteinDFA {
   2   public:
   3   State           Start();  //初始状态
   4   State           Step(State s, Char c); //状态转化
   5   bool            IsMatch(State s);      
   6   bool            CanMatch(State s);
   7   Array<Char>     Transitions(State s); //获取输入符号集合
   8
   9   private:
   10  String        m_str;      //目标字符串
   11  int           m_maxEdit;  // 最大编辑距离阈值，只能为1或2
   12  }
   

   初始状态伪代码示意如下：

   State LevenshteinDFA::Start() 
   1   n <- length[ m_str ]
   2   s = {0}
   3   for i <- 1 to n
   4       do s.Append(i)
   5   return State(s)
   

   状态转化函数Step()伪代码示意如下：

   State  LevenshteinDFA::Step(State s, Char c )
    1   State snew = [s[0] + 1 ]
    2   for i <- 1 to length[m_str]
    3       do  cost = ( m_str[i-1] == c ? 0 : 1 )
    4           dist = Min(s[i-1] + cost,  s[i] + 1,  snew[i-1] +1 ) 
    5           snew.Append( Min(dist, m_maxEdit+1) )//根据定理1，maxEdit+1能代表所有无效的编辑距离值
    6   return snew
   

   获取输入符号Transitions()伪代码示意如下：

   Array<Char>  Transitions(State s)
   1    n <- length[ m_str ]
   2    resultChars = {}    #结果字符集合，初始化为空集
   3    for i <- 0 to n-1 
   4        do if s[i] <= m_maxEdit
   5              then resultChars.Append(m_str[i])
   6    resultChars <-  resultChars.RemoveDuplicate() #集合去重
   7    c0   <- 为任意 不属于resultChars 的抽象字符
   8    resultChars.Append(c0)
   9    return resultChars
   

   IsMatch(s) 功能是判断s是否是最终可以被接受的状态，即最终与目标字符串是否相似。CanMatch(s) 功能是判断s是否是潜在可以被纳入考虑状态。根据LD的定义可知编辑距离值迭代结果只会不变或增大1，永远不会减小。显然如果s序列中的最小的编辑距离值都> maxEdit，那么该状态s后续怎么迭代也不可能产生<= maxEdit的新状态，于是这样的状态可以永远不被考虑，即not CanMatch。
   IsMatch 和CanMatch 伪代码如下：

   bool LevenshteinDFA::IsMatch(State s) 
   1    return s.Last() <= m_maxEdit //最后一个编辑距离值是否<= maxEdit 
   
   bool LevenshteinDFA::CanMatch(State s) 
   1    return s.Min() <= m_maxEdit //最小的编辑距离值是否<= maxEdit

   1.初始化dfa和全局状态缓存变量cachedStatesMap
   

   1  HashMap<State,HashMap<Char,State> >  cachedStatesMap;
   2  LevenshteinDFA dfa(str, maxEdit);
   

   递归搜索所有可能的状态转换关系并缓存至cachedStatesMap

   RecursiveExploreDFA(State s)
   1  if !cachedStatesMap.Contains(s)
   2     then cachedStatesMap[s] <- HashMap();
   3          for c in dfa.Transitions(s)
   4              do  news <- Step(s,c)
   5                  if  dfa.CanMatch(news)
   6                      then RecursiveExploreDFA(news)
   7                  cachedStatesMap[s][c] <- news
   

   构建Levenshtein DFA

   BuildLevenshteinDFA()
   1  RecursiveExploreDFA(dfa.Start())
   

2. 判断字符串相似性

   bool IsStringSimilar(String b)
   1   n <- length[b]
   2   s <- dfa.Start()
   3   for i <- 1 to n
   4       do if !cachedStatesMap.Contains(s) or !cachedStatesMap[s].Contains(b[i])
   5          then return false
   6          s <- cachedStatesMap[s][b[i]]
   4   return dfa.IsMatch(s)
   

3. 性能分析
   令目标字符串a 长度n = length[a] ; 待判断字符串b长度为m= length[b]；由上述伪代码容易分析得出：IsStringSimilar() 执行m次，复杂度为O(m); BuildLevenshteinDFA() 过程耗时取决于 RecursiveExploreDFA()函数递归次数和 RecursiveExploreDFA()第三行迭代Transitions()字符集和的次数。而Transitions()字符集和规模虽然之前做了优化，但规模最坏情况仍是O(n)。RecursiveExploreDFA()函数递归次数等于 dfa中最终状态个数sc。
   下面分析一下sc的规模：首先容易知道长度为i的字符串 与 长度为j的字符串的LD编辑距离值至少为|i-j|。利用动态规划方法考虑一共可能出现多少种不同的状态值,如下图所示：

   public static int LevenshteinDistance(String a, String b) {
       int[][] dist = new int[a.length()+1][b.length()+1];
       for (int i = 1; i <= a.length(); i++)
           dist[i][0] = i;
       for (int j = 1; j <= b.length(); j++)
           dist[0][j] = j;
   
       for (int j = 1; j <= b.length(); j++) {
           for (int i = 1; i <= a.length(); i++) {
               int cost = (a.charAt(i-1) == b.charAt(j-1) ? 0 : 1);
               int dist = Math.min(dist[i - 1][j] + 1, dist[i][j - 1] + 1);
               dist[i][j] = Math.min(dist, dist[i - 1][j - 1] + cost);
           }
       }
       return dist[a.length() - 1][b.length() - 1];
   }
   

   上述伪代码第8行迭代待检查字符串b的每一个前缀子串b[…j]时，对应该前缀子串的该行编辑距离值中，只有 j-maxEdit ~ j+ maxEdit 一共2maxEdit +1 列编辑距离的值有可能<=maxEdit。其它列的编辑距离值 必定都大于maxEdit,根据定理1，都可以用maxEdit +1 值等价代替。即当maxEdit=1时只有21 +1 = 3; 当maxEdit=2时只有2*2+1=5列编辑距离值<=maxEdit，其它列都是maxEdit+1。maxEdit=1时，<=maxEdit的值有0或1两种；maxEdit=2时<=maxEdit的取值有0,1,2三种；也就是说 所有编辑距离值组合中最多只有 2^3+1 或 3^5+1种组合，即最多只有9种或244种状态。因此对于固定的maxEdit （1或2）， 状态个数sc 也是常量值。
   综合以上可得，BuildLevenshteinDFA时间复杂度为O(sc * length[n]) 即O(n)，为线性的，而且更重要的是，BuildLevenshteinDFA过程是预处理过程，是一次性过程。而每次查找判断字符串b与a的相似性时，复杂度为O(length[b]),即O(m),也是线性的。这线性时间复杂度明显优于动态规划法的O(m * n)时间复杂度。
   最后给出一个目标字符串为a=“北京北站”,maxEdit=1构建的LevenshteinDFA示意图，图中阴影椭圆图形表示该状态是可接受的，即LD编辑距离<=1。字符*表示任意不属于目标字符串a所有包含字符集合{‘北’,‘京’,‘站’}的特殊字符。

4.4 创新点：Damerau Levenshtein DFA

4.4.1 定义Damerau Levenshtein

4.4.2 分析 Damerau Levenshtein DFA

1. 状态
   Damerau Levenshtein DFA 之所以比Levenshtein DFA复杂，就是因为它的状态复杂。根据定义，生成的下一个状态的DLD序列值不仅与当前状态的DLD值有关，还可能在相邻字符交叉相等的情况下，与上一个状态的DLD有关。（LD不同的是只与上一个状态的LD值有关）。因此很自然地，将 上一个状态的DLD值序列 prevDists 和当前状态的DLD值序列 curDists，以及 prevDists 经由什么字符prevChar 转换生成了当前curDists。令字符串a为目标字符串，则Damerau Levenshtein DFA状态State伪代码如下：

   Class  State {
      bool Equal(const State& s);
      int  Hash(); 
   
   public:
      Array[0..n]       m_prevDists;//上一个状态的DLD值序列，n=length[a],不能为null
      Char              m_prevChar; //m_prevDists 经由m_prevChar转换生成了m_curDists，可以为null
      Array[0..n]       m_curDists; //当前状态的DLD值序列,可以为null
      
      String            m_str; //目标字符串
      int               m_maxEdit; //最大编辑距离阈值，必须为1或2 
   }
   

   通过前文4.3.2节对Levenshtein DFA的性能分析类比知道， m_prevDists或m_curDists的可能取值的数量最多可能为9种或244种。m_prevChar取值数量为length[a], 现在如果放任 m_prevDists、m_prevChar、m_curDists 三种变量组合，那么Damerau Levenshtein DFA 状态集合的规模将爆炸式增长，姑且称之为“状态爆炸”。根据对LD性能分析我们大体类比会猜测到 BuildDamerauLeveshteinDFA的时间复杂度大体也与DLD dfa的状态集合规模正相关。又因为构建DFA的过程就是缓存全部可能状态的过程。因此，这种单纯放任状态数量暴涨的朴素方式必然导致 构建DamerauLevenshtein DFA过程时间复杂度高，且耗费内存较大，不可取！
   如何解决“状态爆炸”问题，提高构建DamerauLevenshtein DFA的效率并减少其内存消耗呢？这是本文重要的创新点之一。 下面详细展开论述。
2. Damerau Levenshtein DFA状态消减策略
   消减状态数量本质上就是要把大量逻辑上可以等价对待状态视为1个状态即可。因为所有状态最终是要被缓存到全局Hash表中的。因此消减Damerau Levenshtein DFA状态 策略等价于 为State类数据结构定义一个逻辑完善且正确的 Equal()函数。
   下面给出Damerau Levenshtein DFA状态消减策略的一个定理。
   定理6：在构造目标字符串a的Damerau Levenshtein DFA时，
   对于任意状态s，如果不存在 任意一个k 满足 0 < k < length[a] ,使得
   1）a[k] != a[k-1]
   2）a[k] == s.m_prevChar
   3）s.m_prevDists[k-1] < Min( maxEdit, s.m_curDists[k] , s.m_curDists[k+1])
   以上3个条件同时成立，则 基于状态s为上一个状态的任意状态转换过程中对新编辑距离的计算逻辑可忽略“Damerau 条件分支”，这样不影响最终构建Damerau Levenshtein DFA结果的正确性。

   注：“Damerau 条件分支”前文4.4.1节提到过。

   证明：
   反证法，假定任意存在一个k 满足 0 < k < length[a]，使得 定理6中3个条件同时成立，那么就可能存在1个字符c == a[k-1] 基于状态s进行状态转换，因为c == a[k-1] 且a[k] == s.m_prevChar , 同时a[k] != a[k-1]， 即相邻两个字符不相等，但交叉相等，于是根据DLD的定义，新编辑距离值计算必定从形式包含了“Damerau 条件分支”；于是，新的编辑距离值dist 必定为 s.m_curDists[k]+1, s.m_curDists[k+1] + 1, s.m_prevDists[k-1] + 1 三者中的最小值，又根据定理6条件3)得知，s.m_prevDists[k-1] 是 s.m_curDists[k] 和 s.m_curDists[k+1] 二者的最小值，因此dist值必定恒等于 s.m_prevDists[k-1] + 1 。根据条件3)同时s.m_prevDists[k-1] < maxEdit， 因此dist < maxEdit +1 <= maxEdit。即 最终的新的编辑距离值dist是有效的，且其值来源于 ““Damerau 条件分支””。因此新的编辑距离迭代实质上也是发生在了“Damerau 条件分支” 。即：只要任意存在一个k 满足 0 < k < length[a]，使得 定理6中3个条件同时成立，那么基于状态s为上一个状态，字符c==a[k-1]的状态转换过程中对新编辑距离的计算逻辑 就必定 从形式和实质上都包含“Damerau 条件分支”。反之，迭代目标字符串的每一个位置k，如果都不能使得下一次状态转换逻辑计算过程包含“Damerau 条件分支”，则 该基于该状态s为上一个状态的转换实际就是一个不包含“Damerau 条件分支”的转换，忽略“Damerau 条件分支”，不影响最终构建Damerau Levenshtein DFA结果的正确性。证明完毕。
   根据定理6可以给出如下伪代码,判断状态s是否可能是实质包含“Damerau 条件分支”，即 IsPossibleDamerau()

   IsPossibleDamerau(State s)
   1   n <- length[a]
   2   for i <- 1 to n-1
   3       do if (a[i] != a[i-1] and a[i] == s.m_prevChar 
   4                   and s.m_prevDists[i-1] < Min(maxEdit, s.curDists[i], s.curDists[i+1]) )
   5            then return True
   6   return False
   

   于是根据IsPossibleDamerau，本文给出State的Equal() 伪代码，按照如下示意：

   bool  State::Equal(const State& rhs)
   1    if  m_curDists != rhs.m_curDists
   2        then return False
   3    isIn    <- m_str.Contains(s.m_prevChar)
   4    isInRhs <- m_str.Contains(rhs.m_prevChar)
   5    if isIn != isInRhs
   6       then return False
   7    else if False == isIn
   8            then return True
   9         else if m_preChar != rhs.m_prevChar
   10                then return False
   11                else if IsPossibleDamerau(*this) or IsPossibleDamerau(rhs)
   12                        then return m_prevDists == rhs.m_prevDists
   13                        else return True
   

   State::Equal() 实现算法也是本文的重要创新点，此处不再逐句解释。总的看来该函数的核心思想就是 尽量剥离DamerauLevenshtein的“Damerau条件分支”特性去判断相等，那样的话就如同Levenshtein Distance的状态Equal判断，非常确定。实际中大量测例表明基于此消减策略可以极大地减少状态的数量。

   注：本文提出的状态消减策略缓解Damerau Levenshtein Automaton 状态爆炸后，状态集合数量的理论值能达到多少呢？是否还有可能提出别的更进一步的状态消减策略以进一步缓解“状态爆炸”问题呢？感兴趣的读者可以循着这两个思路继续探讨研究一下。

   此外因为State要被缓存到全局，所以不可以避免要对状态进行散列hash， Hash()函数逻辑很简单，直接按照m_curDists值去散列即可。
3. 转换函数
   转换函数比较简单，直接按照DLD的定义编写即可。
4. 输入符号
   DamerauLevenshtein DFA的输入符号方面，Transitions() 函数实现过程同样遵循定理5。理解过程与Levenshtein 相同。

4.4.3 构建Damerau Levenshtein DFA和性能分析

1. 本文提出的状态消减策略缓解Damerau Levenshtein 自动机状态爆炸后，状态集合数量的理论值能达到多少呢？是否还有可能提出别的更进一步的状态消减策略以进一步缓解“状态爆炸”问题呢？
2. 如何实现FST（Finite State Transducer）词典数据结构应用到搜索引擎中的倒排词典表，以提高搜索引擎系统的性能？
3. 考虑到中文等unicode字符表示方法中用多个字节表示1个unicode字符（如中文字符），在构造FST词典时有何特殊性？
4. Levenshtein/Damerau Levenshtein DFA技术在应用到FST词典上进行近似字符串查找时，有什么有效的“减枝”策略来加速查找过程呢？

丁斌：58同城TEG搜索平台部后端资深开发工程师，专注于搜索引擎相关技术，目前主要致力于58搜索内核功能开发和搜索引擎系统性能优化。2010年硕士毕业于清华大学软件工程专业。目前58搜索团队正在招聘搜索研发工程师，算法和工程都需要，感兴趣的同学可以将简历直接发送至: luke@58.com。

1. https://zh.wikipedia.org/wiki/%E8%90%8A%E6%96%87%E6%96%AF%E5%9D%A6%E8%B7%9D%E9%9B%A2

2. https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

3. https://julesjacobs.com/2015/06/17/disqus-levenshtein-simple-and-fast.html

4. https://github.com/BurntSushi/fst

5. https://blog.burntsushi.net/transducers/