时间戳

首页 > 技术文章 > 搜索引擎原理模拟

搜索引擎原理模拟

Qi-Lin 2020-06-22 17:20 原文

基本原理

搜索引擎由四部分组成：搜索器、索引器、检索器、用户接口。其运行过程如下：

  • 通过爬虫抓取网页
  • 建立索引数据库
  • 按索引进行排序
  • 处理用户请求，对查找结果排序

其中，网页的分析算法有pagerank，hits等，以下采用pagerank算法

搜索器

爬取的页面

为自己乱写了三个页面，便于验证自己的程序和之后的排序算法是否正确。这三个页面的引用关系为

爬虫

采用scrapy框架
新建爬虫项目：scrapy startproject search
然后进入目录，新建爬虫： scrapy genspider MySearch 爬取的域名，之后可以修改
然后修改spiders/MySearch.py文件
其中start_url是开始爬取的链接，parse函数是爬取后对结果的处理
爬取后，将爬取的页面为以网页链接命名的文件保存在result文件夹中，如下

并且同时生成引用关系的文件result2/reltion.txt，用于保存各个页面间的引用关系，如下第一行为index.html引用了1.html

MySearch.py文件如下

import scrapy
class MysearchSpider(scrapy.Spider):
    name = 'MySearch'
    start_urls = ['http://127.0.0.1/qilinweb/index.html']
    url = []

    def parse(self, response):
        name1 = response.url.split('/')[-1]
        f2 = open('D:/code/python/search/result/' + name1, 'w')
        # 保存爬取的内容
        f2.write(response.url + "\n" + response.text)
        # 对页面进行分析，提取每一个链接，加入到url中
        for href in response.css('a::attr(href)').extract():
            if href not in self.url:
                self.url.append(href)
                try:
                    name2 = href
                    # 保存页面的引用关系
                    with open('D:/code/python/search/result2/relation.txt', 'a+') as f:
                        f.write(name2.split('/')[-1] + "," + name1 + "\n")
                    yield scrapy.Request(href, callback=self.parse)  # 生成器，对每一个链接再进行爬取
                except:
                    continue
然后scrapy crawl MySearch进行爬取

爬取过程

索引器

因为页面比较简单，就不生成索引，直接对所有爬取保存的页面内容搜索

检索器

分为检索和排序两部分

检索

也比较简单，就是直接对所有爬取保存的页面内容搜索，代码在MyUser.py中的一小段
for file in fname:
f = open('D:/code/python/search/result/' + file, 'r')
if str in f.read():
result.append(file)

排序

采用pagerank算法，因为该算法是静态的，所以在爬取完页面后就可以直接生成各页面的等级，页面等级以字典形式保存在result2/weight.txt中

代码为MyIndex.py中

算法代码来自知乎https://zhuanlan.zhihu.com/p/81691075
但是感觉原作者算法实现好像有点问题，自己做了一下修改

# 用于存储图
class Graph():
    def __init__(self):
        self.linked_node_map = {}  # 邻接表，
        self.PR_map = {}  # 存储每个节点的入度
        self.L = {}  # 存每个节点的出度

    # 添加节点
    def add_node(self, node_id):
        if node_id not in self.linked_node_map:
            self.linked_node_map[node_id] = set({})
            self.PR_map[node_id] = 0
        else:
            print("这个节点已经存在")

    # 增加一个从Node1指向node2的边。允许添加新节点
    def add_link(self, node1, node2):
        if node1 not in self.linked_node_map:
            self.add_node(node1)
            self.L[node1] = 0
        else:
            self.L[node1] = self.L[node1] + 1
        if node2 not in self.linked_node_map:
            self.add_node(node2)
            self.L[node2] = 0
        else:
            self.L[node2] = self.L[node2] + 1
        self.linked_node_map[node1].add(node2)  # 为node1添加一个邻接节点，表示ndoe2引用了node1

    # 计算pr
    def get_PR(self, epoch_num=3, d=0.5):  # 配置迭代轮数，以及阻尼系数
        for i in range(epoch_num):
            for node in self.PR_map:  # 遍历每一个节点
                self.PR_map[node] = (1 - d) + d * sum(
                    [self.PR_map[temp_node] / self.L[temp_node] for temp_node in self.linked_node_map[node]])  # 原始版公式
        with open('D:/code/python/search/result2/weight.txt', 'w') as f:
            f.write(str(self.PR_map))


graph = Graph()
with open('D:/code/python/search/result2/relation.txt', 'r') as f:
    for line in f:
        node1, node2 = line.strip().split(',')
        graph.add_link(node1, node2)
    graph.get_PR()

用户接口

对输入的内容进行搜索，并且按页面的等级从高到低显示

程序在MyUser.py中

import os
import ast
# 按照页面等级排序
def p(s):
    return str[s]
str = input("搜索：")
fname = os.listdir(r'D:\code\python\search\result')
result = []
for file in fname:
    f = open('D:/code/python/search/result/' + file, 'r')
    if str in f.read():
        result.append(file)
f2 = open('D:/code/python/search/result2/weight.txt', 'r')
str = f2.read()
str = ast.literal_eval(str)  # 将读入的字符串转化为字典类型
show = sorted(result, key=p, reverse=True)
print("搜索结果如下\n")
print(show)

推荐阅读