简单搜索引擎

来源：搜索引擎技术基础大作业

地址：https://github.com/chen2511/SimpleSearchEngine

一、 概述

互联网信息复杂多样，因此想要迅速、快捷的找到所需要的信息内容，就需要搜索引擎来帮忙实现。

第一个现在意义上的搜索引擎是1994年Michael Mauldin创建的Lycos。是在网络爬虫的基础上加上索引程序，采用网络、数据库等关键技术来实现，检索速度也非常慢。

第二个阶段是1996年到1998年,这个期间,搜索引擎采用分布式检索方案,使用多个微型计算机来协同工作,其目的是为了提高数据规模和响应速度。一般可以响应千万次的用户检索请求。第三代搜索引擎,就当前所使用的搜索引擎,也是搜索引擎极为繁荣的时期。它拥有完整的索引数据库，除了一般的搜索，还有主题搜索和地域搜索。

​ 本系统以西北工业大学的工大要闻为目标，使用python简单实现了搜索引擎的三个部分：网页搜集、对搜集网页的预处理、查询服务。并能满足其基本要求：在可以接受的时间内，输入一个查询词，输出符合条件的网页列表。

二、 页面获取与解析

2.1 理论基础

搜索引擎的页面获取流程如下：

1、首先选取一部分精心挑选的种子URL，将这些URL放入待抓取URL队列

2、从待抓取URL队列中取出待抓取在URL

3、解析DNS，并且得到主机的ip

456、将URL对应的网页下载下来，存储进已下载网页库中

79、分析页面中的其他URL，并且将URL放入待抓取URL队列，从而进入下一个循环

8、将这些URL放进已抓取URL队列

2.2 实践

相关代码位于：spider.py

本程序的搜集流程：挑选工大要闻的某些新闻列表页，作为种子；之后获取种子url的页面，分析其中存在的url（新闻）并加入待爬取列表（考虑不爬取过多页面，只爬取两级），然后再爬取列表里的所有url，之后再进行保存等。

首先是页面内容获取，本程序借助的是模拟浏览器。下载chrome相关驱动程序，配合python selenium 包，即可完成页面内容获取。

部分代码如下：

# 模拟浏览器，使用谷歌浏览器，将chromedriver.exe复制到谷歌浏览器的文件夹内
chromedriver = r"C:\Program Files (x86)\Google\Chrome\Application\chromedriver.exe"
# 设置浏览器
os.environ["webdriver.chrome.driver"] = chromedriver
browser = webdriver.Chrome(chromedriver)
browser.get(url_seed)

这样就获得了相应url_seed的原始网页。

在获取到种子页面的内容后，需要解析其中存在的url（二级url），并加入待爬取列表，以便下一遍爬取。

​ 解析html页面的内容可以通过xpath来解析，从而获得其中的url。

​ 页面中某篇新闻对应的url所在位置如下图所示。

实现方法如下所示：

for i in range(6):
    path = '//*[@id="line_u12_' + str(i) + '"]/div[2]/a'
    url = browser.find_element_by_xpath(path).get_attribute('href')
    # 如果未访问过，则加入url列表
    if(check_curent_visited(url)):
        urls.append(url)

首先可以通过在浏览器查看元素的界面中，右击相关元素可以获得其对应的xpath路径，通过find_element_by_xpath方法，即可在python代码中获得相关元素的内容，但是url是一个属性，则需要再次调用其get_attribute即可获得url。仍需注意，这里的url在浏览器中显示的是相对路径，但python提供的方法返回的是绝对路径。

​ 不能将上一步获得的url直接加入待爬取列表中，还有很重要的一步，是检查页面是否已经被爬取过。使用一个词典记录新闻页是否已经被爬取，词典的键为url的序号（本来应该是url的哈希值，但注意到页面不多，且有规律，键值仅仅是url末尾的编号，值则是0或1，用来表示该url是否被访问过）。该词典通过读取visited-set.json文件初始化，再获取页面过程结束后，写回到visited-set.json文件。

​ 具体见spider.py的load.dic()、check_curent_visited(url)和save_dic()方法。

​ 最后再对获取到的所有url进行爬取，即完成了页面获取的全部内容。

三、 页面存储

3.1 网页信息存储的格式

将获取网页信息保存在磁盘中，需要按照规定的格式保存，便于后续处理和提供服务。这里的存储格式只是顺序保存网页信息，没有索引文件。

原始网页库（raw.txt）由若干记录组成，每个记录包含一个网页的原始数据，记录的存放是顺序追加的，记录之间没有分隔符；

每条记录由头部、数据和空行组成，顺序是：头部 + 空行 + 数据 + 空行；（html文件中有空行）

​ 具体效果下图所示：

具体见spider.py的save_raw_page(data, rawfile, url)方法：

def save_raw_page(data, rawfile, url):
    # data.replace('\n', '')
    rawfile.write('\nversion: 1.0\n')
    rawfile.write('url: ' + url + '\n')
    rawfile.write('date: ' + time.strftime("%Y-%m-%d %H:%M:%S", time.localtime()) + '\n')
    rawfile.write('length: ' + str(len(data)) + '\n\n')
    rawfile.write(str(data)) 
    # 当前文件指针所在位置
    # print(rawfile.tell())
    rawfile.write('\n')
    return rawfile.tell()

值得一提的是，为了便于生成索引网页库，写完内容之后会返回当前的文件指针。

3.2 建立索引网页库

至此，我们体系结构中的第一部分全部完成；下面将开始数据处理部分。首先是建立索引网页库：

索引网页库的任务就是完成给定一个 URL，在原始网页库中定位到该 URL 所指向的记录。如果不建立索引信息，只能通过顺序查找的方法，查找指定的记录，这样会消耗大量的I/O，数据量增大的时候不能够满足搜索引擎的快速响应要求。

​ 所以我们一共建立两个文件：网页索引文件和URL索引文件。

​ 网页索引文件：以 ISAM（索引顺序访问模式）存储，其中每一行不记录文档长度，因为文档长度可以通过后续文档起始位置的偏移和当前文档其位置的偏移的差获得。为了保证对最大文档号数据读取的一致性，在最后一行增加“哨兵”，它不对应实际的文档数据，其中文档摘要为空，表示文档索引的结束。如下图所示：

URL索引文件：以 ISAM 存储，包含了 URL 的摘要和文档编号。为了能够快速的对给定 url 找到对应的文档编号，按照 URL摘要排序。

代码实现：

​ 首先是哈希值的计算：见spider.py的get_md5()方法：

import hashlib
def get_md5(data):
    # 应用MD5算法
    md5 = hashlib.md5()
    md5.update(data.encode('utf-8'))
    return md5.hexdigest()

输入字符串返回hash值

网页索引：

# 原始网页索引列表添加新项
def append_pageIndex(data, cnt, index):
    data_md5 = get_md5(data)

    pageIndex[-1]['md5'] = data_md5
    #pageIndex[-1]['pagelen'] = len(data)
    pageIndex.append({'No': cnt, 'offset':index, 'md5': None})

url索引：

# 原始网页url索引列表添加新项
def append_urlIndex(url, cnt):
    url_md5 = get_md5(url)
    urlIndex.append({'url':url_md5, 'No':cnt})

最后要对url索引列表根据url的hash值排序，加速查找速度。

save_json(pageIndex, 'pageIndex.json')
   save_json(urlIndex, 'urlIndex.json')

最近结果保存到json格式的文件中。

四、 页面解析

部分页面解析的内容在前面已经提到过，如获取网页中存在的URL。所以该部分内容还包括：网页编码识别和获取标题。

​ 切词前需要识别网页的编码，编码格式不对，导致切出来的词没有意义。

我们可以在网页内容中得到网页的编码格式，即从http返回的head信息中的charset域得到，如下图所示：

​ 获取标题是显示结果时需要的必须步骤，本程序使用的是BeautifulSoup包来解析。

soup = BeautifulSoup(data, 'html.parser')
title = soup.find("title")

五、 切词

生成了所以网页库之后，需要分析网页，并进行分词。分词是网页分析的前提。

分词方法是按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。按照扫描方向不同，串匹配分词方法可以分为：正向匹配和逆向匹配。按照匹配长度可以分为最长/最大匹配和最短/最小匹配。

本程序使用的是结巴分词。jieba是一个基于Python的中文分词工具。对于一长段文字，其分词原理大体可分为三步：

1.首先用正则表达式将中文段落粗略的分成一个个句子。

2.将每个句子构造成有向无环图，之后寻找最佳切分方案。

3.最后对于连续的单字，采用HMM模型将其再次划分

程序实现：

​ 首先结合网页索引从原始网页库中读取一篇篇原始网页，逐网页进行分析。读取到一篇网页之后，根据正则表达式找出其中的中文内容，之后对这些内容进行切词，根据得到的切词结果，进一步构造倒排文件。

部分代码如下：

url, data = read_raw_info(rawfile, pageIndex['offset'])
            #data = data.decode('utf-8')
data_list = re.findall('[\u4e00-\u9fa5]', data)
data_str = "".join(data_list)
token = jieba.tokenize(data_str, mode='search')

搜索引擎的模糊查询。同时还会返回一个分词结果列表，不仅存储分词结果，还存储分的词的起始位置和结束位置。如下图所示：

六、 倒排文件

我们切词之后得到的结果是正向索引，为了提高查找效率，我们需要生成倒排文件。

本程序中使用的是字典存储倒排索引，键是一个个关键词，值对应的是一个列表，列表中的每一项都是一个列表（列表的元素按顺序是：文档编号、关键词在该篇文档中出现的次数，最后是每次出现的位置），其对应一个网页。如上图所示。这样一个二维列表就存储了该关键词在所有文档中出现的次数与位置。

编程实现：见process.py

# 将一篇文档的所有token加入倒排文件
def insert_invertion(token, id):
    for tk in token:
        if tk[0] in invert_dic:
            # 当前词在字典已经出现过
            # print(invert_dic[tk[0]])
            if id == invert_dic[tk[0]][-1][0]:
                invert_dic[tk[0]][-1][1] += 1
                invert_dic[tk[0]][-1].append(tk[1])
            else:
                invert_dic[tk[0]].append([id, 1, tk[1]])
        else:
            invert_dic[tk[0]] = []
            invert_dic[tk[0]].append([id, 1, tk[1]])

上述算法是将一篇文档建立倒排文件，之后遍历所有文档即可建立所有的倒排文件。

​ 还要将倒排索引进行排序（这样便于显示搜索结果），遍历每个关键词，按照每个文档中当前关键词出现的频次进行排序，这样在搜索该关键词时，显示的结果将会是提前排好序的。

​ 最后调用之前写好的方法，将字典写如json格式的文件中：invert.json。

七、 查询服务

查询服务包括接受用户输入的查询短语、检索、获得相应的匹配结果并显示给用户。搜索引擎三段式工作流程的最后一个环节。

​ 实现流程：首先接受输入的词汇，之后读取倒排文件，找到相关词汇的文档序号。由于生成倒排文件时已经按照词频排好序，又因为查询结果排序我使用的就是词频，所以得到相关文档的序号的列表之后即是我们需要显示的内容。有时相关文章太多，那么将显示部分网页。

​ 根据要显示的网页的序号，我们还需要读取原始网页库，获取url和标题和摘要。获取url和标题较为简单，摘要的生成是截取关键词前后的一定词，词的数量通过程序中abstract_ahead_offset和abstract_len参数来实现，其表示关键词前多少个字和一共取得长度。

程序实现：search.py

general_pageinfo（）：

输入：倒排索引关键词对应的列表数组里的一个列表，也就是一篇文档的倒排索引：[文档id，词频, 索引词每次出现的位置……]

输出：标题、url，摘要

def general_pageinfo(page):
    no = page[0]
    # time = page[1]
    pos = page[2:]
    raw_offset = pageIndexs[no]['offset']
    rawfile = open('raw.txt', 'r', encoding='UTF-8')
    url, data = process.read_raw_info(rawfile, raw_offset)
    soup = BeautifulSoup(data, 'html.parser')
    title = soup.find("title")
    data_list = re.findall('[\u4e00-\u9fa5]', data)
    data_str = "".join(data_list)
    abstract = get_abstract(data_str, pos[0])
    rawfile.close()
    return title.text, url, abstract

生成摘要：get_abstract（）

注意：生成的摘要的内容仅包括关键词第一次出现位置的前后文。

输入：原始网页正文，关键词偏移

输出：关键词前后的一定长度的上下文

def get_abstract(data, offset):
    if(offset > abstract_ahead_offset):
        offset -= abstract_ahead_offset
    else:
        offset = 0
    return data[offset : offset + abstract_len]

八、 Web页面

Web页面用的是Flask。运行web.py，然后就可以打开浏览器访问http://127.0.0.1:5000/。

Web页面只有两部分。一部分是主页index.html，一部分是搜索结果显示页面search.html。在主页输入搜索词，然后点击搜索，就会跳转到显示结果界面。关于网页的css用的是仿百度的。

​ 全部代码见web.py，关键函数：

@app.route("/", methods=['POST', 'GET'])
def mainpage():
    if request.method == 'POST' and request.form.get('inputs'):
        inputs = request.form['inputs']
        return redirect(url_for('search', inputs=inputs))
    return render_template('index.html')

@app.route("/search/<inputs>", methods=['POST', 'GET'])
def search(inputs):
    results = SE.search(inputs)
    highlight_results = highlight(results, inputs)
    return render_template('search.html', results=highlight_results, value=inputs, length=len(results))

​ 首先是根地址，是搜索页面index.html，点击搜索按钮之后会发送POST请求到本地5000端口，并将搜索词作为表单上传。之后会运行mainpage函数，重定向到search，在本地搜索引擎搜索，之后再用模板search.html显示结果。

页面源代码和css见/templates下的html文件

九、 使用说明：

9.1 终端显示

首先在终端（推荐vscode执行，因为url可以点击）执行：python .\search.py

​ 之后会提示输入查询词，若有查询结果，则显示相关结果，否则提示未找到相关词汇。

9.2 Web

​ 首先打开终端，运行：python web.py

之后打开http://127.0.0.1:5000/即可，就有如下画面：

之后就可以开始搜索，如“融水县”

再次点击搜索会返回主页。搜索框还会显示搜索记录。