商用搜索引擎的架构与原理.pdf

1主讲：于俊清搜索引擎技术基础联系方式电话：[phone]电子邮件：yjqingQQ 号 码:735091398办 公 室：网络与计算中心（南六楼）209室网址：课程资源下载课程资源下载课程资源下载技术革命伴随着大国的崛起第一个殖民大国葡萄牙美洲大陆的主宰西班牙帝国金融资本家荷兰从“快乐的英格兰”到“日不落帝国”路上强权法兰西夹缝中的德意志东方列强日本好霸争强的俄罗斯从蚂蚁到大象的美国正在崛起中中国2技术革命伴随着大国的崛起技术变革航海技术葡萄牙、西班牙、荷兰等技术变革第一次工业革命 18世纪60年代19世纪40年代 18世纪60年代，瓦特改进的蒸汽机的发明技术革命第二次工业革命 19世纪70年代-20世纪初 电力的广泛应用（即电气时代)、内燃机技术变革信息革命 1946年，第一台电子计算机ENIAC 1969年，第一个计算机网络APPANET华尔街3硅谷风云人物风云人物风云人物风云人物360-周鸿祎小米-雷军风云人物京东商城-刘强东苏宁易购-凌国胜4搜索应用根叔搜索应用武汉 广州 高铁搜索应用北京青年5搜索应用武汉天气搜索应用武汉哪里可以找到女朋友搜索应用根叔6搜索应用Search Engine Optimization内事找百度，外事问谷歌2011.12-2012.6 各类网络应用使用率何谓“搜索引擎”？搜索引擎(Search Engine)根据一定的策略、运用特定的计算机程序搜集互联网上的信息 在对信息进行组织和处理后，为用户提供检索服务的系统搜索引擎的核心价值 让人们最便捷最便捷地获取信息，找到所求课程简介专业选修课，交叉学科的新兴课程32学时，2学分考试方式 考试 平时作业7基本要求掌握搜索引擎的工作原理熟悉搜索引擎的使用方法基本掌握搜索引擎的设计方法课程内容商用搜索擎架构与原理（6学时）1移动搜索（2学时）6搜索引擎优化（2学时）5利用开源工具构建小型搜索引擎（1学时）7商务智能与搜索引擎推广（4学时）4社区与垂直搜索（2学时）2多媒体搜索（4学时）3搜索引擎的未来（1学时）8参考教材教材 卢亮，张博文.搜索引擎原理、实践及应用，电子工业出版社，2007参考资料 W.Bruce Croft.Search Engines,机械工业出版社，2009 李晓明，闫宏飞，王继民著.搜索引擎-原理、技术与系统,科学出版社,2005 邱哲，符滔滔.开发自己的搜索引擎，人民邮电出版社，2007扩展阅读主讲：于俊清第一讲：搜索引擎架构与原理内容提要搜索引擎的前世今生商用搜索引擎结构与组成搜索引擎质量评估搜索引擎排序策略分布式搜索引擎8早期搜索引擎Archie1990字符方式人工收录检索文件第一个基于互联网的检索服务Gopher1991图形方式人工收录检索文件图形方式，超文本Wanderer/Wandex1993图形方式自动收录检索网站第一个搜索引擎Yahoo!1994图形方式半自动检索网站著名门户搜索引擎战国时代搜索引擎名称成立时间 终止时间收购方特色WebCrawler19941996Excite第一个全文字符检索Excite19942001InfoSpace综合门户Lycos19942000Fast自动摘要/索 引 量Infoseek19942000Inktomi基本语法括号Yahoo!1994技术为王搜索引擎名称成立时间 终止时间 收购方特色AltaVista19952003Overture速度Inktomi19962002Yahoo!综合Fast19972003Overture全/高级功能Overture19982003/4Yahoo!竞价排名/附费Google1998pagerank百度2000全球最大的中文搜索引擎中文搜索引擎名称网址类别/主要特点百度搜索引擎、免费收录网站/竞价广告新浪分类目录/付费登录搜狐分类目录/付费登录网易分类目录/付费登录3721 实名搜索/地址栏搜索中国搜索（慧聪）行业搜索8848 在线购物搜索引擎TOM搜索搜索引擎/付费登录中文G搜索引擎、免费收录网站/关键词自助广告一搜雅虎中国提供的中文搜索引擎，免费登录搜索引擎/竞价广告搜狗搜狐提供的独立搜索引擎，免费登录搜索引擎/竞价广告Yahoo!中国分类目录/免费登录网站Lycos中国分类目录/付费登录英文搜索引擎名称网址类别/主要特点G搜索引擎/关键词广告Overture(Yahoo!)搜索引擎/PPC分类目录MSN S搜索引擎AOL S搜索引擎/分类目录LookS分类目录/PPCAsk J分类目录AltaV搜索引擎Inktomiwww.I搜索引擎InfoS黄页/白页登录与搜索L搜索引擎Find W搜索引擎/PPCEspotting M搜索引擎（欧洲最大）A分类目录E搜索引擎T搜索引擎Dmozwww.dmoz.org分类目录/免费B在线购物搜索引擎搜索引擎的发展趋势9世界搜索霸主-Google的故事创始人 拉里佩奇（Larry Page）谢盖尔布林（Segey Brin）PageRank横空出世 1995年开始车库起家 1998.9.7：休学$100万天使基金创办Google Page-CEO,Brin总裁 地点：加州废旧车库世界搜索霸主-Google的故事把握搜索市场机遇 定位：为用户提供便捷的互联网搜索服务，帮助使用者从互联网的海量信息中找到自己需要的东西 1999年度最好的网络技术 1999年春天，搬到帕洛阿尔托中心的大学街世界搜索霸主-Google的故事顺利向成长阶段过渡 1999.6.7：获风投2500万美元 迅速扩张：8人-200人，搜索次数50万-200万次/天 主要收益来自搜索技术的授权费 管理局限日益凸显，开始物色贤能之士主持大局世界搜索霸主-Google的故事加速成长 2001.3：埃利克施密特（Eric Schmidt）出任董事长，开始大刀阔斧的改革世界搜索霸主-Google的故事全面盈利 赞助商链接-关键词广告 2000年盈利2500万美元，2001年翻4倍，2002年3亿，2003年9.619亿 2003年，超越雅虎和微软MSN,成为最受欢迎的搜索引擎 2011年第四季度，营业收入105.8亿美元，净利润27.1亿美元世界搜索霸主-Google的故事非常规上市 选择摩根斯坦利和瑞士信贷第一波士顿为上市承销商 2004.8.19，以每股85美元在纳斯达克上市 当天股价上涨18%，第二天108.31，11月200美元 Google的成功上市，在整个硅谷、华尔街乃至世界引起极大的轰动 评论家称“Google上市具有里程碑意义，这是网络泡沫破灭多年以来，高科技企业在市场上取得的最大一次成功”10世界搜索霸主-Google的故事昨天今天世界搜索霸主-Google的故事中文搜索第一品牌-百度的故事1998年夏天，清华大学做技术讲座，搜狐员工建议回国创业1999.10月，再次回国，感受到祖国互联网的巨大变化，决定归国创业1999年底，与好友徐勇带着$120万的融资回国2000年，创办“百度公司”，取诗句“众里寻他千百度”地点：北大归国学人招待所2个房间中文搜索第一品牌-百度的故事勤俭创业 公司地址：北大归国学人招待所 两个房间：一间卧室，一间办公室埋头苦干 工作深夜 4个月，百度1.0诞生中文搜索第一品牌-百度的故事渐入佳境 早期定位：做出最好的搜索引擎，卖给门户网站 2000年6月，百度正式推出“最大、最快、最新”的中文搜索引擎 两人作为推销员上门找新浪、搜狐等门户网站 Powered by Baidu,按照访问量分成 绝大多数门户网站成了百度搜索引擎的客户，逐渐走上正轨中文搜索第一品牌-百度的故事11中文搜索第一品牌-百度的故事危机意识中酝酿转型战略 早期商业模式：为各大门户网站提供搜索技术服务，一度占据国内搜索技术服务市场的80%2000，2001年的网络低潮之后，能够付得起价钱的只剩下新浪、搜狐等少数门户网站 公司未来的增长点不明确 李彦宏开始酝酿战略转型中文搜索第一品牌-百度的故事力排众议通过转型决议 李彦宏在Overture首推的竞价排名模式基础上，提出“百度竞价排名”构想 摆脱对门户网站过分的依赖，直接面对终端网民 建立自己的网站，由于对门户网站产生“截流”效应，多数股东反对 李彦宏一改平素的温文尔雅和民主、安静，慷慨陈词3个小时，最终通过转型决议中文搜索第一品牌-百度的故事转型带来百度事业的飞跃 2001年9月20日，上线 同年10月，推出搜索竞价排名（OverTure）2002年底，公司发展到120名员 2003年3月，新浪停机事件“新浪欠费，百度停机，如果需要更好的搜索结果，请登录”2004年，百度竞价排名客户达3万余家，续费率达85%中文搜索第一品牌-百度的故事上市缔造中国神话 2005年8月5日美国纳斯达克上市，当天涨幅达到3.5倍 李彦宏拥有百度22.9%的股份，身价超过9亿美元 一夜之间，诞生6位亿万富翁，51位千万富翁，240位百万富翁 据称“前台接线员也光荣加入到百万富翁的行列”中文搜索第一品牌-百度的故事中文搜索第一品牌-百度的故事12中文搜索第一品牌-百度的故事百度的最大投资商-德丰杰公司问题：搜索引擎为什么可以如此成功？原因之一：简单易用原因之二：互联网上的数据太多全球网站总量(3亿4千万)中国网站数量中国网民规模、增长率及普及率13中文搜索引擎搜索次数增长（2007-2012）27029536537046582101002003004005006007008009002007Q42008Q12008Q22008Q32008Q42012Q4亿次9.0亿次/天搜索引擎的搜索过程华中科技大学搜索引擎的搜索过程百度一下，找到相关网页约14,000,000篇，用时0.007秒搜索引擎的搜索过程包含信息：（1）网站链接（2）摘要（3）快照（4）排序（5）查询扩展搜索引擎面临的挑战海量的数据 数百万的网站 数亿的网页海量的需求 9.0亿/天复杂的处理 检索、排序、摘要、快照、查询扩展快速的服务 1/10秒搜索引擎如何应对这些挑战？（1）搜索引擎是如何工作的？（2）搜索结果是查询提交之后再去搜索的呢？（3）还是事先已经准备好的呢？14内容提要搜索引擎的前世今生商用搜索引擎结构与组成搜索引擎质量评估搜索引擎排序策略分布式搜索引擎酒店点菜-桌餐特点：点菜之后，需要等待，人越多，等待越久自助餐所有的食物都是已经做好了！来了就吃，吃了就走！网页抓取网页抓取网页抓取华中科技大学数字媒体实验室15网页抓取网页之间通过超链接互相连接在一起网页A网页F网页E网页B网页C网页D网页抓取抓取程序 一般称为蜘蛛（Spider）或爬虫（Crawler）通过页面间的链接关系自动获取页面信息 必须确保有效资源的覆盖和及时更新问题：如何才能使网站被搜索引擎抓到？抓取策略（遍历算法）ABCDEHIFGKL深度优先 先沿一条路径采到叶节点，再从同层其他路径进行采集广度优先 先采集完同一层网页，再采集下一层网页简化的网页链接模型深度优先ABCDEHIFGKL路径编号路径点问题：1 A B E H2 A B E I3 A C4 A D F K L5 A D G K L重复节点很多？改进后的深度优先路径编号路径点1 A B E H2 I3 C4 D F K L5 GABCDEHIFGKL路径1路径3路径2路径4路径516深度优先爬虫必须判断 是否继续向更深一层爬？这个链接是否已爬过了？上次爬到哪里了？问题 效率较低 适用于站内搜索ABCDEHIFGKL路径1路径3路径2路径4路径5广度优先层1层2层3层4层5BCDEHIFGKLA路径编号路径点1 A 2 B C D3 E F G4 H I K5 L优点：效率高网页的重要性更好实际的网络爬虫由成百上千甚至成千上万台服务器组成的分布式系统分布式系统的通讯开销是影响性能的关键网站之间采用广度优先某一个网站采用深度优先这样可以避免握手的次数，减少通信开销搜索引擎的结构与组成预处理分词文档服务器网 页抓 取网页预处理预处理关键词的提取-分词 文档转换与分析 分词重复或者转载网页的消除 网页的重复率大约为4链接分析 分析标签，确定关键词的重要程度 分析网页的链接关系（出度和入度）网页重要程度的计算-排序17数据分析与预处理工具数据分析与预处理工具中文分词分词：将一句话切分成一个个的词分词的目的：建立有效、准确的关键词倒排索引 如：文档D：我是一个学生我是一个学生我/是/一个/学生关键词文档标识我D是D一个D学生D中文信息的特征明末著名画家徐渭的故事“下雨天留客天留人不留”“下雨天，留客天，留人不？留”中文信息的特征 词与词之间无空格 句子之间有标点中文分词方法分类基于词典（字符串匹配）的分词方法 正向最大匹配 逆向最大匹配 最少切分基于统计的分词方法-统计语言模型混合分词方法基于词典的分词思想事先准备一个分词词典 一般词典中有大量的词 十几万到几十万不等将待分的句子按照一定的扫描规则与词典中的词进行匹配如果匹配上，就将这个词分出来，否则继续扫描18最大匹配最大匹配：要求每一句话分词的结果中词汇的总量要最少举例说明 我们是中华人民共和国的公民 我们、是、中华、人民、共和国、的、公民 我们/是/中华人民共和国/的/公民正向最大匹配分词正向最大匹配分词 减字匹配法 增字匹配法从句首开始分词减字分词法过程开始读入一个句子读入词典文件待切分的临时变量匹配？词典分词结果结束匹配成功匹配失败句子减字减字法正向最大匹配分词步骤操作的句子操作分词结果1我们是中华人民共和国的公民词典匹配失败2我们是中华人民共和国的公词典匹配失败3我们是中华人民共和国的词典匹配失败我们词典匹配成功我们是中华人民共和国的公民词典匹配失败我们是中华人民共和国的公词典匹配失败我们是单字直接分出我们/是中华人民共和国的公民词典匹配失败我们/是中华人民共和国的公词典匹配失败我们/是减字法正向最大匹配分词步骤操作的句子操作分词结果中华人民共和国词典匹配成功我们/是/中华人民共和国的公民词典匹配失败我们/是/中华人民共和国的公词典匹配失败我们/是/中华人民共和国的单字直接分出我们/是/中华人民共和国/的公民词典匹配成功我们/是/中华人民共和国/的/公民减字法正向最大匹配分词存在的问题 速度太慢 无法满足搜索引擎索引的需要改进方法 已知分词词典中最长的词的长度L 以L为一个段落进行匹配19改进后的分词方法步骤操作的句子操作分词结果1我们是中华人民共和国的公民只前7个字2我们是中华人民词典匹配失败3我们是中华人词典匹配失败我们词典匹配成功 我们是中华人民共和国词典匹配失败 我们是词典匹配失败 我们是单字直接分出 我们/是中华人民共和国词典匹配成功 我们/是/中华人民共和国的公民词典匹配失败逆向最大匹配分词从句子结尾进行分词统计结果表明 单纯使用正向最大匹配分词的错误率为1/169 单纯使用逆向最大匹配分词的错误率为1/245逆向最大匹配分词步骤操作的句子操作分词结果1我们是中华人民共和国的公民只取后7个字2民共和国的公民词典匹配失败3共和国的公民词典匹配失败公民词典匹配成功 公民华人民共和国的词典匹配失败 公民人民共和国的词典匹配失败 公民是单字直接分出 的/公民中华人民共和国词典匹配成功 中华人民共和国/的/公民我们是词典匹配失败举例说明句子 瑞星以技术和服务开拓网络安全市场正向最大匹配分词结果 瑞星/以/技术/和服/务/开拓/网络/安全/市场逆向最大匹配分词结果 瑞星/以/技术/和/服务/开拓/网络/安全/市场语言的二义性发展中国家 发展/中/国家 发展/中国/家上海大学城书店 上海/大学城/书店 上海/大学/城/书店此地安能居住，其人好不悲伤 此地/安能/居住，其人/好不/悲伤 此地安/能居住，其人好/不悲伤基于统计的分词方法原理 从概率的角度出发，单个字出现在词汇中的联合概率是比较大的，因此相邻的字越经常出现，则越有可能是一个词汇基本方法 对需要分词的材料进行分析，得到相应的单字出现的概率 对相邻的字出现的概率进行统计 如果此概率远远大于单字出现的概率之和，则有可能成为一个词20基于统计的分词方法优点 可以结合上下文识别生词 可以消除歧义缺点 在统计意义上某些经常出现在一起的字并不能构成完整的词语，如：“上的”、“下的”、“这一”等 对常见词的识别精度差，计算量大混合分词统计分词与词典分词结合使用 发挥词典分词切分速度快、效率高的特点（可以解决80%左右的问题）利用统计分词结合上下文识别新词，可以消除歧义对分不出来的词的处理背景 新词层出不穷 尤其在互联网上，新词每天都出现方法：多元切分的混合分词方法 一元分词：ABCDEA/B/C/D/E 二元分词:ABCDEAB/BC/CD/DE 不分词:ABCDEABCDE对分不出来的词的处理举例说明 木子美对记者说 木/子/美/对/记者/说/木子/子美/木子美停止词训练方法停止词：指在文档中没有太多实际意义的词，这些词是没有必要进行索引的 倒排表非常长 非常浪费系统的空间 如：的、什么、是、a，an,of 等处理方法 进行大量统计，计算机出倒排表最长的那些词 在分词之后进行索引时处理，而不能先将停止词去掉，如“的士”的确”目的”数据分析与预处理工具中文分词工具ICTCLAS（Chinese LexicalAnalysis System）中文分词、命名实体识别工具 性质：自然语言处理开放资源许可证 作者：张华平，刘群 网址：?proj_id=6 平台：Windows/Linux SIGHAN第一届国际中文分词比赛Bakeoff多项第一名21数据分析与预处理工具中文分词工具ICTCLAS 功能 中文分词 词性标注 中文命名实体识别：人名、地名、机构名数据分析与预处理工具词根还原库Snowball 用于IR的词根还原库 性质：开源 作者：Martin Porter 网址：snowball.tartarus.org/index.php 平台：Windows/Linux搜索引擎的结构与组成预处理分词Web1:青年教师比赛青年教师比赛Web2:学校关心青年学校关心青年教师教师Web3:学校经常举行学校经常举行比赛比赛Web1:青年青年教师教师比赛比赛Web2:学校学校关心关心青年青年教师教师Web3:学校学校经常经常举行举行比赛比赛文档服务器网 页抓 取搜索引擎的结构与组成预处理分词Web1:青年教师比赛青年教师比赛Web2:学校关心青年学校关心青年教师教师Web3:学校经常举行学校经常举行比赛比赛Web1:青年青年教师教师比赛比赛Web2:学校学校关心关心青年青年教师教师Web3:学校学校经常经常举行举行比赛比赛青年：青年：Web1,Web2教师：教师：Web1,Web2比赛：比赛：Web1,Web3学校：学校：Web2,Web3文档服务器建立倒排索引倒排索引排序网 页抓 取搜索引擎的结构与组成预处理分词文档服务器建立倒排索引倒排索引排序华中科技大学检索服务器（查询分析、结果融合）网 页抓 取检索模块查询的分析 词法分析(分词/Stemming)转换成搜索引擎可以处理的格式 查询的意图分析相关度计算信息检索模型查询扩展和相关反馈摘要生成22查询（Query）分析Query解析 检查拼写错误 如：“话中科技大学”语法解析Query分解 分解为适合查询的term 为Multi-term Merge提供必要参数查询的分析和挖掘查询的意图分析 查询的意图分类 通过查询的意图分析可以指导后续的工作，是一个新的研究方向查询日志挖掘发现用户的兴趣查询分析摘要生成静态摘要 一个网页事先生成其摘要动态摘要 基于Query的摘要，不同的Query会生成不同的摘要静态摘要比较简单，但是由于多Topic问题的存在，效果往往不好现代搜索引擎往往采用动态摘要，用户也认可这种方式查询扩展对用户的查询进行扩充 比如用户输入“计算机”，我们扩充一个词电脑同义词扩展 同义词词典 通过统计构造的同义词词典相关词扩展 相关词：“2010年世博会”与“上海”基于全局分析的查询扩展查询重构 对用户的初始查询进行修改(可以是加词、减词，或者对于向量模型表示的初始查询进行权重的修改等等)，是比查询扩展更泛的一个概念查询扩展23查询搜索的研究趋势更精确的查询分析方法更鲁棒的信息检索模型多因素综合检索方法快速并行检索相关查询的快速推荐方法结果的聚类纠错提示用户接口用户接口百度“框计算”-框广天地、创新无限百度“框计算”-框广天地、创新无限24百度“框计算”-框广天地、创新无限百度“框计算”-框广天地、创新无限框计算 为用户提供基于互联网的一站式服务 一种最简单可依赖的互联网需求交互模式 用户只要在框中输入服务需求 系统就能明确识别这种需求 并将该需求分配给最优的应用或内容资源提供商处理 最终返回给用户相匹配的结果百度“框计算”-框广天地、创新无限框计算的实现过程 用户的任意一个需求被提交到“框”里 经过一系列复杂的需求分析 包括语义分析、行为分析、和智能人机交互技术分析和海量计算 用户的需求被分发给框后台的某个或某几个应用所响应 框背后的应用平台是开放的 框计算平台提供了大量即插即用的接口，各种应用可以主动与框计算平台对接，使自己有机会来响应框所收集到的需求小结：搜索引擎的结构与组成网页抓取模块 从Internet上自动获取信息、查重、更新预处理模块 文本分析和处理、分词索引模块 建立倒排索引、排序(Ranking)检索模块 查询的分析 相似度计算 结果摘要用户接口内容提要搜索引擎的前世今生商用搜索引擎结构与组成搜索引擎质量评估搜索引擎排序策略分布式搜索引擎搜索引擎质量评估全新快准稳25搜索引擎质量评估相关性网页结果覆盖率网页死链率作弊率结果重复率中文分词搜索引擎质量评估课堂测试题（十五分钟）请简要阐述搜索引擎的组成和工作原理，通过你平时对搜索引擎的使用，你觉得现有的搜索引擎还存在哪些不足，给出解决的思路。作业题问题1：如何更新抓取的网页信息？定期重采和增量采集各具有什么特点？问题2：互联网上存在大量的重复网页，如何去除这些重复网页？