18577975379 在线客服 联系我们 返回顶部
企业动态 技术分享 行业动态

算法与数据结构之美,搜索引擎中的算法与数据结构你知多少?

2020-03-15

我们常说阿里的运营,腾讯的产品,百度的技术。这背后是对百度技术的肯定,我们都知道,百度是靠搜索引擎起家,搜索引擎与电商与社交产品有明显的区别,有着非常强的技术驱动型。今天我们就来学习学习,搜索引擎大致是怎么组成的,背后的算法与数据结构是怎么样的,作为一个程序员,我们能否实现自己简单的搜索引擎呢?一个经典的搜索引擎,无论是谷歌、百度、微信的搜一搜还是淘宝的搜索,都离不开下面这这个基本过程,收集、分析、索引、查询。我们今天一个一个来介绍这背后的经典算法与数据结构。

首先是收集,最常见的便是爬虫,从各个网站中爬取对应的资料,根据网站的爬取顺序,我们常常有深度优先搜索,广度优先搜索等不同的爬取策略,为了避免爬取重复的网站,我们可能需要对网站的地址进行判重,常用的,我们可以使用布隆过滤器,可以做到非常高效的网站去重。当然,现在有一些搜索引擎也是不需要爬虫的,像淘宝的商品搜索,商家每发布新的产品,或者用户发表新的评论,都会发布异步的消息队列,由搜索引擎订阅并收集。那么多的基础元数据,我们通常需要给他们一个编号,有人说可以用Mysql存储,用自增主键id,那样一个表会非常大,要知道,网络上的网页何止千千万万,我们通常采用NoSql进行存储,同时我们也需要ID生成分配器,给每一个资源一个独立的ID。

程序员们都知道,在网页上我们虽然能看到丰富多彩的文案与图片,背后都是HTML格式的代码,我们需要去掉这些格式,才能获取到真实的文本。那么,如何在一个HTML文件中,去掉各种标签呢?最简单的,便是文本匹配,为了加快匹配的速度,通常我们会常用AC自动机等多模文本匹配算法进行优化,可以快速的去掉HTML页面上的各种标签。

那么多的网页,我们查询的时候,不可能每一个网页都去遍历,找到是否包含这个关键字。通常,我们采用的一个技术,便是倒排索引,什么是倒排索引的,最简单来说,就是记录每一个单词,在哪里出现过。举个简单例子,文章1的内容包含了“我和我的祖国,一刻都不能分割”,文章2的内容包含了“祝伟大祖国70周年生日快乐,繁荣富强”,文章3包含了“国庆节要放假了,程序员可以休息了”。那么,单词“祖国”的倒排索引上面就会有1,2表示,在第1,2号文章上出现过,单词“程序员”的倒排索引是3,表示在第3号文件出现过。

当我们用关键字进行查询的时候,我们首先去索引上面查询这个单词在哪些文章上面出现过。紧接着,便是排序,排序是搜索引擎一个非常牛逼的技术,那么多的文章,一个关键字可能包含了几百万的文章,怎么进行排序的呢?有几种非常简单的方法,例如关键词出现的次数,越多说明权重越高,或者是创建的时间,越新权重越高,当然也有一些其他的排序方法,例如竞价等等。现代的搜索引擎,一般还会用AI进行武装,我们一般用深度学习,对搜索结果去建立神经网络,如果用户点击了,就说明搜索出来的结果用户更喜欢,从而达到不断训练,越来越聪明的作用。

好了,今天我们就分享到这里,有兴趣的程序员同学,可以尝试自己实现一个简单的搜索引擎。相信你会对其中的算法与数据结构有更深一步的认识。欢迎大家关注我,共同学习,共同进步。大家的支持是我继续唠嗑的动力。

在线咨询
  • Copyright © 2013-2020 南宁华寇网络科技有限公司
  • 技术支持: