【搜索引擎设计:信息搜索怎么避免大海捞针?

news/2024/2/23 15:22:00/文章来源:https://blog.csdn.net/Y_hanxiong/article/details/135575584

在前面我们提到了网页爬虫设计:如何下载千亿级网页?中,我们讨论了大型分布式网络爬虫的架构设计,但是网络爬虫只是从互联网获取信息,海量的互联网信息如何呈现给用户,还需要使用搜索引擎完成。因此,我们准备开发一个针对全网内容的搜索引擎,产品名称为“Bingoo”。

Bingoo 的主要技术挑战包括:

  1. 针对爬虫获取的海量数据,如何高效地进行数据管理;
  2. 当用户输入搜索词的时候,如何快速查找包含搜索词的网页内容;
  3. 如何对搜索结果的网页内容进行排序,使排在搜索结果列表前面的网页,正好是用户期望看到的内容。

因此,针对此类问题,我们开发一个搜索引擎系统!

1、概要设计

一个完整的搜索引擎包括分布式爬虫、索引构造器、网页排名算法、搜索器等组成部分,Bingoo 的系统架构如下:

image-20231226130403138

分布式爬虫通过存储服务器将爬取的网页存储到分布式文件集群 HDFS,为了提高存储效率,网页将被压缩后存储。存储的时候,网页一个文件挨着一个文件地连续存储,存储格式如下:

image-20231226130455447

每个网页被分配得到一个 8 字节长整型 docID,docID 之后用 2 个字节记录网页的 URL的长度,之后 4 个字节记录压缩后网页内容数据的长度,所有存储的网页的头 14 个字节都是同样的格式。之后存储 URL 字符串和压缩后的网页内容数据。读取文件的时候,先读14 个字节的头信息,根据头信息中记录的 URL 长度和数据长度,再读取对应长度的 URL和网页内容数据。

搜索引擎能够快速查找的核心就是利用索引,根据用户的查询内容查找匹配的索引,根据索引列表构建结果页面。索引的构造主要通过索引构造器完成,索引构造器读取 HDFS 中的网页内容,解压缩后提取网页中的单词,构建一个“docID-> 单词列表”的正排索引。然后,索引构造器再根据这个正排索引构建一个“单词 ->docID 列表”的倒排索引,“docID 列表”就是包含了这个单词的所有网页列表。利用这个倒排索引,搜索器可以快速获得用户搜索词对应的所有网页。

网页中所有的单词构成了一个词典,实际上,词典就是一个 Hash 表,key 就是单词,value 就是倒排索引的网页列表。虽然互联网页的内容非常庞大,但是使用到的单词其实是非常有限的。根据 Google 的报告,256M 内存可以存放 1400 万个单词,这差不多就是英文单词的全部了。

在构建索引的过程中,因为要不断修改索引列表,还要进行排序,所以,有很多操作是需要进行加锁同步完成的。对于海量的互联网页的计算,这样的索引构建速度太慢了。因此我们设计了 64 个索引桶,根据 docID 取模,将不同网页分配到不同的桶中,在每个桶中分别进行索引构建,通过并行计算来加快索引处理速度。

索引构造器在读取网页内容、构造索引的时候,还会调用 URL 提取器,将网页中包含的URL 提取出来,构建一个链接关系表。链接关系表的格式是“docID->docID”,前一个docID 是当前网页的 docID,后一个 docID 是当前网页中包含的 URL 对应的 docID。一个网页中会包含很多个 URL,也就是会构建出很多个这样的链接关系。后面会利用这个链接关系表,使用 PageRank 排名算法对所有网页进行打分排名,当索引器得到查找的网页列表时,利用 PageRank 值进行排名,最终呈现给用户,保证用户最先看到的网页是最接近用户期望的结果页面。

2、详细设计

一个运行良好的搜索引擎的核心技术就是索引和排名,所以我们将分别说明这两种技术要点!

1、索引

索引构造器从 HDFS 读取网页内容后,解析每个页面,提取网页里的每个单词。如果是英文,那么每个单词都用空格分隔,比较容易;如果是中文,需要使用中文分词器才能提取到每个单词,比如“高并发架构”,使用中文分词器得到的就是“高并发”、“架构”两个词。

首先,索引构造器将所有的网页都读取完,构建出所有的“docID-> 单词列表”正排索引。

image-20231226131318766

然后遍历所有的正排索引,再按照“单词→docID 列表”的方式组织起来,就是倒排索引了。

image-20231226131337477

我们这个例子中只有两个单词、7 个网页。事实上,Bingoo 数以千亿的网页就是这样通过倒排索引组织起来的,网页数量虽然庞大,但是单词数却是比较有限的。所以,整个倒排索引的大小相比于网页数量要小得多。Bingoo 将每个单词对应的网页列表存储在硬盘中,而单词则存储在内存的 Hash 表,也就是词典中,词典示例:

image-20231226131444415

对于部分热门的单词,整个网页列表也可以存储在内存中,相当于缓存。在词典中,每个单词记录下硬盘或者内存中的网页列表地址,这样只要搜索单词,就可以快速得到对应的网页地址列表。Bingoo 根据列表中的网页编号 docID,展示对应的网页信息摘要,就完成了海量数据的快速检索。

如果用户的搜索词正好是一个单词,比如“高并发”,那么直接查找词典,得到网页列表就完成查找了。但是如果用户输入的是一个句话,那么搜索器就需要将这句话拆分成几个单词,然后分别查找倒排索引。这样的话,得到的就是几个网页列表,还需要对这几个网页列表求交集,才能得到最终的结果列表。

比如,用户输入“高并发架构”进行搜索,那么搜索器就会拆分成两个词:“高并发”、“架构”,得到两个倒排索引:

  • 高并发 ->2,3,5,7

  • 架构 ->1,2,4

需要对这两个倒排索引求交集,也就是同时包含“高并发”和“架构”的网页才是符合搜索要求的结果,最终的交集结果应该是只有一篇网页,即 docID 为 2 的满足要求。

列表求交集最简单的实现就是双层 for 循环,但是这种算法的时间复杂度是 O(n^2),我们的网页列表长度(n)可能有千万级甚至更高,这样的计算效率太低。

一个改进的算法是拉链法,我们将网页列表先按照 docID 的编号进行排序,得到的就是这样两个有序链表:

image-20231226131628561

同时遍历两个链表,如果其中一个链表当前指向的元素小于另一个链表当前指向的元素,那么这个链表就继续向前遍历;如果两个链表当前指向的元素相同,该元素就是交集元素,记录在结果列表中;依此继续向前遍历,直到其中一个链表指向自己的尾部 nil。

拉链法的时间复杂度是 O(2n),远优于双层循环。但是对于千万级的数据而言,还是太慢。我们还可以采用数据分片的方式进行并行计算,以实现性能优化。

比如,我们的 docID 分布在[0, 1 万亿) 区间,而每个倒排索引链表平均包含 1 千万个docID。我们把所有的 docID 按照 1 千亿进行数据分片,就会得到 10 个区间[0, 1 千亿)[1千亿,2 千亿)……[9 千亿,1 万亿)。每个倒排索引链表大致均匀分布在这 10 个区间,我们就可以依照这 10 个区间范围,将每个要遍历的链表切分为 10 片,每片大约包含 1 百万个 docID。两个链表只在自己对应的分片内求交集即可,因此我们可以启动 10 个线程对10 个分片进行并行计算,速度可提高 10 倍。

事实上,两个 1 千万长度的链表求交集,最终的结果可能不过几万,也就是说,大部分的比较都是不相等的。比如下面的例子。

image-20231226131736242

第一个链表遍历到自己的最后一个元素,才和第二个链表的第一个元素相同。那么第一个链表能不能跳过前面那些元素呢?很自然,我们想到可以用跳表来实现,如下图:

image-20231226131804802

跳表实际上是在链表上构建多级索引,在索引上遍历可以跳过底层的部分数据,我们可以利用这个特性实现链表的跳跃式比较,加快计算速度。使用跳表的交集计算时间复杂度大约是 O(log(n))。

此外,虽然搜索引擎利用倒排索引已经能很快得到搜索结果了,但搜索引擎应用还会使用缓存对搜索进行加速,将整个搜索词对应的搜索结果直接放入缓存,以减少倒排索引的访问压力,以及不必要的集合计算。

2、PageRank 排名算法

Bingoo 使用 PageRank 算法进行网页结果排名,以保证搜索结果更符合用户期待。

PageRank 算法会根据网页的链接关系给网页打分。如果一个网页 A 包含另一个网页 B 的超链接,那么就认为 A 网页给 B 网页投了一票。一个网页得到的投票越多,说明自己越重要;越重要的网页给自己投票,自己也越重要。

PageRank 算法就是计算每个网页的 PageRank 值,最终的搜索结果也是以网页的PageRank 值排序,展示给用户。事实证明,这种排名方法非常有效,PageRank 值更高的网页,确实更满足用户的搜索期望。

以下面四个网页 A、B、C、D 举例,带箭头的线条表示链接。

image-20231226132710017

B 网页包含了 A、D 两个页面的超链接,相当于 B 网页给 A、D 每个页面投了一票,如果初始的时候,所有页面都是 1 分,那么经过这次投票后,B 给了 A 和 D 每个页面 1/2 分(B 包含了 A、D 两个超链接,所以每个投票值 1/2 分),自己从 C 页面得到 1/3 分(C包含了 A、B、D 三个页面的超链接,每个投票值 1/3 分)。

而 A 页面则从 B、C、D 分别得到 1/2,1/3,1 分。用公式表示就是

image-20231226132751916

等号左边是经过一次投票后,A 页面的 PageRank 分值;等号右边每一项的分子是包含 A页面超链接的页面的 PageRank 分值,分母是该页面包含的超链接数目。

这样经过一次计算后,每个页面的 PageRank 分值就会重新分配,重复同样的算法过程,经过几次计算后,根据每个页面 PageRank 分值进行排序,就得到一个页面重要程度的排名表。根据这个排名表,将用户搜索出来的网页结果排序,排在前面的通常也正是用户期待的结果。

但是这个算法还有个问题,如果某个页面只包含指向自己的超链接,其他页面不断给它送分,而自己一分不出,随着计算执行次数越多,它的分值也就越高,这显然是不合理的。这种情况就像下图所示的,A 页面只包含指向自己的超链接。

image-20231226132818673

解决方案是,设想浏览一个页面的时候,有一定概率不是点击超链接,而是在地址栏输入一个 URL 访问其他页面,表示在公式上,就是

image-20231226132837504

上面 (1 - a)就是跳转到其他任何页面的概率,通常取经验值 0.15(即 为 0.85),因为有一定概率输入的 URL 是自己的,所以加上上面公式最后一项,其中分母 4 表示所有网页的总数。

那么对于 N 个网页,任何一个页面 的 PageRank 计算公式如下:

image-20231226132918850

公式中 Pj ∈ M(P**i), 表示所有包含有 超链接的 , 表示 页面包含的超链接数,N 表示所有的网页总和。由于 Bingoo 要对全世界的网页进行排名,所以这里的 N 是一个万亿级的数字。

计算开始的时候,将所有页面的 PageRank 值设为 1,带入上面公式计算,每个页面都得到一个新的 PageRank 值。再把这些新的 PageRank 值带入上面的公式,继续得到更新的PageRank 值,如此迭代计算,直到所有页面的 PageRank 值几乎不再有大的变化才停止

3、总结

PageRank 算法我们现在看起来平平无奇,但是正是这个算法造就了 Google 近 2 万亿美元的商业帝国。在 Google 之前,Yahoo 已经是互联网最大的搜索引擎公司。按照一般的商业规律,如果一个创新公司不能带来十倍的效率或者体验提升,就根本没有机会挑战现有的巨头。而 Google 刚一出现,就给 Yahoo 和旧有的搜索引擎世界带来摧枯拉朽的扫荡,用户体验的提升不止十倍,这其中的秘诀正是 PageRank。

二十几年前,我刚刚接触编程的时候,我们中国也有很多这样的编程英雄,王选、王江民、求伯君、雷军等等,他们几乎凭一己之力就创造出一个行业。正是对这些英雄们的崇拜和敬仰,引领我在编程这条路上一直走下去。软件编程是一个可以创造奇迹的地方,而不只是为了混碗饭吃。梦想不能当饭吃,但是梦想带来的可不止是一碗饭。

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925911.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Flutter-Web从0到部署上线(实践+埋坑)

本文字数:7743字 预计阅读时间:60分钟 01 前言 首先说明一下,这篇文章是给具备Flutter开发经验的客户端同学看的。Flutter 的诞生虽然来自 Google 的 Chrome 团队,但大家都知道 Flutter 最先支持的平台是 Android 和 iOS&#xff…

c语言-数据类型(下)

目录 4.实型变量 5.字符常量 直接常量: 转义字符: 6.字符变量 7.字符串常量 五、输出格式总结 整型: 浮点型: 字符及字符串: 指针(地址): 六、typedef 七、sizeof一个问…

鸿蒙开发之blank组件

一、使用 使用blank可以在row/column/flex在容器主轴方向上填充剩余部分。 可以通过设置min最小宽度/高度来控制填充的大小, 也可以通过backgroundColor设置背景颜色来改变默认的透明色填充。 //设置最小宽度为200,填充颜色灰色 Blank(200).backgrou…

项目架构之Zabbix部署

1 项目架构 1.1 项目架构的组成 业务架构:客户端 → 防火墙 → 负载均衡(四层、七层) → web缓存/应用 → 业务逻辑(动态应用) → 数据缓存 → 数据持久层 运维架构:运维客户端 → 跳板机/堡垒机&#x…

AttributeError: module ‘openai‘ has no attribute ‘error‘解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

RIP【新华三与华为区别】

【介绍】 rip分为rip 1 与 rip 2 ,rip 2 是对 rip 1 的一种升级,rip 2 可以进行认证等功能 【命令】 新华三: [HC3-R1] rip #启用rip [HC3-R1-rip] version 2 #告知rip 版本号 [HC3-R1-rip] network 192.168.1.0 #宣告其网段 [HC3-R1-rip] …

【NI-DAQmx入门】LabVIEW中DAQmx同步

1.同步解释 1.1 同步基础概念 触发器:触发器是控制采集的命令。您可以使用触发器来启动、停止或暂停采集。触发信号可以源自软件或硬件源。 时钟:时钟是用于对数据采集计时的周期性数字信号。根据具体情况,您可以使用时钟信号直接控制数据采…

深度学习记录--正则化(regularization)

什么是正则化? 正则化(regularization)是一种实用的减少方差(variance)的方法,也即避免过度拟合 几种正则化的方法 L2正则化 又被称为权重衰减(weight dacay) 在成本函数中加上正则项: 其中 由于在w的更新过程中会递减,即权…

鸿蒙HarmonyOS实战-工具安装和Helloworld案例

🚀前言 HarmonyOS是华为自主开发的操作系统,它在2020年9月正式发布。它最初被称为鸿蒙OS,后来更名为HarmonyOS。HarmonyOS旨在提供一种可在各种设备上无缝运行的统一操作系统,包括智能手机、平板电脑、智能穿戴设备、智能音箱、车…

代码随想录 Leetcode541. 反转字符串 II

题目&#xff1a; 代码(首刷自解 2024年1月16日&#xff09;&#xff1a; class Solution { public:void reverse(string& s,int left,int right) {char temp;while (left < right) {temp s[left];s[left] s[right];s[right] temp;left;--right;}return;}string rev…

分类预测 | Matlab实现CS-SVM布谷鸟算法优化支持向量机的数据分类预测

分类预测 | Matlab实现CS-SVM布谷鸟算法优化支持向量机的数据分类预测 目录 分类预测 | Matlab实现CS-SVM布谷鸟算法优化支持向量机的数据分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现CS-SVM布谷鸟算法优化支持向量机的数据分类预测。 2.自带数据…

Qt QRubberBand 如何实现鼠标框选控件

QRubberBand类提供了一个矩形或直线&#xff0c;可以指示选择或边界。常见的模式是结合鼠标事件来执行此操作。本文将使用框选QCheckBox控件&#xff0c;来演示QRubberBand是如何配合鼠标进行工作的。 一、RubberBand 框选效果图 二、RubberBand 代码 rubberband.h #ifndef …

用LED数码显示器伪静态显示数字1234

#include<reg51.h> // 包含51单片机寄存器定义的头文件 void delay(void) //延时函数&#xff0c;延时约0.6毫秒 { unsigned char i; for(i0;i<200;i) ; } void main(void) { while(1) //无限循环 { P20xfe; …

TS学习笔记四:函数及泛型枚举

本节介绍ts的函数及泛型的相关内容&#xff0c;包括函数的声明格式及泛型的相关知识。 视频讲解 TS学习笔记四&#xff1a;函数的定义使用 B站视频 TS学习笔记四&#xff1a;函数的定义使用 西瓜视频 https://www.ixigua.com/7321535978286514727 一、函数 函数是js程序的…

[oeasy]python005_退出游乐场_重启游乐场_系统态shell_应用态_quit

0005_ 退出游乐场_重启游乐场_系统态shell 退出终端_重启游乐场_shell_quit &#x1f94a; Python 回忆 上次 了解了 python进入了 python 游乐场 在游乐场 可以做 简单的计算还可以做 乘方运算 数字特别大之后 游乐场 会迟疑一下不过 最终 还是能算出来 可以让数字 更大一…

Vue学习笔记3--全局事件总线

Vue学习笔记3—全局事件总线 1.全局事件总线可以实现任意组件间通信 X需具备的条件&#xff1a; 所有的组件都要能看见X可以调用$on $off $emitVue.prototype.x {a:1, b:2} 可以被所有组件看见VueComponent.protoype.proto Vue.prototype组件实例对象(vc)可以访问到Vue原型上…

Java多线程并发篇----第十八篇

系列文章目录 文章目录 系列文章目录前言一、寄存器二、程序计数器三、PCB-“切换桢”四、上下文切换的活动五、引起线程上下文切换的原因前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了…

QT软件在线安装与维护

一.安装 安装QT开发环境分离线安装和在线安装两种方式&#xff0c;具体步骤如下&#xff1a; QT官网注册账号----下载安装包-----安装-----选择要安装的版本与开发包----版本维护 注意&#xff1a;Qt5.14.2是最后提供二进制安装包的版本&#xff0c;后面的版本都需要在线安装…

小程序系列--7.页面配置以及网络数据请求

一. 页面配置 1.页面配置文件的作用 小程序中&#xff0c;每个页面都有自己的 .json 配置文件&#xff0c;用来对当前页面的窗口外观、页面效果等进行配置。 2. 页面配置和全局配置的关系 3. 页面配置中常用的配置项 二、网络数据请求 1. 小程序中网络数据请求的限制 2. 配…

数据分析中常用的指标或方法

一、方差与标准差二、协方差三、皮尔逊系数四、斯皮尔曼系数 一、方差与标准差 总体方差 V a r ( x ) σ 2 ∑ i 1 n ( x i − x ˉ ) 2 n ∑ i 1 n x i 2 − n x ˉ 2 n E ( x 2 ) − [ E ( x ) ] 2 Var(x)\sigma^2\frac {\sum\limits_{i1}^{n} (x_i - \bar{x})^2} {n…