005、编辑距离、词向量、句子向量、余弦相似度（重点）

东方耀

005、编辑距离、词向量、句子向量、余弦相似度（重点）


拼写纠错问题：
1、识别错别字 纠错
2、用错了单词 上下文 语义的（LM）
I am go home     go>>>going


候选词集candidates是怎么来的？
1、词库里的所有单词 时间复杂度太高 无法实时
2、根据用户的输入生成编辑距离为1与2的所有字符串


编辑距离算法（面试必考）：基于动态规划的
从一个单词变成另外一个单词需要多少步操作：编辑距离
编辑距离越大代表两个单词之间的相似度越小
定义三个操作：1、insert 2、delete 3、replace
编辑距离可以用来计算两个字符串的相似度，它的应用场景很多，
其中之一是拼写纠正（spell correction）。
编辑距离的定义是给定两个字符串str1和str2, 我们要计算通过最少多少代价cost可以把str1转换成str2

1. 举个例子：
   
2. 
   
3. 输入: str1 = "geek", str2 = "gesek" 输出: 1 插入 's'即可以把str1转换成str2
   
4. 
   
5. 输入: str1 = "cat", str2 = "cut" 输出: 1 用u去替换a即可以得到str2
   
6. 
   
7. 输入: str1 = "sunday", str2 = "saturday" 输出: 3
   
8. 
   
9. 我们假定有三个不同的操作： 1. 插入新的字符 2. 替换字符 3. 删除一个字符。 每一个操作的代价为1.

复制代码

1. # 基于动态规划的解法
   
2. def edit_dist(str1, str2):
   
3.    
   
4.     # m，n分别字符串str1和str2的长度
   
5.     m, n = len(str1), len(str2)
   
6.    
   
7.     # 构建二位数组来存储子问题（sub-problem)的答案
   
8.     dp = [[0 for x in range(n+1)] for x in range(m+1)]
   
9.       
   
10.     # 利用动态规划算法，填充数组
    
11.     for i in range(m+1):
    
12.         for j in range(n+1):
    
13.   
    
14.             # 假设第一个字符串为空，则转换的代价为j (j次的插入)
    
15.             if i == 0:
    
16.                 dp[i][j] = j   
    
17.               
    
18.             # 同样的，假设第二个字符串为空，则转换的代价为i (i次的插入)
    
19.             elif j == 0:
    
20.                 dp[i][j] = i
    
21.             
    
22.             # 如果最后一个字符相等，就不会产生代价
    
23.             elif str1[i-1] == str2[j-1]:
    
24.                 dp[i][j] = dp[i-1][j-1]
    
25.   
    
26.             # 如果最后一个字符不一样，则考虑多种可能性，并且选择其中最小的值
    
27.             else:
    
28.                 dp[i][j] = 1 + min(dp[i][j-1],        # Insert
    
29.                                    dp[i-1][j],        # Remove
    
30.                                    dp[i-1][j-1])      # Replace
    
31.   
    
32.     return dp[m][n]

复制代码

生成指定编辑距离的单词（面试必考）
给定一个单词，我们也可以生成编辑距离为K的单词列表。 比如给定 str="apple"，K=1, 可以生成“appl”, "appla", "pple"...等

1. def generate_edit_one(str):
   
2.     """
   
3.     给定一个字符串，生成编辑距离为1的字符串列表。
   
4.     """
   
5.     letters    = 'abcdefghijklmnopqrstuvwxyz'
   
6.     splits = [(str[:i], str[i:])for i in range(len(str)+1)]
   
7.     inserts = [L + c + R for L, R in splits for c in letters]
   
8.     deletes = [L + R[1:] for L, R in splits if R]
   
9.     replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
   
10.    
    
11.     #return set(splits)
    
12.     return set(inserts + deletes + replaces)
    
13. 
    
14. print (len(generate_edit_one("apple")))

复制代码

1. def generate_edit_two(str):
   
2.     """
   
3.     给定一个字符串，生成编辑距离不大于2的字符串
   
4.     """
   
5.     return [e2 for e1 in generate_edit_one(str) for e2 in generate_edit_one(e1)]
   
6. 
   
7. print (len(generate_edit_two("apple")))

复制代码

Noisy Channel Model


Stemming算法：英文里常用 中文不常用


Normalization：1、Stemming（基于规则） 2、Lemmazation（基于规则 要求高一些）


（NLP核心部分）文本的表示：单词的表示（词向量）  句子的表示（句子向量）
|V| = 词库的大小
Word2Vec出现之前：   
单词的表示：one-hot 该单词在词库中对应位置设为1 其他为0 这个词向量的长度为|V|
句子的表示（先分词）：基于boolean是否出现  基于count出现次数（在词库中一个一个词的遍历，看这个词在句子中出现的次数，组成
句子表示的向量，该向量的长度=词库的大小）


有什么问题：
1、没有考虑词的先后顺序，上下文   解决：Word2Vec N-gram
2、巨大的稀疏矩阵  解决：Word2Vec
3、有些单词出现次数非常大    解决：次数前面统一加log    log(n+1)
并不是出现的越多就越重要！
并不是出现的越少就越不重要！
4、除了考虑词频或count次数 还需要考虑词的重要性！---> TF-IDF


1个语料库（corpus）包含了很多文档 语料库也可以说成训练数据
词库是从语料库中所有的单词进行Unique的操作 构建起来的


相似度计算：欧式距离（用得少）、余弦相似度（用得多）
向量既有大小也有方向 而欧式距离没有考虑方向的相似度
余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。
余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫"余弦相似性"。


东方老师AI官网：http://www.ai111.vip
有任何问题可联系东方老师微信：dfy_88888
【微信二维码图片】