Web 检索 信息检索研究室 秦兵

提纲 Web检索历史 Web检索系统结构 信息采集系统 网页与处理系统 链接分析算法

The World Wide Web 1989年，伯纳斯·李在日内瓦欧洲离子物理研究所（CERN）开发计算机远程控制时首次提出了Web概念，并在1990年圣诞节前推出了第一个浏览器。 接下来的几年中，他设计出HTTP、URL和HTML的规范，使网络能够为普通大众所应用 Ted Nelson 在1965年提出了超文本的概念. 超文本传输协议(HTTP，HyperText Transfer Protocol)是互联网上应用最为广泛的一种 网络传输协议 超文本标注语言（HTML）

Web Search 历史 1993, 早期的 web robots (spiders) 用于收集 URL: Wanderer ALIWEB (Archie-Like Index of the WEB) WWW Worm (indexed URL’s and titles for regex search) 1994, Stanford 博士生 David Filo and Jerry Yang 开发手工划分主题层次的雅虎网站.

Web Search 历史(cont) 1994年初，WebCrawler是互联网上第一个支持搜索文件全部文字的全文搜索引擎，在它之前，用户只能通过URL和摘要搜索，摘要一般来自人工评论或程序自动取正文的前100个字 Lycos（Carnegie Mellon University Center for Machine Translation Announces Lycos ）是搜索引擎史上又一个重要的进步。除了相关性排序外，Lycos还提供了前缀匹配和字符相近限制，Lycos第一个在搜索结果中使用了网页自动摘要，而最大的优势还是它远胜过其它搜索引擎的数据量 DEC的AltaVista 是一个迟到者，1995年12月才登场亮相. AltaVista是第一个支持自然语言搜索的搜索引擎，AltaVista是第一个实现高级搜索语法的搜索引擎（如AND, OR, NOT等) 1994年初，Washington大学CS学生Brian Pinkerton开始了他的小项目WebCrawler（Brian Pinkerton Announces the Availability of Webcrawler）。1994年4月20日，WebCrawler正式亮相时仅包含来自6000个服务器的内容。WebCrawler是互联网上第一个支持搜索文件全部文字的全文搜索引擎，在它之前，用户只能通过URL和摘要搜索，摘要一般来自人工评论或程序自动取正文的前100个字。（后来webcrawler陆续被AOL和Excite收购，现在和excite一样改用元搜索引擎Dogpile）. 　Lycos（Carnegie Mellon University Center for Machine Translation Announces Lycos ）是搜索引擎史上又一个重要的进步。Carnegie Mellon University的Michael Mauldin将John Leavitt的spider程序接入到其索引程序中，创建了Lycos。1994年7月20日，数据量为54,000的Lycos正式发布。除了相关性排序外，Lycos还提供了前缀匹配和字符相近限制，Lycos第一个在搜索结果中使用了网页自动摘要，而最大的优势还是它远胜过其它搜索引擎的数据量 　DEC的AltaVista(2001年夏季起部分网友需通过p-roxy访问，无p-roxy可用qbseach单选altavista搜索，只能显示第一页搜索结果)是一个迟到者，1995年12月才登场亮相（AltaVista Public Beta Press Release ）。但是，大量的创新功能使它迅速到达当时搜索引擎的顶峰。Altavista最突出的优势是它的速度（搜索引擎9238：比较搞笑，设计altavista的目的，据说只是为了展示DEC Alpha芯片的强大运算能力）。　　而Altavista的另一些新功能，则永远改变了搜索引擎的定义。AltaVista是第一个支持自然语言搜索的搜索引擎，AltaVista是第一个实现高级搜索语法的搜索引擎（如AND, OR, NOT等)。 .

Web Search 近期历史 1995年博士生Larry Page开始学习搜索引擎设计，于1997年9月15日注册了google.com的域名，1997年底，开始提供Demo。1999年2月，Google完成了从Alpha版到Beta版的蜕变。Google公司则把1998年9月27日认作自己的生日 Google在Pagerank、动态摘要、网页快照、多文档格式支持、地图股票词典寻人等集成搜索、多语言支持、用户界面等功能上的革新，象Altavista一样，再一次永远改变了搜索引擎的定义 主要的进步在于应用链接分析根据权威性对部分结果排序

Web Search 近期历史 北大天网 是国家“九五”重点科技攻关项目“中文编码和分布式中英文信息发现”的研究成果，由北大计算机系网络与分布式系统研究室开发，于1997年10月29日正式在CERNET上提供服务  2000年1月，超链分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇（加州伯克利分校博士）在北京中关村创立了百度（Baidu）公司 2001年8月发布Baidu.com搜索引擎Beta版（此前Baidu只为其它门户网站搜狐新浪Tom等提供搜索引擎） 2001年10月22日正式发布Baidu搜索引擎。Baidu虽然只提供中文搜索，但目前收录中文网页超过9000万，可能是最大的的中文数据库

Web Challenges for IR 数据的分布性：文档散落在数以百万计的不同服务器上，没有预先定义的拓扑结构相连。 不稳定的数据高比例：许多文档迅速地添加或删除 (e.g. dead links). 大规模：网络数据量的指数增长，由此引发了一系列难以处理的规模问题。 无结构和冗余信息：每个HTML页面没有统一的结构, 许多网络数据是重复的，将近 30% 的重复网页. 数据的质量: 许多内容没有经过编辑处理，数据可能是错误的，无效的。错误来源有录入错误，语法错误，OCR错误等。 异构数据：多媒体数据(images, video, VRML), 语言,字符集等.

Number of Web Servers

Number of Web Pages

从用户输入查询词到得到检索结果这短短的几秒钟内发生了什么事情呢？ 网页爬行下来 预处理：网页去重，正文提取，分词等 建立索引 接受用户请求，检索词串的处理，查询重构 找到满足要求的列表 根据连接和文本中的词进行排序输出

Web搜索引擎系统组成 Web搜索引擎系统可以被分成以下四个大的子系统： Web数据采集系统 网页预处理系统 索引检索系统 检索结果排序系统

Web搜索引擎体系结构 小型的搜索引擎系统一般是集中式的结构 很多搜索引擎采用了升级Web数据采集系统硬件的方法 系统实现简单，花费的资源比较少 自身处理能力比较弱，能支持同时访问用户数量也比较小 很多搜索引擎采用了升级Web数据采集系统硬件的方法 使用大型机和并行机作为采集系统的硬件使采集能力提高 升级硬件的方法扩展性有限，性价比也不高 用网络连接多台微机组成一个分布式的机群系统提供的分布式网络服务 现代网络服务的体系结构已经由集中式向分布式转变

分布式结构:主次结构

分布式结构:对等结构

Web信息采集

Spiders (Robots/Bots/Crawlers) 从一个URL根集开始搜索. 根据这些网页的链接寻找另外的网页. 将遇到的所有新的网页建立索引. 也允许直接索引用户提交的网页.

Web信息采集系统的作用 一个 web crawler( spider, or robot) 获取网络资源到本地机器上 存储的本地资源用于： 镜像资源 HTML 确认, link 确认, 发现新信息, …

Web信息采集系统的作用（续） 信息查全率,评价搜索引擎好坏的一个重要指标 最主要的作用 Google号称采集30亿网页 Baidu号称采集10亿网页 最主要的作用 采集网上的信息 网页，文本，ppt, doc ,音乐，图片 及时更新信息 增加新出现的链接 删除死链接

Web信息采集当前研究方向 实际的采集器往往是几种采集技术的结合 基于整个Web的信息采集(Scalable Web Crawling) 增量式Web信息采集 (Incremental Web Crawling ) 基于主题的Web信息采集(Focused Web Crawling ) 基于用户个性化的Web信息采集(Customized Web Crawling ) 基于Agent的信息采集(Agent Based Web Crawling ) 迁移的信息采集(Relocatable Web Crawling ) 基于元搜索的信息采集(Metasearch Web Crawling) 实际的采集器往往是几种采集技术的结合

基于整个Web的信息采集 传统的采集方式 优点 缺点 目前在实际应用中占较为主流的地位 典型代表：Google Crawler, 百度 是指从一些种子URL扩充到整个Web的信息采集 优点 采集数据广，采集速度快，适用于广泛主题的搜索 缺点 采集数据乱，数据利用率低，页面失效率高，采集周期长 目前在实际应用中占较为主流的地位 典型代表：Google Crawler, 百度

增量式Web信息采集 在页面刷新时，只需要采集新产生的或者已经发生变化的页面，而对于没有变化的页面不进行采集 预测变化的策略： 优点 缺点 基于统计的方法：观察网站的平均变化周期 基于数据建模的方法：通过网页中变化估计模型和参数 优点 极大地减小数据采集量进而极大地减小采集时空开销 。 缺点 增加了一定的判别开销。 典型代表： Google Crawler, WebFountain。

有统计资料表明 随机选择270个站点，132个.com站点，78个.edu站点，30个.net站点和30个.gov站点 下载72000个页面，40%的.com每天变化，.net和.org变化适中，.edu和.gov变化最为缓慢 需要为更新较快的页面提高刷新率

主题Web信息采集 选择性的搜寻那些与预先定义好的主题集相关页面进行采集 目前是研究热点，垂直搜索 优点 缺点 给定特定的种子URL 目前是研究热点，垂直搜索 优点 采集页面更加有针对性，采集效率更高。 缺点 采集速度较慢，判别相关性带来较大的开销。 典型代表：Focused Crwaler -- IIT&IBM 采集系统首先保存一个经典的主题分类 每个主题分类都保存若干个内容样本

用户个性化Web信息采集 轻量级的信息采集 不同的用户对一个搜索引擎提交同一个检索词，他们期望的返回结果是不同的 通过用户兴趣制导或与用户交互等灵活手段来采集信息 优点 灵活、小巧、针对性强。 缺点 实用性和有效性还有待提高。 典型代表：SPHINX

基于Agent的信息采集 智能Agent系统是指一种处于一定环境下包装的计算机系统 它除了具有自治性、社会能力、反应能力和自发行为 还具有一般人类所有的知识、信念、意图和承诺等心智状态,这使得智能Agent系统具有人类的社会智能 将Agent技术用于采集，像人一样感知用户的兴趣变化，使得采集有更强的灵活性、适应性和自主性 典型代表：InfoSpiders ，Letizia

迁移的Web信息采集 将自己上载到它所要采集的服务器中，在当地进行采集，并将采集结果压缩后，回传到本地 优点 缺点 解决：信任机制，半迁移 不被采集对象所信任 解决：信任机制，半迁移 典型代表：SPHINX

元搜索Web信息采集 元搜索引擎是这样一种搜索引擎系统，对用户提交的查询请求通过多个领域或门户搜索引擎搜索，并将结果整合后以统一的界面提交个用户 信息采集部分在元搜索引擎中有相当的退化 典型代表： 美国Binghamton大学 ：对数据选择问题进行了研究 美国华盛顿大学：实验发现大多数搜索引擎对于同一个查询要求返回的结果很不相同，重叠率很低。单一搜索引擎会错过许多相关网页

Crawler基本思想

不同IR系统的资源性质 事先存在、范围明确、固定不变的文档集合 例如，全唐诗，全宋诗，古典哲学著作，… 部分存在，定期更新的文档集合 例如，生物医学周刊，《计算机学报》，CDAL，… 随时间推移逐渐失效的流数据（Streaming data） 例如，沪市股票新闻，国际期货行情，… 分布的，特有（proprietary）信息 例如，联合数据库，CALIS，… 分布的，链接的，公开可访问的文档 例如，Web 不同类型有不同的技术需求

网页分布的若干特点 网页：内容（C），物理存在（P），IP地址（A）， url（L） 存在有大量内容相同，但物理上不同的，url不同，IP地址不同的网页  镜像，拷贝 同一篇（物理）网页可能被多个url指向 例如，ir.hit.edu.cn 和 www.ir-lab.org 一个url可能对应多个IP地址，从而多个物理的网页（尽管此时内容大都是相同） 例如，一些大门户网站采用的负载分配技术（http://www.google.com也是一个例子）

Web有向图 网页为节点 HTML链接引用为有向边 <href …> <href …> <href …>

系统框图

单个采集线程个工作过程 将url解析成host和file。 host: www.zjs.com.cn file: /asp/customercenter/center_home.asp 根据host（www.zjs.com.cn）做DNS解析 创建一个socket，用于网络通信 把创建的socket编号和DNS解析得到的网络地址作为参数传递给connect()函数，进行本地服务器和远程网页服务器的连接操作

单个采集线程个工作过程（续） 在本地服务器缓冲区中组装http请求。 用write()函数将组装好的http头发给网页服务器。 调用read()函数读从网页服务器返回的网页数据 当read()函数返回的字节数是0的时候，说明网页已经下载完毕。 调用close()函数终止与网页服务器的连接。 将网页保存到本地服务器

先广搜索算法 The basic crawling algorithm is as follows: Create an empty URL queue Add user-supplied seed URLs to the tail of the queue Using the HTTP HEAD request, retrieve the HTTP headers for the resource at the head of the queue If the resource is found, hasn’t been visited previously, and meets all crawling criteria, then: Retrieve the resource using an HTTP GET request Extract URLs from the resource. For each URL: Decide if the URL should be added to the URL queue. If so, add the URL to the tail of the URL queue Store the headers and resource in the collection store Record the URL in the visited URL list Repeat from Step 2 until the queue is empty, then stop. 36

搜索策略 Breadth-first Search 37

搜索策略 (cont) Depth-first Search 38

算法1：Web Graph-Search PROCEDURE SPIDER1(G) Let ROOT := any URL from G Initialize STACK <stack data structure> Let STACK := push(ROOT, STACK) Initialize COLLECTION <big file of URL-page pairs> While STACK is not empty, URLcurr := pop(STACK) PAGE := look-up(URLcurr) STORE(<URLcurr, PAGE>, COLLECTION) For every URLi in PAGE, push(URLi, STACK) Return COLLECTION

算法1存在的问题 如果web graph有回路 算法将无法停止 遇到汇聚的结构 Crawl 完整吗？ 网页在集合中是重复的 无效的增大索引 重复的信息成为用户是负担 Crawl 完整吗？ 算法1只能爬行到由根结点网页连接的子图 Web不是强连通的

A Correct Spidering Algorithm PROCEDURE SPIDER2(G) Let ROOT := any URL from G Initialize STACK <stack data structure> Let STACK := push(ROOT, STACK) Initialize COLLECTION <big file of URL-page pairs> While STACK is not empty, | Do URLcurr := pop(STACK) | Until URLcurr is not in COLLECTION PAGE := look-up(URLcurr) STORE(<URLcurr, PAGE>, COLLECTION) For every URLi in PAGE, push(URLi, STACK) Return COLLECTION

A More Efficient Correct Algorithm PROCEDURE SPIDER3(G) Let ROOT := any URL from G Initialize STACK <stack data structure> Let STACK := push(ROOT, STACK) Initialize COLLECTION <big file of URL-page pairs> | Initialize VISITED <big hash-table> While STACK is not empty, | Do URLcurr := pop(STACK) | Until URLcurr is not in VISITED | insert-hash(URLcurr, VISITED) PAGE := look-up(URLcurr) STORE(<URLcurr, PAGE>, COLLECTION) For every URLi in PAGE, push(URLi, STACK) Return COLLECTION

A More Complete Correct Algorithm PROCEDURE SPIDER4(G, {SEEDS}) | Initialize COLLECTION <big file of URL-page pairs> | Initialize VISITED <big hash-table> | For every ROOT in SEEDS | Initialize STACK <stack data structure> | Let STACK := push(ROOT, STACK) While STACK is not empty, Do URLcurr := pop(STACK) Until URLcurr is not in VISITED insert-hash(URLcurr, VISITED) PAGE := look-up(URLcurr) STORE(<URLcurr, PAGE>, COLLECTION) For every URLi in PAGE, push(URLi, STACK) Return COLLECTION

一种Crawler的体系结构

大规模爬取器的一种结构图

DNS resolver

DNS缓存，预取和解析 如果不采取措施，DNS地址解析会成为一个重要的瓶颈 局域网中，DNS服务器通常较小，对付几百个工作站的常规操作没问题，但一个crawler产生的压力大很多 同时从一个服务器抓许多网页也可以使DNS的cache能力发挥出来 搜索引擎中可以设计一个专用的DNS模块，含有 用于地址解析的DNS client（和本模块的DNS缓存服务器打交道） 缓存server 预取client

高效地址解析的定制client 一般系统（例如UNIX）提供的DNS client没有考虑cralwer的需求，带来两个问题： 以gethostbyname()为基础，它不能并发； 不会考虑在多个DNS server之间分配负载。 因此一个custom client很必要。 专门对付多个请求的并发处理 容许一次发出多个解析请求 协助在多个DNS server之间做负载分配（例如根据掌握的URL进行适当调度）

DNS缓存服务器 大缓存容量，跨DNS系统的刷新保持内容 映射尽量放在内存，可以考虑用一台专门的服务器 Internet的DNS系统会定期刷新，交换更新的域名和IP的信息。 普通的DNS cache一般应该尊重上级DNS服务器带来的域名“过期”的信息，但用于爬取网页的DNS cache不一定如此，以减小开销（让缓存中有些过期的无所谓，但也要注意安排适时刷新） 映射尽量放在内存，可以考虑用一台专门的服务器

预取client 为了减少等待查找涉及新主机的地址的时间：尽早将主机名投给DNS系统 步骤 通常用UDP实现 用不着等待解析的完成 分析刚得到的网页 从HREF属性中提取主机名（不是完整的URL） 向缓存服务器提交DNS解析请求 结果放到DNS cache中（后面可能有用，也可能用不上） 通常用UDP实现 非连接，基于包的通信协议，不保证包的投递 用不着等待解析的完成

大规模爬取器的一种结构图

网页抓取 问题: 网络连接及传输的开销 解决: 局域网的延迟在1-10ms，带宽为10-1000Mbps,Internet的延迟在100-500ms，带宽为0.010-2 Mbps 在一个网络往返时间RTT为200ms的广域网中，服务器处理时间SPT为100ms，那么TCP上的事务时间就大约500ms（2 RTT+SPT） 网页的发送是分成一系列帧进行的，则发送1个网页的时间量级在(13KB/1500B) * 500ms ≈4s 解决: 多个并发的抓取

多个并发的抓取 管理多个并发的连接 过多的硬件并行好处不大 两种基本方法 单个下载可能需要几秒钟 同时对不同的HTTP服务器建立许多socket 连接 过多的硬件并行好处不大 爬取的性能瓶颈主要在网络和硬盘 两种基本方法 用多线程/多进程 用带事件处理的非阻塞sockets

大规模爬取器的一种结构图

链接提取和规格化 目标：得到网页中所含URL的标准型 URL的处理和过滤 避免多次抓取被不同URL指向的相同网页 IP地址和域名之间的多对多关系 大规模网站用于负载平衡的技术：内容镜像 不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要（Apache支持） 相对URL 需要补齐基础URL

节省资源：避免“同义”地址 域名与IP对应存在4种情况： 后三种情况都有可能造成重复搜集 一对一，一对多，多对一，多对多。一对一不会造成重复搜集 后三种情况都有可能造成重复搜集 可能是虚拟主机，多个域名共一个IP,内容不同 www.ir-lab.org , hitmslab.cs.hit.edu.cn -> 202.118.250.16 可能是DNS轮转 ent.sina.com.cn -> 202.112.8.2， 202.112.8.3 cul.sina.com.cn ent.sina.com.cn -> 202.112.8.3 可能是一个站点有多个域名对应 www.ir-lab.org和ir.hit.edu.cn等价

对URL进行规格化 用一个标准的字符串表示协议 利用主机名 显式加上一个端口号（80也加上） 规格化并清理好文档路径 查DNS会返回IP和一个主机名 显式加上一个端口号（80也加上） 规格化并清理好文档路径 例如将/books/../papers/sigmod1999.ps写成/papers/sigmod1999.ps

礼貌工作：不给网站造成明显负载 随着人们自我保护的意识越来越强，这问题越来越重要 不希望搜索引擎上“黑名单” “香港天网”从一开始就被抱怨 天网最近也受到抱怨 不希望搜索引擎上“黑名单”

Robot exclusion 检查 限制只是对crawlers，一般浏览无妨 在服务器文档根目录中的文件，robots.txt #AltaVista Search User-agent: AltaVista Intranet V2.0 W3C Webreq Disallow: /Out-Of-Date #exclude some access-controlled areas User-agent: * Disallow: /Team Disallow: /Project Disallow: /Systems 限制只是对crawlers，一般浏览无妨 “君子协定”（你的crawler可以不遵守）

爬取器的陷阱 防止系统异常 病态HTML文件 误导爬取器的网站 例如，有的网页含有68 kB null字符 用CGI程序产生无限个网页 用软目录创建的很深的路径 www.troutbums.com/Flyfactory/hatchline/hatchline/hatchline/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/hatchline HTTP服务器中的路径重映射特征

爬取器的陷阱：解决方案 不存在完美的自动方案，积累历史数据很重要 检查URL的长度 保护模块（Guards） 定期收集爬取中的统计数据 不爬取动态的内容（unsolved problem），例如由CGI表格查询产生的 清除非文本类型的URLs（即它的MIME类型不是text/****）

避免在重复网页上再提取链接 减少爬取中的别名冗余网页（不仅本身开销，还有其中的相对链接v） 重复网页的检测：镜像网页和网站 检测完全重复的网页（exact duplicates） 对比不同URL对应网页的MD5摘要 将相对于网页u的链接v表示为(h(u);v)，其中h(u)是u的内容的散列。这样，两个别名的相同相对链接就有同样的表示，直接放到isUrlVisited中检查 检测接近重复的网页（near-duplicates） 即使是一个字符的改变也会完全改变MD5摘要 例如，网页的转载常伴随有日期或者网站管理者名字的变化 解决方案：网页去重

文本仓储 爬取器最后的任务 好处：将crawler和搜索引擎系统的其他功能分开，既有效率的好处，也有可靠性好处 和网页相关的信息存成两个部分 将抓得的网页放到一个仓储（repository）中 好处：将crawler和搜索引擎系统的其他功能分开，既有效率的好处，也有可靠性好处 和网页相关的信息存成两个部分 元数据 网页内容

和网页相关信息的存贮 元数据 (描述数据的数据) （我们这里不谈建立索引的问题） 包括的域有content-type, last-modified date, content-length, HTTP status code, etc. 本质上可以表达成关系 但通常是由特别定制的软件来管理，以避免关系数据库的访问开销（以可能的可靠性损失为代价） （我们这里不谈建立索引的问题）

网页内容的存贮 典型HTML网页可以压缩到2-4 kB (using zlib) 文件系统的block size通常是4-8 kB（对网页太大！），“一个block，一个文件”损失太大 因此网页的存贮管理应该由专用存贮管理器来完成 提供简单的访问方法，用来便于 让crawler往里添加网页 后边的程序（索引器等）从中获取文档

网页存贮 小规模系统 能在一台机器的硬盘上放下 用存贮管理器（例如，Berkeley DB） 在一个文件内，管理基于磁盘的数据库 如果后续访问操作是随机的，例如以URL为键，则可以将它配置成hash-table/B-tree。访问开销较大。 如果后续访问可以是顺序的，例如索引器，则可以将它配置成一个顺序的网页记录。访问效率较高

网页存储 大规模系统 仓储分布在多个存储服务器上 存储服务器 通过高速局域网连到crawler 按照URL散列网页到存储服务器

还存在什么问题呢？ 网络资源的大小和动态性同时增长 真实世界是不完善的 效率问题 瓶颈 没有足够的内存支持所有的数据结构 1 billion pages / per month385pages/sec 瓶颈 DNS and tcp connection/transfer overheads -> improve network bandwidth utilization 没有足够的内存支持所有的数据结构 真实世界是不完善的 url/html syntax error , server traps Server complains, legal issues

高性能的 Crawler 需要… Scalable Fast Polite Robust Continuous Parallel , distributed Fast Bottleneck? Network utilization Polite DoS, robot.txt Robust Traps, errors, crash recovery Continuous Batch or incremental

网页预处理

网页预处理任务 网页去重 网页正文提取 分词等 网络上可能会出现多个域名对应同一个网站的情况或者网站的互相转载 去除重复的网页是为了避免同一个网站的内容被多次采集和索引 网页正文提取 由于网页中有很多对建立索引无用的信息，比如广告信息，一些无用的连接信息，还有一些脚本语言 所以在建立索引之前，需要先清理一下垃圾信息，这个过程被称为正文提取 分词等

网页重复情况 内容相同的网页分情况 其中前两种情况在相同网页中所占比例最大，大致占到80%左右 网页正文完全相同 网页正文大部分相同只是一些地方做了少量变动，一篇文章是另一篇的一部分 一种是两篇文章的某些段落相同 其中前两种情况在相同网页中所占比例最大，大致占到80%左右

网页去重算法 现在广泛使用的是基于指纹识别（fingerprinting）思想的网页内容重复性判断方法 主要思想 是抽取出网页内容中的一系列字符串，计算这些字符串hash值产生指纹 判断两网页是否相同时只需计算它们的相同指纹个数是否大于一定的阈值即可

使用文本块的网页去重方法 网页进行预处理，去除格式化信息以及非文字信息 对文本利用一定的策略进行分块，利用hash函数计算每一块的hash值，产生记录文本块信息的三元组<h,r,l>，其中h是利用此文本块计算出的hash值，r是文本块所属的文章的编号，l是此文本块在文章中的位置 将<h,r,l>信息存放到hash表中 对与d具有相同文本块的所有文章进行统计 如果相同文本块个数占文章d中所有文本块个数的比例大于一个阈值则认为文章d与r是相同的文章，它们对应网页是相同网页

利用shingle和超级shingle的网页去重方法 判断重复的方法 获取网页，对每一篇网页进行预处理，去除结构信息和html信息，产生对应的文字信息 利用文本信息产生与每个网页对应的shingle集合。shingle集合的方法是抽取出所有长度为w个单词的shingle，其中每两个紧邻的shingle有w-1个单词重叠 利用两文本的shingle集合来计算两个文本的相同度，如果大于一个阈值则认为这两个网页是内容重复的网页

利用shingle和超级shingle的网页去重方法 将一篇文本D的所有shingle随机排序，然后挑选出前m个保留，保留下来的shingle记为Fm(D) 将D中随机排序后的所有shingle的序号对数m进行模运算，所有保留下所有计算结果为0即序号是m的倍数的shingle，这些shingle的集合记为Vm(D)

基于集合统计的网页去重方法 对文档进行预处理，移除文档中的格式信息等，将文档分解成单词流 利用从样本集合中统计出的词的idf并利用一定的策略保留重要的单词（相同的单词只保留一个） 利用哈希算法将保留下来的单词计算出一个hash值，并且生成<文档编号, hash>二元组 将<文档编号，hash>按照hash值的大小存放到树形结构中，如果树形结构中已经存在和此文档相同hash值的文档则说明它们是内容重复的文档

其他方法 除了上述方法之外还有利用相似度计算和聚类来进行网页去重的方法 此方法的基本思想是利用向量余弦夹角的方法将所有相同网页聚成一类 判断一个网页的相同网页时需要将此网页的向量与每一个聚类中心向量计算两向量之间的余弦夹角值 但是这种方法的时间复杂度是O(n2)，因此当数据量非常大

正文提取

正文提取 大部分网页中除了包含它的主要有用信息（正文）外还含有许多的噪声信息： 正文提取的任务就是从给定的网页中抽取出正文信息 网站的导航信息 相关链接和广告等 正文提取的任务就是从给定的网页中抽取出正文信息

基于DOM树的正文提取 DOM（Document Object Model）是由W3C组织发布的一种访问和操作HTML文档的规范 Element： <body> Text： I love IR-LAB <head> Welcome to Html <p> <title>

基于DOM树的正文提取 利用网页的源文件建立一个DOM树结构 遍历DOM树，从网页中删除掉所有不是正文的信息 广告信息的移除：首先需要建立一个经常更新的广告服务器列表，如果地址是指向列表中的广告服务器地址则将此链接节点删除 链接群的移除：计算每一个节点所包含的链接个数相对非链接的词个数的比例，如果比例大于一个给定的阈值则删除此节点 删除不包含重要信息的节点：用户事先指定一些不重要的HTML标签以及一个有用标签至少需要包含多少字符 上述非正文信息移除掉后，DOM树中剩余的内容就是正文信息，可以直接从余下的树节点中抽取出正文信息

基于内容块的正文提取 基于内容块的方法是将HTML文件分块然后利用每一块关键词平均熵的大小来发现正文块的方法 遍历网页的HTML文件，利用table标签将网页粗略地分为许多内容块 对于每一个内容块提取出可以代表它的内容的一些特征词以便于后面计算内容块的熵，计算每一个特征Fi的熵 ： 对于内容块，如果它的熵大于一个阈值则认为是噪声信息，如果小于阈值则认为是正文块并包含了正文信息

举例 一个类别中含有两个网页，第一个网页含有F1, F2,…, F8这8个特征，第二个网页含有F1, F2,…, F6, F9, F10这8个特征，则 利用一个内容块中包含的所有特征的熵来计算此内容块的熵 如果熵大于一个阈值则认为是噪声信息

利用文字和标签的正文提取 边界标签识别的五种方法： 启发式匹配 标准偏差 可确认的分隔标签 最大个数标签 重复标签模式 由于以上方法都有一定的使用范围，因此最后使用以上方法的融合方式来处理网页

利用文字和标签的正文提取 为网页D建立对应的树状结构T 统计每一个节点的出度，选择具有最大出度的节点包含的子树HF 分别利用上述五种方法，融合计算出最有可能的边界标签

正文提取其他技术 基于视觉效果的网页分割技术 用中文标点符号提取正文 用HTML标签中的分隔线以及一些视觉信息（如文字颜色、字体大小、文字信息等）把网页分割成不同的信息块 用中文标点符号提取正文

相关排序

搜索引擎的排序最为重要 排序很重要 排序算法为各公司的机密。 SEO（搜索引擎优化） 65%一70%的网民点击搜索结果的第一页。 20%-25%的网民点击搜索结果第二页 3%-4%的网民点击量其他的网页 排序算法为各公司的机密。 Google 拥有PageRank技术 全球最大的中文搜索引擎—百度之所以能脱颖而出，在短短的几年时间内飞速发展，就是因为它们都拥有自己的核心技术:Google拥有PageRank技术，百度拥有超链分析技术。 SEO（搜索引擎优化） 互相博弈

传统的相关排序技术 文档d和查询q的相关性可以由它们包含的共有词汇情况来刻画 对于网页近似为普通的文本，采用上述方法 该方法只考虑网页中用户可见的文字部分，忽略标记和超链等内容

早期的基于词频和位置的排序 早期的搜索引擎结果排序都是基于这一思想的，如Infoseek, Excite, Lycos等 词频的加权 VSM等模型 词位置的加权 网页标题元、网页描述/关键字元、正文标题、正文内容、文本链接、ALT标识等，版式包括:字体、字号、有无加粗强调等

网页和普通文本的不同 HTML标签 HTML设计有丰富的标签，主要追求的是视觉效果 网页的字体、布局等等标签能给我们提示其中文字的重要程度 许多著名搜索引擎在网页的预处理阶段记录了这些信息，并用于结果排序。例如Alta Vista, Inktomi, Excite, Infoseek等等

网页和普通文本的不同（续） 网页之间的超链接 链接反映的是网页之间形成的“参考”、“引用”和“推荐”关系 可以合理的假设，若一篇网页被较多的其他网页链接，则它相对较被人关注，其内容应该是较重要、或者较有用 因此，可以认为一个网页的“入度”（指向它的网页的个数）是衡量它重要程度的一种有意义的指标。这和科技论文的情况类似，被引用较多的就是较好的文章 同时，人们注意到，网页的“出度”（从它连出的超链个数）对分析网上信息的状况也很有意义的，因此可以考虑同时用两个指标来衡量网页

链接分析技术分类 基于随机漫游模型。如：PageRank、 Repution算法 基于Hub和Authority相互加强模型。如：HITS及其变种 基于概率模型，如：SALSA,PHITS 基于贝叶斯模型，如：贝叶斯算法及其简化版本 所有的算法在实际应用中都结合传统的内容分析技术进行了优化

PageRank Sergey Brin 和 Lawrence Page于1998年提出PageRank算法 Google 采用的一种链接分析方法 仅通过权威性对网页排序，这样可以有校防止人为加工的页面欺骗搜索引擎。即由Web间的超链关系发现重要页面 应用于整个网络而不是围绕一个query结果主页的局部临近主页

Initial PageRank Idea 仅测量链入数，而不考虑链接的权威性. 初始化网页p排序公式: Nq 是网页q链出总数. 网页q, 将它权威性的值平均分给它指向的网页（例如p）. c 是归一化常数集.

Initial PageRank Idea (cont.) .1 .09 .05 .03 .08

初始算法 迭代排序过程直到收敛: S为网页集合 初始化 pS: R(p) = 1/|S| 直到排序不再改变 或者两次结果之差小于一定阈值(convergence) For each pS: For each pS: R(p) = cR´(p) (normalize)

初始算法的问题  如果有2个相互指向的网页a，b,他们不指向其它任何网页，另外有某个网页c，指向a，b中的某一个，比如a，那么在迭代计算中，a，b的rank值不分布出去而不断的累计。如下图：

随机冲浪模型(Random Surfer Model) 用户随机的选择一个网页作为上网的起始网页 看完这个网页后，从该网页内所含的超链内随机的选择一个页面继续进行浏览 沿着超链前进了一定数目的网页后，用户对这个主题感到厌倦，重新随机选择一个网页进行浏览，如此反复

PageRank 按照以上的用户行为模型，每个网页可能被访问到的次数越多就越重要 可能被访问的次数就定义为网页的权值，PageRank值 公式如下: Wj代表第j个网页的权值，li,j只取0，1的值，代表从网页i到网页j是否存在连接，ni代表网页i有多少个连向其他网页的链接，d代表“随机冲浪”中沿着链接访问网页的平均次数

收敛速度 在Google上的早期试验采用了322万链接. PageRank 算法大约在迭代52次后收敛. 根据经验，算法收敛要求的迭代次数为O(log n) (n为链接数). 效率较高

基于PageRank的简单的主题搜索 通过简单的布尔检索来检索网页标题，并且返回通过PageRank排序的检索结果. 例如检索 “大学”: 百度 返回标题带有“大学”的任意集合 简单的Google 返回大学的主页.

Google Ranking 完整的 Google 排序包括 当前商业排序函数的详细描述属于商业机密. 向量空间相似度. 关键词接近程度. HTML标记权重 (e.g. title preference). PageRank. 当前商业排序函数的详细描述属于商业机密.

HillTop算法简介 Google的一个工程师Bharat在2001年获得专利。 Google的排序规则经常在变化，但变化最大的一次也就是基于HillTop算法进行了优化，造成了天翻地覆的变化。 据说：现在google主要采用的方法也是HillTop算法

HillTop算法思想 类似于PageRank思想，也是通过网页被链接的数量和质量来确定搜索结果的排序权重 如果网站是介绍“服装”的，有10个链接都是从“服装”相关的网站链接过来，那这10个链接比另外10个从“电器”相关网站链接过来的贡献要大 Bharal称这种对主题有影响的文档为“专家”文档，从这些专家文档页面到目标文档的链接决定了被链接网页“权重得分”的主要部分

HITS算法的提出 基于商业或竞争因素考虑，很少有WEB网页指向其竞争领域的权威网页。 例如“Microsoft” 和 “Netscape”都是浏览器的权威主页，但并不互指 权威网页很少具有显式的描述，比如Google主页不会明确给出WEB搜索引擎之类的描述信息 比如Google主页不会明确给出WEB搜索引擎之类的描述信息 PageRank算法中对于向外链接的权值贡献是平均的，Hits算法考虑了不同链接的重要性

网页的权威性 权威性是公认的提供重要度，可信度及有用信息的页面记录 链入数（in-degree）（指向一个网页的链接数）是权威性的一个简单度量 但是链入数将所有链接同等对待

中心性网页（Hubs） Hub网页是提供指向权威网页链接集合的WEB网页 一般来说，好的Hub网页指向许多好的权威网页；好的权威网页是有许多好的Hub网页指向的WEB网页。

HITS算法的简介 Kleinberg于1998年就提出了HITS算法 基本思想 1个网页有两个属性： Hub/Authority 好的Authority 页被好的Hub页指

Hubs and Authorities 合起来趋向于形成一个双向图: Hubs Authorities

HITS算法的简介 HITS（Hyperlink－Induced Topic Search）算法是利用Hub/Authority方法的搜索方法 算法如下： 将查询q提交给传统的基于关键字匹配的搜索引擎 搜索引擎返回很多网页，从中取前n个网页作为根集(root set)，用R表示，R满足如下3个条件 R中网页数量相对较小 R中网页大多数是与查询q相关的网页 R中网页包含较多的权威网页 通过向R中加入被R引用的网页和引用R的网页将R扩展成一个更大的集合S 采用迭代的方法计算A/H值，最终按照A进行排序

构造子图 对一个特定的Q,从标准的搜索引擎返回的文档集合作为根集R 对R初始化 S 将指向R中任意网页的所有网页加入到S中

迭代算法 采用迭代算法收敛互指的hubs 和 authorities集合. 保证每个网页p  S: Authority score: ap (vector a) Hub score: hp (vector h)

HITS 更新规则 权威网页被许多好的中心性网页所指: 中心性网页指向许多好的权威网页:

更新规则说明 2 3 a4 = h1 + h2 + h3 1 4 5 4 6 h4 = a5 + a6 + a7 7

迭代算法 以S中的Hub网页为顶点集Vl，以权威网页为顶点集V2， 对V1中的任一个顶点v，用h(v)表示网页v的Hub值，对V2中的顶点u，用a(u)表示网页的Authority值。 开始时h(v)＝a(u)＝1，对u执行I操作修改它的a(u)，对v执行O操作修改它的h(v)，然后规范化a(u),h(v),如此不断的重复计算下面的操作I，O，直到a(u),h(v)收敛。

HITS算法的公式 I 操作： O操作： 每次迭代后要进行归一化

收敛性 如果无限迭代算法会收敛到一个固定点. 定义A是S定义的子图的邻接矩阵. 权威向量, a, 收敛到 ATA的主特征向量 Aij = 1 for i  S, j  S iff ij 权威向量, a, 收敛到 ATA的主特征向量 中心向量, h, 收敛到 AAT 的主特征向量 一般情况下, 20次迭代就可以产生十分稳定的结果.

Results Authorities for query: “Java” java.sun.com comp.lang.java FAQ Authorities for query “search engine” Yahoo.com Excite.com Lycos.com Altavista.com Authorities for query “Gates” Microsoft.com roadahead.com

根据链接结构寻找相似网页 给定网页P,令R(根集)中t (e.g. 200) 个网页指向P. 从R中获得基集S. 在S上运行 HITS. 返回S中最好的权威网页作为P的最相似网页.

相似网页结果 Given “honda.com” toyota.com ford.com bmwusa.com saturncars.com nissanmotors.com audi.com volvocars.com

PageRank与Hits算法 它们都利用了网页和超链组成的有向图，根据相互链接的关系进行递归的运算。 但是，两者又有很大的区别，主要在于运算的时机 Google是在网页搜集告一段落时，离线的使用一定的算法计算每个网页的权值，在检索时只需要从数据库中取出这些数据即可，而不用做额外的运算，这样做的好处是检索的速度快，但丧失了检索时的灵活型。 HITS使用即时分析运算策略，每得到一个检索，它都要从数据库中找到相应的网页，同时提取出这些网页和链接构成的有向子图，再运算获得各个网页的相应链接权值。这种方法虽然灵活性强，并且更加精确，但在用户检索时进行如此大量的运算，检索效率显然不高。

链接分析技术小结 提供了一种衡量网页质量的客观方法 独立于语言，独立于内容，不需人工干预就能自动发现WEB上重要的资源

链接分析技术小结（影响因素） 根集的质量。根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页，产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量网页集找出很多高质量的网页。 噪音链接。WEB上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商，用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果。如何有效的去除这些无关链接，也是算法的一个关键点。 查询的分类。每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法，以求获得最好的结果。因此，对于查询的分类也显得非常重要。