- N +

搜索引擎的基石-倒排索引

文章目录 [+]

Google和百度这两家公司都挺能挣钱的,而给它们印钞票的机器就是搜索引擎,果果虽然没写过印钞机程序,但还是了解一些搜索引擎的原理,今天就聊聊它的基础,倒排索引。



先来回想一下我们使用搜索引擎的过程,输入一个或多个关键词,然后搜索引擎就返回了一个结果列表,这些搜索结果都是链接到不同的网页文档。这个过程其实很简单,对于搜索引擎,它要做的事情,就是从一大堆文档中,找出关键词的相关的文档,展示出来。


简单的做法就是,搜索引擎将会遍历它抓取到的所有文档,从中挑选出与关键词相关的文档,这种叫做正向索引。可是要知道,Google现在收录的网页数目是万亿级别的,要是真像这样遍历全部文档,那估计你搜索一个关键词,要等个一年才能看到搜索结果。


那么为了加快搜索速度,需要建立相反的一个索引的列表,在爬虫抓取回一个网页后,先对它进行分词处理,然后把这些提取出来的关键词与这个网页的ID做一个映射,这就是倒排索引(Inverted index)。


比如我们有编号T0-T2的三篇文档,它们的内容分别是:T0="it is what it is",T1="what is it",T2="it is a banana",可以对每篇文章都先分词处理,然后统计每个词对应的文档,得到这样一个倒排索引:


当我们要搜索"what is it"时,可以直接找出这三个词索引的文档编号的并集,即T0和T1,这就是用倒排索引搜索关键词的基本流程。所以平时我们使用搜索引擎时,它的搜索结果并不是实时查找出来的,而是使用了提前做好的倒排索引,将关键词的索引结果合并展示出来的。


当然了,倒排索引只是搜索引擎的一个基础架构,一个单词的索引结果也会有成百上千万个,如何对这些结果进行有效的排序,让用户真正想要的搜索结果排名靠前,才是关键技术。


搜索引擎都是倒排索引,即关键词对应文件(文档)的形式。


作者:huchao
未来永远在它该来的路上,能够把握的只是此时此刻——万折必东
返回列表
上一篇:
下一篇:
评论列表 (暂无评论,共510人参与)参与讨论

还没有评论,来说两句吧...

发表评论中国互联网举报中心

快捷回复: