写完之后，重新看一下哪一部分比较慢，然后试图去优化。一个好的习惯是每写一部分就思考这部分代码的时间复杂度和空间复杂度，AI工程是的日常习惯！
Part 1: 搭建一个分词工具
Part 1.1 基于枚举方法来搭建中文分词工具
此项目需要的数据：
- 综合类中文词库.xlsx： 包含了中文词，当做词典来用
- 以变量的方式提供了部分unigram概率 word_prob
举个例子： 给定词典=[我们 学习 人工 智能 人工智能 未来 是]， 另外我们给定unigram概率：p(我们)=0.25, p(学习)=0.15, p(人工)=0.05, p(智能)=0.1, p(人工智能)=0.2, p(未来)=0.1, p(是)=0.15
Step 1: 对于给定字符串：”我们学习人工智能，人工智能是未来“, 找出所有可能的分割方式
- [我们，学习，人工智能，人工智能，是，未来]
- [我们，学习，人工，智能，人工智能，是，未来]
- [我们，学习，人工，智能，人工，智能，是，未来]
- [我们，学习，人工智能，人工，智能，是，未来]
…
Step 2: 我们也可以计算出每一个切分之后句子的概率
- p(我们，学习，人工智能，人工智能，是，未来)= -log p(我们)-log p(学习)-log p(人工智能)-log p(人工智能)-log p(是)-log p(未来)
- p(我们，学习，人工，智能，人工智能，是，未来)=-log p(我们)-log p(学习)-log p(人工)-log p(智能)-log p(人工智能)-log p(是)-log p(未来)
- p(我们，学习，人工，智能，人工，智能，是，未来)=-log p(我们)-log p(学习)-log p(人工)-log p(智能)-log p(人工)-log p(智能)-log p(是)-log p(未来)
- p(我们，学习，人工智能，人工，智能，是，未来)=-log p(我们)-log p(学习)-log p(人工智能)-log p(人工)-log p(智能)-log(是)-log p(未来)
…
Step 3: 返回第二步中概率最大的结果
import warnings
warnings.filterwarnings("ignore") #Ignoring unnecessory warnings
import numpy as np #for large and multi-dimensional arrays
import pandas as pd #for data manipulation and analysis
import nltk #Natural language processing tool-kit
import math
from nltk.corpus import stopwords #Stopwords corpus
from nltk.stem import PorterStemmer # Stemmer
from sklearn.feature_extraction.text import CountVectorizer #For Bag of words
from sklearn.feature_extraction.text import TfidfVectorizer #For TF-IDF
# from gensim.models import Word2Vec
dic_path = r"综合类中文词库.xlsx"
dic = pd.read_excel(dic_path, header = None)
# TODO: 第一步： 从dic.txt中读取所有中文词。
# hint: 思考一下用什么数据结构来存储这个词典会比较好？ 要考虑我们每次查询一个单词的效率。
dic_words = set(dic[0].tolist()) # 保存词典库中读取的单词
# 以下是每一个单词出现的概率。为了问题的简化，我们只列出了一小部分单词的概率。 在这里没有出现的的单词但是出现在词典里的，统一把概率设置成为0.00001
# 比如 p("学院")=p("概率")=...0.00001
word_prob = {"北京":0.03,"的":0.08,"天":0.005,"气":0.005,"天气":0.06,"真":0.04,"好":0.05,"真好":0.04,"啊":0.01,"真好啊":0.02,
"今":0.01,"今天":0.07,"课程":0.06,"内容":0.06,"有":0.05,"很":0.03,"很有":0.04,"意思":0.06,"有意思":0.005,"课":0.01,
"程":0.005,"经常":0.08,"意见":0.08,"意":0.01,"见":0.005,"有意见":0.02,"分歧":0.04,"分":0.02, "歧":0.005}
print (sum(word_prob.values()))
1.0000000000000002
基于规则的中文分词
包括， 正向最大匹配法，逆向最大匹配法和双向最大匹配法。
最大匹配方法是最有代表性的一种基于词典和规则的方法，其缺点是严重依赖词典，无法很好地处理分词歧义和未登录词。优点是由于这种方法简单、速度快、且分词效果基本可以满足需求，因此在工业界仍然很受欢迎。
正向最大匹配法思想：
正如方法名称，正向表示对句子从左到右选择词典中最长的词条进行匹配，获得分词结果。
- 1、统计分词词典，确定词典中最长词条的字符m；
- 2、从左向右取待切分语句的m个字符作为匹配字段，查找词典，如果匹配成功，则作为一个切分后的词语，否则，去掉待匹配字符的最后一个继续查找词典，重复上述步骤直到切分出所有词语。
dictA = ['南京','南京市', '南京市长', '市长' ,'长江大桥', '大桥']
maxDictA = max([len(word) for word in dictA])
sentence = "南京市长江大桥"
def cutA(sentence):
result = []
sentenceLen = len(sentence)
n = 0
while n < sentenceLen:
matched = 0
for i in range(maxDictA, 0, -1):
piece = sentence[n:n+i]
if piece in dictA:
result.append(piece)
matched = 1
n = n + i
break
if not matched:
result.append(sentence[n])
n += 1
return result
逆向最大匹配法思想：
与正向最大匹配原理相同，主要差异是：
- 1、对句子从右到左选择词典中最长的词条进行匹配，获得分词结果；
- 2、当匹配失败时，去掉待匹配字符的最前面的一个继续查找词典。
maxDictA = max([len(word) for word in dictA])
def cutB(sentence):
result = []
sentenceLen = len(sentence)
while sentenceLen > 0:
word = ''
for i in range(maxDictA, 0, -1):
piece = sentence[sentenceLen-i:sentenceLen]
if piece in dictA:
word = piece
result.append(word)
sentenceLen -= i
break
if word is '':
sentenceLen -= 1
result.append(sentence[sentenceLen])
return result[::-1]
双向最大匹配法思想：
将正向最大匹配和逆向匹配得到的分词结果进行比较，按照最大匹配原则，选择切分总词数最少的作为最终分词结果。
举例：
dictA：# [‘南京市长’, ‘江’, ‘大桥’]
dictB: # [‘南京市’, ‘长江大桥’]
最终选择，dictB的结果。
def twowaycut(sentence):
if len(cutA(sentence)) > len(cutB(sentence)):
result = cutB(sentence)
elif len(cutA(sentence)) < len(cutB(sentence)):
result = cutA(sentence)
return result
基于枚举方法来搭建中文分词工具
def word_break(s, dic):
def sentences(cur):
result=[]
if cur <len(s):
for next in range(cur+1, len(s)+1):
if s[cur:next] in dic:
result = result+[s[cur:next]+(tail and','+tail) for tail in sentences(next)]
else:
return ['']
return result
list_new = []
for line in sentences(0):
line = line.split(",")
list_new.append(line)
return list_new
# 分数（10）
import math
## TODO 请编写word_segment_naive函数来实现对输入字符串的分词
def word_segment_naive(input_str):
"""
1. 对于输入字符串做分词，并返回所有可行的分词之后的结果。
2. 针对于每一个返回结果，计算句子的概率
3. 返回概率最高的最作为最后结果
input_str: 输入字符串 输入格式：“今天天气好”
best_segment: 最好的分词结果 输出格式：["今天"，"天气"，"好"]
"""
# TODO： 第一步： 计算所有可能的分词结果，要保证每个分完的词存在于词典里，这个结果有可能会非常多。
segments = word_break(input_str, dic_words) # 存储所有分词的结果。如果次字符串不可能被完全切分，则返回空列表(list)
# 格式为：segments = [["今天"，“天气”，“好”],["今天"，“天“，”气”，“好”],["今“，”天"，“天气”，“好”],...]
# TODO: 第二步：循环所有的分词结果，并计算出概率最高的分词结果，并返回
best_segment =[]
best_score = math.inf
for seg in segments:
score=0
for word in seg:
if word in word_prob.keys():
score += word_prob[word]
else:
score += round(-math.log(0.00001),1)
if score < best_score:
best_score=score
best_segment = seg
return best_segment
# 测试
print(word_segment_naive("今天的课程内容很有意思"))
print(word_segment_naive("经常有意见分歧"))
print(word_segment_naive("北京的天气真好啊"))
['今天', '的', '课程', '内容', '很', '有意思']
['经常', '有意', '见', '分歧']
['北京', '的', '天气', '真好', '啊']
Part 1.2 基于维特比算法来优化上述流程
此项目需要的数据：
- 综合类中文词库.xlsx： 包含了中文词，当做词典来用
- 以变量的方式提供了部分unigram概率word_prob
举个例子： 给定词典=[我们 学习 人工 智能 人工智能 未来 是]， 另外我们给定unigram概率：p(我们)=0.25, p(学习)=0.15, p(人工)=0.05, p(智能)=0.1, p(人工智能)=0.2, p(未来)=0.1, p(是)=0.15
Step 1: 根据词典，输入的句子和 word_prob来创建带权重的有向图（Directed Graph） 参考：课程内容
有向图的每一条边是一个单词的概率（只要存在于词典里的都可以作为一个合法的单词），这些概率已经给出（存放在word_prob）。
注意：思考用什么方式来存储这种有向图比较合适？ 不一定只有一种方式来存储这种结构。
Step 2: 编写维特比算法（viterebi）算法来找出其中最好的PATH， 也就是最好的句子切分
具体算法参考课程中讲过的内容
Step 3: 返回结果
跟PART 1.1的要求一致
# 分数（10）
## TODO 请编写word_segment_viterbi函数来实现对输入字符串的分词
def word_segment_viterbi(input_str):
"""
1. 基于输入字符串，词典，以及给定的unigram概率来创建DAG(有向图）。
2. 编写维特比算法来寻找最优的PATH
3. 返回分词结果
input_str: 输入字符串 输入格式：“今天天气好”
best_segment: 最好的分词结果 输出格式：["今天"，"天气"，"好"]
"""
# TODO: 第一步：根据词典，输入的句子，以及给定的unigram概率来创建带权重的有向图（Directed Graph） 参考：课程内容
# 有向图的每一条边是一个单词的概率（只要存在于词典里的都可以作为一个合法的单词），这些概率在 word_prob，如果不在word_prob里的单词但在
# 词典里存在的，统一用概率值0.00001。
# 注意：思考用什么方式来存储这种有向图比较合适？ 不一定有只有一种方式来存储这种结构。
graph ={}
N = len(input_str)
for i in range(N,0,-1):
k=i-1
in_list=[]
flag=input_str[k:i]
while k>=0 and flag in dic_words:
in_list.append(k)
k-=1
flag = input_str[k:i]
graph[i]=in_list
# TODO： 第二步： 利用维特比算法来找出最好的PATH， 这个PATH是P(sentence)最大或者 -log P(sentence)最小的PATH。
mem=[0]* (N+1)
last_index=[0]*(N+1)
for i in range(1,N+1):
min_dis=math.inf
for j in graph[i]:
# 有向图的每一条边是一个单词的概率（只要存在于词典里的都可以作为一个合法的单词），这些概率在 word_prob，如果不在word_prob里的单词但在
# 词典里存在的，统一用概率值0.00001。
if input_str[j:i] in word_prob.keys():
if min_dis > mem[j]+round(-math.log(word_prob[input_str[j:i]]),1):
min_dis=mem[j]+round(-math.log(word_prob[input_str[j:i]]),1)
last_index[i]=j
else:
if min_dis > mem[j]+round(-math.log(0.00001),1):
min_dis=mem[j]+round(-math.log(0.00001),1)
last_index[i]=j
mem[i]=min_dis
# TODO: 第三步： 根据最好的PATH, 返回最好的切分
best_segment=[]
j=N
while True:
best_segment.append(input_str[last_index[j]:j])
j=last_index[j]
if j==0 and last_index[j]==0:
break
best_segment.reverse()
return best_segment
#测试
print(word_segment_viterbi("经常有意见分歧"))
['经常', '有', '意见', '分歧']
# 分数（3）
# TODO: 第一种方法和第二种方法的时间复杂度和空间复杂度分别是多少？
第一个方法：
时间复杂度=O(2**N) , 空间复杂度=O(N)
第二个方法：
时间复杂度= , 空间复杂度=
# 分数（2）
# TODO：如果把上述的分词工具持续优化，有哪些可以考虑的方法？ （至少列出3点）
- 0. （例）， 目前的概率是不完整的，可以考虑大量的语料库，然后从中计算出每一个词出现的概率，这样更加真实
- 1.
- 2.
- 3.
Part 2: 搭建一个简单的问答系统
本次项目的目标是搭建一个基于检索式的简单的问答系统。至于什么是检索式的问答系统请参考课程直播内容/PPT介绍。
通过此项目，你将会有机会掌握以下几个知识点：
- 字符串操作 2. 文本预处理技术（词过滤，标准化） 3. 文本的表示（tf-idf, word2vec) 4. 文本相似度计算 5. 文本高效检索
此项目需要的数据：
- dev-v2.0.json: 这个数据包含了问题和答案的pair， 但是以JSON格式存在，需要编写parser来提取出里面的问题和答案。
- glove.6B: 这个文件需要从网上下载，下载地址为：https://nlp.stanford.edu/projects/glove/， 请使用d=100的词向量
检索式的问答系统
问答系统所需要的数据已经提供，对于每一个问题都可以找得到相应的答案，所以可以理解为每一个样本数据是 <问题、答案>。 那系统的核心是当用户输入一个问题的时候，首先要找到跟这个问题最相近的已经存储在库里的问题，然后直接返回相应的答案即可。 举一个简单的例子：
假设我们的库里面已有存在以下几个<问题,答案>：
<"贪心学院主要做什么方面的业务？”， “他们主要做人工智能方面的教育”>
<“国内有哪些做人工智能教育的公司？”， “贪心学院”>
<“人工智能和机器学习的关系什么？”, “其实机器学习是人工智能的一个范畴，很多人工智能的应用要基于机器学习的技术”>
<“人工智能最核心的语言是什么？”， ”Python“>
…
假设一个用户往系统中输入了问题 “贪心学院是做什么的？”， 那这时候系统先去匹配最相近的“已经存在库里的”问题。 那在这里很显然是 “贪心学院是做什么的”和“贪心学院主要做什么方面的业务？”是最相近的。 所以当我们定位到这个问题之后，直接返回它的答案 “他们主要做人工智能方面的教育”就可以了。 所以这里的核心问题可以归结为计算两个问句（query）之间的相似度。
在本次项目中，你会频繁地使用到sklearn这个机器学习库。具体安装请见：http://scikit-learn.org/stable/install.html sklearn包含了各类机器学习算法和数据处理工具，包括本项目需要使用的词袋模型，均可以在sklearn工具包中找得到。 另外，本项目还需要用到分词工具jieba, 具体使用方法请见 https://github.com/fxsjy/jieba
Part 2.1 第一部分： 读取文件，并把内容分别写到两个list里（一个list对应问题集，另一个list对应答案集）
import json
from matplotlib import pyplot as plt
import re
import string
import nltk
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize
from nltk.stem.porter import PorterStemmer
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity
from queue import PriorityQueue as PQueue
from functools import reduce
# 分数（5）
def read_corpus():
"""
读取给定的语料库，并把问题列表和答案列表分别写入到 qlist, alist 里面。 在此过程中，不用对字符换做任何的处理（这部分需要在 Part 2.3里处理）
qlist = ["问题1"， “问题2”， “问题3” ....]
alist = ["答案1", "答案2", "答案3" ....]
务必要让每一个问题和答案对应起来（下标位置一致）
"""
qlist = []
alist = []
with open("data/train-v2.0.json", 'r') as path:
fileJson = json.load(path)
json_list=fileJson['data']
for data_dict in json_list:
for data_key in data_dict:
if data_key=="paragraphs":
paragraphs_list=data_dict[data_key]
for content_dict in paragraphs_list:
for qas_key in content_dict:
if "qas" == qas_key:
qas_list = content_dict[qas_key]
for q_a_dict in qas_list:
if len(q_a_dict["answers"]) > 0:
qlist.append(q_a_dict["question"])
alist.append(q_a_dict["answers"][0]["text"])
print("qlist len:" + str(len(qlist)))
print("alist len:" + str(len(alist)))
assert len(qlist) == len(alist) # 确保长度一样
return qlist, alist
Part 2.2 理解数据（可视化分析/统计信息）
对数据的理解是任何AI工作的第一步，需要充分对手上的数据有个更直观的理解。
# 分数（10）
# TODO: 统计一下在qlist 总共出现了多少个单词？总共出现了多少个不同的单词？
# 统计一下qlist中每个单词出现的频率，并把这些频率排一下序，然后画成plot.
# 这里需要做简单的分词，对于英文我们根据空格来分词即可，其他过滤暂不考虑（只需分词）
# TODO: 统计一下qlist中每个单词出现的频率，并把这些频率排一下序，然后画成plot. 比如总共出现了总共7个不同单词，而且每个单词出现的频率为 4, 5,10,2, 1, 1,1
# 把频率排序之后就可以得到(从大到小) 10, 5, 4, 2, 1, 1, 1. 然后把这7个数plot即可（从大到小）
# 需要使用matplotlib里的plot函数。y轴是词频
def data_analysis(data):
# TODO: 统计一下在qlist 总共出现了多少个单词？ 总共出现了多少个不同的单词？
# TODO: 统计一下qlist中每个单词出现的频率，并把这些频率排一下序，然后画成plot.
qlist_word = []
word_dic = {}
for sentences in data:
cur_word = sentences[:len(sentences) - 1].strip().split(" ")
qlist_word += cur_word
for word in cur_word:
if word in word_dic.keys():
word_dic[word] = word_dic[word] + 1
else:
word_dic[word] = 1
#统计一下在qlist总共出现了多少个不同单词
word_total = len(set(qlist_word)) # 53306
print (word_total)
word_dic=sorted(word_dic.items(), key = lambda x:x[1], reverse = True)#按词频排序
# 出现频率前100的单词进行可视化
x = range(100)
y = [c[1] for c in word_dic[:100]]
plt.figure()
plt.plot(x, y)
plt.show()
word_freq = []
word_list = []
for line in word_dic:
word_list.append(line[0])
word_freq.append(line[1])
print(word_freq[:100])
print(word_list[:100])
x = range(total_diff_word)
plt.plot(x,word_freq,'ro')
plt.ylabel("word frequency")
plt.show()
temp = [n for n in word_freq if n <=50]
plt.plot(range(len(temp)),temp, color='r',linestyle='-',linewidth=2)
plt.ylabel("word frequency")
plt.show()
qlist, alist = read_corpus()
data_analysis(qlist)
2.3 文本预处理
次部分需要尝试做文本的处理。在这里我们面对的是英文文本，所以任何对英文适合的技术都可以考虑进来。
# 分数（10）
# TODO: 对于qlist, alist做文本预处理操作。 可以考虑以下几种操作：
# 1. 停用词过滤 （去网上搜一下 "english stop words list"，会出现很多包含停用词库的网页，或者直接使用NLTK自带的）
# 2. 转换成lower_case： 这是一个基本的操作
# 3. 去掉一些无用的符号： 比如连续的感叹号！！！， 或者一些奇怪的单词。
# 4. 去掉出现频率很低的词：比如出现次数少于10,20....
# 5. 对于数字的处理： 分词完只有有些单词可能就是数字比如44，415，把所有这些数字都看成是一个单词，这个新的单词我们可以定义为 "#number"
# 6. stemming（利用porter stemming): 因为是英文，所以stemming也是可以做的工作
# 7. 其他（如果有的话）
# 请注意，不一定要按照上面的顺序来处理，具体处理的顺序思考一下，然后选择一个合理的顺序
# hint: 停用词用什么数据结构来存储？ 不一样的数据结构会带来完全不一样的效率！
def data_pre(temp_list):
stop_words = set(stopwords.words('english'))
stemmer = PorterStemmer()
pattern = re.compile('[{}]'.format(re.escape(string.punctuation)))#正则匹配特殊符号
word_list_list = []
word_dict = {}
for line in temp_list:
temp_word_list = []
sentence = pattern.sub("", line) # 1.去掉一些无用的符号
sentence = sentence.lower() # 2.转换成lower_case
word_list = sentence.split()
for word in word_list:
if word not in stop_words: # 3.过滤停用词
word = "#number" if word.isdigit() else word # 4.数字特殊处理
word = stemmer.stem(word) # 5.词干提取（包括词形还原）
word_dict[word] = word_dict.get(word, 0) + 1
temp_word_list.append(word)
word_list_list.append(temp_word_list)
return word_dict, word_list_list
#6. 去掉出现频率很低的词
def filter_words(in_list=[], in_dict={}, lower=0, upper=0):
word_list = []
for key, val in in_dict.items():
if val >= lower and val <= upper:
word_list.append(key)
new_list = []
for line in in_list:
words = [w for w in line if w in word_list]
new_list.append(' '.join(words))
return new_list
qlist_word_dict, qlist_list_list = data_pre(qlist)
alist_word_dict, alist_list_list = data_pre(alist)
qlist = filter_words(in_list= qlist_list_list, in_dict = qlist_word_dict, lower = 2,upper = 1000 )
alist = filter_words(in_list= qlist_list_list, in_dict = qlist_word_dict, lower = 2,upper = 1000 ) # 更新后的
# TODO: 在前面步骤里，我们删除了出现次数比较少的单词，那你选择的阈值是多少（小于多少的去掉？）， 这个阈值是根据什么来选择的？
#
# 画出100分为类的词频统计图
def drawgraph(dic, name):
freq = list(dic.values())
freq.sort(reverse=True)
temp = [n for n in freq if n <=50]
plt.plot(range(len(temp)),temp,'r-')
plt.ylabel(name)
plt.show()
drawgraph(qlist_word_dict,"word frequency of qlist")
drawgraph(alist_word_dict,"word frequency of alist")
在上面步骤，我删除了出现次数小于2和大于10000的词，原因是这两个位置词频断档比较严重
2.4 文本表示
当我们做完关键的预处理过程之后，就需要把每一个文本转换成向量。
# 分数（10）
# TODO: 把qlist中的每一个问题字符串转换成tf-idf向量, 转换之后的结果存储在X矩阵里。 X的大小是： N* D的矩阵。 这里N是问题的个数（样本个数），
# D是字典库的大小。
from sklearn.feature_extraction.text import TfidfVectorizer
vectorizer = TfidfVectorizer() # 定一个tf-idf的vectorizer
X = vectorizer.fit_transform(qlist) # 结果存放在X矩阵
# TODO: 矩阵X有什么特点？ 计算一下它的稀疏度
x_mat = X.toarray()
n = len(x_mat)
m = len(x_mat[0])
t = 0
for i in range(n):
for j in range(m):
if x_mat[i][j] != 0:
t += 1
sparsity = t / (n*m)
print (sparsity) # 打印出稀疏度(sparsity)
2.5 对于用户的输入问题，找到相似度最高的TOP5问题，并把5个潜在的答案做返回
# 分数（10）
def top5results(input_q):
"""
给定用户输入的问题 input_q, 返回最有可能的TOP 5问题。这里面需要做到以下几点：
1. 对于用户的输入 input_q 首先做一系列的预处理，然后再转换成tf-idf向量（利用上面的vectorizer)
2. 计算跟每个库里的问题之间的相似度
3. 找出相似度最高的top5问题的答案
"""
stop_word = set(stopword.words("english"))
stemmer = PorterStemmer()
pattern = re.compile("[{}]".format(re.escape(string.punctuation))) # 正则匹配特殊符号
input_q = pattern.sub("", input_q) #1.去掉无用的符号
input_q = pattern.sub("", input_q) # 1.去掉一些无用的符号
input_q = input_q.lower() # 2.转换成lower_case
word_list = input_q.split()
temp_word_list=[]
for word in word_list:
if word not in stop_words: # 3.过滤停用词
word = "#number" if word.isdigit() else word # 4.数字特殊处理
word = stemmer.stem(word) # 5.词干提取（包括词形还原）
temp_word_list.append(word)
new_input=' '.join(temp_word_list)
#向量化
vectorizer = TfidfVectorizer(smooth_idf=False) # 定义一个tf-idf的vectorizer
X = vectorizer.fit_transform(qlist) # 结果存放在X矩阵
#注意fit_transform是训练，transform是加入新数据
input_vec = vectorizer.transform([new_input])# 结果存放在X矩阵
res = cosine_similarity(input_vec, X)[0]
#即输出前k个高频词使用优先队列，优化速度
pq = PQueue()
for i, v in enumerate(res):
pq.put((1.0 - v, i))
top_idxs = [] # top_idxs存放相似度最高的（存在qlist里的）问题的下表
for i in range(5):
top_idxs.append(pq.get()[1])
print(top_idxs) # top_idxs存放相似度最高的（存在qlist里的）问题的下表
# hint: 利用priority queue来找出top results. 思考为什么可以这么做？
# 因为优先级队列的第一个值可以是浮点数，数值越低级别越优先，所以用1.0-相似度，就可以转换为优先级
result = [alist[i] for i in top_idxs]
return result # 返回相似度最高的问题对应的答案，作为TOP5答案
# TODO: 编写几个测试用例，并输出结果
qlist, alist = read_corpus()
q_dict, q_list_list = data_pre(qlist)
new_qlist = filter_words(q_list_list, q_dict, 2, 1000)
print(top5results("when did Beyonce start becoming popular?"))
print(top5results("what languge does the word of 'symbiosis' come from"))
# 分数（5）
# TODO: 上面的top5results算法的时间复杂度和空间复杂度分别是多少？
时间复杂度 = O()， 空间复杂度 = O()
2.6 利用倒排表的优化。
上面的算法，一个最大的缺点是每一个用户问题都需要跟库里的所有的问题都计算相似度。假设我们库里的问题非常多，这将是效率非常低的方法。 这里面一个方案是通过倒排表的方式，先从库里面找到跟当前的输入类似的问题描述。然后针对于这些candidates问题再做余弦相似度的计算。这样会节省大量的时间。
# 分数（10）
# TODO: 基于倒排表的优化。在这里，我们可以定义一个类似于hash_map, 比如 inverted_index = {}， 然后存放包含每一个关键词的文档出现在了什么位置，
# 也就是，通过关键词的搜索首先来判断包含这些关键词的文档（比如出现至少一个），然后对于candidates问题做相似度比较。
#
from functools import reduce
inverted_idx = {} # 定一个简单的倒排表
for i in range(len(qlist)):
for word in qlist[i].split():
if word in inverted_idx:
inverted_idx[word].append(i)
else:
inverted_idx[word] = [i]
for key in inverted_idx:
inverted_idx[key] = sorted(inverted_idx[key])
# 求两个set的交集
def intersections(set1, set2):
return set1.intersection(set2)
def top5results_invidx(input_q):
"""
给定用户输入的问题 input_q, 返回最有可能的TOP 5问题。这里面需要做到以下几点：
1. 利用倒排表来筛选 candidate
2. 对于用户的输入 input_q 首先做一系列的预处理，然后再转换成tf-idf向量（利用上面的vectorizer)
3. 计算跟每个库里的问题之间的相似度
4. 找出相似度最高的top5问题的答案
"""
# 处理输入字符串
stop_words = set(stopwords.words('english'))
stemmer = PorterStemmer()
pattern = re.compile('[{}]'.format(re.escape(string.punctuation))) # 正则匹配特殊符号
sentence = pattern.sub("", input_q)
sentence = sentence.lower()
word_list = sentence.split()
result_list = []
for word in word_list:
if word not in stop_words:
word = "#number" if word.isdigit() else word
word = stemmer.stem(word)
result_list.append(word)
# 找到倒排表中相关的索引，用于答案的候选集
candidate_list = []
for word in result_list:
if word in inverted_idx:
idx_list = inverted_idx[word]
candidate_list.append(set(idx_list))
# 候选问题的索引
# print(candidate_list)
candidate_idx = list(reduce(intersections, candidate_list))
input_seg = ' '.join(result_list)
vectorizer = TfidfVectorizer(smooth_idf=False) # 定义一个tf-idf的vectorizer
X = vectorizer.fit_transform(new_qlist) # 结果存放在X矩阵
input_vec = vectorizer.transform([input_seg])
# 计算所有候选索引中的相似度
similarity_list = []
for i in candidate_idx:
similarity = cosine_similarity(input_vec, X[i])[0]
similarity_list.append((i, similarity[0]))
res_sorted = sorted(similarity_list, key=lambda k: k[1], reverse=True)
print(type(res_sorted))
# 根据索引检索top 5答案
answers = []
i = 0
for (idx, score) in res_sorted:
if i < 5:
answer = alist[idx]
answers.append(answer)
i += 1
return answers
# TODO: 编写几个测试用例，并输出结果
print (top5results_invidx(""))
print (top5results_invidx(""))
# 分数（3）
# TODO: 上面的top5results算法的时间复杂度和空间复杂度分别是多少？
时间复杂度 = O()， 空间复杂度 = O()
2.7 基于词向量的文本表示
上面所用到的方法论是基于词袋模型（bag-of-words model）。这样的方法论有两个主要的问题：1. 无法计算词语之间的相似度 2. 稀疏度很高。 在2.7里面我们
讲采用词向量作为文本的表示。词向量方面需要下载： https://nlp.stanford.edu/projects/glove/ （请下载glove.6B.zip），并使用d=100的词向量（100维）。
# 分数（10）
# TODO
#embedding = # 读取每一个单词的嵌入。这个是 D*H的矩阵，这里的D是词典库的大小， H是词向量的大小。 这里面我们给定的每个单词的词向量，那句子向量怎么表达？
# 其中，最简单的方式 句子向量 = 词向量的平均（出现在问句里的）， 如果给定的词没有出现在词典库里，则忽略掉这个词。
def load_glove(path):
#第一元素存储全为0的向量，代表词典里不存在的
vocab = {}
embedding = []
vocab["UNK"] = 0
embedding.append([0] * 100)
with open(path, 'r', encoding='utf8') as f:
i = 1
for line in f:
row = line.strip().split()
vocab[row[0]] = i
embedding.append(row[1:])
i += 1
return vocab, embedding
def top5results_emb(input_q=''):
"""
给定用户输入的问题 input_q, 返回最有可能的TOP 5问题。这里面需要做到以下几点：
1. 利用倒排表来筛选 candidate
2. 对于用户的输入 input_q，转换成句子向量
3. 计算跟每个库里的问题之间的相似度
4. 找出相似度最高的top5问题的答案
"""
path = "data/glove.6B.100d.txt"
# vacab为词典库，embedding为len(vacab)*100的矩阵。
vocab, embedding= load_glove(path)
stop_words = set(stopwords.words('english'))
pattern = re.compile('[{}]'.format(re.escape(string.punctuation)))
sentence = pattern.sub("", input_q)
sentence = sentence.lower()
word_list = sentence.split()
result_list = []
for word in word_list:
if word not in stop_words:
word = "#number" if word.isdigit() else word
result_list.append(word)
input_q = " ".join(result_list)
qlist, alist = read_corpus()
q_dict, q_list_list = data_pre(qlist)
new_qlist = filter_words(q_list_list, q_dict, 2, 1000)
inverted_idx = {} # 定一个一个简单的倒排表
for i in range(len(new_qlist)):
for word in new_qlist[i].split():
if word in inverted_idx:
inverted_idx[word].append(i)
else:
inverted_idx[word] = [i]
for key in inverted_idx:
inverted_idx[key] = sorted(inverted_idx[key])
candidates = []
for word in result_list:
if word in inverted_idx:
ids = inverted_idx[word]
candidates.append(set(ids))
candidate_idx = list(reduce(intersections, candidates)) # 候选问题索引
input_q_vec=word_to_vec(input_q,vocab, embedding)
scores = []
for i in candidate_idx:
vec = word_to_vec(new_qlist[i], vocab, embedding)
score = cosine_similarity([input_q_vec, vec])[0]
scores.append((i, score[1]))
scores_sorted = sorted(scores, key=lambda k: k[1], reverse=True)
# 根据索引检索top 5答案
answers = []
i = 0
for (idx,score) in scores_sorted:
if i < 5:
answer = alist[idx]
answers.append(answer)
i += 1
return answers
print(top5results_emb("when did Beyonce start becoming popular?"))
print(top5results_emb("what languge does the word of 'symbiosis' come from"))
print(top5results_emb("In her music, what are some?"))
# TODO: 编写几个测试用例，并输出结果
print(top5results_emb("when did Beyonce start becoming popular?"))
print(top5results_emb("what languge does the word of 'symbiosis' come from"))
print(top5results_emb("In her music, what are some?"))
# 我们在验收作业时在后台会建立几个测试用例，来验证返回的准确性。