上节简单学习了分词，这节主要学习拼写错误纠正

编辑距离(Minimum Edit Distance，MED)的定义

在信息论、语言学和计算机科学领域，Levenshtein Distance 是用来度量两个序列相似程度的指标。通俗地来讲，编辑距离指的是在两个单词之间，由其中一个单词转换为另一个单词所需要的最少单字符编辑操作次数。

定义的单字符编辑操作有且仅有三种：

• 插入（Insertion）
• 删除（Deletion）
• 替换（Substitution）

计算编辑距离的例子

1.kitten → sitten (substitution of "s" for "k")
2.sitten → sittin (substitution of "i" for "e")
3.sittin → sitting (insertion of "g" at the end)

因此，"kitten" 和 "sitting" 这两个单词之间的编辑距离为 3 。

如何纠错

我们不可能将一个正确词的所有不同编辑距离的情况生成, 但可以问题简化为生成距离为1或者2的单词(一般用户输错的词距离与真实词距离为2以内)

image.png

假设用户输入为s需要纠正为c,但是我们生成出来的词c有很多,我们需要找到概率最大的单词c作为矫正词.
这里我们使用了beyes定理进行了条件概率的转换. 简化了c的概率计算方式. (unigram)
表示实际的词是c, 但用户输入词s的统计概率.
表示正确词c的统计概率.

目前我们将错误的词改为指定正确的词的概率, 但,当错误的词对应多个错误的词的时候,还需要借助句子的xxgram模型得到候选正确的词放入句子中的xxgram概率, 将这两个概率取log相加得到最终的概率值,取概率值最大的修正词即可.

过滤

刚介绍了纠错的方法,这里介绍过滤,我们一般会过滤掉

1. 停用词,需要一个符合实际情况的停用词库
2. 低频词

合并

除了过滤,还要进行合并, 即将表达同一个意思的词归一化为一个词,例如:
西葫芦-> 角瓜, 云南小瓜
go -> going, went

reference

1. https://www.jianshu.com/p/a617d20162cf
2. 文本预处理（代码参考） https://www.kaggle.com/shashanksai/text-preprocessing-using-python
3. 分词中的最大匹配算法 https://blog.csdn.net/selinda001/article/details/79345072
4. 拼写纠错 https://web.stanford.edu/class/cs124/lec/spelling.pdf
5. Edit Distance https://www.geeksforgeeks.org/edit-distance-dp-5/
6. DP练习题 https://people.cs.clemson.edu/~bcdean/dp_practice/
7. Porter Stemmer https://tartarus.org/martin/PorterStemmer/java.txt
8. tf-idf介绍（技术博客）https://www.cnblogs.com/pinard/p/6693230.html
9. Porter Stemming （网页版介绍）http://facweb.cs.depaul.edu/mobasher/classes/csc575/papers/porter-algorithm.html