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

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

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

整体系统介绍

实际上的商用搜索引擎,所包含的技术细节非常多。但是本节主要展示如何在一台机器上(假设这台机器的内存是 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。数据结构需要满足如下几个条件:

阅读全文 »