Autocomplete

Posted on | In | Comments:

Autocomplete?

Autocomplete是现代搜索引擎的一个重要功能之一，当用户只输入了query的一部分时我们可以根据输入的这部分预测用户想输入的内容，作为suggestion提供给用户选择，可以有效的节省用户时间和提高搜索体验，同时可能提高搜索质量。

先看一下公司Paul大神实现的awesome的Autocomplete:

最直接的实现方式是，将query log中的queries(query dictionary)构建一棵Trie树（前缀树or字典树)，并且对于每个query都给出一个评分（基于count或者其他更加高级的方式）。然后对于用户已经输入的query，去Trie树中搜索以已经输入的内容为前缀的query。

然而这种方式是非常理想化的，在实际使用中有很多问题。最根本的一个问题是，如果用户的query不是以前缀方式出现在Trie树中，匹配就会失败（用户的query常常会有typos或者query里的词顺序本来就是可以交换的）。

解决方法是，我们不应该拘泥于前缀（暂时先忘记前缀树），而应该选择在query dictionary(query log里的所有query)寻找尽量和用户已经输入的query相似的queries作为suggestions。Query的similarity可以通过很多种方式进行衡量，最常用的包括Levenshtein-distance（编辑距离）或n-gram distances。这里我们讲使用的是Levenshtein-distance。

所以我们的问题现在转换为：

1
2
3
4
5
6
7
Input: (D, q, n)
D -- queries dictionary(millions of queries or more)
q -- The query input by the current user
n -- Maximum Levenshtein-distance allowed from q

Output: (suggestions)
suggestions -- The queries from D whose Levenshtein-distance are smaller than n

Here comes a stupid method

最直接的方法当然是，对于D中的每个query计算其与q的Levenshtein-distance，与n进行比较确定是否要作为suggestions。当然最后可能有很多suggestions，我们需要根据distance以及其他features进一步rank suggestions。

我们来看一下这种方式的复杂度。首先是计算两个query的Levenshtein-distance，比较经典且高效的是基于动态规划的算法：

要想把字符串(query) S1变成S2，可以经过若干次下列原子操作：

  1. 删除一个字符
  2. 增加一个字符
  3. 更改一个字符

字符串S1和S2的Levenshtein-distance定义为从S1变成S2所需要原子操作的最少次数。

设字符串S去掉最后一个字符T后为S'，T1和T2分别是S1和S2的最后一个字符。

则dist(S1,S2)是下列4个值的最小者：

  1. dist(S1',S2') —当T1==T2
  2. 1+dist(S1',S2) —当T1!=T2，并且删除S1的最后一个字符T1
  3. 1+dist(S1,S2') —当T1!=T2，并且在S1后面增加一个字符T2
  4. 1+dist(S1',S2') —当T1!=T2，并且把S1的最的一个字符T1改成T2

把问题转换为二维矩阵：

M[i][j]表示S1.sub(0,i)和S2.sub(0,j)的编辑距离，则

1
2
3
4
M[0][j]=j
M[i][0]=i
M[i][j]=  min(M[i][j-1]+1, M[i-1][j]+1, M[i-1][j-1]+cost)
where cost = 0 if S1[i]==S2[j], and cost = 1 otherwise.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int minDistance(String word1, String word2) {
        if(word1.length()==0) return word2.length();
        if(word2.length()==0) return word1.length();
        int[][] distances = new int[word1.length()+1][];
        for(int i=0; i<distances.length; i++) distances[i] = new int[word2.length()+1];
        
        for(int i=0; i<=word1.length(); i++) {
            for(int j=0; j<=word2.length(); j++) {
                if(i==0) distances[i][j] = j;
                else if(j==0) distances[i][j] = i;
                else {
                    if(word1.charAt(i-1)==word2.charAt(j-1)) distances[i][j] = distances[i-1][j-1];
                    else {
                        distances[i][j] = Math.min(distances[i-1][j-1], Math.min(distances[i-1][j], distances[i][j-1])) + 1;
                    }
                }
            }
        }
        return distances[word1.length()][word2.length()];
    }
}

计算两个query的编辑距离的算法时间复杂度为O(len(s1)*len(s2))。一般两个query的长度都不会太长，所以还是可以接受的。
然而，上面这种直接的方法需要对于D中每一个query计算到q的编辑距离，则处理一个q的时间复杂度约为size(D)*O(average_len(q'」)*len(q))， q' belong to D。

这在实际情况下是完全不能接受的，我们必须有比这高效得多的方法。下面我们将介绍如何高效的解决这个问题。

Levenshein Automaton

前面对于每个D中的query，我们计算其到q的编辑距离。当存在很多query是，这会非常的昂贵。

更好的方法对于给定的q和n，我们可以其对应的Levenshein Automaton（Levenshei自动机）。

这样在判断query到qLevenshtein-distance是否小于等于q时，我们不需要再去计算其Levenshtein-distance，而是简单的query输入到Levenshein Automaton得到Accept或者Reject结果，时间复杂度将是O(len(query))。

Levenshein Automaton是一个有限状态自动机，可以识别出和给定q(任意给定字符串)在编辑距离n的所有query(字符串)。也就是得到给定q和n的Levenshein Automaton后，我们可以输入任何query判断是否Accept。

What？有限状态自动机（Finite State Machine）是啥。。。。。。参考Finite-state machine.

Levenshein Automaton是不是有些像什么魔法道具。。So, how can we get this awesome stuff?

首先我们来构建给定q和n的非确定Levenshein Automaton（也就是一个非确定有限状态自动机形式），Refer to Nondeterministic finite automaton。

再明确一下我们要解决的问题：

1
2
3
Input:  (q, n)
Output: Levenshein Automaton that accepts exactly 
all words(queries) where the Levenshtein-distance to q does not exceed n.

也就是给定q=food, n=2，我们需要得到如下的非确定有限状态自动机：

直观上理解这个有限状态自动机就是对于输入的query的letter串从前到后替换，删除，插入，匹配等操作，判断是能否在允许的错误个数（编辑次数）内转换成目标字符串q。直观？。。。。。。。。

上面有限状态自动机中的每个状态(State)以 $N^e$表示，N表示已经匹配到q的第N位，e表示error number，也就是已经使用的编辑次数。必须要匹配到q的第len(q)才算匹配完成，同时e在允许的范围内时则是匹配成功，也就是有限状态自动机的Final state必须是 $len(q)^0, len(q)^1,…,len(q)^n$。

另外上面的有限状态自动机的水平转移表示匹配了q中对于的字符，不需要使用编辑。垂直表示解释query当前字符为插入字符，使用一次插入编辑操作。对角线转移有两种类型的转移，*表示替换编辑操作，也就是替换query的当前字符来match``q当前字符，使用一次替换编辑操作。$\varepsilon$表示删除q的当前字符，使用一次删除编辑操作。

下面给出一种比较简单的构建NFA的方法的代码，from Damn Cool Algorithms: Levenshtein Automata。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def levenshtein_automata(term, k):
  nfa = NFA((0, 0))
  for i, c in enumerate(term):
    for e in range(k + 1):
      # Correct character
      nfa.add_transition((i, e), c, (i + 1, e))
      if e < k:
        # Deletion
        nfa.add_transition((i, e), NFA.ANY, (i, e + 1))
        # Insertion
        nfa.add_transition((i, e), NFA.EPSILON, (i + 1, e + 1))
        # Substitution
        nfa.add_transition((i, e), NFA.ANY, (i + 1, e + 1))
  for e in range(k + 1):
    if e < k:
      nfa.add_transition((len(term), e), NFA.ANY, (len(term), e + 1))
    nfa.add_final_state((len(term), e))
  return nfa

在得到给定q和n的Levenshein Automaton后，对于一个需要判断的query，我们只需要简单将其输入到Levenshein Automaton，判断处理完后达到的活跃状态中是否包括至少一个Accepted state。

仍然存在的一个问题是，这里得到是NFA Levenshein Automaton(Nondeterministic finite automaton，非确定有限状态自动机)，而非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。
也就是每次直接使用NFA判断能否accept给定的query时，NFA每次转移后都可能存在多个活跃状态以及epsilon transition(删除q的操作，也就是不需要消耗query输入符号的转移)，会导致更多的计算。

在形式理论中，对于任何给定NFA，都可以构造一个等价的DFA（确定有限状态自动机），反之亦然。尽管DFA和NFA有不同的定义，但是它们是等价的。
所以通常我们需要使用powerset construction, 幂集构造把NFA转换为DFA，也就是每次transition后都有一个确定的活跃状态。

Let’s build DFA Levenshein Automata

Continuing..

Any further optimization?

  • Dictionary Automata with Levenshein Automata
  • Caret awareness (by Paul)

Continuing..