搜索引擎中的算法与数据结构你知多少？ _搜索引擎

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

文章插图

收集首先是收集，最常见的便是爬虫，从各个网站中爬取对应的资料，根据网站的爬取顺序，我们常常有深度优先搜索，广度优先搜索等不同的爬取策略，为了避免爬取重复的网站，我们可能需要对网站的地址进行判重，常用的，我们可以使用布隆过滤器，可以做到非常高效的网站去重。当然，现在有一些搜索引擎也是不需要爬虫的，像淘宝的商品搜索，商家每发布新的产品，或者用户发表新的评论，都会发布异步的消息队列，由搜索引擎订阅并收集。那么多的基础元数据，我们通常需要给他们一个编号，有人说可以用MySQL存储，用自增主键id，那样一个表会非常大，要知道，网络上的网页何止千千万万，我们通常采用NoSql进行存储，同时我们也需要ID生成分配器，给每一个资源一个独立的ID 。
分析程序员们都知道，在网页上我们虽然能看到丰富多彩的文案与图片，背后都是html格式的代码，我们需要去掉这些格式，才能获取到真实的文本。那么，如何在一个HTML文件中，去掉各种标签呢？最简单的，便是文本匹配，为了加快匹配的速度，通常我们会常用AC自动机等多模文本匹配算法进行优化，可以快速的去掉HTML页面上的各种标签。
索引那么多的网页，我们查询的时候，不可能每一个网页都去遍历，找到是否包含这个关键字。通常，我们采用的一个技术，便是倒排索引，什么是倒排索引的，最简单来说，就是记录每一个单词，在哪里出现过。举个简单例子，文章1的内容包含了“我和我的祖国，一刻都不能分割”，文章2的内容包含了“祝伟大祖国70周年生日快乐，繁荣富强”，文章3包含了“国庆节要放假了，程序员可以休息了” 。那么，单词“祖国”的倒排索引上面就会有1，2表示，在第1，2号文章上出现过，单词“程序员”的倒排索引是3，表示在第3号文件出现过。

文章插图

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