A Simple Scratch of Search Engine
作者 史春奇， 搜索工程师， 中科院计算所毕业， chunqi.shi@hotmail.com http://hi.baidu.com/shichunqi 计划：
1， 需求迫切 07/06完成
2， 搜索引擎简单模型 07/08完成
3， 信息导航模型 07/16完成1/3 数据抓取 07/30 预处理 4， 商家推广模型 5， 未来
本文是学习搜索引擎的涂鸦草稿， 高深读者请拐弯到：http://sewm.pku.edu.cn/IR-Guide.txt （北大搜索引擎小组--信息检索指南）
简单搜索引擎模型 .................................................................................................................................. 1
A Simple Scratch of Search Engine.................................................................................................... 1 第一章 需求迫切 ................................................................................................................................. 2
一）泛信息化 .................................................................................................................................. 2 二）泛商品化 .................................................................................................................................. 2 第二章 导航模型--草根需求信息 ....................................................................................................... 3
第一节 第二节
最直观简单模型 ............................................................................................................. 3 互联网简单模型 ............................................................................................................. 5
1．发展历史 ............................................................................................................................ 6 2．大陆互联网现状 ................................................................................................................ 7 3．草根需求 .......................................................................................................................... 10 第三节 网页抓取简单模型 .......................................................................................................... 10
1. 2. 3. 4. 5. 1. 2. 3.
最简单Spider抓取模型 ............................................................................................... 11 最简单Spider调度模型 ............................................................................................... 12 最简单Spider调度质量模型 ....................................................................................... 15 最简单Spider调度策略模型 ....................................................................................... 18 Spider的常见问题 ........................................................................................................ 23 质量筛选（Quality Selection） .................................................................................... 24 相似滤重（De-duplicate）........................................................................................... 35 反垃圾（Anti-spam） .................................................................................................. 43
第四节 网页预处理简单模型 ...................................................................................................... 23
第五节 索引存储简单模型 .......................................................................................................... 48
第六节 检索框架简单模型 ....................................................................................................... 48
信息检索评价指标 ................................................................................................................ 48
第三章 推广模型--商家需求客户 ........................................................................................................ 49 第四章 未来 .......................................................................................................................................... 49
第一章 需求迫切
之前说过， 搜索引擎是互联网大爆炸后的新生事物， 他的成功来源于两个方面高度发展， 一个是泛信息化， 一个是泛商品化。
一）泛信息化
分为两个方面， 一方面是信息的类型呈百花齐放， 另一方面是信息的数量呈海量增长。 1, 信息种类繁多。
大家切身感受到的是多媒体娱乐和社交联系在互联网上变得明显的丰富起来。信息种类繁多不可避免会导致搜索引擎的种类繁多起来。 而搜索引擎种类繁多这一点，你可以看一下Google，Baidu提供的服务是多么繁多，你就知道了。参考百度更多（http://www.baidu.com/more/）， Google更多（http://www.google.com.hk/intl/en/options/）， 这些还不包括实验室（Lab）的产品。 我们换个角度看这个问题， 看看现在已经有多少种搜索引擎来满足信息繁多的各种需求了， Wiki的搜索引擎列表（http://en.wikipedia.org/wiki/List_of_search_engines）有一个分类，显示了10种类型，分别是，1）论坛， 2）博客， 3）多媒体（音乐，视频，电视），4）源代码，5）P2P资源，6）Email，7）地图，8）价格，9）问答信息，10）自然语言。 我们知道信息爆发都是由需求带动的，那么目前有多少需求已经有搜索引擎在满足了呢？ 下面列出了14种类型， 分别是， 1）普通[知识]， 2）地理信息，3）会计信息，4）商业信息，5）企业信息，6）手机和移动信息，7）工作信息，8）法律信息，9）医疗信息，10）新闻信息， 11）社交信息，12）不动产信息， 13）电视信息， 14）视频游戏信息。 2，信息海量增长。
类似， 我们从搜索引擎的发展，反向来看信息增长。搜索引擎的索引量是选择收录入库的网页数， 肯定小于或者远小于互联网的信息量。 最早Yahoo是人工编辑的目录索引， 就几万和几十万的级别。 到Infoseek，Google早期等的几百万的索引量。 到Baidu早期的千万、上亿的索引量。 到现在Google等上千亿的索引量。 如果你看一个网页要1秒钟， 1000亿网页要看3171年，而且不吃不喝， 一秒不停地看。如果你是愚公世家，你的祖辈在大禹治水的时候就开始看网页， 到现在你还没看完。
因此草根（Grassroots）用户需要搜索引擎来满足它们的信息的导航，草根用户追求免费，快捷和有效的服务。
二）泛商品化
也分为两个问题， 一方面， 满足新需求的商品种类繁多。 另一方面， 满足老需求的新商品的种类繁多。 现在有很多新产品，你如果不推广，很多有需求的人都找不到你， 或者找到的不是你。举例啊，如果你不看新闻广告，你都不知道有人在给狗狗举行隆重的葬礼，那么你知道去那里找个满意的祭司么？ 有人告诉你说网上。 那么你知道哪家的服务好么？ 又有人告诉你说找论坛看评论。 同样，你了解商家怎么推销自己的产品么？他们可以选择在网上打广告， 可以找搜索引擎帮助推广。现在产品的确太多了， 商家太多了， 让你都不知道何去何从。 就说最古老的饮食， 现在遍地是餐饮， 选哪个好了？如果某商家嫌客户少， 想打折推广。 古老的方式是挂大旗，发传单。 而今你要想让更多的人看到， 可以去互联网花钱推广， 可能花同样的钱， 被推广的对象还是有迫切需求的潜在用户。 这样你的广告费用花的会更有效果。 而搜求引擎广告，满足信息查询需求的同时，只要搜索的用户足够多，就会有很多提供服务的商家想请你帮忙做推广，满足他们脱颖而出的广告需求。
因此商家需要搜索引擎来满足它们的广告的推广，商家追求用户和利润是愿意付费的。
第二章 导航模型--草根需求信息
信息爆炸给搜索带来人气， 商品爆炸迫使商家追逐人气， 两者的结合使得搜索引擎成为互联网的宠儿。
第一节 最直观简单模型
在谈及基础前，还有些基础，插曲一下：
1. 什么是顺序文件(Sequential File)，什么是随机文件(Random File)，两者的优缺点？ 2. 什么是索引(Index)， 什么是哈希(Hash)，两者有关联么？
3. 什么是计算机的金字塔存储系统（Storage Pyramid）， 为啥是金字塔状？那寄存器
（Register），高速缓存（Cache），内存储器（Internal Storage），外存储器（External Storage）等分别有什么优缺点？
在理想的场景下， 搜索引擎能够对互联网内容进行理解， 并且对用户的提问也能够理解， 然后直接给出用户需要的结果。但是目前计算机技术的发展， 搜索引擎还只能对互联网的页面进行索引（Index）， 然后对用户提供的查询词进行分解成关键词（Keywords/Term）。 然后完成基于关键词的搜索（Retrieval）。
这样就搜索引擎就需要首先划分成“网页获取”， “建索引”， “查询”， 这三个大模块， 使得数据流从“互联网”保存到“网页库”， 然后到“索引库”，再到检索服务器， 最后流向用户， 见图（1.1）。
网页获取： 能够及时地， 全部地获取（复制）整个互联网的所有的网页。 我们知道互联网首先已经是海量的， 其次互联网还在动态变化， 每一秒都在变化（增更减）。 假如我们的存储足够大， 读取互联网数据的能力足够快。 那么每天将互联网全部复制一次，就可以满足要求。 显然这是不可能实现的。 那么怎么抓取才能尽可能完整地（entirely），及时地（timely）获得互联网数据呢？
建索引： 将全部网页， 按关键词索引。 由于文档的数量非常大， 并且文档的价值不一样。 要是能将所有新获取的页面， 在每天抓完之后， 当天就能索引完成（fast indexing）， 并
且索引的访问快速（efficient accessibility）， 而且索引的存储空间（small storage space）较小。 并且索引的全部是有意义（valuable）的页面。 显然有点像又要马儿好， 又要马儿不吃草，是难以完美地实现的。 那么如何高效地进行索引成为这个阶段的核心问题。 高效地索引成为这个阶段的核心目标。
查询：对用户的查询词分解成索引能处理的关键词（Terms）， 其次查找匹配的文档（resemblance）， 再将文档排序（ranking）后返回给用户。
InternetWWW数据获取用户查询建索引索引库检索架构网页库检索服务器
图（1.1），最直观数据流模型
网页库：保存网页数据， 或保存成自定义结构化数据，或者文本块。 为了提高读写性能，一般会顺序保存。 为了增加空间利用率， 很可能进行压缩写入， 解压读出。 当然网页的相关属性也会保存到网页库， 为的是流水线处理， 尽量减少读写（IO）次数，从而减少处理时间和磁盘/闪盘的损耗。因为互联网的网页数量实在太大了。
索引库：索引库直观上从存储上来说可以是磁盘/闪盘上的一组索引文件。但是要真正完成索引机制—快速查询或者检索， 必然要对应到内存的数据管理。 因此会有对应的索引架构，对索引数据进行金字塔式地管理。一般是内存CACHE->内存高层索引结构->内存底层索引结构->磁盘/闪盘高层索引结构->磁盘/闪盘文件， 这样一个类似的金字塔结构（Pyramid Hierachy）。并且为了进一步提高效率，会采用多机并发，很可能是集群（Cluster）或者分布式（Distributed）的架构。 另外从索引机制上来看， 目前主要是倒排索引（Inverted Index）和顺序（Sequential）或者哈希（Hashing）正排索引的综合体。 倒排索引做到高效地检索， 正派索引可以在保证效率的前提下， 极大地减小倒排索引的索引内容的大小。 因此很是一个综合体架构。
检索服务器：直观上来看，检索服务器做到人机WEB服务接口。 因此可能采用MVC(Model-View-Controller)的模型来剥离WEB和数据（DATA）。 另外检索服务器又要做到查询比较， 涉及到相似性（Resemblance）和排序（Rank）的机制， 也就是说在WEB和DATA之后，必然还有一层进行检索（Retrieval）功能， 因此，检索架构很可能或者至少是一个Web-Data-Retrieval的三层架构。而为了分流用户群和增加安全性（不要把所有鸡蛋放到一个篮子里）， 也会结合采用分流并行的架构。
有了数据流模型，不可避免要进行数据处理，数据处理是搜索引擎公司（Google， Baidu， Yahoo等）的核心竞争力， 会涉及到复杂的算法和架构。 另外，又是研究领域的热点和难点， 会有TREC，SIGIR，WWW等很多会议对各方面进行创新。 同时， 开源界也在发力。
首先，数据处理大体以用户可见与否，分成后端和前端两个部分。 将网页库和索引库相关
联的部分， 称为后端。 而和互联网与查询词相关联的部分称为前端。后端和信息检索(Information Retrieval)领域更贴近。 前端和WEB技术（Web Technology）更贴近。自此，开始慢慢学习后端模型，这是看不见得的竞争力， 见图（1.2）。
完成“数据获取”的数据处理模型被称为爬虫Spider，从“互联网”获取数据，更新到本地“网页库”的核心程序被称为Spider或者Crawler。一方面，Spider和“互联网”之间要通过Schedule来进行数据获取。另外一方面， Spider又要将数据Update到“网页库”。
完成“建索引”的数据处理模型被称为索引器Indexer， 一方面， Indexer获取“网页库”的数据后， 要进行一次预处理或者清洗， 这也是所有IR领域的常见做法， 为了简化处理和优化效果。 另外一方面， Indexer又要Analyze数据，将结果保存到索引库。 索引库可以是结构化数据结构， 也可以用数据库（Data Base）来保存。
完成“查询”的数据处理模型被称为检索器Retrieval， 一方面， Retrieval要决定读取“索引库”的哪些索引数据。 另一方面， Retrieval要根据Query的相关性（Resemblance）来进行排序（Rank）。 因此这是一个决策机制。 打个简单比喻， 如果前面所有的处理是身体的话， 那么这就是大脑。说句土话，有健康的身体才能为大脑供血， 有牛掰的大脑才能理解用户的需求。
User InterfaceInternetQueryScheduleSpiderIndexerRetrievalFrontendUpdatePreprocessAnalyzeRankBackend索引库网页库图（1.2），最直观数据处理模型
第二节 互联网简单模型
管中窥豹， 略见一斑。 由于信息获取的便捷性，和大家的切身体会， 选择中国互联网来讲述简单见解。 这里纯属草根见识， 有专业需求的， 可以参考《Modeling the Internet and the Web. Probabilistic Methods and Algorithm》是形式化描述互联网模型的极好的一本书。豆瓣介绍： http://book.douban.com/subject/1756106/ 幻灯片： http://ibook.ics.uci.edu/slides.html PDF下载：
http://bib.tiera.ru/DVD-010/Baldi_P.,_Frasconi_P.,_Smyth_P._Modeling_the_Internet_and_the_Web._Probabilistic_Methods_and_Algorithms_(2003)(en)(285s).pdf
互联网（Internet）最重要的是互联， 对应的是内联网Intranet或者说局域网LAN。 还记得我当时做双绞线RJ-45的水晶头， 然后把几个机器链接起来， 能够相互之间拷贝电影， 打红警，就很开心。 当时还买书看什么是对等网，星型网络结构。 后面再学ISO七层模型和TCP/IP四层模型等等才知道互联是如何而来的。 自我感觉互联网（Internet）中的互联和搜索引擎的所利用的网页互联，还是不太一样。互联网（Internet）和局域网（Intranet）和LAN的互联， 强调的是物理层上的互联， 是TCP/IP协议的描述。 而搜索引擎所利用的互联， 某种意义上是强调的万维网（World Wide Web）的互联， 是HTTP协议中的超链（hyperlinks）互联。 或许也是计算机领域Net和Web的区别来着。 万维网（WWW）是网站（Website）的互联。如果将一个网页看成承载信息的一个单元， 那么网站可以看成承载一类信息的单元。 而WWW是不同类信息的互联， 是信息的海洋。 我体会较早的上网是1999年开始的Chinaren校友录和263电子邮箱。可以从同学谈话的页面点击跳到同学照片的页面。 正是这种简单的点击跳转，互联了WWW，所以你看到大部分站点的域名是WWW开头的， 表明那是一个Web服务器。 每个网站都有一个首页， 表示这是入口， 从这个入口，应该可以访问整个网站。 随着互联网的发展，网站之间的点击跳转成为必然，起初可能是你自己收藏链接， 慢慢一些门户网站成为大家访问互联网的入口， 从这里你应该可以访问整个万维网， 到如今搜索引擎在这方面起的作用越来越大。 其实搜索引擎也是在利用网站之间的这种点击跳转的互联信息，只不过大大减少了你查看点击跳转后是页面否为目标页面的尝试和时间代价。
1．发展历史
《中国互联网发展大事记》 -- 中国互联网络信息中心（CNNIC）， 从中选择了草根基本可以感受到的16个大事。 http://www.cnnic.net.cn/index/0E/21/index.htm
1. 1994年4月20日，NCFC工程通过美国Sprint公司连入Internet的64K国际专线开通，实现了与Internet的全功能连接。从此中国被国际上正式承认为真正拥有全功能Internet的国家。 2. 1994年5月，国家智能计算机研究开发中心开通曙光BBS站，这是中国大陆的第一个BBS
站。
3. 1998年6月，CERNET正式参加下一代IP协议(IPv6)试验网6BONE。
4. 1999年7月12日，中华网在纳斯达克首发上市，这是在美国纳斯达克第一个上市的中国概念网络公司股。
5. 2000年12月12日，人民网、新华网、中国网、央视国际网、国际在线网、中国日报网、中青网等获得国务院新闻办公室批准进行登载新闻业务，率先成为获得登载新闻许可的重点新闻网站。
6. 2001年1月1日，互联网\"校校通\"工程进入正式实施阶段。
7. 2001年7月9日，中国人民银行颁布《网上银行业务管理暂行办法》。
8. 2001年12月20日，中国十大骨干互联网签署了互联互通协议，这意味着中国网民今后可以更方便、通畅地进行跨地区访问了。
9. 2004年2月3日至18日，新浪、网易和搜狐先后公布了2003年度的业绩报告，首次迎来了全年度盈利。
10. 2004年5月13日，网络游戏公司盛大网络正式在美国纳斯达克上市，这是中国网络游戏在纳斯达克证券 市场首次亮相。
11. 2004年6月16日，即时通讯服务提供商腾讯公司正式在香港挂牌上市。 12. 2005年8月5日，百度公司在美国纳斯达克挂牌上市。
13. 2005年，以博客为代表的Web2.0概念推动了中国互联网的发展。Web2.0概念的出现标志互联网新媒体发展进入新阶段。在其被广泛使用的同时，也催生出了一系列社会化的新事物，比如Blog，RSS，WIKI，SNS交友网络等
14. 2006年12月18日，中国电信、中国网通、中国联通、中华电信、韩国电信和美国Verizon
公司 六家运营商在北京宣布，共同建设跨太平洋直达光缆系统。
15. 2007年，腾讯、百度、阿里巴巴市值先后超过100亿美元。中国互联网企业跻身全球最大互联网企业之列。
16. 截止2008年6月30日，我国网民总人数达到2.53亿人，首次跃居世界第一。7月22日， CN
域名注册量以1218.8万个首次成为全球第一大国家顶级域名。
从《大事记》简单来看， 中国互联网走过了，国际互联， BBS， 新闻网， 校园网， 门户网， 网络游戏， 即时通信， 搜索引擎， WEB2.0， 高速互联， 全民上网。
1. 互联网刚开始的突破是取代印刷页，社交功能还非常低级，人们以获取单一新信息为主。 2. 门户网站标志着信息爆炸(半有序)的初级阶段已经到来， 人们求助于门户来获取综合信息。 3. 网络游戏和即时通信的阶段标志着互联网承载了人与人之间关系的初级阶段。
4. 搜索引擎标志着信息爆炸(半有序)的高级阶段已经到来， 人们求助于搜索来获取任何信息。 5. WEB2.0时代标志着互联网成为人们生活的不可或缺的一部分。
一句话， 来简单回顾互联网发展特征，内容站 => 导航站 => 参与站 => 生活站。
2．大陆互联网现状
既然互联网革命性地改变了人们获取信息的方式。 那么， 就从信息的角度出发来观察互联网。 信息定义为事物存在的方式和运动状态的表现形式。 来主要观察一下信息的载体， 信息随时间的变化情况，信息的数量和质量。 对应到互联网， 网页的构成情况， 页面的更新周期， 网页的数量和质量。
根据《中国互联网络发展状况统计报告（2010年1月）》，中国互联网络信息中心（CNNIC）。 http://www.cnnic.net.cn/uploadfiles/pdf/2010/1/15/101600.pdf ， 后面简称“统计报告”。我们可以获取到部分信息： 包括页面编写语言，页面更新周期，页面数目（静态/动态）。
《统计报告-附表 11》， 可以看到静态页面（html/htm）， 半静态页面（shtml）， 动态页面（php， asp， jsp， aspx）的大致比例是3:1:5的样子。 可以看到超半数信息已经由动态网页在承载。
《统计报告-附表10》，按更新周期分类的网页情况， 75%的信息在半年内将会更新， 55%的信息在一个季度内更新， 30%的信息会在一个月内更新， 8%的信息在一周内更新。 那么估计会有1%以上的信息会在一天内更新。
《统计报告-表 5》可以看到互联网的网页数目336亿， 已经在百亿~千亿的级别之间了。
《统计报告-附表 14 分省网页字节数》可以看到国内平均页面大小是30K左右， 网页总大一句话，目前看到的是动态链接占有很大比例的， 变化很快的， 数据很大的互联网。
《统计报告-附表 11》 按照后缀形式分类的网页情况
网页后缀形式 .html htm / 比例 20.1% 6.5% 2.1% 小在964太（Terabytes）数据。
shtml asp php txt nsf xml jsp cgi pl aspx do dll jhtml cfm php3 phtml 其他后缀 合计
8.7% 12.6% 22.2% 0.0% 0.0% 0.0% 1.0% 0.2% 0.0% 6.1% 0.5% 0.0% 0.0% 0.0% 0.0% 0.0% 19.7% 100% 《统计报告-附表 10》 按更新周期分类的网页情况 网页更新周期 一周更新 一个月更新 三个月更新 六个月更新 六个月以上更新 合计
《统计报告-表 5》 中国网页数
网页总数 静态网页 占网页总数比例 动态网页 占网页总数比例 静态/动态网页的比例 网页长度（总字节数） 平均每个网站的网页数 平均每个网页的字节数
《统计报告-附表 14》 分省网页字节数 单位 2008年 个 个 个 KB 个 KB 16,086,370,233 7,891,388,272 49.06% 8,194,981,961 50.94% 0.96:1 5,588 28.6 2009年 33,601,732,128 18,998,243,013 56.54% 14,603,489,115 43.46% 1.3:1 10,397 31.5 增长率 108.88% 140.75% —— 78.20% —— —— 130.32% 86.06% 10.30% 比例 7.7% 21.2% 28.1% 18.8% 24.3% 100% 460,217,386,099 1,059,950,881,533
北京 浙江 广东 山东 福建 上海 辽宁 湖南 重庆 天津 四川 江苏 甘肃 河南 河北 江西 云南 湖北 陕西 青海 广西 安徽 黑龙江 吉林 海南 内蒙古 新疆 贵州 山西 宁夏 西藏 全国
总页面大小（T） 平均网页大小（K） 289.5 119.4 124.1 20.7 40.4 93.5 12.8 8.1 7.2 31.3 18.9 61.8 1.1 30.0 22.8 8.0 2.4 18.4 12.1 0.2 8.8 10.9 7.2 2.7 5.5 1.2 0.2 1.2 2.1 1.2 0.1 964.0 32.2 35.2 26.6 29.6 29.7 30.6 31.8 30.5 27.3 33.4 26.5 30.8 28.1 27.7 33.0 26.5 27.4 27.5 38.9 29.5 34.6 27.2 31.9 31.2 35.5 28.6 26.1 24.6 25.1 26.5 43.9 30.8 质量是个难以简单说明的啦， 是和需求密切相关的东西。 需求是和人密切相关的东西。
人相当复杂， 因此导致质量会比较复杂， 还是从草根需求观望下下罢了。
3．草根需求
作为草根的我，会在网上看看新闻和时事评论， 在自己的博客上发点东西， 闲暇时上个开心， 去好友主页看看。
而我的表弟， 一个在读大学生， 则会不停地折腾QQ， 沉迷于魔兽世界， 疯狂的优酷电影。
我的叔叔， 一个初中教师， 则每次打开，都是hao123主页， 然后去看看新闻， 看看财经频道， 偶尔在小说网站逗留。
从《统计报告-图8》来看， 三个不同年龄段几乎占了80%的用户比例， 所以上述的三个的草根还是代表些什么的。 按这些草根的需求来看， 大致分为： 资讯获取， 大站导航， 草根参与， 网络游戏。 可以对应大致的质量要求是内容准确， 傻瓜指引， 民主生活， 大侠体验。
《统计报告-图 8》 网民年龄结构对比
第三节 网页抓取简单模型
世界上第一个网络爬虫Spider是由麻省理工学院 (MIT)的学生马休.格雷（Matthew Gray)在 1993 年春天写成的，就在NCSA Mosaic的浏览器发布后数月。他给他的程序起的名字叫“万维网漫游者”(\"www wanderer\")。 Wanderer是用类Perl书写的抓取程序。而第一个在研究论文里面介绍网页抓取的是大卫.艾希曼（David Eichmann）描述的RBSE spider。
图（3.1）Matthew Gray， Google工程师
图（3.2）David Eichmann，爱荷华（Iowa）大学教授
从第一个Spider的出现，人们已经将互联网类比成蜘蛛网， Spider做的事情就是遍历整张网。 吴军（腾讯搜搜EVP(执行副总裁)助理， 前Google研究员）在（数学之美系列六--图论和网络爬虫）有数学模型角度的阐述。
http://www.cqumzh.cn/att_blog/month_0901/a2fe1b64c99263b246e9d923f1055549_1231307756.pdf
1. 最简单Spider抓取模型
Spider抓取整个互联网数据到本地，在我看来有两个基本的假设： 1， 只要从少量网页出发， 最终能遍历整个网络。
2， 只要采用合适的遍历算法，Spider肯定能够在合适时间内遍历整个网络。 这两个基本假设会直接映射到两个现实的问题：
1， 希望随着遍历，互联网的网页数目是能够被穷尽的。 2， 希望算法可以快速区分已遍历和未遍历的网页。
我们知道， 网页可以用URI/URL来标识， 但是不是唯一标识。所以，
1， 希望URL的数据是能够被穷尽的， 会引入问题， 如何标准归一化URL， 尤其动态网
页（JSP/ASP/Servlet/PHP）等技术中，URL映射（URL Mapping）技术盛行， 加大了这方面的难度。
2， 算法快速区分已经遍历和未遍历的URL，会引入问题，如何存储和读取URL信息。
根据之前互联网现状， 目前动态网页数量已经超过半壁江山。 动态网页会极大地引入URL标准归一化的难度。 同时会提高爬虫陷阱（Spider Trap）的概率（爬虫陷阱的解决分为网页处理后经验数据解决和目标站点配合解决两种途径）。 这样， 可以大致得出网页库存网页， URL库存链接， 下载器抓取未抓URL的最简单Spider双库（URI库/网页库）抓取模型。
Internettcp/ipDownloaderunfetched URLsURI库updatetcp/ipSpiderURL extractor & normalizerHTMLupdateupdateAnalyzer网页库图（3.1.1）最简单Spider双库（URI库/网页库）抓取模型
2. 最简单Spider调度模型
现实中，每个机器的的网卡速度和对应IP的带宽都是有限制的， 而互联网网页的数量都是上千上万亿， 必然需要多个机器并行抓取才能加快。 并且URL抓取肯定需要将HOST变成IP地址， 这就需要DNS解析（Resolver）。 另外， Spider在抓取站点（WebSite）的时候， 需要遵守Robots协议。 Robots协议是一个开放协议， 是为保护目标站点而采取的限制措施， 从而达到双赢（Win-Win）的局面。 例如对可能存在爬虫陷阱（Crawler Trap）的URL path可以在robots.txt禁止抓取， 这样既可以避免Spider的无用功， 另外也可以避免站点的无效抓取比例过高而导致搜索引擎对站点收录降级。
毕竟一个网站的带宽也是有限制的， 在抓取这个网站的时候， 还要考虑这个网站的访问压力(Stress)。 因为不同的站点在访问率（Access Rate）和压力上限（Maximum Stress）都是有预期的。 否则网站就无法提供正常访问服务， 站长极可能封禁（Block）频率大的访问。 这就需要配置站点的抓取频率了， 而互联网的站点都是上亿上千万级别的， 肯定无法一一手动配置， 这就需要有反馈式调度机制了， 需要统计站点的信息。 同时，站点（Website）与域名(Domain Name)是一对多的关系。 而域名（DN）和IP是多对多的关系。 而抓取下载（Download）是和
IP关联的。 例如，对可能存在的泛域（Wildcard Domain）特征的站点， 虽然站点的内容是有限的， 但是却可以产生无限的二级域名（Infinite Sub-domain Generator），从而导致无效抓取。 因此，具体到站点的时候， 既要归一化域名（Domain Uniformization）， 减少重复抓取， 又要均衡各个IP之间的压力， 提高并发度， 加快站点收录频率。
这样， 加上上述协议和物理上的限制， 在之前的模型上就需要增加多下载器调度（Multi-Downloader Schedule）， DNS解析服务（DNS resolver）， Robots协议识别（Robots Protocol Checker）， 站点特征收集（Website Meta-info Collector）[包括访问量（Maximum Stress），多IP压力均衡（Multi-IP Stress Balance），域名归一化（Domain Uniformization）]等等。 同时， 为了减少网页库的读写， 会将网页内容抽取也会加入进来， 作为网页解析器的功能模块（HTML Parser）。
至此一个简单的网页抓取调度模型就如此初露端倪， 可以大致看到有三个环结构。 涉及面小一点的是调度反馈环，主要会做优化抓取效率的工作。 而调度循环抓取环， 是保证整个流程循环起来的根本，是核心骨架。 涉及面最大的是调度质量控制， 也是最难把握的地方。 正所谓核心竞争力所在。 调度反馈和调度质量控制， 一个追求的是数量， 一个追求的是质量。 很明显，这里三个环的交汇点是调度， 并且最不清楚的地方也是调度。 所以说从最简单的调度模型出发的话， Spider爬虫把几乎所有难点问题都推给了调度。
Internetrobots.txtDNS CachepagesMulti-DownloaderMulti-DownloaderDNS ResolverClientRobots CheckerSchedulerunfetched URLsURI库调度反馈updateSite/Domainupdate特征库tcp/ip调度循环抓取统计信息URL extractor & normalizerContent extractor Spider调度质量控制updateAnalyzer网页库updateHTML ParserHTMLData Package图（3.2.1）最简单Spider调度抓取模型
另外，爬虫Spider抓取的下载器也随着互联网在全球范围的快速发展而在马不停蹄地
升级。 早期的是单机多线程/多进程（单核/多核）的下载器（Multi-Downloader）。采用多下载器模式（Multi-Downloader）可以增加单机的吞吐量， 提高内容和网卡的利用率。 随着互联网数据量进一步增大，和单机存储和带宽的限制， 出现多机并行下载（Paralleled Crawler）。多机并行抓取可以很好地进行负载均衡，而且多机架构容易增加或者减少并行机器来适应抓取状态的
变化，同时容易对站点进行划分管理（Partitioning）， 让部分机器固定抓取部分站点。进一步随着互联网的全球联网，和跨国搜索巨头的出现， 在各个地区设置抓取中心（Crawler Center），架构分布式抓取（Distributed Crawler）成为趋势。 一方面由于受到地区之间主干网的带宽限制，按地区分布（Locally Distributed）的抓取中心有利于减少延迟（Lower Latency），减小地区间主干出口压力（Internet Backbone Traffic Interchange Politeness），同时有利用对地区语言文化的适应（Linguistic Validation & Cultural Adaptation）。
并行抓取又分为静态并行（Static Paralleled）和动态并行（Dynamic Paralleled）， 主要区分在于下载器是由调度来按固定策略预先分配好抓取任务呢，还是下载器动态向调度索取抓取任务。 本质上， 采取合适的策略， 两者可以达到类似的效果。
Downloader 0Downloader 0Downloader 0Multi-Downloader吞吐量资源利用Crawler 0Crawler 1负载均衡可扩展性站点控制Crawler Center 0Crawler Center 1地区均衡分区抓取安全容错语言文化SpiderArchi-tectureCrawler NParalleled CrawlerCrawler Center LDistributed Crawler图（3.2.2）分布式Spider最简单架构
InternetCrawler 0qq.com/downloadqq.com/blog163.com/news163.com/mailCrawler 1news.sina.com.cn/beijingnews.sina.com.cn/whethersohu.com/newssohu.com/mapsCrawler N-1……SpiderSchedulerStatic Paralleled图（3.2.3）静态并行抓取
InternetCrawler 0Crawler 1Crawler N-1Schedulerqq.com/downloadqq.com/blog163.com/news163.com/mailnews.sina.com.cn/beijingnews.sina.com.cn/whethersohu.com/newssohu.com/maps…SpiderDynamic Paralleled图（3.2.4）动态并行抓取
3. 最简单Spider调度质量模型
大家对一个好的互联网产品都有点了解，泛泛地说首先是要符合互联网发展的现状， 其次要贴近用户的需求， 估计这样基本算一个可用的互联网产品。同样，什么是一个好的调度呢， 类比来说， 首先符合互联网发展现状， 其次贴近用户需求的调度，应该算一个可用的调度了吧。 题外话， 对于互联网应用的评价的数学模型的描述， 可以参考南洋理工大学（新加坡）的Devanshu Dhyani的综述《A Survey of Web Metrics》。
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.5859&rep=rep1&type=pdf
那么再来看一下互联网的现状和用户需求，说明调度的关注点。 关注点一：
互联网现状之一是互联网的网页数目336亿。 而抓取都是从种子页面（Seeds）开始发散抓取。 如何调度才能保证能够抓全这些网页，召回绝大部分的网页？ 关注点二：
互联网现状之二是30%的信息会在一个月内更新， 8%的信息在一周内更新。 如何调度才能保证网页库的更新变化能够跟上互联网的更新变化的节奏？ 关注点三：
草根需求之一是内容准确，傻瓜指引，民主生活，大侠体验，那么不同的互联网页面肯定会满足不同人的需求。 那么就需要按用户需求来对网页进行综合评价。 如何调度才能保证体现用户需求的页面被优先抓取呢？
也就是说，从“两个现状，一个需求”出发来评价爬虫调度，应该来说是符合互联网发展现状，贴近用户需求的， 是可以用来评价互联网产品—爬虫调度是否可用。
Yahoo 的Research Barcelona Lab实验室（http://labs.yahoo.com/Yahoo_Labs_Barcelona）的Ricardo
Baeza-Yates
和
B.
Barla
Cambazoglu
在
“
Tutorial
Yahoo
”
（http://www.lirmm.fr/~coletta/CaisePresentations/TutorialYAHOO.pdf）的介绍中，对Spider调度的质量三个标准（Quality Metrics）：
1． 覆盖面： Crawler发现和下载的互联网页面的百分比。
（Coverage: The percentage of the Web discovered or downloaded by the crawler.）
2． 时新性： 当时保存到本地的互联网原始页面是否更新变化的度量。
（Freshness: Measure of out-datedness of the local copy of a page relative to the page’s original copy on the Web）
3．页面价值：重要或者受欢迎的页面在库里面的比例。
（Page importance: Percentage of important or popular pages in the repository）
注：Ricardo Baeza-Yates是Yahoo的VP，欧洲和拉美的实验室的头， 信息检索算法和技术方向的ACM Fellow。 智利人， 加拿大名校滑铁卢大学的计算机博士。他最新的SIGIR 2009的文章“Quantifying Performance and Quality Gains in Distributed Web Search Engines. In SIGIR
2009”（http://research.yahoo.com/search/node/Quantifying）应该相当值得一读。
http://www.dcc.uchile.cl/~rbaeza/ http://research.yahoo.com/user/70
Spider覆盖面Coverage数据很大Internet变化很快调度Schedule时新性Freshness页面价值Page importance草根需求用户Analyzer网页库
图（3.3.1）最简单的调度质量控制模型
其中， 对于互联网更新和调度时新性之间的关系， 北京大学王继民在他的2003年的论文: 《国内综合性搜索引擎时新性的计算--计算机工程与应用》有很好的描述。
（http://sewm.pku.edu.cn/TianwangLiterature/Other/%5B%CD%F5%BC%CC%C3%F1,2003a%5D/032116.pdf）
从中可以看到，泊松（Poisson）过程能较好地描述Web页面变化的规律。泊松（Poisson）过程主要有3个特点:(1)事件随机发生;(2)事件之间相互独立;(3)以一个固定频率反复出现。并且根据泊松分布来估算“Web站点的半变化期”，即经过T时间后，一个Web站点所包含网页的一半发生变化1-exp（-λ*T）=0.5。 并且提到两点， 一）二个半月国外大部分后缀的站点基本都更新一半了。 二）国内网页的更新频率要比国外网页慢一些。 从这来看CNNIC的报告《统计报告-附表10》表明国内网页的半变化期为一个季度， 还是相当可信的。
对互联网更新模型有兴趣的读者可以仔细阅读印度马德拉斯理工学院博士Sanasam Ranbir
Singh在IJCAI07的论文“Estimating the Rate of Web Page Updates”。 （http://www.aaai.org/Papers/IJCAI/2007/IJCAI07-462.pdf）
前面有提到， 互联可以表现为网站之间的点击跳转和网站内的点击跳转。 同时， 也已经知道互联网的更新相当频繁。 那么必然会有一个网站更新了， 而链接到这个网站的点击链接失效（Link Rot）了。 如果你收藏了这个链接， 直接访问这个链接， 那么这个链接会无法访问， 成为死链（Dead Link / Broken Link）。 可以说链接失效（Link Rot）和死链接（Dead Link）现象是互联本质和更新特征所并生的东西。 如果一个网站的页面更新或者删除了， 那么对于指向这个网站页面的页面来说就是链接失效了（Link Rot）， 对于搜索引擎来说， 该页面已经无法访问了，是一个死链接（Dead Link）。 可以说互联网的更新就是互联网的成长过程中的新陈代谢。会产生一批新链接等待Spider去抓取， 同时会产生一批死链接。 已经抓取的部分必然会包含死链， 这就需要Spider重新抓取， 区分出死链并删除。
obsolete重新抓取Re-fetchstable已经抓取Fetchedfresh等待抓取To-fetch新链接New LinksInternet Status(t + T) 死链接Dead LinksInternet Status(t)图（3.3.2）互联网更新（T时间）的简单模型
其实， 除了链接彻底失效外， 还存在一种情况是， 链接依然能够访问， 但是页面的内容已经更新了， 变成了过期页面（Outdated/Obsolete）。 这样Spider获取互联网数据更新到本地网页库的增删改（Create-Delete-Update）就都有了， 再加上读取操作，就是数据存储CRUD操作了。 很多时候，重新抓取的Spider调度和抓取新链接的Spider调度会分开进行。 例如，Google就有传说中的Deepbot和Freshbot两类， Deepbot会深挖未抓取的链接，来扩大覆盖面（Coverage）。 而Freshbot会重新访问（Re-visit/Refresh）已经抓取过的链接， 分析已经抓取过的链接是否已经过期。
Spider覆盖面Coverage数据很大InternetFetch抓取变化很快时新性FreshnessRefresh刷新调度Schedule页面价值Page importance草根需求体验用户死链接Dead links同步Analyzer网页库
图（3.3.3）死链接和刷新简单模型
4. 最简单Spider调度策略模型
目前调度方面首推应该是Carlos Castillo的博士论文《EffectiveWeb Crawling》了， http://www.webir.org/resources/phd/Castillo_2004.pdf
Carlos Castillo毕业于智利大学（University of Chile）， 他的老板就是前面提到的YAHOO大牛&VP，智利人，Ricardo Baeza-Yates。
另外对于刷新的调度方面《搜索引擎页面刷新策略研究综述--计算机系统应用》的综述也可以看一下。写的一般吧， 没有把发展趋势调研清楚， 聊胜于无嘛。 http://www.c-s-a.org.cn/ch/reader/view_abstract.aspx?file_no=20090752&flag=1
以调度为名， 选链策略（Selecting/Ordering Strategies）是复杂的东东。 首先， 根据前面提到的抓取（Fetch）和刷新（Refresh）， 就可以分为抓取调度和刷新调度。 其次，根据利用经验数据反馈，还分为固定策略调度，和经验反馈策略调度。最后，在调度粒度（Granularity）， 就是考虑的目标点就会有地区差异，网站差异，网页差异和链接差异。 然后， 各个粒度层面上， 涉及面也会有差异， 例如地区层面， 有语言，编码等等。 网站层面， 有网站的架构，网站的知名度等等。 网页层面， 有页面的受欢迎程度， 页面的作用类型， 页面的内容相关性。 链接层面， 有链接模式分组， 链接关键词， 路径层次等等。 划分（Divide Standard） 是否页面已经抓取入库 是否利用经验数据反馈 否 抓取（Fetch） 固定策略 是 刷新（Refresh） 经验反馈策略 （Regular） 表（4.1）调度划分
粒度 层面 （Tracks） 地区 语言 （Linguistic） 编码 （Encoding） 网站 （Website） 架构 （Architecture） 访问量 （Traffic） 知名度 （Popularity） 页面数量和比例 （Quantity & Saturation） 表（4.2）调度粒度划分
（Historical/Empirical Feedback） 网页 （Page） 受欢迎度 （Popularity） 作用类型 （Utility） 内容相关性 （Relevance） 链接 （Link/URL） 模式分组 （Group Pattern） 链接关键词 （URL Keyword） 路径层次 （Path Depth） （Granularity） （Geographically） 前面说到， 一个好的调度, 首先符合互联网发展现状， 其次贴近用户需求的调度。 而用户（草根）需求主要体现在网页价值（Page Importance）。如何评价页面价值？直接的来看，从消费者的角度，如果已知用户需求，那么直接匹配用户需求的， 肯定最有价值的。 间接的来看，从生产者的角度，如果一个网站要做的好， 那么其本身除了内容对用户有价值的同时， 还必须方面用户获取信息，毕竟“酒好不怕巷子深”的产品稀缺的年代已经成为历史。 也就是说网站的架构， 链接的特征要便宜用户访问。
因此网站架构（Website Architecture），和链接路径层次（Link Path Depth）都会涉及到这个间接的评价。 另外也正是搜索引擎对这种间接的评价信任， 引入了搜索引擎优化（Search Engine Optimize），作弊（Search Engine Cheat）， 垃圾网站（Spam Website）等搜索引擎相关话题。
那么网站架构在知名搜索引擎看来， 对网页价值（Page Importance）有多大价值呢？ 这个不太好评估，不过据Google高级工程师马特.卡茨（Matt Cutts）建议，你要有好内容，还是要想办法方便别人找到。HI，This is the great content I has！ http://www.mattcutts.com/blog/
http://v.youku.com/v_show/id_XMTY3NTM2ODQ0.html {
依然内容为王还是其他（如结构）成为了主流依据？ “内容很必要啦，但不充分呀， 怎么着也要让人们能够找到你的内容吧。 不过你要没内容， 要做搜索引擎优化，很有难度！”~马特.卡茨。
Is content still the king or has something else (structure) taken over? \"Content is necessary. It's not always sufficient because people have to find out about your content. But if you don't have good content, it's a lot harder to do good search engine optimization for your site.\" ~ Matt Cutts. }
说起万维网的时候，一般把互联网看成一个网（Net）。而在描述网站架构的时候， 更多的时候，是看成一棵树。 网站的首页（Homepage/Index）被看成是树根， 链接页（Link）是树枝， 内容页（Content）是树叶。网页简单分为两种类型．一种是以链接（Link）为主的网页．例如一个含有大量链接的导航型网页。另一种是以内容（Content）为主的网页，即含有大量文本内容的普通网页。一种区分的简单而有效的方法是对某一网页进行解析．分析链接中的锚文本长度占网页中的文本总长度的比值。当比值超过一定阈值，则认定此网页为链接页：反之，内容页。 同时将连接主页和重要内容页的链接页称为主干。
首页链接页主干内容页网站万维网 图（2.3.4.1）网站树状结构简单模型 1）广度优先 （Breadth First）
a)调度粒度： 网站--架构。
b)调度类型： 抓取/刷新， 固定策略。
c)算法说明： 根据一般网站首页和浅层页面，用户更容易访问到，因此网站会将更多重要的内容放到浅层链接。广度优先就意味说优先抓取浅层链接， 所以是比较调度效果的基线（Baseline）， 如果效果比广度优先还差的调度算法就可以忽略啦。Carlos Castillo的博士论文《EffectiveWeb Crawling》的第五章里面说明，《Crawling the Infinite Web: Five Levels are Enough》， 无论是理论还是实践，从一个网站的开始页面， 最多点进3-5层， 就可以覆盖用户现实中会访问的页面的90%。 对重要站点90%的覆盖率可能还足， 但是对于一般站点而言是足够了，也就是说对一般站点而言，跟进（Follow）链接层数不需要超过5层。
d)算法描述： 以队列的方式， 将新发现的链接放到队列的末尾。
2）大站优先（Larger Site First）
a)调度粒度：网站--页面数量和比例 b)调度类型：抓取，固定策略。
c)算法说明：数据很大导致覆盖面是个重点和难点，在考虑覆盖面的时候，希望优先抓取页面量大的站点， 但是又想均衡各站的抓取，患寡亦患不均。 因此在评价站点的时候，如果按已抓取的站点全部链接，或者按已经发现的站点全部链接排序抓取， 会导致胜者全得（Winner-Take-All）的不均境地。 因此按已经发现，待抓取（Pending）的链接来评价。有论文说明单一大站优先的效果要比单一的广度优先策略要佳。
d)算法描述：统计所有站点的未抓取数量， 按从大到小排序，选择TOP N进行一轮抓取， 完成后在循环进入下一轮。
3）骨干链接优先（Skeleton Links）
a)调度粒度：网站--架构。 b)调度类型：抓取，固定策略。
c)算法说明：微软亚洲研究院的Yida Wang等人在SIGIR08年论文中描述利用网站骨干链接优先来抓取的方法， 并且表明此法在论坛等动态页面抓取中更能彰显其价值。《Exploring Traversal Strategy for Web Forum Crawling》
http://research.microsoft.com/pubs/131117/forumcrawl_sigir08.pdf
识别骨干链接后，可以优先抓取独一无二（Unique）的资源， 并且是站点最重要链接，能指向绝大部分价值内容页。
d)算法描述：分为随机抽样（Randon Sampling）， 站点导航构建（Sitemap Construction），遍历展开（Traversal Strategy Exploring）和抓取。
随机抽样： 采用双向队列（Double-ended Queue）， 结合广度优先和深度优先的遍历采样。 1000个页面已经足够。
站点导航构建： 采用根据网页布局来聚类和链接模式分组结合的方式，构建站点导航。 遍历展开：采用剪枝（Pruning）方法对站点导航，剪枝的标准是正反两条， 选入的话不会引起重复页面大量增加。 剪掉的话不会引起覆盖大幅下降。 抓取： 按遍历展开剪枝后的网站导航进行排序抓取。
4）泊松过程（Possion Process）
a)调度粒度：网站--架构。
b)调度类型：刷新，经验反馈策略。
c)算法说明：《基于泊松过程的爬虫调度策略分析--现代计算机》描述到， http://d.wanfangdata.com.cn/Periodical_xdjsj-xby200912018.aspx
利用网页更新的泊松模型，得出如果误差控制在10%以内， 这刷新频率要是更新频率的五倍。而初始更新频率由短期内， 根据网页是否为首页（Index），链接页（Link）和内容页（Content）预设更新频率和预定时间。之后根据学习到的更新频率设定刷新频率。
另外对于更新频率预估的方法， 除了上述基于一段时间内网页变化的次数的估算，还有基于一段时间内网页未变化的次数的估算。 《网页变化和增量搜集技术及研究进展—软件学报》 http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20060513 对这种性能更好的模型进行了描述。
d)算法描述：首先区分页面（Index/Link/Content）， 然后按F(Index)/F(Link)/F(Content)的频率调度刷新， 当累积更新次数到达阈值X， 开始进行按5*X/t的频率进行刷新调度。
5）导入链接计数 （Backlink Count）
a)调度粒度：页面—受欢迎度 b)调度类型：抓取/刷新， 固定策略
c)算法说明：如果一个页面很受欢迎的话， 那么会有很多其他页面中的链接（Hyperlink）指向该页面， 而那些链接就被称为导入链接或者入链（Backlink/Inlink）。 一般情况下， 导入链接数目愈大， 那么该页面就越受欢迎。 导入链接计数应该是页面受欢迎度计算方面的基线（Baseline），
如果效果比它还差的页面受欢迎度计算的算法可以忽略了。
d)算法描述：预设种子链接的导入链接为零。 当链接抓取之后， 将网页解析出来， 那么解析出来的链接Link的导入链接度（Backlink Count）加一。 将已经发现的链接， 按照导入链接度进行排序。 当进入下一轮抓取的调度抓取的时候， 优先选择导入链接度最高的页面。
6）批量Pagerank（Batch Pagerank）
a)调度粒度：页面—受欢迎度 b)调度类型：抓取/刷新， 固定策略
c)算法说明：导入链接计数的方法无法比较不同导入来源的价值，这时候人们想到了Pagerank算法， 但是由于每次抓取之后都会有链接的变化， 因此选择分批计算一部分链接的Pagerank， 然后从中选择优先调度。
d)算法描述：计算已有链接的Pagerank， 从总选择K个Pagerank高的链接进行调度。在调度完成后， 更新计算Pagerank， 进入下一轮的抓取。
7）部分Pagerank（Partial Pagerank）
a)调度粒度：页面—受欢迎度 b)调度类型：抓取/刷新， 固定策略
c)算法说明：部分Pagerank和批量Pagerank都是预估， 但是批量Pagerank的计算有些频繁， 代价过高。 部分Pagerank是根据Pagerank的思想， 直接将父层页面的Pagerank值按Pagerank的传递公式传给未抓取的子层页面。
d)算法描述：计算已有链接的Pagerank， 从总选择K个Pagerank高的链接进行调度。在调度完成后， 估算解析出来的链接的Pagerank， 等于父页面的Pagerank按导出度划分后的加权。
8）在线页面权重计算（Online Page Importance Computation）
a)调度粒度：页面—受欢迎度 b)调度类型：抓取/刷新， 固定策略
c)算法说明：前面提到导入链接计数的方法无法比较不同导入来源的价值。Pagerank可以大体解决这个问题。 但是Pagerank有个问题是初始化的随机性会导致收敛的时间不可控， 在在线（online）计算中，不方面跟踪和调控。 因此OPIC基于导入链接计数，但是引入了Pagerank的思想， 来部分解决导入来源价值评价的机制。
d)算法描述：首先给所有初始链接固定的现金（Cash）。 每轮抓取完成后， 现金会被出链所划分， 类似遗产划分。 在新一轮开始时， 拥有最多现金的未抓链接（Pending）优先进入下一轮抓取。 如此循环。
9）用户体验为中心抓取（User Centric Crawling）
a)调度粒度：页面—内容相关性 b)调度类型：刷新，经验反馈策略。
c)算法说明：Pandey and Olston提出了以用户体验为中心(user-centric)的刷新策略。《User-Centric Web Crawling》
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.6287&rep=rep1&type=pdf
统计一个页面刷新后对索引质量(主要是排序位置)带来影响的平均值，以及最后一次刷新的时间，来确定刷新的排序，目标是既要降低用户可以遇到的死链接数，优先刷新优质页面。结合用户访问习惯与查询历史，最先刷新与查询相关度高的页面，保证了用户的查询质量。同时结合最近刷新时间，防止页面长时间得不到刷新。
d)算法描述： 具体实现方法如下：首先将查询日志中多词（Phrase/Multi-Words Query）查询转换成多个单词（Single Word Query）查询， 选出有效查询词。 然后对于每个有效查询词，记录更新索引后，页面p 对于查询q 的排序位置r1 和r2。 用r1,r2来估算△Q(p)。 最后，将页面p 的各个历史△Q(p)值求平均得到δQ(p)。 那么刷新优先权值P(p,t)=δQ(p)*(t-LR(p,t))，其中LR(p,t)表示最后一次刷新时间。
这里描述的调度策略都是比较热门的单一模型， 而真正在商业搜索引擎调度的时候， 肯定会将各个调度粒度综合考虑。 而如何综合，这就不得而知了。
5. Spider的常见问题
调度反馈：压力上限控制（Maximum Stress Control），多IP压力均衡（Multi-IP Stress Balance），域名归一化（Domain Uniformization），爬虫陷阱处理（Spider-Trap Handle），泛域二级域名（Wildcard Subdomain/Infinite Domain Name Generators）。
调度循环抓取：分布式抓取框架（Distributed Crawling Architecture），HTML Parser，页面补全（ill-formed HTML Restore），JavaScript链接提取，URL归一化（URL Normalize），URI库存储方式（是否采用Hash还是顺序等等），重定向控制（Redirect Control），登陆页抓取（Login-protected Page Fetch）， 增量抓取（Incremental Crawler）。
调度质量控制：覆盖面（Coverage）， 时新性（Freshness），页面质量（Page Importance），死链接检查（Dead Link Check），垃圾站控制（Spam Control），链接农场惩罚（Link Farm Penalize）。
第四节 网页预处理简单模型
抓取到网页之后， 要完成一个所有信息检索（Information Retrieval）系统都要完成的工作， 数据清洗。 这个过程一般称为预处理（Pre-process）。 由于互联网的数据量太大， 也使得分布很广， 在对这种泛分布（Universal/Opening Distribution）的数据进行清洗（Clean）的时候， 一个基本的思想就是采用进行正反两方面奖惩（Pros and Cons）的评价标准。 这个会在整个网页预处理过程中体现的相当明显。
Site/Domain特征库反垃圾Anti-SpamIndexer网页数据清洗Web Page CleaningHTMLparser锚点Anchors链接关系Link-relation标题Tilte内容ContentContent extractor 特征Specials滤重De-duplicatePre-process切词Segmentation质量筛选Quality Selection页面分析page analyze 词典Dictionary网页库
图4.1 网页预处理简单模型
1. 质量筛选（Quality Selection）
前面我们讲到在进行“爬虫调度”的时候，有一条很重要的判断标准时页面价值（Page Importance）， 而页面的价值的判断是和用户的需求密切相关的。 所以在判断一个页面的价值的时候，如果在知道用户的需求的前提下， 会变得可行很多。 但是在爬虫调度的时候，尤其在预处理的时候， 无法得到根据确定的用户需求来进行判断。 这时候就需要有一个更通用（General）的标准来进行质量筛选（Quality Selection）。 结合前面的“网站树状结构简单模型”， 一个站点的页面可以分为首页，链接页（主干/非主干）， 内容页。 因此在进行质量筛选的时候要综合考虑属于不同架构类型的页面之间的区别。 并且在进行质量筛选的时候， 进行正反两方面奖惩（Pros and Cons）的评价标准， 而对于低价值或者价值不明确的地方， 尽量避免误处理。
表4.1.1 质量筛选的对象和直观判断
通用质量 直观判断 首页 链接页 垃圾站 死链接， 指向不合格内容页 内容页 无内容， 广告内容 信息丰富 网站内容 （Site Topics） 2-5层 >80% 不合格 价值低或 不明确 大站 链接丰富 网站字典 （Sites Dictionary） 网站地图 （Site Map） 2-4层 <20% 1层 价值高 优质数据说明 层数 比例 根据前面提到的， 通常遍历3-5层就可以遍历一个站点90%以上的页面， 那么链接页主要
集中在2-4层， 而内容主要集中在2-5层。 并且由比例来说，链接页的比例应该小于，或者远小于20%，而内容页的比例应该大于，或者远大于80%。用简单的3层的满N叉树模型来估算。链接页与内容页的比例大约是1：N， 那么一般情况下N>4， 那么链接页的比例应该小于 1/5=20%，而内容页的比例应该大于4/5=80%。
在这里如果你对低价值和不明确的这个类别的信息还没有什么概念的话。 有一种方法， 可以让你有进一步的认识。就是你在搜索引擎里面查询一个词的时候， 如果查询结果数小于搜索引擎能展现的结果数目的话。 那么排在最后的结果， 非常可能就是这种低价值或者价值不明确的页面。 例如， 你搜“史春奇”，查询结果的最后几个结果对应的页面， 基本就属于该搜索引擎认为的低价值，或者价值不明确的页面。 例如Google结果， Baidu结果。
站点评价（Site Evaluation）
站点（Website）是互联网的基本组织形式，基于之前的“网站树状结构简单模型”来说， 千
万不能只见树叶树枝， 不见树。 在站点评价方面目前还没有统一的标准。 因此各个搜索引擎采用的标准也不得而知。 但是可以见到的常用评价有以下的方面。 1)可信度/权威性（Credibility/ Authority）
首先， 要判断一个站点的类型。 有个很好的例子就是比较一下三个站点
www.whitehouse.gov， www.whitehouse.org 和 www.whitehouse.net 的权威性。虽然他
们有着同样的名称， 但是站点类型（Types）不一样， 一个是gov的政府网站，一个是组织机构，一个是net的大众网站。 显然政府网站的权威性要大，组织机构其次， 而大众网站再次。 如果你是Google， 别人搜whitehouse， 你会怎么排这三个站点呢？ （注：www.whitehouse.org 会自动跳转到 whitehouse.georgewbush.org）。
下面再说明一下， 一些典型域名的含义。
表4.1.2 典型域名
.gov/.edu /.mil .org com .net/.cn 政府、高等教育、军事 非盈利组织 商业公司 有钱就能买 其次， 要判断一个站点的作者。 网站是否会公示作者信息， 作者是否权威， 这些都是极好的判断标准。 一个站点作者可能是权威团体， 例如媒体或者报刊机构， 银行金融机构，等。 一个站点的作者可能是知名个人， 例如Lucene，Hadoop之父道哥（Doug Cutting）的个人站http://cutting.wordpress.com/。 那肯定是相当不一样的。
最后，是资源的权威性。 这个方面对于目前基于关键词的搜索引擎来说， 还不是很好判断。 等以后语义网（Semantic Web）大行其道之后，应该会有很大作为。 但是目前还是有一些简单的信息可以参考（是否给出服务Email，或者联系方式等等）。
2)知名度（Reputation）
一个站点的知名度，目前简单的判断方法是人气指数，权威导航和用户能记住，这三个方面来凸显的。 目前的人气指数，主要通过一些流量（Traffic）评测机构的指数（Index）来体现。 如果一个Alex前100名的网站，你都不给予高评价的话， 会让多少粉丝失望呀。 另外， 如果一些大部分导航（Navigation）都指向的站点， 你都不给予高度评价的话。 会让多少傻把式用户绝望呀。 最后， 如果用户都能够记得住网站名称， 并且反复的查找的话。 那么对应站点
的知名度也不能小瞧。
3)用户群（Audience）
一个网站的用户，主要用户是注册用户还是非注册用户。 是保密用户还是非保密用户。 是中文用户还是英文用户群。 例如同样搜索“苹果”，如果已知用户群， 那么对于小学低年级的用户， 那么可能给出水果是正确的， 而对于一个大学生来说，可能给出苹果公司相关的信息更为合适。
4)完整性（Completeness）
5)可访问性（Access/Workability）
6)准确性（Accuracy）
7)流通性（Currency）
流通性主要是指网站的创建时期， 更新周期， 最后更新时间等等。 前面提到， 互联网的“站点半变化期”是有一个大致的期望的。 如果更新周期不符合期望的话， 很难说这是一个高价值的站点。
8)稀缺性（Uniqueness）
9)真实性/客观性（Facticity/Objectivity）
百科（Encyclopaedia）一般被认为最真实客观的信息。在虚假信息充斥的互联网上， 由多人合著的百科，维基百科（Wikipedia）， 问答（Ask）类的内容会在真实性或者客观性上的意义更明显。 这也是为啥Wikipedia这么被Google宠爱的理由。
10)书写质量(Quality of writing)
语法拼写错误（Typographical errors/spelling mistakes）是影响理解的天敌。 一个不能被理解的网站，很难讲是高质量的站点。 因此像充斥着火星文的用户回复， 很难得到搜索引擎的高评价。
在抓取的时候提到， 一个站点的骨干链接是优先抓取的， 因为对网站的有价值内容起到导航（Navigability）的作用。 而这些骨干链接也是一个优秀网站的必备要素。 是增加可读性的良药。 因此一个好网站的必要条件也是， 有良好的导航地图， 有较好前后翻页的架构。
12)多媒体（Multimedia）
在互联网高度发展的今天， 多媒体的内容会比文本内容更受用户欢迎， 这也是为什么当11)可读性/架构（Browsability and layout）
资源的稀缺性正是资源的价值所在， 这里真是媒体所描述的独家的价值所在。 一个稀缺性好的站点的价值必然会被大幅度提高。
网站的准确性， 主要由网站自身的标题和说明是否能够准确匹配。 网站的访问速度是否可以保证正常阅读。 网站的颜色设置是否适合浏览。
一个网站是否完整是指一个用户在访问网站的时候能够体验到所有的内容。 例如， 一个网站的死链接的比例。是不是所有的链接用户可见并且可以点击。不存在“正在建设中”的地方。
有多媒体匹配的时候， Google总是会在第一页就给出结果的原因。
上面， 可以说是基本列出了评价一个站点的黄道十二宫（Sign of Zodiac）。 如果能够摸透这十二宫， 那么就能识别出一个站点的质量， 然后这个站点的首页的价值也会十分明确了。
表4.1.3 站点评价的黄道十二宫
1 可信度/权威性
2 知名3 用户4 完整5 可访性 6 准确7 流通8 稀缺9 真实/客观性 10 11 12 书写质可读性架构 多媒体 度 群 性 问性 性 性 性量 /链接/锚点内容（Link/Anchor Content）
说点题外话，西游记里的描述的真经（Canon）既然这么好， 为啥只有唐三藏才能搞定呢？
因为他有三个高徒和一匹好马护驾，路途艰险呀。 同样，如果路途艰险，就算你的站点内容是真经的话， 那么也只有圣僧(Saint)才能看的到了。 换个角度， 对于搜索引擎， 在我等凡人敢问路在何方的时候。 就要分析出来，首先哪些是路， 其次哪些是高质量的路（Authority and Hub Link）。 而在互联网的世界里， 路就是路标—锚点（Anchor）内容和穿越—链接这两部分。
在链接分析之前， 有必要将链接分析的三大原则， 先介绍一下。 如果链接Link_A指向Link_B， 则Link_A与Link_B相关。
如果存在链接Link_C同时指向Link_A和Link_B， 则Link_A与Link_B主题相关。
如果链接Link_A和Link_B在文档中的位置越近，本身URL含有相同的单词越多，则Link_A与Link_B的亲近性越高。 扩展一下，如果Anchor含有相同单词愈多， 则链接的单词亲近性也越高。
原则一，链接相关原则（Relevant Linkage Principle） [Kleinberg 1997] 原则二，主题一致原则（Topical Unity Principle） [Kessler 1963, Small 1973] 原则三，词亲近性原则（Lexical Affinity Principle） [Maarek et al. 1991]
Link_ALink_B链接相关原则（Relevant Linkage Principle）Link_ALink_CLink_B主题一致原则（Topical Unity Principle）Link_ALink_BHTML词亲近性原则（Lexical Affinity Principle）图4.1.1 链接分析的三大原则
区分链接页
前面已经提到， 判断是否为链接页最原始的方法，是比较锚点文本， 占页面文本内容的比例。 但是在真正实施的时候， 会遇到边缘广告， 网站页面边框等信息的干扰。
页面清洗（Page Clean）目前有两种情况， 一种叫站点模板（Site Templates）， 一种叫区域分解（Pagelets Analysis）。站点模板是为了找出并且排除无用页面信息， 而区域分解更倾向于挑选有意义的页面信息。 并且这两种方式基本都是基于HTML DOM TREE的分析的， 但是HTML是线性的(ordered linear space)， 而人们看到的页面是二维空间的（two-dimensional space）， 因此在添加视觉信息（例如CSS）后， 会形成视觉树（Visual Tree）。 再分析的基础上， 如果对满足词亲近性原则的链接对应的多个页面， 进行DOM Tree聚类， 极可能发现站点模板。 另一方面， 对同一个页面里面的链接集中的地方对词亲近性原则进行划分的话， 就是区域分解。 下面有一些对应的论文， 有兴趣的可以研究一下。
DOM Tree “Web Page Cleaning for Web Mining through Feature Weighting” Visual Tree “Entropy-Based Visual Tree Evaluation on Block Extraction”
Site Templates “Joint Optimization of Wrapper Generation and Template Detection” Site Templates “Site-Independent Template-Block Detection”
Site Templates “Page-level Template Detection via Isotonic Smoothing”
Pagelets “Improving Hypertext Data using Pagelets and Templates” Page Templates “Page-level Template Detection via Isotonic Smoothing”
Visual TreeDOM TreeCSSHTML图4.1.2 基于视觉树的网页分析简单模型
http://news.sina.com.cn/c/2010-07-29/012020778393.shtml站点模板Site Templateshttp://news.sina.com.cn/c/2010-07-29/163620785082.shtml
图4.1.3 站点模板（Site Templates）
区域分解Pagelets Analysis图4.1.4 区域分解（Pagelets Analysis）
区分重要链接页
根据“网站树状结构简单模型”， 链接页是树枝， 但是要区分哪些是重要树枝。 在站点
调度的时候讲到一个采用抽样剪枝的方法。 而链接分析中， 还有三个一般的方法可以被用来区分重要链接页， 简单列一下。
1， 基于图结构来计算链接页的重要性， 代表PageRank算法，Hilltop算法。 2， 基于查询相关性传递来计算链接页的重要性， 代表HITS算法， SALSA算法。 3， 基于信息量来计算链接页的重要性， 代表Entropy Analysis算法。
后面在排序（Ranking）的时候， 还会详细的介绍链接分析（Link Analysis）在Ranking中的重要作用。
PageRank算法
“The Anatomy of a Large-Scale HypertextualWeb Search Engine”
图4.1.5 PageRank算法示意图
Hilltop算法
“When Experts Agree: Using Non-Affiliated. Experts to Rank Popular Topics”
Krishna Bharat George Andrei Mihaila
图4.1.6 Hilltop算法作者
HITS算法
Hyperlink-Induced Topic Search --“Authoritative Sources in a Hyperlinked Environment”
图4.1.7 HITS算法示意图
SALSA算法
The Stochastic Approach for Link-Structure Analysis – “The Stochastic Approach for Link Structure Analysis (SALSA) and the TKC Effect”
图4.1.8 SALSA算法示意图
Entropy Analysis算法
“Entropy-Based Link Analysis for Mining Web Informative Structures” “Mining Web Informative Structures and Contents Based on Entropy Analysis”
图4.1.9 Entropy算法示意图
文本内容（Text Content）
其实当涉及到单个页面的文本内容的时候， 如果要对文本内容进行高质量评价的话， 就
需要了解文本内容所对应的领域。 但是还是有一些基本的方法可以进行一些文本内容有无价值的判断。 和站点评价类似，进行正反两方面奖惩（Pros and Cons）的评价标准。 一边打压无价值的页面，一边筛选高价值的页面。 同样文本内容的价值判断， 也需要页面清洗， 减少噪音（Noise）的影响。
区分有无价值
HTML是一种半结构化（Semi-structured）的数据组织方式，它带给人们的数据，按是否具1）无结构（Unstructured）： 纯文本(Plain Text) 等。
2）有结构（More structured）： 表格（Table）， 列表（List）等。
3）固定结构（Fixed Structured）： 多媒体（Multimedia data）， 文档（Document） 等。 在完成了页面清洗之后， 对于清洗后的保留的部分， 就可以进行有无价值的区分了。 可以先区分页面中上述三个方面的内容是否存在和数量， 然后区分内容的质量。
对于固定结构和有结构的部分， 如果能够识别出多媒体内容或者表格的话， 基本能够说明页面是有价值的。 但是对于无结构的纯文本， 最好还是判断文本的信息量。 文本的信息量一般可以通过文本长度， 语言文字的信息熵等来判断。 但是在判断前最好对一些网络提示进行过滤， 或者将这部分文字信息量贡献设零。
有结构来分：
有无价值？含有？含有？固定结构（Fixed Structured）多媒体（Multimedia data）含有？...有结构（More structured）表格（Table） 列表（List）...无结构（Unstructured）纯文本(Plain Text)信息量？...HTML图4.1.10 判断页面内容有无价值
区分是否高价值
前面提到要区分高价值页面，就必须对页面的内容进行识别，在第一章的“泛信息化”里
面就提到维基百科（Wikipedia）已经将内容分为14个主题（Topic）， 将信息类型分为10个类型， 1）论坛， 2）博客， 3）多媒体（音乐，视频，电视），4）源代码，5）P2P资源，6）Email，7）地图，8）价格，9）问答信息，10）自然语言。
根据主要通用搜索（Universal Search）引擎， Google，Baidu，Yahoo，Bing 和国内的主流垂直搜索（Vertical Search）引擎，酷讯（kooxoo）， 狗狗（gougou）， 奇虎（qihoo）， 再加上时下逐步起色的手机搜索。 至少要区分如下几大类内容。
表4.1.2 页面内容类型
类型 博客（Blog） 新闻（News） 图片（Image） 视频（Vedio） 论坛（Forum） 点对点资源(P2P) 手机（Wap）
直观质量说明 主题明确， 内容详尽。 时间新，符合出版的结构。 数量丰富， 图文并茂。 主题明确， 正确播放。 回复及时， 专业度高。 数量丰富， 正确下载。 （手机内容与上面对应） 2. 相似滤重（De-duplicate）
重复网页检测技术（Duplicate/Near-Duplicate Detection）来自于自然语言复制检测技术（Copy Detection / Plagiarism Detection / Duplicate Detection), 而复制检查技术， 最初是用来进行知识产权保护的， 用来防止大规模的程序/软件的拷贝/剽窃。 76年Ottenstein搞了个属性统计（Attribute Counting）的东西开始检测软件剽窃， 打开了Copy Detection的大门。 约20年后的1993年，乌迪.曼博Udi Manber在Arizona大学整出一个SIFF工具(Finding
Similar Files in a Large File System)， 首次提出近似指纹（Approximate Fingerprints）， 来在大规模的文本文件系统中寻找相似文件， 一下子撞开了自然语言复制检查的大门， 但是没有明确提出文本复制检查。 而Manber（http://manber.com/）也经历了Amason， Yahoo，而今已经是Google的VP， 负责搜索的核心技术。 如果说Manber你可能不熟悉， 但是《算法引论》(Introduction to Algorithms)你肯定知道， 而Manber就是该书的作者。
图4.2.1 Google VP, Udi Manber
95年，谢尔盖.布林Sergei Brin和加西亚-莫利纳Garcia-Molina在Stanford的数字图书馆工程中， 首次提出了文本复制检测机制COPS(copy protection system)系统与相应算法。 不久， Garcia-Molina和Shivakumar等人又提出了SCAM(Stanford copy analysis method)原型， SCAM借鉴了信息检索技术中的向量空间模型(Vector Space Model)， 基于词频统计的方法来度量文本相似性。 至此，万事具备， 就等搜索引擎的出现了。 而这里Garcia-Molina就是Google创始人谢尔盖·布林Sergei Brin和拉里·佩奇Larry Page的导师之一。
目前在相似滤重方面，我看到的比较好的材料， 大致列一下：
软件所博士，阿里巴巴工程师，张俊林。有兴趣读一下他的2004年的博士论文《基于语言模型的信息检索系统研究》 和他的CSDN博客。
http://blog.csdn.net/malefactor/
他的“搜索引擎重复网页发现技术分析”也相当不错。 http://blog.csdn.net/malefactor/archive/2006/06/09/782882.aspx
Google的Gurmeet Singh Manku的“Detecting Near Duplicates for Web Crawling”着重介绍了SimHash算法的好处。
http://infolab.stanford.edu/~manku/papers/07www-duplicates.ppt
Yahoo的P Govindarajulu也对相似滤重做了个很好的综述，“Duplicate and Near Duplicate Documents Detection: A Review”
http://www.eurojournals.com/ejsr_32_4_08.pdf
MIT的硕士Shreyes Seshasai在09 的毕业论文 “Efficient Near Duplicate Document Detection for Specialized Corpora” 也有个简单综述。 http://via.mit.edu/documents/Seshasai.pdf
另外北大李晓明的博士生黄连恩的博士毕业论文 “历史网页的持续收藏及其再访问的关键技术研究”的第五章也有所涉及。
http://sewm.pku.edu.cn/TianwangLiterature/PhdDissertation/%5BHuang,2008%5D/hle_thesis.pdf
基本流程(Process Introduction)
1, 重复的优缺点：
重复换句话说就是冗余， 冗余会带来资源的占用， 包括存储空间， 处理性能， 和处理时间。 除了资源占用方面的问题， 还会带来用户体验方面的问题，
当然， 事物总是有两面性的， 冗余不一定全部不好， 冗余会带来一些资源安全， 访问便捷的考虑。 例如用户访问了一个死链， 可以引导替换成重复的结果。
2, 重复的问题程度：
互联网的数据大约有20%以上的数据是重复或者相似， 在无线互联网上可能会有30%的数据是重复或者相似。
并且目前要做到Precision>90% && Recall > 90%， 这个基本上很难。 一般85%以上算是相当有效的了。
3, 分类情况：
1），按相似程度来分：
2），按处理时间来分：
4，基本处理流程：
1）. 内容主体识别（预处理部分）， 例如把一个网站里面公用模板的部分，如导航条，广告，版权，LOGO等噪声滤掉。这部分用的主要技术是网页净化（Page Clean/Noise Redection）。 类似技术在摘要提取（Abstarct Extraction）的时候，还会更有用的。
2）. 指纹/特征码（FingerPrint）提取（编码提取）， 这个是核心部分， 也是决定最后准确率和召回率的最关键的地方。
3）. 相似度（Resemblance）计算， 和步骤2几乎极其相关的一块， 又称距离（Distance）公式。 根据Fingerprint在特征空间的距离来表示两者相似程度。 一般在线（online）的方式， 进行两两比较来判断是否重复情况的话。 而后处理时，由于数据是海量的，一般无法进行两两比较的，所以相似度计算的机制会有所不同。
4）. 聚类（Cluster）， 目前海量数据聚类， 一般进行迭代（Iterative）算法或者基于图（Graph）的方法进行聚类。 其中有著名的 Union Find算法是基于图的。
5）. 选取代表（Delegates）， 从聚类数据里面选择一个作为聚类代表。
通常来说： Hashing=>Signatures=>Fingerprint; Vector=>Cosine=>Distance=>Resemblance;
聚类Cluster相似度计算Resemblance指纹提取FingerPrint选取代表Delegates滤重De-duplicate完全重复（exact duplicates）:主要由于镜像（mirroring）和盗版（plagiarism）等带来的问题。 近似重复（near duplicates）: 主要由于广告（Advertisements），页面框架（Template Frames），
和时间戳（timestamps）等非核心信息的差异导致的。
后处理（post process）: 存储之后，再进行滤重，然后释放重复存储。例如，建索引之前进 在线处理（inline process）: 实时识别，不进行重复存储。例如，线上抓取的时候判断相同
行相似滤重， 或者在用户检索的时候进行相似滤重。 url内容是否重复。
切词Segmentation词典DictionaryHTML页面清洗Page Clean图4.2.2 相似滤重简单流程模型
链接重复（Link-duplicate）
对于镜像站点， 如果将两个页面的外链接（outlinks）的路径（Path）映射到Hash列表， 如
果两个页面的外链对应的Hash表相同， 则两个页面为相似或者近似页面。 这种方法操作简单， 但是局限性太大。
另外对于搜索引擎优化（SEO）或者部分垃圾站（SPAM）站点， 会将站点的链接组合成
一个有向图， 再根据有向图， 分析图的主要结构，保留核心节点， 得到一个全真子图（proper subgraph）。 最后根据图相似性算法来比较两个站点的相似性。
内容重复（Content-duplicate）
目前网页滤重已经有积累了一些经典的特征码（FingerPrint）里程碑（Milestones）了： 1, 校验和算法（CheckSum）: Checks MD5 & SHA & CRCs 2, 最长公共子序列（Longest Common Subsequence）：
3, Shingling算法（Broder 1997）: Jaccard index of 文档中连续的顺序的特征词（tokens） 4, SimHash算法（Charikar 2002/ Gurmeet Singh Manku 2007WWW）:
5, I Match算法 （Chowdhury等人 2002）:用IDF进行tokens选择， 然后通过升序有序树来进行tokens排序， 将排序后tokens相加计算Digest。 再利用词典保存Digest， 如果词典有冲突， 标明冲突的文档重复。
6, Spotsig算法（Martin Theobald等人 2008）: 用大众词（Common Words）来选择Spot Words。 例如“的”、“这个”、“那个”之后的词。 然后计算Jaccard相似度。
7, Bloom Filter算法（ Bloom 1970 / Chazelle 2004）:选择K个Hash 函数， 和一个m的数组， Hash（x，k）=>m，0<=m<=M-1的位置标记为1。重复标记忽略。
8, Chunk算法（HP LAB 2005/2009）: 用窗口（Window）将文档分为长度不等的Chunk， 从每个Chunk提取一个特征， 从而得到一个文档的一组特征。
内容重复是目前采用最多的页面重复的判断方式， 目前一般采用特征码（Fingerprint）的
算法来对内容进行特征标记， 然后判断特征码是否一致， 从而判断两个页面的内容是否相似。
1. 校验和算法（CheckSum）
用来检测完全相似的页面的滤重， 此类页面， 往往是因为URL归一化没有做好导致的。 因此
校验和算法，容易识别出完全相同页面， 可以为URL归一化的改进提供依据。
2. 最长公共子序列（Longest Common Subsequence）
“一种基于LCS 的相似网页检测算法”
http://sewm.pku.edu.cn/TianwangLiterature/Report/NCIS_TR_2007012.pdf
是基于特征的文本相似度计算的一种类型。 一般文本特征分成字（Character），词（Phrase）， 句子（Statement） 三个方面的特征。 常用的特征有：
1)热门词汇（Top Keyword Feature）特征，
2) 特殊句子（Special Statement）特征[例如首句子， 尾句子， 最长句子]，
3) 查询词（Query Phrase）特征[定义一些查询词， 例如：总之， 一般来说， 结论如下， 调研表明， 实验说明， 等， 将这次词紧跟着的词作为特征]， 4) 最长公共子序列
经 典的求解LCS的算法是动态规划算法， 是一个O（N*N）的算法。 Myers提出了O（ND）的算法， N是两个比较的句子的长度之和（Length（A） + Length（B））， D是这两个句子之间的最小编辑距离（LevenShtein Distance）。
求解Sentence A和Sentence B之间 LCS的问题和求解由Sentence A转变为Sentence B的最短编辑距离（SES， Shortest Edit Script）。 而SES的求解可以用编辑图（Edit Graph）来完成， 公共最长字串等价于求编辑图的最大斜边数。 具体细节有兴趣的可以参考如下论文 An O(ND) Difference Algorithm and Its Variations ∗
类似之前的Tonimoto距离， R(A,B) = |LCS| / (|A| + |B| - |LCS|)。
不过LCS有个问题， 它是基于两两比较来实现的， 因此需要做预先的粗分类， 之后再进行。 优点是能够兼容位置信息， 并且有较高的准确率。
3. Shingling算法
（Broder 1997）Jaccard index of 文档中连续的顺序的特征词（tokens） Syntactic Clustering of the Web
www.hpl.hp.com/techreports/Compaq-DEC/SRC-TN-1997-015.pdf
4. SimHash算法
Google --“Detecting Near-Duplicates for Web Crawling”
http://infolab.stanford.edu/~manku/papers/07www-duplicates.ppt
5. I Match算法
“ Improved Robustness of Signature-Based Near-Replica. Detection via Lexicon Randomization” www.ir.iit.edu/~abdur/publications/470-kolcz.pdf
6. Spotsig算法
“SpotSigs: Robust and Efficient Near Duplicate Detection in. Large Web Collections.” http://ilpubs.stanford.edu:8090/831/1/2008-14.pdf
7. BloomFilter算法
“Using Bloom Filters to Refine Web Search Results” www.cs.utexas.edu/users/dahlin/papers/webdb-167.pdf
8. Chunk算法
A Framework for Analyzing and Improving Content-BasedChunking Algorithms http://www.hpl.hp.com/techreports/2005/HPL-2005-30R1.pdf
“Extreme Binning: Scalable, Parallel Deduplication for Chunk-based File Backup” www.hpl.hp.com/personal/Mark_Lillibridge/Extreme/final.pdf
相似距离（Resemblance Distance）
一般在计算机领域会遇到的距离度量，大致不会超过以下六大类：欧氏（Euclidean）距离, 曼
哈顿（Manhattan）距离,契比雪夫（Chebyshev）距离, 雅卡尔（Jaccard）系数, 夹角（Cosine）余弦,相关系数（Correlation Coefficient）。 在网页滤重用到的相似距离主要由以下6种。 1. 余弦距离（Cosine Similarity） 2. 雅卡尔系数（Jaccard Index） 3. Tonimoto系数（Index）
4. 皮尔逊联列系数（Pearson Correlation Coefficient） 5. SimRank相似
6. 编辑距离（Levenshtein distance）
1. 余弦距离（Cosine Similarity）.
当说到文本的余弦距离， 那么词频和倒排文档频率（TF-IDF）权重模型是首选， 而谈到TF-IDF， 那么向量空间模型（Vector Space Model）就是前提条件。（When comes to Cosine Similarity, TF-IDF weigting model is always the first choice. As TF-IDF weigting model is mentioned, the Vector Space Model is a must.） 向量空间模型（Vector Space Model） 模型其实很简单。 直观来讲， VSM是将每个文档看成一个向量。 所有的文档在一起构成一个向量空间。 很显然这个空间是一个有限的高维的空间。 空间的维度由什么来决定呢？ 这个就关系到分词（Word Segmentation）了， 一般按分词的词典为切分维度。 中文一般以词组为单位， 英文一般以单词为单位。 切词是个很高深的话题， 最简单的是最大正向匹配的方式进行切词。 还需要认真学习。
例如： 有个词典： Dictionary： 1. 刘德华 2. 新闻 3. 写 4. 博客 5. 周末 6 正在 7看 Stop Words： 1.的 2.吧
Document A： 刘德华的博客， 刘德华正在看 Document B： 正在写博客的刘德华 Document C： 看新闻吧
还有个东东叫停用词（Stop Words）， 又叫过滤词， 一般是高频词的助词， 语气词等等，加上标点符号等等。 最多就1000个的样子吧。
维度 1. 刘德华 2. 新闻 A B C ** * * 3. 写 4. 博客 5. 周末 6 正在 7看
最直观的表示方式如下： Document A ： 1 4 1 6 7 Document B ： 1 3 4 6 Document C ： 2 7
* * * * * * * 这有个问题， Document A和Document C的维度不一样， 这么计算呢？于是就表示成： 1 2 3 4 5 6 7 Document A ： 2 0 0 1 0 1 1 Document B ： 1 0 1 1 0 1 0 Document C ： 0 1 0 0 0 0 1
开始大家以为这样比较完美了， 后来人们发现还有个问题， 如果一个词大家都出现的区分， 那么它的权重应该降低， 而只有出现的少的词才有区分度。 这里有一点信息量的概念了。
那么这个权重怎么调整呢？
1983 年Salton和McGill提出了TF-IDF技术， Term Frequency-Inverse Document Frequency, 来解决了这个问题。 Term Frequency 就是词频， 例如 Document A ： 2 0 0 1 0 1 1 中的2，刘德华出现了两次。 Inverse Document Frequency就是用来进行调权的。 Inverse表示取倒数， 那么Document Frequency是怎么计算的呢？ 1 2 3 4 5 6 7 Document Frequency： 2 1 1 2 0 2 1
那么TF-IDF等于多少呢？ 那么“刘德华”在“文档A”里面的TF-IDF是不是就是 2/2 = 1呢 1 ）首先TF， 是Term Frequency， 这里是一个归一化的词频：从上面列出的矩阵可以看成， 一个词频，由两个维度来定位， 一个是词的维度i， 一个是文档的维度j，决定了TF（i,j）。 例如第i个词， 在第j个文档里面的出现次数为词计数[Count(i,j)]。刘德华是第1个词， Document A是第A个文档， TF(1,A) = Count(i,j) / Total = Count(i,j) / ∑i∑j Count(i,j)。 Total是多少了， 是所有词频总和。 TF(1,A) = Count(1,A) / ∑i∑j Count(i,j) = 2 / 11。
2） 其次是IDF, 是 Inverse Document Frequency， 首先如果Document Frequency是如何计数呢? 从上面可以看出Document Frequency由一个维度决定， 词的维度i，决定了 DF(i) 。例如第i个词， 出现该词的文档个数[Number(i)]。 DF(i) = Number(i) / ∑i Number(i)。 那么 Inverse Document Frequency IDF(i) = ∑i Number(i) / Number(i)。 “刘德华是第1个词, 那么IDF(1) = 9 / 3 = 3;
3）那么TF-IDF 是不是就是 TF（i,j） * IDF(i) = Count(i,j) / ∑i∑j Count(i,j) * ∑i Number(i) / Number(i) 呢？ 答案是否定的。 为什么呢？ 直观上理解TF（i,j）是最早确定单词i在文档j中价值的核心， IDF(i)是对该单词i分布的一种估计， 做参数调整。直观上而言，log形式是经常用来做参数的一种方式。 （log的核心是化乘法为加法， 化除法为减法。） TF-IDF（i,j）= Count(i,j) / ∑i∑j Count(i,j) * log ( ∑i Number(i) / Number(i) ) ， 为了避免出现除零的情况TF-IDF（i,j）= Count(i,j) / ∑i∑j Count(i,j) * log ( ∑i Number(i) / (1 + Number(i)) )
TF-IDF（i,j）= Count(i,j) / ∑i∑j Count(i,j) * log ( ∑i Number(i) / (1 + Number(i)) )。 那么“刘德华”在“文档A”里面的TF-IDF（1,A）= 2 / 11 * log（9 / （3+1）） = 0.06。
那么TF-IDF（i,j）的证明和解释并非如此简单， 要用到信息论的互信息（Mutual Information）和 交叉熵KL距离（Kullback-Leibler Divergence）。 不过数学太烂， 一时也说不清楚。
既然有了TF-IDF， 那么如何计算Document A 和Document B的Cosine Similarity？ TF-IDF： (1, *), (2, *), (3, *), (4, *), (5, *), (6, *), (7, *) Document A ： 0.06 0 0 ？ 0 ？ ？ Document B ： ? 0 ? ? 0 ? 0 Document C ：
这下我们有了相同维度的向量来表示Document A， Document B， 并且没有元素都是[0~1]之间的一个数值。 那么我们就可以很容易地利用向量公司来计算向量夹角的Cos（θ） = A·B / (||A|| *||B||) = A·B / ((A · A) *( B · B)) )
有兴趣的可以看一下《数学之美， 吴军，Google 研究员》
2. 雅卡尔系数（Jaccard Index）
如果说Cosine Similarity是将文档看成两个向量， 那么Jaccard Index是将文档看成两个集合。 Jaccard Coefficient来表示两个集合A, B的相似度 A, B 交集的模， 与 A,B并集的模的比值。 Jaccard Coefficient = ||A∩B || / ||A∪B|| 。
那么Jaccard Distance = 1 - Jaccard Coefficient = (||A∪B|| - ||A∩B ||) / ||A∪B||。 Document A ： 1 4 1 6 7 Document B ： 1 3 4 6
Jaccard Distance = 1 - || (1, 4, 6) || / || (1, 3, 4, 6, 7) || = 1 - 3 / 5 = 0.4
3. Tonimoto Index
如果综合1. Cosine Similarity. 2. Jaccard Index的集合思想， 又会得到Tonimoto Index 向量表示： T(A, B) = A·B / (A·A + B·B - A·B)
集合表示： T(A, B) = ||A∩B || / ( ||A|| + ||B|| - ||A∩B || )
还有一个叫Dice Coefficient 满足如下 向量表示： D(A, B) = 2 A·B / (A·A + B·B) 集合表示： D(A, B) = 2 ||A∩B || / ||A|| + ||B||
D = 2J / (1 + J) and J = D / (2 − D)
4. 皮尔逊积差系数（Pearson Correlation Coeafficient）.
p(A, B) = cov (A, B) / (σAσB) = E(A-υA)E(B-υB) / (σAσB) E是数学期望，cov表示协方差。
5. SimRank
是一种间接比较的方式， 认为相似的东西是这样的， 与他们有关系的对象也是相似的。 如果将关系表示为有向图的模式， R0(a,b) = (a == b);
Ri(a, b) = C∑i∑jR(Ii(a), Ij(b)) / (||I(a)|| * ||I(b)|| ) I(x) : x节点的入读节点集合 in-neighbors of x。
6. 编辑距离（Levenshtein distance ）
Levenshtein distance 又称 Edit distance， 是将一个字符串转化成另外一个字符串所需要的最小编辑次数。
一般由动态规划来进行计算。 Document A ： 1 4 1 6 7 Document B ： 1 3 4 6 Levenshtein distance = 3
3. 反垃圾（Anti-spam）
Spam解释有两种， 一种叫罐头猪肉， 另外就是我们关心的垃圾信息。Spam是最早伴随中电子邮件来露出 尖尖角， 到了搜索引擎时代变得扑面而来， 想而今已经是WEB2.0，电子商务，游戏和社交盛行的新世界， Spam竟然发展到了防不胜防的境界。 张俊林的博客上面有《搜索引擎anti-spam系统设计指南》 http://blog.csdn.net/malefactor/archive/2006/05/30/762895.aspx
斯坦福大学（Stanford University）计算机系的Zolt´an Gy¨ongyi和他的导师Hector Garcia-Molina http://infolab.stanford.edu/~zoltan/
http://infolab.stanford.edu/people/hector.html
的“Web Spam Taxonomy”是这方面很好的一个介绍。其中对Spam针对搜索引擎采用的两大机制作了很好的概述。 分别是“激励（Boosting）机制”和“隐藏（Hiding）机制”。 激励机制：
内容方面的做法有：垃圾词的反复（repetition），倾销(dumping)，编织（weaving），缝合（stiching）。 链接方面的做法有：下诱饵（hony Pot），进目录（directory），广招贴（posting），换链接（exchange），开农场（farm）， 抄目录（dir.clone）。
隐藏机制：
隐身术，障眼法，重定向。
《Web Spam Taxonomy》引图一，激励（Boosting）机制
《Web Spam Taxonomy》引图二，隐藏（Hiding）机制
链接垃圾（Link-spam）
概述中提到了链接Spam会用到激励和隐藏两种机制来实现作弊（cheat），这里换个角度来，为了制造垃圾， 聪明人用尽资源， 自己的， 认识的， 不是认识的资源纷纷用上。 聪明人想
尽方法， 坑蒙拐骗统统使出。 看你搜索引擎如何应对。
表：常见链接垃圾的类型
类别 添加出链（outlinks）： 添加入链（inlinks）： 现象 剽窃导航页（Hub pages） 垃圾链接农场（Spam farm） 链接互换联盟（In-link exchange） 博客/维基张贴（Links posting / Splogging） 渗入网页目录（Web directory） DNS障眼法（DNS cloaking） 过期域名收购（Expired domains purchase） 生成欺骗诱饵（Honey pot）
垃圾斗士也发明了很多反垃圾（Anti-Spam）算法，常用的垃圾链接分析的算法： 1, Spam HITS 2, Spam PageRank 3, TrustRank (VLDB2004) 4, BadRank (WWW2005)
5, SpamRank (WWW2005, workshop) 6, ParentRank (WWW2005)
装好人 来自自己的站点 来自同族的站点 来自陌生的站点 坑 蒙 拐 骗 解说 1. Spam HITS算法
“Improvements of HITS algorithms for spam links”
2. Spam PageRank算法
Microsoft --“Robust PageRank and Locally Computable Spam Detection Features”
3. TrustRank算法
Yahoo -- “Combating Web Spam with TrustRank” “Propagating Trust and Distrust to Demote Web Spam”
4. BadRank算法
Google -- “PR0 -Google's PageRank 0 penalty.” “Generalized BadRank with Graduated Trust”
5. SpamRank算法
“SpamRank – Fully Automatic Link Spam Detection”
6. ParentRank算法
“Identifying link farm spam pages”
内容垃圾（Content-Spam）
网页上的内容是总的来说还是以文本为主， 而那些有作者认证书写的文章基本上要满足两个基本的定律， 一个叫做齐夫定律（Zipf’s law）， 另外一个是Heaps定律（Heaps' law）。 而这两个定律是从不同的方面去描述文本和构成文本的语义单元（词）之间的统计规律的。 但是仅仅靠一些统计规律是难以大面积召回内容垃圾的， 还需要进行一些综合的判断。
1. 齐夫定律（Zipf’s law）
每个数据集合所用的查询词要考虑词典以及词在这个数据集的分布情况。 每个数据集的词频都符合齐夫定律（Zipf’s law）。齐夫定律是由哈佛大学教授G．K．Zipf在1935年对文献词频研究的结论：一篇较长的文章中每个词出现的频次从高到低进行递减排列，其数量关系特征呈双曲线分布。 既然满足双曲线分布， 那么最简单的齐夫定律的例子是“1/f”函数，给出一组齐夫分布的频率，按照从最常见到非常见排列，第二常见的频率是最常见频率的出现次数的1/2，第三常见的频率是最常见的频率的1/3，第n常见的频率是最常见频率出现次数的1/n。
图4.3.1 哈佛大学教授齐夫（G．K．Zipf）
另外一个类似的现象，就是本福德定律（Simon Newcomb）：在b进位制中，以数n起头的数出现的机率为logb(n + 1) − logb(n)。本福特定律不但适用于个位数字，连多位的数也可用。这样计算到1出现的机率最大，接近三分之一，2为17.6%，3为12.5%，依次递减，9出现的机率是4.6%。目前本福德定律已经用在审计假账中。
图4.3.2 本福德定律（Simon Newcomb）
同样齐夫定律也可以用来审计文章的内容是否作弊， 但是目前Spam作弊的手段的高超， 仅仅简单的审计，大部分的Spam是难以召回的。
2. Heaps定律（Heaps' law）
随着文本内容的增长，出现的词的数量也会同步增长， 但是这个增长的比例是如何的呢？ Heaps定律（Heaps' law）告诉我们，词表的增长大约与文本的的方根的增长成正比的样子。VR(n)
= KnβK≈[10~100],β≈[0.4~0.6]。 因此， 如果一个站点的文本和单词的这种增长关系发生突变，
那么是内容Spam的概率也会比较高。
3. 综合分析
需要对网页的标题（Title）， 锚点（Anchor），元数据（Meta）等容易生成Spam的项，进
行专门的统计。 除此之外， 5%的最常用词的归一化分布， 30%的最稀少的词的归一化分布。 在齐夫定律基础上分析分布情况。
无意义的高频词有意义的区分度最高无意义的低频词按词频降序排列图4.3.2 不同词频分布
最后需要将多个方面综合起来，决策判断， 可能由需要用到决策树算法。
Microsoft -- “Detecting Spam Web Pages through Content Analysis” http://research.microsoft.com/apps/pubs/default.aspx?id=65140
第五节 索引存储简单模型
第六节 检索框架简单模型
有句话叫做，一个成功的搜索引擎，给用户提供查询结果的带宽流量要远大于她的爬虫下载网页的流量。 “A successful search engine requires more bandwidth to upload query result pages than its crawler needs to download pages”
李绍华，高文宇的综述“搜索引擎页面排序算法研究综述” http://www.seo.com.cn/seopdf/搜索引擎页面排序算法研究综述.pdf 有对算法比较详细的介绍。
信息检索评价指标
信息检索评测指标直接关系到参评系统的最终评价，指标不合理会导致对系统的评价也不合理，因此规范化的评测会议对于评价指标的选择都是很慎重的。
早期常用的评测指标包括准确率（Precision）、召回率（Recall）、F1值等，其意义如下: 召回率=系统检索到的相关文件数/相关文件总数 准确率=系统检索到的相关文件数/系统返回文件总数
显而易见，召回率考察系统找全答案的能力，而准确率考察系统找准答案的能力，两者相辅相成，从两个不同侧面较为全 面地反映了系统性能。F1值是一个把准确率和召回率结合起来的指标。考虑到某些情况下不同系统的准确率和召回率互有高低，不便于直接比较，而使用F1值就 可以更直观地对系统性能进行排序。
随着测试集规模的扩大以及人们对评测结果理解的深入，更准确反映系统性能的新评价指标逐渐出现，包括:
1. 平均准确率（Mean Average Precision，即MAP）: 单个主题的MAP是每篇相关文档检索后的准确率的平均值。主题集合的MAP是每个主题的MAP的平均值。MAP是反映系统在全部相关文档上性能的单值指标。
2. R-Precision: 单个主题的R-Precision是检索出R篇文档时的准确率。其中R是测试集中与主题相关的文档的数目。主题集合的R-Precision是每个主题的R-Precision的平均值。
3. P@10: P@10是系统对于该主题返回的前10个结果的准确率。考虑到用户在查看搜索引擎结果时，往往希望在第一个页面（通常为10个结果）就找到自己所需的信 息，因此设置了这样一个拟人化的指标，P@10常常能比较有效地反映系统在真实应用环境下所表现的性能。
第三章 推广模型--商家需求客户
http://www.sales2marketing2.com/PracticalInternetMarketing_VincentCheng.ppt
Online Marketing Channels are:
1. Search Engine Optimization and Marketing 2. (Google, Yahoo, MSN) 3. Social Network Sites
4. (MySpace, Friendster, YouTube)
5. Social BookMarking (De.li.cio.us, BlogMarks) 6. Email Marketing 7. Viral Marketing 8. Online Press Release 9. Blogs
10. Link Building – Reciprocal and One Way Paid Links 11. Affiliate Marketing 12. E-Zine / Articles Marketing
13. Paid by Impression/Click Banner Advertising 14. Vertical Search Engines 15. Relevant / Vertical Directories 16. Video Advertising 17. Relevant / Vertical Forums 18. RSS – Really Simple Syndication 19. PodCasting / Video Casting 20. Chat and Messengers 21. EBay / Auction Sites 22. B2B – Business Networks 23. Mobile Marketing
第四章 未来
搜索引擎是会死掉的。
经过了多年的发展之后,现在的搜索引擎功能越来越强大,提供的服务也越来越全面据。研究者统计, 目前互联网上的搜索引擎已达数千种, 仅中文搜索引擎就达上百种，可谓是百花争艳。然而随着WWW信息的急剧增加，目前的搜索引擎存在界面不够友好、响应时间长、死链接过多、结果中重复信息及 不相关信息过多等问题，难以满足人们的各种信息需求，搜索引擎将向智能化、个性化、精确化、专业化、交叉语言检索、多媒体检索等适应不同用户需求的方向发 展。
因篇幅问题不能全部显示，请点此查看更多更全内容