实现简单搜索引擎
在上节的程序实战中，薯条老师教大家写了个非常简单的基于词典匹配的中文分词器。大家都有使用过搜索引擎的经验，比如在谷歌或百度上进行搜索，按下回车键后搜索引擎就可以返回我们要查找的内容。在今天的代码实例中，薯条老师教大家写个非常简单的搜索引擎。
搜索引擎的三大过程
搜索引擎技术主要包含以下3个过程
(1) 爬取内容，建立内容数据库
(2) 对数据库的内容(通常以单篇文章为单位)进行分词，并建立倒排索引
(3) 提供查询服务
爬取内容由爬虫来负责，这里的爬虫不是现实世界中的爬虫动物，是我们程序员编写的爬虫程序，用来自动地爬取网络数据，比如爬取网站中的网页。在本节的程序实战中，笔者以字符串来表示网站中的网页。对文本进行分词，读者可以使用上节中的简单中文分词器。所谓倒排索引是指建立关键词与整篇内容的映射关系，笔者举个简单的例子：
web_page = ''' hit girl，正义联盟中的成员，在联盟中排行第五，她是一个内心善良又极富正义感的天使。 '''
将这段文本进行分词，分词后的结果包含"正义","善良"，这里的倒排索引即把分割出来的关键词与整篇文章进行映射。倒排索引可以用python中的字典结构来进行表示，那么建立好的倒排索引如以下代码所示：
reverse_index = {"正义": web_page, "善良": web_page}为什么需要倒排索引？
如果没有倒排索引，那么只能在已爬取的整篇内容中逐一地进行关键词匹配，这显然是低效的。有了倒排索引后，我们可以先将搜索串进行分词，然后将分词后的关键词直接在倒排索引中进行hash查找，这大幅提高了搜索的效率。
但如果关键词对应到多篇文章怎么办，怎么从多篇文章中查找到最相关的文章？如何度量关键词与文章的相关度？
TF-IDF
利用TF-IDF，就可以度量关键词与文章的相关度，这里的TF是"Term Frequency"，词频的意思。IDF是"Inverse Document Frequency"，即逆文档频率。所谓词频，是指关键词在文件中出现的频率：
假设一篇文章的总关键词数为100个，某个关键词出现了10次，那么TF=10/100。
逆文档频率指的是文件的总数与包含关键词的文件总数相除后再取对数(以10为底的对数)：
假设"天使"一词在1000个文件中出现过，而文件总数是10000000份的话，那么其逆向文件频率IDF=lg(10000000 / 1000)=4。
为什么TF-IDF可以度量关键词与文章的相关度？关键词在单篇文章中的频率越高，那么它的重要性可能就越高。而关键词在所有文章中出现的次数越少，那么该关键词与其它文章的区分度就越高。将两者(TF与IDF)进行相乘就可以量化这种相关性。TF-IDF算法也有它的局限性，因为数据是存在噪音的，如何降低噪声词对TF-IDF算法的干扰是一门值得研究的课题。关于更多与搜索引擎，TF-IDF相关的知识，同学门可以查阅相关论文进行深入地学习。
程序源码
# 导入math模块，用来计算对数
import math
# 定义web_page系列变量来表示网页的内容
WEB_PAGE1 = '''
hit girl，正义联盟中的成员，在联盟中排行第五，她是一个内心善良又极富正义感的战斗天使。
'''
WEB_PAGE2 = '''
正义联盟中的hit girl, 从小就爱乐于助人，匡扶正义。人人都喜欢hit girl。
'''
WEB_PAGE3 = '''
科洛·莫瑞兹出生于1997年2月10日，她8岁便开始涉足影坛。
科洛年纪虽小，作品却不少，她的从影生涯始于2003年。。
'''
def calc_max_length(dictionary):
"""
:param dictionary: a object of set, indicates all of the keywords. e.g.: {"正义", "hit girl"}
:return: the max length of keyword
"""
max_length = 1
for _ in dictionary:
if len(_) > max_length:
max_length = len(_)
return max_length
def cut(text, dictionary, max_split_width):
"""
:param text: a text to be cut, e.g.: "正义联盟中的hit girl, 从小就爱乐于助人，匡扶正义"
:param dictionary: a object of set, indicates all of the keywords. e.g.: {"正义", "hit girl"}
:return:
"""
keywords = {}
words_size = 0
while text:
# 这里的range函数为生成一个倒排序列，比如6,5,4,3,2,1
for index in range(max_split_width, 0, -1):
# 对文本按最大宽度进行切片
keyword = text[:index]
# 如果切片分出来的词语在词典集合中，就保存到列表words变量中，并且退出for循环
# 在集合中进行快速查找
if keyword in dictionary:
words_size += 1
keywords[keyword] = 1 if keyword not in keywords else keywords[keyword] + 1
text = text[index:]
break
else:
text = text[1:]
return keywords, words_size
def build_inverse_index_table(web_pages, dictionary):
"""
:param web_pages: a object of list, e.g.:["", ""]
:param dictionary: a object of set, indicates all of the keywords. e.g.: {"正义", "hit girl"}
:return: a object of dict, e.g.:{
"正义" : [{"tf":xxx, "idf":xxx, "tfidf": xxx, "content": ""}]
}
"""
inverse_index_table = {}
web_pages_size = len(web_pages)
max_split_width = calc_max_length(dictionary)
for index, web_page in enumerate(web_pages):
terms, terms_size = cut(web_page, dictionary, max_split_width)
for term in terms:
# 计算term的tf值
tf = round(terms[term] / terms_size, 4)
page = {"content": web_page, "tf": tf}
if term not in inverse_index_table:
inverse_index_table[term] = [page]
continue
# 如果term已存在于倒排表中，那么当前的term肯定是其它网页的term
# 其它网页的term被添加进列表中，方便后续计算tf-idf
inverse_index_table[term].append(page)
for _, pages in inverse_index_table.items():
terms_in_docs_length = len(pages)
for page in pages:
# 计算term的idf和tf-idf值
page["idf"] = round(math.log10(web_pages_size / terms_in_docs_length), 4)
page["tfidf"] = page["tf"] * page["idf"]
return inverse_index_table
def search():
# 定义词典，用来保存分词的词语，读者也可以自行扩充其它的词语
dictionary = {"科洛·莫瑞兹", "hit girl", "正义"}
max_split_width = calc_max_length(dictionary)
web_pages = [WEB_PAGE1, WEB_PAGE2, WEB_PAGE3]
inverse_index_table = build_inverse_index_table(web_pages, dictionary)
prompt = "您好，欢迎使用薯条橙子在线搜索引擎chipscoco"
print(prompt)
while True:
query = input("薯条一下:"+"_"*10+"\b"*10)
keywords, _ = cut(query, dictionary, max_split_width)
for keyword in keywords:
pages = inverse_index_table.get(keyword, [])
if pages:
pages = sorted(pages, key=lambda page: page["tfidf"], reverse=True)
print("chipscoco为您找到相关结果约{}个".format(len(pages)))
for page in pages:
print("{}...\n".format(page["content"][:30])+"_"*55)
if input("按下键盘任意键继续使用该搜索系统，"
"或者输入quit退出系统:____\b\b\b\b").lower() == "quit":
break
if __name__ == "__main__":
search()程序的输出界面
程序扩展
本节中的程序仅用拆分出来的单个关键词进行搜索，同学们需要在源码基础上实现对整个搜索串进行搜索的功能。
最具实力的小班培训
来这里参加Python和Java小班培训的学员大部分都找到了很好的工作，平均月薪有11K，学得好的同学，拿到的会更高。由于是小班教学，所以薯条老师有精力把每位学员都教好。打算参加线下小班培训的同学，必须遵守薯条老师的学习安排，认真做作业和项目。把知识学好，学扎实，那么找到一份高薪的工作就是很简单的一件事。
(1) Python后端工程师高薪就业班，月薪11K-18K，免费领取课程大纲
(2) Python爬虫工程师高薪就业班，年薪十五万，免费领取课程大纲
(3) Java后端开发工程师高薪就业班，月薪11K-20K, 免费领取课程大纲
(4) Python大数据分析，量化投资就业班，月薪12K-25K,免费领取课程大纲
扫码免费领取学习资料：
