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

2021-03-01 00:00:00 集合 字符串 状态 距离 字符

导读

本文主要介绍如何基于Levenshtein和Damerau Levenshtein自动机技术高效地解决在搜索引擎系统中相似字符串快速查找问题的技术原理和操作实践。文中创造性地提出一种Damerau Levenshtein自动机的有效构建算法，并创造性地给出了利用Levenshtein自动机和Damerau Levenshtein自动机技术，解决快速查找相似字符串问题实现方案的正确性理论依据论证。


背景

首先从字符串相似查找谈起。相似字符串查找，顾名思义即查询与目标字符串在物理上词形相似的字符串集合，在搜索引擎中有很多应用。其中比较常见的有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）。其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，长公共子串长度只允许增加、删除字符这两个编辑操作。

一些主流搜索引擎如开源搜索引擎Elastic Search都采用莱文斯坦距离（Levenshtein distance），同时包含更进一步的Damerau Levenshtein距离来度量字符串相似程度，以此为搜索引擎中的模糊搜索和拼写纠错提供基础解决方案。
由此引入本文将重点讨论的主题：Levenshtein和Damerau Levenshtein 自动机技术在58同城搜索引擎场景下的应用实践。在进入下一节之前，先用简短的篇幅迅速描述一下Levenshtein距离和Damerau Levenshtein距离的定义。

  • 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 == )         return lenB;    if (lenB == )        return lenA;
    int cost = (a.charAt(lenA-1) == b.charAt(lenB-1) ?  : 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 = ; i <= a.length(); i++)        dist[i][0] = i;    for (int j = ; 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) ?  : 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三种编辑距离的候选词。因为在搜索引擎场景下，我们很难想象提供一个与用户输入的检索目标词很不相似或很不相关的结果给用户是明智的。
鉴于搜索引擎场景下查找相似字符串问题的以上特点，如何高效地解决问题：在搜索引擎场景中如何快速找出与目标字符串a相似的前N个候选字符串集合 是否有一些更有效、更的解决方案呢？下面展开分析：
首先一个朴素直观的解法是：
遍历搜索引擎索引倒排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构建和实现方法正确性的理论证明。


进阶

首先简单谈一下DFA（Deterministic Finite Automata，确定的有穷自动机）和自动机(Automaton)。
很多人一听到“自动机”就觉得很陌生高深难理解,莫名地恐惧自动机。很多计算机科班同学早接触有限自动机可能是在本科课程《编译原理》中，后来可能又会在CLRS《算法导论》黑宝书中的《利用优先自动机进行字符串匹配》一节中接触到用有限自动机理论解决字符串匹配以及改进版的KMP算法等内容。因此在进入正题之前，本文先来迅速补充一下关于有限自动机的相关知识，尽力熟悉一下有穷自动机解决问题的本质，消除自动机恐惧症。

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


  1. 非确定的有穷自动机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
    注意：DFA与NFA的区别在于，DFA对于每一次输入只能产生一个结果，结果是确定的。而NFA的一次输入可能产生多个结果。如上图用红色方框标出的位置，DFA的每一次输入只对应一个结果，而NFA的依次输入可能对应多个结果，形成一个结果集。
    综合以上：我们不妨尝试高度抽象且不失直观感性地总结一下有穷自动机，尤其是DFA解决问题的思路：
    有穷状态自动机解决问题的思路，本质上就是: 在预处理阶段我们生成一个包含: 要素1）一系列抽象出来的状态集合S，（当然S里包含初始状态s0和可以被接受的状态的集合F,这二者能够被确定）；要素2）一个包含所有可能输入符号的输入符号集合Σ；和要素3）对于任意属于状态集合S的任意元素s, 以及属于输入符号集合Σ的任意符号c，能够明确转换生成新状态的状态转换函数 δ(s,c) 。
    当具备了这三要素后，就可以在后续大量判别过程中，从头到尾依次迭代给定的每个输入符号序列，比如给定的目标字符串a, 然后不断地 转化生成新的状态 ，并且同步判断每一步产生的新状态是否可被接受，直到输入符号序列迭代结束。通过这样的方式 一般能在线性时间甚至更快的时间复杂度内快速解决问题。
    后面我们也将通过构造Levenshtein DFA或 Damerau Levenshtein DFA解决字符串相似性判断问题来加深对上面这段话的理解。
    接下来我们给出一些将DFA应用于搜索引擎中查找相似字符串的直观理解。

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

    首先我们再重新审视一下我们的待解决目标问题：
    • 如何快速确定某个字符串b与目标字符串a是否相似，即编辑距离LD或DLD<=2？
    前文已经提到，单纯用动态规划法先计算a和b的LD/DLD，再判断是否<=2，时间复杂度是O（length[a] * length[b])，在大规模判断中每次都这样操作太慢。
    引入DFA优化这一过程的思想在于：提前对目标字符串a进行预处理，生成一个DFA，该DFA的核心要素包括：
    • 所有可能的有限的状态集合S,初始状态S0，能被接受的所有状态集合F；
    • 输入符号集合Σ ：表明所有可能输入的符合的集合；
    • 状态转换函数δ：Convert(State s, Char c) -> newState
    有了DFA以后，确定某个字符串b与目标字符串a的相似问题，就可以按如下伪代码示例进行操作：
    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])。
    可见：引入DFA后，增加了预处理过程O(length[a])的时间复杂度，每次相似性判断的时间复杂度从动态规划算法的O（length[a] x length[b])降低至O(length[b])。该过程的前提是正确构造出正确高效的DFA结构。 我们接下来论述该主题。

    4.3 Levenshtein DFA

    4.3.1 分析 Levenshtein DFA
    通过前文4.1节我们已知一个DFA有5要素组成：M = ( S，Σ ，δ，s0，F )，5要素可以归结为3类要素如下：

    • 状态：跟状态有关的要素有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串的所有前缀子串。


    		 空
    		 w
    		 wo
    		 woo
    空



    w



    wo



    woo



    如上方表格示意，行为目标字符串a自底向上的每一个前缀子串,列为待检查字符串b自底向上的每一个前缀子串。（注意空串也是前缀子串,不能省略，因为动态规划方法自底向上解决问题的一个重要基础就是空，空串或空集合）。

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

    如下面伪代码所示：

    #a是目标字符串，b是待判断字符串for i <-  to length[b]    do for j <-  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]是否相等有关系
    既然dist[i,j] 跟dist[i-1,j],dist[i,j-1],dist[i-1,j-1]以及a[i]和b[j]是否相等有关系，那么我们是不是就可以定义任意待判断字符串b的每一个前缀子串（假定名称为 prev-substr(b) ) 与目标串a的 所有前缀子串集合中每一个元素的 编辑距离值 的集合呢。对应到上面表格中的例子，所有的状态应该就是每一行的元素值的集合。全部状态集合S是（计算过程如下表格）：‍
    {
      { ,1,2,3,4 },
      { 1,,1,2,3 },
      { 2,1,,1,2 },
      { 3,2,1,1,1 }
    }
    				
	
    
	
    
		
    相关文章