当前课程知识点：微软亚洲研究院大数据系列讲座 > 第二讲：互联网搜索中的大数据研究（宋睿华） > 大规模超文本网络搜索引擎的解析(the anatomy of a large scale hypertextual web search engine) > 大规模超文本网络搜索引擎的解析(the anatomy of a large scale hypertextual web search engine)
欢迎大家来听我们的讲座
今天的讲座是关于大数据在互联网搜索中的应用
这个讲座是微软亚洲研究院开设的大数据课程的一部分
在今天的讲座中，我将
向大家介绍互联网搜索这个大数据最成功的应用
我把讲座分成两个部分。
在第一部分，我将介绍
大规模互联网搜索的详细设计，
我会解释为什么
搜索引擎能够在一秒钟之内响应一千次查询请求。
在第二部分，我将介绍我们在计算查询的维度方面将介绍我们在计算查询的维度方面的研究工作
这次的讲座是一个很好的例子。
这个例子是关于我们利用搜索引擎和大数据来挖掘有用的知识。
搜索无处不在。
搜索并不局限于日常使用的搜索引擎。
请大家给我举一些你们在日常生活中使用搜索的例子。
你们经常会需要在一个文件或者
一个文档中查找一个词么？这是搜索。
你们会查找一个App或者一个网站么？
这依然是搜索。
你们会在周末查找
或者导航到一家餐厅么？
这还是搜索。
你们会在一家书店里查找一本书么？
这是另一种形式的搜索。
你们会在家里找东西么？
这同样是搜索。
能否找到一首老歌，仅仅通过你能记住的几句话或者几段
旋律呢？
这依然是搜索。
现在，
搜索引擎能够帮助我们做很多事情。但是，你是不是还有什么
仍然感到痛苦的任务呢？
网络上有海量的信息。
我们能不能把它们组织起来，这些知识
同样可以被搜索到呢？
还有其他的么？
我们做些什么来从这些大数据中挖掘出一些知识呢？
因此，在这一讲中，
我会介绍这些问题的答案。
在这一部分，
我将介绍大规模搜索引擎的逻辑架构。
我们选择谷歌的一篇论文作为我们介绍的内容。
虽然这里介绍的结构
是由谢尔盖.布林和拉里.佩奇设计的。
他们在1998年共同创立了谷歌。
但是这个结构对于我们理解现在的大规模搜索引擎是如何运行的仍然是有帮助的。
如果我们想要在任何互联网文档中查找任何单词，
我们都需要从互联网上获取这些文档，这就是爬取。
一篇一篇地读取这些文档并记住哪些单词出现在哪些文档中，
这就是索引。最后，使得通过关键词查询成为可能
并对提取的文档进行排序，这就是搜索。
在那个时候，谷歌因为两件事情而变得特别。
他们声称使用anchor text来描述目标文档
并利用文档之间的链接来对文档的重要性进行排序。
这就是著名的PageRank。下面，我将介绍
依次介绍数据结构和模块。
在我们介绍他们之前，
我想先讨论搜索引擎的数据结构。
为了保存海量的页面，我们
需要有效管理文件，谷歌的创立者
将大文件设计为虚拟文件。
在存储中，他们使用三个维度来描述每个页面：
同步码，是指一个页面数据长度的开始，
它们会读取多少字节和压缩包。
压缩包包括
文档ID（docID）、编码信息、URL长度、
页面长度、URL和页面。
或者，可以说，包括
页面本身及其相关信息。
文档索引由两个文件组成。
一个根据docID排序，
另一个根据URL排序。
因为有时候我们需要使用docID来存取文档，
有时候我们则需要通过URL来存取文档。
词典是一个查找表，
它需要保存在内存中。
词典中包含单词，由指针组成的哈希表以及这些指针的信息。
命中是索引文件中的一个重要概念，
它意味着一个词出现在了一个文档中。
在谷歌的早期原型中，
命中的设计是非常好的。
如这张表所示，
它们不仅
记录命中的类型，而且
记录命中的位置。
以便
在排序算法中，我们能够
利用命中位置来计算
不同关键词之间的接近程度。
命中包括两种类型：特殊命中和普通命中。
特殊命中包括在URL、标题、
元数据和锚文本中的命中。
锚文本的命中是特别的，因为它们
使用四个二进制位来
记录锚文本的来源。
这与其他特殊命中都是不同的。
对于普通命中，
搜索引擎会
根据重要性对字体大小和大写的信息
进行编码。
在正向索引中，
如你们所知，barrels会记录
文档ID（docID）、单词ID（wordID）和
文档中的每个词出现了多少次。
在索引末尾，
会有所有出现和所有命中。
倒排索引
包含与正向索引相似的信息。
但是，倒排索引中的信息排列方式不同于正向索引中，倒排索引中的信息
是根据单词排序的。因此，如你们所知，单词ID
之后跟随着有多少文档中包含了这个单词。
然后一些指向
这些文档的指针。对于每个文档，倒排索引
都会记录
在这个文档中命中了多少次。
在索引末尾还有
命中的列表。
在介绍了主要数据结构之后，
我们再来看看这个架构。
这是当代搜索引擎的逻辑视图。
第一个模块是爬取模块。
爬取模块抓去所有互联网页面并把它们保存在一个
仓库中。第二个模块是索引模块。
索引模块一个一个地读取文档并记住
每个单词在文档中出现的位置。
如你们所知，索引模块对正向索引进行排序并生成
搜索使用的倒排索引。
第三个模块
是搜索模块。
在收到一个查询请求时，我们能做什么呢？
如你们所知，我们会从包含关键词的单词索引中获取所有文档，
然后根据相关性和重要性
对它们进行排序。
还有一个模块是
链接分析模块。如你们所知，
链接分析模块根据两个文档之间的链接
计算文档页面的重要性。
第一步中的爬取比人们所想象的要复杂很多。
因为，如你们所知，爬取会涉及和成千上百个Web服务器
进行交互。为了提高效率，我们
需要用分布式的方式完成爬取任务。
关于爬取有很多细节。
例如，域名服务器查询
就是一个主要性能瓶颈，因此在爬取时，我们需要
一些域名服务器缓存来提高爬取效率。
一个爬虫会有四种工作状态：
查找域名服务器、
连接主机、发送请求和接收
响应。
此外，还有很多问题。
例如，一些页面和网站并不知道
网络爬虫排除标准。
因此虽然它们对于
谷歌爬取他们的页面非常恼火。
但是它们却不知道如何让爬虫不要爬取它们的页面。
还有很多垃圾链接。
第二个模块是索引模块。
索引包括三步。第一步是解析，我们需要
快速而且健壮的解析器来处理
HTML页面中的各种错误。
索引一个文档意味着需要生成正向索引
和检索哪个文档中
包含哪个单词ID和它们的所有命中列表。
第三部是排序，是指对
正向索引中的记录排序并
生成倒序索引。
由于规模很大，所以排序是非常具有挑战性的。
在第三个模块搜索模块中
有一个过程。
首先，
搜索引擎解析查询请求
并把单词转换成单词ID。然后，搜索引擎
对短桶中的每个单词都转到文档列表的开始
并获得所有文档列表。
下面，搜索引擎对每个查询请求计算文档排序。
然后，根据排序得分，
搜索引擎为用户返回
排序得分最高的搜索结果。
下面的例子是1998年时查询“Bill Clinton”
的搜索结果，在大部分
主流搜索引擎的搜索结果中，
除了谷歌意外，白宫的页面并不是排名第一的。
谷歌之所以能够返回这样的结果是因为它们使用了
连接分析。如你们所知，这是由于很多页面通过
使用“Bill Clinton”作为锚文本来
指向白宫的主页。这就是谷歌为什么能够
在全世界获胜的原因。
-什么是大数据(What is big data?)
-为什么大数据是当前热点（Why big data is a nature phenomenon?)
--为什么大数据是当前热点（Why big data is a nature phenomenon?)
-新的计算基础设施和工具(New Infrastructure and tools)
--新的计算基础设施和工具(New Infrastructure and tools)
-课程简介(Course Introduction)
-基础设施，机器学习和可视化（Infrastructure,Machine Learning and Visualization)
--基础设施，机器学习和可视化（Infrastructure,Machine Learning and Visualization)
-大数据与传统商业智能的区别（Big data:different from traditional BI)
--大数据与传统商业智能的区别（Big data:different from traditional BI)
-Quiz
--Quiz--作业
-大规模超文本网络搜索引擎的解析(the anatomy of a large scale hypertextual web search engine)
--大规模超文本网络搜索引擎的解析(the anatomy of a large scale hypertextual web search engine)
-搜索引擎如何实现每秒数千次的查询(How does a web search engine process thousands of queries per second?)
--搜索引擎如何实现每秒数千次的查询(How does a web search engine process thousands of queries per second?)
-探寻搜索的多个维度(finding dimensions for queries)
--探寻搜索的多个维度(finding dimensions for queries)
-Quiz
--Quiz--作业
-背景介绍(background)
-用户移动规律的理解-1(user mobility understanding-1)
--用户移动规律的理解-1(user mobility understanding-1)
-用户移动规律的理解-2(user mobility understanding-2)
--用户移动规律的理解-2(user mobility understanding-2)
-用户画像与个人隐私-1(user profiling and privacy-1)
--用户画像与个人隐私-1(user profiling and privacy-1)
-用户画像与个人隐私-2(user profiling and privacy-2)
--用户画像与个人隐私-2(user profiling and privacy-2)
-Quiz
--Quiz--作业
-城市计算中的大数据研究简介（introduction to urban big data）
--城市计算中的大数据研究简介（introduction to urban big data)
-概念，框架和挑战（concepts,framework and chanlleges）
--概念，框架和挑战（concepts,framework and chanlleges)
-基础技术（fundamental techniques）
--基础技术（fundamental techniques)
-城市规划（urban planning）
-识别特定区域（indentify functional regions）
--识别特定区域（indentify functional regions)
-城市空气质量与大数据研究（urban air quality meets big data）
--城市空气质量与大数据研究（urban air quality meets big data)
-能源交通和环境污染（traffic energy and pollution）
--能源交通和环境污染（traffic energy and pollution)
-大数据在城市噪音处理中的应用（diagnose urban noise with big data）
--大数据在城市噪音处理中的应用（diagnose urban noise with big data)
-Quiz
--Quiz--作业
-软件分析的概念（the concepts of software analytics）
--软件分析的概念（the concepts of software analytics）
-软件分析的实例（examples of software analytics）
--软件分析的实例（examples of software analytics）
-传统的数据可视化（Traditional information visualization）
--传统的数据可视化（traditional information visualization）
-同质数据的可视化分析-1（Visual Analytics of Homogeneous Data-1）
--同质数据的可视化分析-1（Visual Analytics of Homogeneous Data-1）
-同质数据的可视化分析-2（Visual Analytics of Homogeneous Data-2）
--同质数据的可视化分析-2（Visual Analytics of Homogeneous Data-2）
-异质数据的可视化分析（Visual Analytics of Heterogeneous Data）
--异质数据的可视化分析（Visual Analytics of Heterogeneous Data）
-Quiz
--Quiz--作业
