做视频网站一般多少钱,抚州网站seo,建设银行贷款官方网站,网站做数学题文章目录1. 整体系统介绍2. 搜集2.1 待爬取网页链接文件#xff1a;links.bin2.2 网页判重文件#xff1a;bloom_filter.bin2.3 原始网页存储文件#xff1a;doc_raw.bin2.4 网页链接及其编号的对应文件#xff1a;doc_id.bin3. 分析3.1 抽取网页文本信息3.2 分词并创建临时…
文章目录1. 整体系统介绍2. 搜集2.1 待爬取网页链接文件links.bin2.2 网页判重文件bloom_filter.bin2.3 原始网页存储文件doc_raw.bin2.4 网页链接及其编号的对应文件doc_id.bin3. 分析3.1 抽取网页文本信息3.2 分词并创建临时索引4. 索引5. 查询6. 总结搜索引擎实现起来技术难度非常大技术的好坏直接决定了产品的核心竞争力。 搜索引擎的设计与实现中会用到大量的算法。百度、Google 这样的搜索引擎公司面试时会格外重视考察候选人的算法能力。
1. 整体系统介绍
以下介绍如何在一台机器上假设内存是8GB硬盘是100多GB通过少量的代码实现一个小型搜索引擎。
搜索引擎大致分为四个部分搜集、分析、索引、查询。
搜集就是利用爬虫爬取网页。分析主要负责网页内容抽取、分词构建临时索引计算PageRank值。索引主要负责通过分析阶段得到的临时索引构建倒排索引。查询主要负责响应用户的请求根据倒排索引获取相关网页计算网页排名返回查询结果给用户。
2. 搜集
互联网越来越发达网站越来越多对应网页也越来越多。对于搜索引擎来说它事先并不知道网页都在哪里。那搜索引擎是如何爬取网页的呢
搜索引擎把整个互联网看作 有向图把每个页面看作一个顶点。如果某个页面中包含另外一个页面的链接就在两个顶点之间连一条有向边。利用图的遍历搜索算法来遍历整个互联网中的网页。
搜索引擎采用的是广度优先搜索策略。具体点讲的话先找一些比较知名的网页权重比较高的链接比如新浪主页、腾讯主页作为种子网页链接放入到队列中。爬虫按照广度优先的策略不停地从队列中取出链接然后爬取对应的网页解析出网页里包含的其他网页链接再将解析出来的链接添加到队列中。
2.1 待爬取网页链接文件links.bin
广度优先搜索爬取页面过程中爬虫会不停地解析页面链接将其放到队列中。于是队列中的链接会越来越多可能多到内存放不下。所以用一个存储在磁盘中的文件links.bin来作为广度优先搜索中的队列。爬虫从links.bin文件中取出链接去爬取对应的页面。等爬取到网页之后将解析出来的链接直接存储到links.bin文件中。这样用文件来存储网页链接的方式还有其他好处。比如支持断点续爬。当机器断电之后网页链接不会丢失重启之后还可以从之前爬取到的位置继续爬取。
如何解析页面获取链接可以把整个页面看作一个大的字符串利用字符串匹配算法搜索这样一个网页标签然后顺序读取之间的字符串就是网页链接。
2.2 网页判重文件bloom_filter.bin
如何避免重复爬取相同的网页呢使用布隆过滤器就可以快速并且非常节省内存地实现网页的判重。
如果把布隆过滤器存储在内存中宕机重启后布隆过滤器就被清空了。可能导致大量已经爬取的网页会被重复爬取。
我们可以定期地比如每隔半小时将布隆过滤器持久化到磁盘中存储在bloom filter.bin文件中。即便出现机器宕机也只会丢失布隆过滤器中的部分数据。当机器重启后就可以重新读取磁盘中的bloom_filter.bin文件将其恢复到内存中。
2.3 原始网页存储文件doc_raw.bin
爬取到网页后需要将其存储下来以备后面离线分析、索引之用。如何存储海量的原始网页呢
如果把每个网页都存储为一个独立的文件那磁盘中的文件会非常多。常用的文件系统显然不适合存储如此多的文件。所以可以把多个网页存储在一个文件中。每个网页之间通过标识进行分隔方便后续读取。具体的存储格式如图所示。其中doc_id这个字段是网页的编号。 这样的一个文件也不能太大因为文件系统对文件的大小也有限制。所以我们可以设置每个文件的大小上限比如1GB。随着越来越多的网页被添加到文件中文件越来越大当超过1GB的时候就创建一个新文件用来存储新爬取的网页。
假设机器的硬盘大小是100GB左右一个网页的平均大小是64KB。那在一台机器上我们可以存储100万到200万左右的网页。假设机器的带宽是10MB那下载100GB的网页大约要10000秒。也就是说爬取100多万的网页只需要花费几小时的时间。
2.4 网页链接及其编号的对应文件doc_id.bin
网页编号就是给每个网页分配一个唯一的ID方便后续对网页分析、索引。那如何给网页编号呢
可以按照网页被爬取的先后顺序从小到大依次编号。具体是这样做的维护一个中心的计数器每爬取到一个网页就从计数器中拿一个号码分配给这个网页然后计数器加一。存储网页的同时将网页链接跟编号之间的对应关系存储在另一个doc_id.bin文件中。
爬取网页的过程中涉及的四个重要的文件links.bin 和 bloom filter.bin 这两个文件是爬虫自身所用的。另外两个doc raw.bin、doc id.bin是作为搜集阶段的成果供后面的分析、索引、查询用。
3. 分析
网页爬下来后需要对网页进行离线分析。主要包括两个步骤1. 抽取网页文本信息2. 分词并创建临时索引。
3.1 抽取网页文本信息
网页是半结构化数据里面夹杂着各种标签、JavaScript代码、CSS样式。搜索引擎只关心网页中的文本信息我们依靠HTML标签来抽取网页中的文本信息大体可以分为两步。
第一步是去掉JavaScript代码、CSS格式以及下拉框中的内容因为下拉框在用户不操作的情况下也是看不到的。也就是style/stylescript/scriptoption/option这三组标签之间的内容。可以利用AC自动机这种多模式串匹配算法一次性查找stylescriptoption这三个关键词。当找到某个关键词出现的位置之后只需要依次往后遍历直到对应结束标签/style/script/option为止。这期间遍历到的字符串连带着标签就应该从网页中删除。第二步是去掉所有HTML标签。也是通过字符串匹配算法来实现的。
3.2 分词并创建临时索引
经过上面的处理我们就从网页中抽取出了我们关心的文本信息。接下来要对文本信息进行分词并且创建临时索引。
对英文网页来说分词非常简单。只需要通过空格、标点符号等分隔符将每个单词分割开来就可以了。对于中文来说分词就复杂太多了。介绍一种比较简单的思路基于字典和规则的分词方法。
字典也叫词库里面包含大量常用的词语。借助词库并采用最长匹配规则来对文本进行分词。所谓最长匹配也就是匹配尽可能长的词语。具体到实现层面我们可以将词库中的单词构建成Trie树结构然后拿网页文本在Trie 树中匹配。
每个网页的文本信息在分词完成后都得到一组单词列表。把单词与网页之间的对应关系写入到一个临时索引文件中tmp_Index.bin这个临时索引文件用来构建倒排索引文件。临时索引文件的格式如下 在临时索引文件中我们存储的是单词编号term_id而非单词本身。这样做的目的主要是为了节省存储空间。这些单词的编号是怎么来的呢
给单词编号的方式跟给网页编号类似。维护一个计数器每当从网页文本信息中分割出一个新单词的时候就从计数器中取一个编号分配给它然后计数器加一。
在这个过程中我们还需要使用散列表记录已经编过号的单词。在对网页文本信息分词的过程中我们拿分割出来的单词先到散列表中查找如果找到那就直接使用已有的编号如果没有找到再去计数器中拿号码并且将这个新单词以及编号添加到散列表中。
当所有的网页处理分词及写入临时索引完成之后再将这个单词跟编号之间的对应关系写入到磁盘文件中并命名为term_id.bin。
经过分析阶段得到了两个重要的文件。它们分别是临时索引文件tmpindex.bin和单词编号文件term_id.bin。
4. 索引
索引主要负责将分析阶段产生的临时索引构建成倒排索引。倒排索引Inverted index中记录了每个单词以及包含它的网页列表。 如何通过临时索引文件构建出倒排索引文件呢
考虑到临时索引文件很大无法一次加载到内存搜索引擎一般会选择使用多路归并排序的方法来实现。
先对临时索引文件按照单词编号的大小排序。因为临时索引很大所以一般基于内存的排序算法就没法处理这个问题。可以用归并排序的处理思想将其分割成多个小文件先对每个小文件独立排序最后再合并在一起。实际的软件开发中可以直接利用MapReduce来处理。临时索引文件排序完成之后相同的单词就被排列到了一起。只需顺序地遍历排好序的临时索引就能将每个单词对应的网页编号列表找出来然后把它们存储在倒排索引文件中。如图。 除了倒排文件之外我们还需要一个文件来记录每个单词编号在倒排索引文件中的偏移位置。把这个文件命名为term_offset.bin。这个文件的作用是帮助我们快速地查找某个单词编号在倒排索引中存储的位置进而快速地从倒排索引中读取单词编号对应的网页编号列表。 经过索引阶段的处理我们得到倒排索引文件index.bin和记录单词编号在索引文件中的偏移位置的文件term_ofset.bin。
5. 查询
前面三个阶段的处理只是为了最后的查询做铺垫。
doc_id.bin记录网页链接和编号之间的对应关系。term_id.bin记录单词和编号之间的对应关系。index.bin倒排索引文件记录每个单词编号以及对应包含它的网页编号列表term_offsert.bin记录每个单词编号在倒排索引文件中的偏移位置。
除了倒排索引文件index.bin比较大之外其他的都比较小。为了方便快速查找数据将其他三个文件都加载到内存中并且组织成散列表这种数据结构。
当用户在搜索框中输入某个查询文本的时候先对用户输入的文本进行分词处理。假设分词之后得到k个单词。
拿这k个单词去term_id.bin对应的散列表中查找对应的单词编号。经过这个查询之后得到了这k个单词对应的单词编号。
拿这k个单词编号去term_offset.bin对应的散列表中查找每个单词编号在倒排索引文件中的偏移位置。得到了k个偏移位置。
拿这k个偏移位置去倒排索引index.bin中查找k个单词对应的包含它的网页编号列表。得到了k个网页编号列表。
针对这k个网页编号列表统计每个网页编号出现的次数。我们可以借助散列表来进行统计。统计得到的结果我们按照出现次数的多少从小到大排序。出现次数越多说明包含越多的用户查询单词用户输入的搜索文本经过分词之后的单词。
经过一系列查询就得到了一组排好序的网页编号。拿着网页编号去doc_id.bin文件中查找对应的网页链接分页显示给用户就可以了。
6. 总结
以上只是一个搜索引擎设计的基本原理有很多优化、细节并未涉及如计算网页权重的 PageRank 算法、计算查询结果排名的 tf-idf 模型等等。
涉及的数据结构和算法有图、散列表、Trie树、布隆过滤器、单模式字符串匹配算法、AC自动机、广度优先遍历、归并排序等。
如果有时间自己写代码实现一个简单的搜索引擎。即便只是一个demo但对于深入理解数据结构和算法是很有帮助的。
