游离态GLZ的NLP任务1：拼写纠错

当我们使用搜索引擎的时候，经常会发现我们打错了我们想要检索的东西，但是搜索引擎仍旧给了我们正确的答案。比如我们把"python"打成了"pathon"，百度成功识别了出来我们真正想要的。

拼写纠错的核心在于编辑距离这一NLP任务的常用基础算法。编辑距离等于把一个字符串通过删除、修改、插入三种操作改为另一个字符串的最短距离（强烈建议刷一下这道DP题）。

实现拼写纠错时，我们需要预先准备好一个词典库，代表常见的词汇（一般认为这些是正确的）。当用户输入一个可能拼写错误的词时，我们生成编辑距离一定的候选词，把这些候选词和词库中的词对比，如果一样则认为可能是用户拼错的输入真正想要的词。

为了实现方便选择编辑距离为1：

#加载词典库，注意用set，检索复杂度为0（1）
vocab = set(line.rstrip() for line in open("vocab.txt"))

#选出所有与用户输入编辑距离为1的词作为候选
def generate_candidates(input_word):
    '''
    input_word:用户输入（可能有错）
    return:与用户输入编辑距离为1的候选词
    '''
    
    # 所有输入都已经归一化为小写
    letters = 'abcdefghijklmnopqrstuvwxyz'
    
    #遍历所有输入拆开的情况（拆开成为原始输入和空也算）
    splits = [(input_word[:i],input_word[i:]) for i in range(len(input_word)+1)]
    #插入情况
    inserts = [L + c + R for L,R in splits for c in letters]
    #删除情况
    deletes = [L + R[1:] for L,R in splits]
    #修改情况
    replaces = [L + c + R[1:] for L,R in splits for c in letters]
    
    candidates = set(inserts + deletes + replaces)
    candidates = [word for word in candidates if word in vocab]
    
    return candidates

测试效果：

注意实现的时候词典库使用set数据结构，这样检索的代价是O(1)。整体算法时间复杂度：
1.拆分输入：O(m)(m为用户输入长度)
2.删除、插入、修改方法的候选词生成:O(lm)(l为可能的字符数量)
3.筛选词：O(n)(n为生成的候选词数量，查找词典库O(1))
总体T = O(lm + n)，代价并不大。

本文地址：https://blog.csdn.net/qq_37477357/article/details/107179481