zdaiot

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

搜索是一个技术驱动的产品。所谓技术驱动是指，搜索引擎实现起来，技术难度非常大，技术的好坏直接决定了这个产品的核心竞争力。

本节就借助搜索引擎，展示一下，数据结构和算法是如何应用在其中的。

整体系统介绍

实际上的商用搜索引擎，所包含的技术细节非常多。但是本节主要展示如何在一台机器上（假设这台机器的内存是 8GB， 硬盘是 100 多 GB），通过少量的代码，实现一个小型搜索引擎。

最近在师兄的推荐下，阅读了一篇利用半监督图做PolSAR图像分类的文章，感觉这篇文章整体思路不错，值得借鉴。在这里做一下简单的笔记。

基本信息

• 年份：2019
• 期刊：IEEE Transactions on Geoscience and Remote Sensing
• 标签：Graph, PolSAR, Semisupervised
• 数据：Flevoland、San Francisco

创新点

1. 第一个将半监督图分类算法和深度卷积神经网络融合于PolSAR图像分类框架中 。
2. 设计了结合半监督项、CNN项、成对平滑损失项的能量函数。其中：
   • 半监督项强迫类标预测受人类标记样本的约束
   • CNN项负责提取具有分辨性的PolSAR特征并预测类标
   • 成对平滑损失项负责预测类标和图像边缘对齐
3. 设计了一个迭代、交替的优化过程优化模型

之前一直听说过MRF的大名，但是一直没有了解过。最近在看论文的时候，经常遇到这个专业术语，就专门对这个概念学习一下。声明下面内容主要参考了这篇文章——马尔科夫随机场(MRF)在图像处理中的应用-图像分割、纹理迁移，加了一些个人见解。

马尔科夫随机场，英文名称Markov Random Field，简写为MRF。

基础概念

条件概率和贝叶斯定理

条件概率常用来解决逆问题，也就是已知结果反推原因。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

时间复杂度是衡量算法执行效率的一种标准。但是，时间复杂度并不能跟性能划等号。算法的目的是为了提高代码执行的效率。当算法无法再继续优化的情况下，需要借助另外一种优化方法提高执行效率——并行计算。那么如何借助并行计算的处理思想对算法进行改造？

并行排序

假如要对8GB大小的数据排序，最常用的就是时间复杂度为 $O(nlogn)$ 三种排序算法——归并排序、快速排序、堆排序。理论上，这个排序问题很难再从算法层面优化了。但是借助并行的处理思想，可以轻松地把执行效率提高很多倍。具体实现思路有如下两种：

第一种是对归并排序并行化处理。可以把这8GB的数据划分为16个大小为500MB的小数据集合，使用16个线程并行地对这16个500MB 的数据集合进行排序，然后再将这16个有序集合合并。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

之前讲过，MySQL底层使用的是B+树这种数据结构，实现数据库索引的。那么类似 Redis 这样的 Key-Value 数据库中的索引，又是怎么实现的呢？底层依赖的又是什么数据结构呢？

本节讲述一下索引这种常用的技术解决思路，底层往往会依赖哪些数据结构。

为什么需要索引？

实际开发中，众多复杂的业务和功能的外壳，本质都可以抽象成“对数据的存储和计算”。对应到数据结构和算法中，那“存储”需要的就是数据结构，“计算”需要的就是算法。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

游戏中常有一个功能——人物自动绕过障碍物寻路。这是怎么实现的呢？

算法解析

这是一个非常典型的搜索问题。人物经过的路径要绕过地图上所有的障碍物，并且走的路不能太绕。理论上，最短路径显然是最好的走法，是这个问题的最优解。

但是在第43节最优出行路线规划问题中说过，若地图非常大，Dijkstra 最短路径算法的执行耗时会很多。实际运用时，经常面对的是超级大的地图和海量的寻路请求，算法的执行效率太低，这显然是无法接受的。实际上，像出行路线规划、游戏寻路这样的问题，不需要求得最优解。在权衡路线规划质量和执行效率后，寻找一个次优解就可以了。那如何快速找出一条接近于最短路线的次优路线呢？这就需要用到本节要学习的A*算法，它是对Dijkstra 算法的优化和改造。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

为了加速数据库中数据的查找速度，常常对表中数据创建索引。那么数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？

算法解析

解决问题的前提是定义清楚问题

如何定义清楚问题呢？除了对问题进行详细的调研，还可以通过对一些模糊的需求进行假设，来限定要解决的问题的范围。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

现在的听歌软件都会根据你听歌的偏好给你推荐歌曲，那么这个功能该如何实现呢？

算法解析

这个问题的解决思路核心很简单、直白：

• 找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你；
• 找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

上一节讲了如何用位图、布隆过滤器来过滤重复的数据。今天再讲一个与过滤相关的问题——如何过滤垃圾短信和骚扰电话。应该用什么样的数据结构和算法？

算法解析

基于黑名单的过滤器

可以维护一个骚扰电话号码和垃圾短信发送号码的黑名单。若黑名单中电话号码不多，可以用散列表、二叉树等动态数据结构来存储，对内存的消耗并不会很大。但是，若黑名单中的电话号码很多时，比如500万个，每个号码看作一个长度为16的字符串，那大概需要100MB的存储空间，有点大。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

搜索引擎中爬虫的工作原理是——解析已经爬取页面中的网页链接，然后再爬取这些链接对应的网页。那同一个网页链接可能包含在多个页面中，导致爬虫的过程中，重复抓取相同的页面。那如何避免这些重复的爬取呢？最简单的方法是记录爬取的网页链接（URL），每次爬取一个网页之前，在记录中进行查询。

不过，应该如何记录已经爬取的网页链接呢？需要用什么样的数据结构呢？

算法解析

这个问题要处理的对象是网页链接，也就是URL。数据结构需要满足如下几个条件：