搜索笔记 ---- 1

分词

完全切分

完全切分指的是，找出一段文本中的所有单词。

• 商品和服务 - > 商 商品 品 和 和服 服 服务 务

前向最大匹配 (正向最长匹配)

在某个下标为起点，递增查词的过程中，优先输出更长的单词，该下标的扫描顺序如果是从前往后的，则称为正向最长匹配

• 就读北京大学 -> 就读 北京大学

• 研究生命起源 -> 研究生 命 起源

后向最大匹配（逆向最长匹配）

在某个下标为起点，递增查词的过程中，优先输出更长的单词，该下标的扫描顺序如果是从后往前的，则称为逆向最长匹配

• 研究生命起源 -> 研究 生命 起源

双向最大匹配法

1. 同时执行正向和你想最长匹配， 若两者的词数不同， 则返回词数更少的那个

2. 否则，返回两者中单字更少的那一个。 当单子数也相同时， 优先返回逆向最长匹配的结果

ngram模型

N-Gram是一种基于统计语言模型的算法。它的基本思想是将文本里面的内容按照字节进行大小为N的滑动窗口操作，形成了长度是N的字节片段序列。

每一个字节片段称为gram，对所有gram的出现频度进行统计，并且按照事先设定好的阈值进行过滤，形成关键gram列表，也就是这个文本的向量特征空间，列表中的每一种gram就是一个特征向量维度。

• 一元标注器(Unigram Tagging) 单字计算概率 p(w1) * p(w2) * p(w3) * p(w4)

• 二元标注器(Bi-gram) 计算2个字计算概率 p(w1)* p(w1|w2) * p(w3|w2) * p(w4|w3)

• 三元标注器(Tri-gram) 计算3个字计算概率 p(w1)* p(w1|w2) * p(w3|w1,w2) * p(w4|w2,w3)

词袋模型

将所有词语装进一个袋子，不考虑其词法和语序的问题，即每个词语都是独立的。

count

# 方法1： 词袋模型（按照词语出现的个数）

from sklearn.feature_extraction.text import CountVectorizer

vectorizer = CountVectorizer()

corpus = [

'He is going from Beijing to Shanghai.',

'He denied my request, but he actually lied.',

'Mike lost the phone, and phone was in the car.',

]

X = vectorizer.fit_transform(corpus)

print (X.toarray())

print (vectorizer.get_feature_names())

[[0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0]

[1 0 0 1 0 1 0 0 2 0 0 1 0 0 1 0 1 0 0 0 0]

[0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 2 0 0 2 0 1]]

['actually', 'and', 'beijing', 'but', 'car', 'denied', 'from', 'going', 'he', 'in', 'is', 'lied', 'lost', 'mike', 'my', 'phone', 'request', 'shanghai', 'the', 'to', 'was']

tf-idf

# 方法2：词袋模型（tf-idf方法）

from sklearn.feature_extraction.text import TfidfVectorizer

vectorizer = TfidfVectorizer(smooth_idf=False)

X = vectorizer.fit_transform(corpus)

print (X.toarray())

print (vectorizer.get_feature_names()

[[ 0.          0.          0.39379499  0.          0.          0.

0.39379499  0.39379499  0.26372909  0.          0.39379499  0.          0.

0.          0.          0.          0.          0.39379499  0.

0.39379499  0.        ]

[ 0.35819397  0.          0.          0.35819397  0.          0.35819397

0.          0.          0.47977335  0.          0.          0.35819397

0.          0.          0.35819397  0.          0.35819397  0.          0.

0.          0.        ]

[ 0.          0.26726124  0.          0.          0.26726124  0.          0.

0.          0.          0.26726124  0.          0.          0.26726124

0.26726124  0.          0.53452248  0.          0.          0.53452248

0.          0.26726124]]

['actually', 'and', 'beijing', 'but', 'car', 'denied', 'from', 'going', 'he', 'in', 'is', 'lied', 'lost', 'mike', 'my', 'phone', 'request', 'shanghai', 'the', 'to', 'was']

编辑距离

编辑距离可以用来计算两个字符串的相似度，它的应用场景很多，其中之一是拼写纠正（spell correction）。 编辑距离的定义是给定两个字符串str1和str2, 我们要计算通过最少多少代价cost可以把str1转换成str2.

举个例子：

输入: str1 = "geek", str2 = "gesek" 输出: 1 插入 's'即可以把str1转换成str2

输入: str1 = "cat", str2 = "cut" 输出: 1 用u去替换a即可以得到str2

输入: str1 = "sunday", str2 = "saturday" 输出: 3

我们假定有三个不同的操作： 1. 插入新的字符 2. 替换字符 3. 删除一个字符。 每一个操作的代价为1.

# 基于动态规划的解法

def edit_dist(str1, str2):

# m，n分别字符串str1和str2的长度

m, n = len(str1), len(str2)

# 构建二位数组来存储子问题（sub-problem)的答案

dp = [[0 for x in range(n+1)] for x in range(m+1)]

# 利用动态规划算法，填充数组

for i in range(m+1):

for j in range(n+1):

# 假设第一个字符串为空，则转换的代价为j (j次的插入)

if i == 0:

dp[i][j] = j

# 同样的，假设第二个字符串为空，则转换的代价为i (i次的插入)

elif j == 0:

dp[i][j] = i

# 如果最后一个字符相等，就不会产生代价

elif str1[i-1] == str2[j-1]:

dp[i][j] = dp[i-1][j-1]

# 如果最后一个字符不一样，则考虑多种可能性，并且选择其中最小的值

else:

dp[i][j] = 1 + min(dp[i][j-1],        # Insert

dp[i-1][j],        # Remove

dp[i-1][j-1])      # Replace

return dp[m][n]