洋蔥

贪婪,找不到比这更好的词了,是件好事。

网页爬虫是搜索引擎中的非常重要的系统,负责爬取几十亿、上百亿的网页。爬虫的工作原理是,通过解析已经爬取页面中的网页链接,然后再爬取这些链接对应的网页。而同一个网页链接有可能被包含在多个页面中,这就会导致爬虫在爬取的过程中,重复爬取相同的网页。如果你是一名负责爬虫的工程师,你会如何避免这些重复的爬取呢?

最容易想到的方法就是,我们记录已经爬取的网页链接(也就是URL),在爬取一个新的网页之前,我们拿它的链接,在已经爬取的网页链接列表中搜索。如果存在,那就说明这个网页已经被爬取过了;如果不存在,那就说明这个网页还没有被爬取过,可以继续去爬取。等爬取到这个网页之后,我们将这个网页的链接添加到已经爬取的网页链接列表了。

思路非常简单,我想你应该很容易就能想到。不过,我们该如何记录已经爬取的网页链接呢?需要用什么样的数据结构呢?

阅读全文 »

基础篇的时候,我们学习了图的两种搜索算法,深度优先搜索和广度优先搜索。这两种算法主要是针对无权图的搜索算法。针对有权图,也就是图中的每条边都有一个权重,我们该如何计算两点之间的最短路径(经过的边的权重和最小)呢?今天,我就从地图软件的路线规划问题讲起,带你看看常用的最短路径算法(Shortest Path Algorithm)。

像Google地图、百度地图、高德地图这样的地图软件,我想你应该经常使用吧?如果想从家开车到公司,你只需要输入起始、结束地址,地图就会给你规划一条最优出行路线。这里的最优,有很多种定义,比如最短路线、最少用时路线、最少红绿灯路线等等。作为一名软件开发工程师,你是否思考过,地图软件的最优路线是如何计算出来的吗?底层依赖了什么算法呢?

阅读全文 »

从今天开始,我们就进入了专栏的高级篇。相对基础篇,高级篇涉及的知识点,都比较零散,不是太系统。所以,我会围绕一个实际软件开发的问题,在阐述具体解决方法的过程中,将涉及的知识点给你详细讲解出来。

所以,相较于基础篇“开篇问题-知识讲解-回答开篇-总结-课后思考”这样的文章结构,高级篇我稍作了些改变,大致分为这样几个部分:“问题阐述-算法解析-总结引申-课后思考”。

好了,现在,我们就进入高级篇的第一节,如何确定代码源文件的编译依赖关系?

阅读全文 »

Trie树那节我们讲过,利用Trie树,可以实现搜索引擎的关键词提示功能,这样可以节省用户输入搜索关键词的时间。实际上,搜索引擎在用户体验方面的优化还有很多,比如你可能经常会用的拼写纠错功能。

当你在搜索框中,一不小心输错单词时,搜索引擎会非常智能地检测出你的拼写错误,并且用对应的正确单词来进行搜索。作为一名软件开发工程师,你是否想过,这个功能是怎么实现的呢?

阅读全文 »

上一节,我通过两个非常经典的问题,向你展示了用动态规划解决问题的过程。现在你对动态规划应该有了一个初步的认识。

今天,我主要讲动态规划的一些理论知识。学完这节内容,可以帮你解决这样几个问题:什么样的问题可以用动态规划解决?解决动态规划问题的一般思考过程是什么样的?贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系?

理论的东西都比较抽象,不过你不用担心,我会结合具体的例子来讲解,争取让你这次就能真正理解这些知识点,也为后面的应用和实战做好准备。

阅读全文 »

淘宝的“双十一”购物节有各种促销活动,比如“满200元减50元”。假设你女朋友的购物车中有n个(n>100)想买的商品,她希望从里面选几个,在凑够满减条件的前提下,让选出来的商品价格总和最大程度地接近满减条件(200元),这样就可以极大限度地“薅羊毛”。作为程序员的你,能不能编个代码来帮她搞定呢?

要想高效地解决这个问题,就要用到我们今天讲的动态规划(Dynamic Programming)。

阅读全文 »

我们在第31节提到,深度优先搜索算法利用的是回溯算法思想。这个算法思想非常简单,但是应用却非常广泛。它除了用来指导像深度优先搜索这种经典的算法设计之外,还可以用在很多实际的软件开发场景中,比如正则表达式匹配、编译原理中的语法分析等。

除此之外,很多经典的数学问题都可以用回溯算法解决,比如数独、八皇后、0-1背包、图的着色、旅行商问题、全排列等等。既然应用如此广泛,我们今天就来学习一下这个算法思想,看看它是如何指导我们解决问题的。

阅读全文 »

MapReduce是Google大数据处理的三驾马车之一,另外两个是GFS和Bigtable。它在倒排索引、PageRank计算、网页分析等搜索引擎相关的技术中都有大量的应用。

尽管开发一个MapReduce看起来很高深,感觉跟我们遥不可及。实际上,万变不离其宗,它的本质就是我们今天要学的这种算法思想,分治算法。

阅读全文 »

很多支持用户发表文本内容的网站,比如BBS,大都会有敏感词过滤功能,用来过滤掉用户输入的一些淫秽、反动、谩骂等内容。你有没有想过,这个功能是怎么实现的呢?

实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找用户输入的这段文字,是否包含敏感词。如果有,就用“***”把它替代掉。

我们前面讲过好几种字符串匹配算法了,它们都可以处理这个问题。但是,对于访问量巨大的网站来说,比如淘宝,用户每天的评论数有几亿、甚至几十亿。这时候,我们对敏感词过滤系统的性能要求就要很高。毕竟,我们也不想,用户输入内容之后,要等几秒才能发送出去吧?我们也不想,为了这个功能耗费过多的机器吧?那如何才能实现一个高性能的敏感词过滤系统呢?这就要用到今天的多模式串匹配算法

阅读全文 »
0%