CosmosNing的个人博客

探索·好奇

0%

电子词典中查词的模糊推荐是怎么做的

发表于 更新于 分类于
本文字数： 5.3k 阅读时长 ≈ 5 分钟
电子词典是依据什么标准为你提供查词时的模糊推荐呢？

引入

cover

大家在学习英语的时候经常会用到电子词典，当你在查询一个英语单词的时候，搜索框下方通常会依据你的输入给出词条的模糊推荐。即使你不小心输错了，电子词典也会给你一个看似模糊实则精准的推荐。这个功能大大提升了用户了单词查阅的效率，带给用户非常好的体验。那么，问题来了，这种模糊推荐到底是怎么做的呢？今天，我们就来一起探讨一下其中的算法。

单词相似度

做模糊推荐，一种很直观的想法就是找到它们之间的相似度，如果相似度高，就将它可以排在模糊推荐集合中较前的位置。

那么，怎样去定义单词之间的相似度呢？根据单词相似度定义的方式不同，主要分为以下两种算法：

  1. 最长公共子串（Longest common substring）
  2. 最长公共子列（Longest common subsequence）

最长公共子串（Longest common substring）

单词相似度的定义

正如名称所述，该算法将单词的相似度定义为两个单词中共同含有的最长子串（这个子串在原字符串中是连续的）的长度大小。

算法简述

为了找到两个单词（一个设为 S ，另一个设为 T ）之间的最长公共子串，我们可以这样处理。

首先定义一个二维表 L （大小为 r × n，其中 r 为 S 的长度， n 为 T 的长度），用于存储算法处理的中间结果。

然后，循环比较每一组从两个单词中取出的字母。比较结果无非两种情况，一种不同，一种相同。不同的情况下，给二维表 L 对应的位置赋值为 0 ，表示在该位置最长公共子串的长度为0；相同的情况下，找到当前位置的前一个位置上存储的长度，将它加一，保存在当前位置即可。可以用公式描述如下：

\[ L(i, j) = \left \{ \begin{aligned} & L(i-1, j-1)+1, & if\ S[i] = T[j]\\ & 0, & otherwise\\ \end{aligned} \right. \]

那么，寻找最长子串的长度就可以定义为

\[ \underset{ i\in [ 0, r ), j\in [ 0, n ) }{ max } L( i, j ) \]

因而，为了求出两个字符串的最长公共子串，维基百科给出了如下的伪码描述1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function LCSubstr(S[1..r], T[1..n])
    L := array(1..r, 1..n)
    z := 0
    ret := {}
    for i := 1..r
        for j := 1..n
            if S[i] == T[j]
                if i == 1 or j == 1
                    L[i,j] := 1
                else
                    L[i,j] := L[i-1,j-1] + 1
                if L[i,j] > z
                    z := L[i,j]
                    ret := {S[i-z+1..i]}
                else
                if L[i,j] == z
                    ret := ret ∪ {S[i-z+1..i]}
            else
                L[i,j] := 0
    return ret

为了方便阐释，我们可以举一个例子帮助理解。假设要找到 process 和 progress 两个单词的最长公共子串。那么二维表 L 的最终状态如下：

p r o c e s s
p 1 0 0 0 0 0 0
r 0 2 0 0 0 0 0
o 0 0 3 0 0 0 0
g 0 0 0 0 0 0 0
r 0 1 0 0 0 0 0
e 0 0 0 0 1 0 0
s 0 0 0 0 0 2 1
s 0 0 0 0 0 1 3

由上图可知， process 和 progress 两个单词的最长公共子串为 pro 和 ess ，最长长度为 3 。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import numpy as np


def LCSubstr(S, T):
    """
    寻找两个字符串S、T的最长相同子串
    :param S: ( str ) 字符串1
    :param T: ( str ) 字符串2
    :return: ( list ) 符合条件的子串集合
    """
    r = len(S)
    n = len(T)
    L = np.zeros((r + 1, n + 1))  # 初始化大小为 ( r + 1 ) × ( n + 1 ) 并且值全为 0 的数组。将 r 和 n 都加 1 是为了方便后续的计算
    z = 0  # 保存当前找到的最长相同子串的长度
    ret = []  # 保存符合条件的子串集合

    for i in range(1, r + 1):
        for j in range(1, n + 1):
            if S[i - 1] == T[j - 1]:  # 如果字母相同，那么L[i][j] = L[i - 1][j - 1] + 1
                L[i][j] = L[i - 1][j - 1] + 1

                if L[i][j] > z:  # 如果找到更大的，更新 z 和 ret 集合
                    z = int(L[i][j])
                    ret.clear()
                    ret.append(S[i - z:i])
                elif L[i][j] == z:  # 如果找到与当前最长的长度一样，将该子串加入 ret 集合
                    ret.append(S[i - z:i])
    return ret  # 返回结果


if __name__ == "__main__":
    print(LCSubstr("progress", "process"))
    print(LCSubstr("BABA", "ABAB"))

"""
输出结果：
['pro', 'ess']
['BAB', 'ABA']
"""

最长公共子列（Longest common subsequence）

单词相似度的定义

上面的子串要求其在原字符串中是连续的，那不连续的又会怎样？这就诞生了 最长公共子列 。最长公共子列将单词相似度定义为两个单词的最长公共子列（这个子列不要求在原字符串中是连续的，但要求保持原序）的长度大小。

算法简述

受求最长公共子串的启发，对于两个单词 X 和 Y，同样的，我们可以定义一个二维表 C ，用于存储算法处理的中间结果。

那么对应的循环过程中，怎样去改变 C ，从而满足题目的需要呢？

在字母相同的情况下，我们依旧可以用和求最长公共子串相同的方法，即当前位置的前一个位置的存储的长度加一；而字母不同的情况下，连续子串到此结束，因而不能简单的使用上一个位置存储的长度。那么决定当前位置的值，还剩下以下两种情况。

  1. （ X 当前位置， Y 上一个位置）
  2. （ X 上一个位置，Y 当前位置）

而当前位置的最长公共子列长度由于当前位置上的两个字母不同，所以该位置不会对上一个位置上的数据产生影响。因而，当前位置上的最长公共子列长度只需取上述两种情况的最大值即可。具体可以用公式描述如下：

\[ C(i, j) = \left \{ \begin{aligned} & C(i-1, j-1)+1, & if\ X[i] = Y[j]\\ & max(C(i, j-1), C(i-1, j)), & otherwise\\ \end{aligned} \right. \]

而其中的最大长度，会在二维表 C 的末尾出现（如果两个单词的长度分别为 m 和 n , 那么 C[m][n] 即为最长公共子列）

实现

对于求最长公共子列的长度，维基百科中给出如下的伪码描述2

1
2
3
4
5
6
7
8
9
10
11
12
13
function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

基于此，我给出 Python 实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import numpy as np


def LCSLength(X, Y):
    """
    计算两个字符串最长公共子列的长度
    :param X: （str）字符串1
    :param Y: （str）字符串2
    :return: （int）两个字符串最长公共子列的长度
    """
    m = len(X)
    n = len(Y)
    C = np.zeros((m+1, n+1), np.int)
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                C[i, j] = C[i-1, j-1] + 1
            else:
                C[i, j] = max(C[i, j-1], C[i-1, j])
    
    return C[m, n]

if __name__ == "__main__":
    print(LCSLength("progress", "process"))

"""
输出结果
6
P.S.也就是proess的长度
"""

动态规划（Dynamic programming）

简述

仔细观察上面两种算法，其共同之处都是将原问题分解为较小的子问题，并将子问题的解进行保存，依据子问题由递推公式得到原问题的解，这种方法通常叫做 ”动态规划“ 。

那么，什么样的问题适合用动态规划来解决呢？

有人在博客中给出了如下的解释3

适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。

最优子结构：如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。

重叠子问题：适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要很小，也就是用来求解原问题的递归算法课反复地解同样的子问题，而不是总在产生新的子问题。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。

说到这里，你应该会想到之前的文章中提到的贪心算法和分治算法，它们的思想和动态规划很类似，那么他们之间的区别又在那里呢？

动态规划 VS 贪心算法 VS 分治算法 VS 遍历搜索

在维基百科中，有人对比了贪心算法，动态规划和遍历搜索。其原文如下4：

Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step. Otherwise, provided the problem exhibits overlapping subproblems as well, dynamic programming is used. If there are no appropriate greedy algorithms and the problem fails to exhibit overlapping subproblems, often a lengthy but straightforward search of the solution space is the best alternative.

也就是说，如果一个问题具有最优子结构并且可以证明其每一步选择都是最优的，那么选用贪心算法。如果该问题除了含有最优子结构，其子问题又是相互重叠的，那么选用动态规划。如果这两种方法都不成功，那么就进行简单的暴力搜索，遍历所有情况。

那么分治呢？分治也是将问题分解为子问题，但是这些子问题是互相独立的，同时它们之间的计算结果不共享。如果将分治法用于子问题相互重叠的问题，那么分治法会做很多重复的计算。这时候，动态规划的优势就显现出来，因为它将子问题的解存储起来，避免了重复计算。

其他方法

现在，让我们回到最初的问题。电子词典中查词的模糊推荐以单词之间的相似度为标准，还有其他的方法吗？

当然有。比如基于用户的历史查询记录，分析查词词频，依据词频来做推荐。限于篇幅，这里不做讨论，有兴趣请自行查阅资料。

总结

今天，我和你一起了解到两种计算不同字符串相似度的算法，一个是 最长公共子串 ，另一个是 最长公共子列 ，并由此引出 动态规划 这种算法思想。最后我将本文要点总结如下：

  1. 最长公共子串要求子串在原字符串中是连续的
  2. 最长公共子列不要求子列在原字符串中是连续的，但要求保持原序
  3. 求最长公共子串和最长公共子列的时间复杂度为 \(O(M\cdot N)\) ，其中 M 和 N 为两个字符串的长度。（这个我在原文中没有写，很容易分析得到）
  4. 适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。
  5. 如果一个问题具有最优子结构并且可以证明其每一步选择都是最优的，那么选用贪心算法。如果该问题除了含有最优子结构，其子问题又是相互重叠的，那么选用动态规划。如果这两种方法都不成功，那么就进行简单的暴力搜索，遍历所有情况。
  6. 动态规划利用存储子问题的解，避免了子问题中的重复计算，有时候会比分治算法快很多。

  1. https://en.wikipedia.org/wiki/Longest_common_substring_problem#Pseudocode↩︎

  2. https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS↩︎

  3. http://hxrs.iteye.com/blog/1055478↩︎

  4. https://en.wikipedia.org/wiki/Optimal_substructure↩︎