文档介绍：计算思维导论– 第3讲–算法方法
2014年10月07日
第一堂课上我们说过:
计算思维的核心是问题求解
算法
计算机科学思想在很多情况下是以“算法”的形式呈现的。
什么是“伟大”的算法
普通的计算机用户每天都在使用这些算法;
它们能解决客观世界中的具体问题;
它们具有科学原理的支撑。
例如:
与搜索相关的算法;
与密码相关的算法;
与数据压缩相关的算法;
与数据一致性相关的算法
……(还有一些注定”伟大”的算法还在我们的期待之中: 例如: 精确的自然语言翻译、自动驾驶汽车、帮我改学生作业)
也是你并没有意识到, 但这个“问题”相当于:
在世界上最大的一堆干草中寻找绣花针!
搜索互联网
Google 的背后有什么?
我们每个人的生活都在很大程度上受到了“搜索引擎”的影响。
这么大量的信息,这么快的速度。因为****以为常”,我们甚至忘记了这其实“不简单”!
Google在全世界拥有数量庞大的服务器,能提供的处理能力极为惊人。但即便如此,这些“硬件”并不能提供我们****以为常的搜索服务。
搜索引擎完成的最重要的事是:matching 和 ranking。
搜索的第一步:匹配
如果你查询“南京到上海的火车时刻表”,搜索引擎首先必须回答:哪些网页与你的查询相匹配。
伟大的思想往往很简单:索引
不仅简单,而且:“原始”,据说巴比伦人5000年前就使用索引了。
网络搜索引擎采用索引算法开始于1994-95年,20世纪90年代中期的“搜索之王”AltaVista(不是Google!)实现了全部网页的索引,在此基础上实现了高效率的匹配。
简单索引–这个真简单
The cat sat on the mat
The cat stood while a dog sat
The dog stood on the mat
a 3
cat 1, 3
dog 2, 3
mat 1, 2
on 1, 2
sat 1, 3
stood 2, 3
the 1, 2, 3
while 3
假设只有3个网页
加入“位置”信息:这个想法不简单
The cat sat on the mat
The cat stood while a dog sat
The dog stood on the mat
a 3-5
cat 1-2, 3-2
dog 2-2, 3-6
mat 1-6, 2-6
on 1-4, 2-4
sat 1-3, 3-7
stood 2-3, 3-3
the 1-1, 1-5, 2-1, 2-5, 3-1
while 3-4
假设只有3个网页
想想:如果要找”cat sat”会怎样?
进一步,不仅可以发现“紧挨着”,还可以发现“隔得不远”。
“加入位置是搜索引擎成功的关键之一”这个说法也不为过。你理解是为什么吗?
有“结构”的网页
<titleStart> my cat <titleEnd> <bodyStart> The cat sat on the mat <bodyEnd>
<titleStart> my pets <titleEnd> <bodyStart> The cat stood while a dog sat <bodyEnd>
<titleStart> my dog <titleEnd> <bodyStart> The dog stood on the mat <bodyEnd>
a 3-10
cat 1-3, 1-7, 3-7
dog 2-3, 2-7, 3-11
mat 1-11, 2-11
on 1-9, 2-9
pets 3-3
sat 1-8, 3-12
stood 2-8, 3-8
the 1-6, 1-10, 2-6, 2-10, 3-6
while 3-9
<bodyEnd> 1-12, 2-12, 3-13
<bodyStart> 1-5, 2-5, 3-5
<titleEnd> 1-4, 2-4, 3-4
<titleStart> 1-1, 2-1, 3-1
查询dog IN TITLE:
Dog 2-3, 2-7, 3-11
<titleStart> 1-1, 2-1, 3-1
<titleEnd> 1-4, 2-4, 3-4