如何实现拼写纠错功能？

在使用搜索引擎时，当我们输入错误的关键词时，当然这里的错误是拼写错误，搜索引擎的下拉框中仍会显示以正确关键词为前前辍的提示，当你直接回车搜索错误的关键词时，搜索引擎的结果中仍包括正确关键词的结果。你有没有想过它是如何实现的呢?

前文已经分享如何使用前辍树实现搜索框的关键词提示功能。大家很容易想到以上纠错功能的实现，关键在于给定一个错误的关键词，如何返回一个正确的关键词。

最简单的方法，我们使用一个数组来存储正确关键词，对于给定的关键词，我们遍历此数组，找到与给定关键词最接近的那个词返回即可。

如何找到最接近的那个词呢？也就是说如何量化两个字符串的相似度。通常有两种方法：一种是求两个字符串的编辑距离，编辑距离越小，两个字符串越相近。另一种是求两个子符串的最长公共子串长度，长度越大，两个字符串越相近。

**编辑距离（莱文斯坦距离）**就是从一个词变成另一个词需要的最小编辑次数。这里的编辑是指删除、替换、或插入。比如 facbok 和 facebook 的编辑距离就是 2 ，因为最小的操作是插入 2 次。比如 faccbook 和 facebook 的编辑距离就是 1 ，因为只需要替换 1 次。

最长公共子串长度从相反的角度来量化相似度，通过最小次数的删除，增加操作后，两个字符串达到相同时的长度。比如 facbok 和 facebook 的最大公共子串长度是 6。

如何求两个字符串的编辑距离？

先考虑如何人脑如何有效的识别编辑距离：

facbok (字符串a)
facebook (字符串b)

初始编辑距离为 0，分别遍历两个字符串，如果一样，则指针 index 后移，如果不一样，有以下三种情况：

1、在字符串 a (或字符串 b) 中 index 处的字符删除，编辑距离 +1，然后比较 a[index+1] 与 b[index]

2、在字符串 a (或字符串 b) 中，a[index]前的位置插入一个字符，编辑距离 +1，然后比较 a[index] 与 b[index+1]

3、在字符串 a (或字符串 b) 中，a[index]的位置替换一个字符，编辑距离 +1，然后比较 a[index+1] 与 b[index+1]

循环结束，比较 3 种情况，找出距离最小的即可。
基于以上思路，我们可以画个表格来尝试找规律：

字符 f = f ，因此单元格 B2 的值为 0 ，相应的 f 与 fa 的编辑距离为 1 因此 C2 的位置是 1，同理可得第 1 行和第 A 列的编辑距离。

接下来求 C3，C3 的值可以 C2 增加一个字符，B3 删除一个字符，或者 B2 替换一个字符转化而来，这三者的最小距离为
min(1+1,1+1,0+0) = 0 ，同样的道理可以得出其余所有格子的数值。

比如：E5 = min(E4+1,D5+1, 0+INT(E1!=A5)) = 1

最终的结果即 I7 的结果为 2。

以上过程可以很容易翻译成代码。

    def levenshtein_dp(s: str, t: str) -> int:
        '''
        计算莱文斯坦距离（Levenshtein distance），距离越小，说明两个单词越相近，时间复杂度为 O(mxn)
        :param s:
        :param t:
        :return:
        '''
        m, n = len(s), len(t)
        table = [[0] * (n + 1) for _ in range(m + 1)]
        table[0] = [j for j in range(n + 1)]
        # print(table)
        for i in range(m + 1):
            table[i][0] = i
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                table[i][j] = min(1 + table[i - 1][j], 1 + table[i][j - 1],
                                  int(s[i - 1] != t[j - 1]) + table[i - 1][j - 1])
        return table[-1][-1]

为了得到正确的函数，你还需要类似以下功能的函数：

  def get_right_word(self,input_word):
        '''
        输入一个单词，返回正确的单词
        :param input_word:
        :return:
        '''
        words = self.get_all_words()#获取所有正确的单词
        right_word = input_word
        min_distance = 99999
        for item in words:
            distance = levenshtein_dp(input_word,item)
            if min_distance >  distance:
                min_distance = distance
                right_word = item
        return right_word

结果前文中的前辍树，你可以很容易实现拼写纠错功能。

下面给出一种最长子串的求法，供参考：

def common_substring_dp(s: str, t: str) -> int:
    m, n = len(s), len(t)
    table = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            table[i][j] = max(table[i - 1][j], table[i][j - 1], int(s[i - 1] == t[j - 1]) + table[i - 1][j - 1])
    return table[-1][-1]

测试

我使用 cet4 词库来测试一下使用莱文斯坦距离和最长公共子串长度获取的正确单词有什么不同，附完整代码如下：

# -*- codeing:utf-8 -*-

def levenshtein_dp(s: str, t: str) -> int:
    '''
    计算莱文斯坦距离（Levenshtein distance），距离越小，说明两个单词越相近，时间复杂度为 O(mxn)
    :param s:
    :param t:
    :return:
    '''
    m, n = len(s), len(t)
    table = [[0] * (n + 1) for _ in range(m + 1)]
    table[0] = [j for j in range(n + 1)]
    # print(table)
    for i in range(m + 1):
        table[i][0] = i
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            table[i][j] = min(1 + table[i - 1][j], 1 + table[i][j - 1],
                              int(s[i - 1] != t[j - 1]) + table[i - 1][j - 1])
    return table[-1][-1]



def common_substring_dp(s: str, t: str) -> int:
    m, n = len(s), len(t)
    table = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            table[i][j] = max(table[i - 1][j], table[i][j - 1], int(s[i - 1] == t[j - 1]) + table[i - 1][j - 1])
    return table[-1][-1]


def get_right_word_from_levenshtein_dp(all_words,input_word):
      '''
      输入一个单词，返回计算莱文斯坦距离最小的单词
      :param input_word:
      :return:
      '''
      words = all_words #获取所有正确的单词
      right_word = input_word
      min_distance = 99999
      for item in words:
          distance = levenshtein_dp(input_word,item)
          if min_distance >  distance:
              min_distance = distance
              right_word = item
      return right_word

def get_right_word_from_common_substring_dp(all_words,input_word):
    '''
    输入一个单词，返回最长公共子串长度最大的单词
    :param input_word:
    :return:
    '''
    words = all_words #获取所有正确的单词
    right_word = input_word
    min_distance = 0
    for item in words:
        distance = common_substring_dp(input_word,item)
        if min_distance < distance:
            min_distance = distance
            right_word = item
    return right_word

if __name__ == '__main__':
    all_words = []
    with open("cet4.txt",encoding="gbk",mode="r") as r:
        for line in r:
            word = line.strip().split(" ")[0]
            if word != '' and len(word) > 2:
                all_words.append(word)

    while True:
        input_word = input("please input a word.(q for quit.): ")
        if input_word == 'q':
            break
        right_word = get_right_word_from_levenshtein_dp(all_words,input_word)
        print("the right word in cet4 is(levenshtein_dp): ",right_word)
        print(levenshtein_dp(right_word,input_word))

        right_word = get_right_word_from_common_substring_dp(all_words,input_word)
        print("the right word in cet4 is(common_substring_dp): ",right_word)
        print(common_substring_dp(right_word,input_word))

运行效果如下：

please input a word.(q for quit.): afection
the right word in cet4 is(levenshtein_dp):  affection
1
the right word in cet4 is(common_substring_dp):  affection
8
please input a word.(q for quit.): advertise
the right word in cet4 is(levenshtein_dp):  adjective
3
the right word in cet4 is(common_substring_dp):  advertisement
9
please input a word.(q for quit.): atmosph
the right word in cet4 is(levenshtein_dp):  almost
3
the right word in cet4 is(common_substring_dp):  atmosphere
7
please input a word.(q for quit.): assembl
the right word in cet4 is(levenshtein_dp):  assemble
1
the right word in cet4 is(common_substring_dp):  assemble
7
please input a word.(q for quit.): 

结论

测试了 4 个错误的单词，有 2 个返回的单词二者返回是一致的，有 2 个返回不一致。

比如：advertise 使用莱文斯坦距离返回正确单词是 adjective
使用最长公共子串长度返回的则是 advertisement，显然返回 advertisement 是输入者较为期望的结果。在某些场景下，莱文斯坦距离更有效。

因此没有一个放置四海而皆准的办法，实际使用中要结合具体需求，比如还可以加入搜索关键词热度等指标加以权衡。

希望本篇文章能让你开发的系统中的输入框更加智能。

（完）

专注有价值的技术分享。欢迎订阅我的微信公众号 somenzz，及时获得更新。