搜索的流程及重要算法

搜索引擎的部分到这里就讲完了,我在本章末总结一下搜索的流程:

建立一个搜索引擎需要三个步骤:用网络爬虫爬取相当数量的网页,在搜索的过程中为每个关键字建立索引,对搜索到的网页进行排序。

爬取网页

网络爬虫爬取的过程有一个大的调度系统来统一指挥。我们从互联网上随机选取一个网页进行爬取,综合运用深度优先遍历广度优先遍历决定网页爬取的顺序,并存入优先级队列当中;由于互联网的结构错综复杂,为了避免重复下载,我们应用哈希技术来记录网页的爬取情况。

建立索引

在爬取所有的网页之后,对于每一次搜索,我们应用了布尔代数将搜索语句转化为表达式,将关键字进行特殊处理后形成一张大表,该表的每一行为一个关键字,每个关键字后面跟随一群数字,每个数字对应一个网页。至此,每个搜索关键字的索引建立完毕。

网页排序

最后一个步骤是对搜索到的网页进行排序,这里应用了Pagerank算法TF-IDF算法,前者确定一个网页的可信赖程度,后者确定了该网页与搜索的相关性程度,二者的乘积决定了该网页在所有网页中的顺序。Pagerank算法为互联网中所有网页都设定了一个权值,当计算某个网页的可信赖程度时,如果引用该网页的网页很多,而且引用该网页的这些网页权值都很大,那么这个网页的可信赖程度自然很高;TF-IDF算法统计每个搜索关键字的权值(在互联网中,包含该关键字的网页越少,该关键字权值越大)和在某篇文章的频率(关键字在该文章出现的次数除以文章长度),最后计算所有关键字的权值频率之积的求和即得出该网页与本次搜索的相关性程度。