Monthly Archives: January 2016

卜神算法作业整理

这学期选修了卜老师的算法课,都说这课是神课,上过之后果然是神课。同样是算法课,别人12月底就考完了,我们要1月底才考试。

本课程主要讲了以下几个专题:

  • Divide-and-conquer
  • Dynamic programming
  • Greedy
  • Linear programming
  • Linear programming: duality
  • Network flow
  • Problem hardness: Polynomial-time reduction
  • NP-Completeness
  • Approximation algorithm

Continue reading

和我一起构建搜索引擎(六)系统展示

前几个博客已经介绍完搜索引擎的所有功能,为了实现更好的用户体验,需要一个web界面。这一部分是另一个队员做的,我这里借用他的代码。

我们利用开源的Flask Web框架搭建了展示系统,搜索引擎只需要两个界面,一个是搜索界面,另一个是展示详细新闻的页面(实际搜索引擎没有这个页面)。编写好这两个模板页面并调用前面给出的接口,得到数据,展示出来就可以。 Continue reading

和我一起构建搜索引擎(三)构建索引

目前正是所谓的“大数据”时代,数据量多到难以计数,怎样结构化的存储以便于分析计算,是当前的一大难题。上一篇博客我们简单抓取了1000个搜狐新闻数据,搜索的过程就是从这1000个新闻中找出和关键词相关的新闻来,那么怎样快速搜索呢,总不可能依次打开xml文件一个字一个字的找吧,这时就需要借助倒排索引这个强大的数据结构。 Continue reading

和我一起构建搜索引擎(二)网络爬虫

网络爬虫又称网络蜘蛛、Web采集器等,它是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本。

我们在设计网络爬虫的时候需要注意两点:

鲁棒性。Web中有些服务器会制造采集器陷阱(spider traps),这些陷阱服务器实际上是Web页面的生成器,它能在某个域下生成无数网页,从而使采集器陷入到一个无限的采集循环中去。采集器必须能从这些陷阱中跳出来。当然,这些陷阱倒不一定都是恶意的,有时可能是网站设计疏忽所导致的结果。

礼貌性。Web服务器具有一些隐式或显式的政策来控制采集器访问它们的频率。设计采集器时必须要遵守这些代表礼貌性的访问政策。 Continue reading

和我一起构建搜索引擎(一)简介

我们上网用得最多的一项服务应该是搜索,不管大事小情,都喜欢百度一下或谷歌一下,那么百度和谷歌是怎样从浩瀚的网络世界中快速找到你想要的信息呢,这就是搜索引擎的艺术,属于信息检索的范畴。

这学期学习了《现代信息检索》课程,使用的是Stanford的教材Introduction to Information Retrieval,网上有电子版,大家可以参考。 Continue reading

认真你就赢了

突然发现,从小到大,自己做事都做得很慢,别人一会做完的作业,我可能要花好几个小时。但拿作业一对比,明显能看出差距,自己精雕细琢的作品不是别人随随便便就能比的。

最近几次和同学合作完成大作业也遇到了类似的情况,数据抓取的同学给我的数据,不是格式不对就是内容缺胳膊少腿,质量极其差,还不愿修改,曰:只是做一个演示系统,有数据就行了。他不知道他这样的数据给我,我们后面做得再好,最终的演示效果也不会好,他这样的随意,后面的人不知要多花多少时间来弥补。我也无意跟他多费口舌,自己挽起袖子重做了他的工作。 Continue reading

2016新年快乐

2015年过得好快,梳理一下,2015年的时间线大概是这样的:

3月来北京计算所做毕设→5月返回武大修改论文→5月30公开答辩→6月毕业季→7月回北京计算所→8月回家陪父母→9月国科大开学→持续高强度的学习→2016元旦还在图书馆研究NPC问题。

2015年给我的总体感受是很忙,但忙的事情都很琐碎,并没有什么大的里程碑事件,不过以下三件事情我认为值得一提。 Continue reading