当前位置: 代码迷 >> 综合 >> 第三章 3、2 文本预处理之拼写纠错(Spell Correction)
  详细解决方案

第三章 3、2 文本预处理之拼写纠错(Spell Correction)

热度:95   发布时间:2023-12-28 22:44:56.0

一、什么是拼写纠错

在这里插入图片描述
根据两个单词的编辑距离,计算相似度。可以将错误的单词改正。

编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。那么,如何用Python计算编辑距离呢?我们可以从较为简单的情况进行分析。
当两个字符串都为空串,那么编辑距离为0;
当其中一个字符串为空串时,那么编辑距离为另一个非空字符串的长度;
当两个字符串均为非空时(长度分别为 i 和 j ),取以下三种情况最小值即可:
1、长度分别为 i-1 和 j 的字符串的编辑距离已知,那么加1即可;
2、长度分别为 i 和 j-1 的字符串的编辑距离已知,那么加1即可;
3、长度分别为 i-1 和 j-1 的字符串的编辑距离已知,此时考虑两种情况,若第i个字符和第j个字符不同,那么	加1即可;如果不同,那么不需要加1。
很明显,上述算法的思想即为动态规划

还有一个问题就是:这个单词跟词典库里面所有单词都比对一次么??
在这里插入图片描述
改进:不要跟所有单词库里面的单词都比较一次,而是生成编辑距离1,2的字符串。
在这里插入图片描述
在这里插入图片描述
过滤:比如一个单词正确的是apple,用户输入错误成了applea
根据公式可以看到,求在输入的基础上更正为正确字符串的概率 = P(s|c) P?
P(s|c):是在正确的基础之上,出现错误的概率。也就是这个正确的单词,被多少人写错的的概率。(左上角)
P(c):是正确的概率。也就是apple在一个统计文本库当中出现的次数。
在这里插入图片描述

二、编辑距离算法

在这里插入图片描述

  • 最简单的方法:
pip install python-Levenshtein //编辑距离依赖包import Levenshtein
print(Levenshtein.distance("cape","cat"))
texta = u'艾伦 图灵传'
textb = u'艾伦?图灵传'
print(Levenshtein.distance(texta,textb))
  • 自己实现

基于动态规划 1、长度分别为 i-1 和 j 的字符串的编辑距离已知,那么加1即可; 2、长度分别为 i 和 j-1
的字符串的编辑距离已知,那么加1即可; 3、长度分别为 i-1 和 j-1
的字符串的编辑距离已知,此时考虑两种情况,若第i个字符和第j个字符不同,那么 加1即可;如果相同,那么不需要加1。
需要一个二维数组保存 i,j 的编辑距离

int edit_dist_1(string str_01, string str_02){
    int len_01 = str_01.length();int len_02 = str_02.length(); int i = 0;int j = 0;int temp[len_01][len_02];  //保存中间结果while(i < len_01){
    temp[i][0] = i;i++;}while(j < len_02){
    temp[0][j] = j;j++; }for(j=1; j < len_02; j++){
    for(i=1; i < len_01; i++){
    if(i == j){
    if(str_01[i] == str_02[j]){
    temp[i][j] = temp[i-1][j-1];}else{
    temp[i][j] = temp[i-1][j-1] + 1;}		}if(i != j){
    temp[i][j] = temp[min(i,j)][min(i,j)] + abs(i-j);}}}return temp[len_01 - 1][len_02 - 1];
}int main(){
    string str_01 = "aaac";string str_02 = "aa";cout << "编辑距离:" << edit_dist_1(str_01, str_02);return 0; 
}

生成编辑距离为K的字符串:在一个字符串的基础之上,可以对每一个位做增加、删除、修改操作,是原始字符串成为一个新的字符串。比如apple,编辑距离是1,可以是appl,pple,aappl等等。


public class mytest {
    public static String[] generate_str_01(String str){
     //生成编辑距离为 1 的所有的字符串 String[] temp = new String[265]; //保存生成的所有的字符串 //1、每一位的改变从a到zCharacter ch ; Integer index;Integer i = 0;String str_temp = null;for(index = 0; index < str.length(); index++){
    for(ch='a'; ch <= 'z' ; ch++,i++){
    str_temp = str.replace(str.charAt(index), ch);temp[i] = str_temp;}}//2、每一位的删除for (index = 0; index < str.length(); index++) {
    if (index == 0 ) {
    temp[i++] = str.substring(1);}else if (index == str.length()-1) {
    temp[i++] = str.substring(0,str.length()-1);}else  {
    temp[i++] = str.substring(0,index).concat(str.substring(index+1));}}//3、增加一位a到z 插空增加 for (index = 0; index < str.length(); index++) {
    if (index == 0) {
    for (ch='a'; ch<='z' ; ch++) {
    temp[i++] = ch.toString().concat(str);}} else if (index == str.length()-1) {
    for (ch='a'; ch<='z' ; ch++) {
    temp[i++] = str.concat(ch.toString());}}else {
      //中间增加for (ch='a'; ch<='z' ; ch++) {
    temp[i++] = str.substring(0, index).concat(ch.toString()).concat(str.substring(index, str.length()));}}}return temp;}public static void main(String[] args) {
    // TODO Auto-generated method stub/** Character ch; for(ch='a'; ch<='z' ; ch++){ System.out.println(ch); }*/Integer count = 0;for(String element: generate_str_01("hello")){
    if (element != null) {
    System.out.println(element);count++;}else {
    break;}}System.out.println(count);System.out.println("因为l替换时候少计算了26,所以是265个");}}

分词工具

  • jieba分词
### 基于结巴(jieba)的分词。 Jieba是最常用的中文分词工具~ 
# encoding=utf-8
import jieba# 基于jieba的分词
seg_list = jieba.cut("大学专注于人工智能教育", cut_all=False)
print("Default Mode: " + "/ ".join(seg_list))  jieba.add_word("大学")
seg_list = jieba.cut("大学专注于人工智能教育", cut_all=False)
print("Default Mode: " + "/ ".join(seg_list)) 

在这里插入图片描述
在这里插入图片描述